-
Régulier
-
Complet
Atelier de théorie des graphes
Un graphe est un ensemble de points, appelés sommets, reliés par des lignes, appelées arêtes. Dessinez-en un ici en quelques clics et l'atelier vous dit de quel type de graphe il s'agit : en combien de morceaux il se divise, s'il s'agit d'un arbre, de combien de couleurs il a besoin au minimum, s'il peut se tracer d'un seul trait, et plus encore. Cliquez sur une propriété pour la voir sur votre graphe, modifiez une arête et regardez les réponses changer. Cliquez sur un emplacement vide pour ajouter un sommet. Cliquez sur un sommet, puis sur un autre, pour les relier par une arête ; recommencez pour supprimer l'arête. Faites glisser un sommet pour le déplacer. Basculez le clic sur Effacer, puis cliquez sur un sommet ou une arête pour l'effacer. Quand un sommet est sélectionné, Suppr le supprime et Échap le désélectionne. Cliquez sur une propriété pour l'afficher sur le graphe. Exemple charge un graphe célèbre, Graphe aléatoire en crée un, Ranger répartit les sommets, et Complémentaire relie exactement les paires qui n'étaient pas reliées. Ctrl+Z annule une étape.
Comment ça marche
- Cliquez sur un emplacement vide pour ajouter un sommet. Cliquez sur un sommet, puis sur un autre, pour les relier ; recommencez pour supprimer l'arête. Faites glisser un sommet pour le déplacer.
- Lisez les propriétés sous le graphe et cliquez sur l'une d'elles pour l'afficher : une coloration, les deux côtés, un parcours eulérien, un arbre couvrant, le plus court cycle ou le diamètre.
- Chargez un exemple comme le graphe de Petersen, créez un graphe aléatoire, prenez le complémentaire, ou basculez le clic sur Effacer pour supprimer des sommets et des arêtes.
Ce que signifient les propriétés
Le degré d'un sommet est le nombre d'arêtes qui en partent. Un graphe est connexe lorsque chaque sommet peut atteindre tous les autres en suivant les arêtes, et c'est un arbre lorsqu'il est connexe et sans cycle. Il est biparti lorsque ses sommets se répartissent en deux côtés de sorte que chaque arête passe d'un côté à l'autre, ce qui arrive exactement lorsqu'il n'a aucun cycle de longueur impaire. Le nombre chromatique est le plus petit nombre de couleurs permettant de donner des couleurs différentes à deux sommets voisins. La longueur du plus court cycle s'appelle la maille, et le diamètre est la plus grande distance entre deux sommets, comptée en arêtes.
Tracer d'un seul trait
Un parcours eulérien emprunte chaque arête exactement une fois. En 1736, avec les sept ponts de Königsberg, Leonhard Euler a vu ce qui fait obstacle : chaque fois qu'un parcours traverse un sommet, il utilise deux de ses arêtes. Donc soit tous les degrés sont pairs, et le parcours peut se terminer là où il a commencé, soit exactement deux degrés sont impairs, et le parcours doit aller de l'un de ces sommets à l'autre. Carl Hierholzer a démontré plus tard que cette condition, avec toutes les arêtes d'un seul tenant, est aussi suffisante. Chargez l'exemple de la maison et trouvez où le trait doit commencer.
Questions fréquemment posées
Qu'est-ce qu'un graphe en théorie des graphes ?
Un ensemble de points, appelés sommets ou nœuds, et de lignes entre certaines paires d'entre eux, appelées arêtes. Ce n'est pas la courbe d'une fonction : il décrit seulement ce qui est relié à quoi. Les cartes routières, les réseaux sociaux, les molécules et les réseaux informatiques sont tous des graphes.
Comment le nombre chromatique est-il calculé ?
L'atelier essaie de colorier le graphe avec une couleur, puis deux, puis trois, et ainsi de suite, et pour chaque nombre il examine toutes les possibilités qui comptent, en coloriant toujours ensuite le sommet dont les voisins utilisent déjà le plus de couleurs. Le premier nombre qui fonctionne est le nombre chromatique. Pour les graphes que vous pouvez dessiner ici, cela prend au plus un instant ; sur un graphe très difficile, la recherche s'arrête plus tôt et la valeur est affichée comme un majorant.
Quand un graphe a-t-il un chemin eulérien ?
Lorsque toutes ses arêtes forment un seul morceau et qu'au plus deux sommets sont de degré impair. Sans sommet impair, il existe un cycle eulérien qui se termine là où il commence ; avec deux, tout chemin eulérien part de l'un et arrive à l'autre. Le nombre de sommets impairs est toujours pair, il ne vaut donc jamais exactement un.
Qu'est-ce que le complémentaire d'un graphe ?
Le graphe sur les mêmes sommets dont les arêtes sont exactement les paires qui n'étaient pas reliées auparavant. Le complémentaire du complémentaire est le graphe de départ. Le complémentaire du graphe de Petersen, par exemple, est 6-régulier, car chaque sommet était relié à 3 des 9 autres.
Pourquoi le graphe de Petersen est-il célèbre ?
C'est un petit graphe de 10 sommets et 15 arêtes qui sert de contre-exemple à bien des conjectures optimistes. Chaque sommet est de degré 3, son plus court cycle est de longueur 5, deux sommets quelconques sont à au plus 2 arêtes l'un de l'autre, et on ne peut pas le dessiner sans que des arêtes se croisent. L'atelier démarre avec lui.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Aller à l'éditeur