Que signifie "Graphes 1-planaires"?
Table des matières
Les graphes 1-planaires sont des types spéciaux de graphes qui peuvent être dessinés sur une surface plane, comme du papier, de manière à ce que chaque arête croise au maximum une fois. Ça veut dire que quand tu relis des points (ou sommets) dans le graphe avec des lignes (ou arêtes), les lignes peuvent se croiser, mais aucune paire d'arêtes ne peut se croiser plus d'une fois.
Jeu des Cops et Voleurs
Dans le jeu des Cops et Voleurs joué sur ces graphes, un groupe de flics essaie d'attraper un seul voleur. Le jeu implique que les deux équipes prennent des tours pour se déplacer le long des arêtes du graphe. L'objectif des flics est d'attraper le voleur, et le voleur essaie de s'échapper.
Nombre de Cops
Le "nombre de cops" d'un graphe est le minimum de flics nécessaires pour garantir qu'ils peuvent attraper le voleur peu importe ses mouvements. Pour beaucoup de types de graphes, y compris les graphes planaires, il y a une limite au nombre de flics nécessaires. Cependant, pour les graphes 1-planaires, le nombre de flics nécessaires peut varier et même devenir très grand pour certains graphes.
Graphes 1-planaires Maximaux
Les graphes 1-planaires maximaux sont un cas spécifique où ces graphes ont le plus d'arêtes possible sans ajouter un autre croisement. Dans ces cas, on a souvent trouvé que juste trois flics suffisent pour attraper le voleur.
Croix et Nombre de Cops
Un aspect unique des graphes 1-planaires est le rôle des croisements. Si on se concentre sur des graphes qui n'ont pas certains types de croisements, ou ceux qui n’autorisent qu’un nombre limité de croisements, il s'avère que le nombre de flics reste gérable, nous permettant même de prédire combien de flics sont nécessaires en fonction des croisements présents.