Graphes particuliers
Les familles de graphes à connaître : complet, chaîne, cycle, étoile, arbre, biparti, régulier, planaire, pondéré, orienté sans circuit, complémentaire et sous-graphe.
- 26 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Graphe complet Kₙ : de quoi s'agit-il ?
Voir la réponse
Structure à n sommets où chaque paire de sommets distincts est reliée par une arête.
Il a n(n − 1)/2 arêtes, le maximum pour un graphe simple d'ordre n, et chaque sommet y a pour degré n − 1.
Lequel de ces graphes est biparti ?
- Le cycle C₆
- Le cycle C₅
- Le graphe complet K₃
- Le graphe complet K₄
Voir la réponse
Le cycle C₆
C₆ alterne deux couleurs : 1, 2, 1, 2, 1, 2 et on boucle sur une couleur différente. C₅, K₃ et K₄ contiennent un triangle ou un cycle de longueur 5, de longueur impaire.
Le graphe complet Kₙ a … arêtes.
Voir la réponse
Le graphe complet Kₙ a n(n − 1)/2 arêtes.
Chaque sommet a n − 1 voisins, soit n(n − 1) extrémités, et chaque arête en a deux : on divise par 2.
Graphe biparti : de quoi s'agit-il ?
Voir la réponse
Structure dont les sommets se répartissent en deux groupes, sans aucune arête à l'intérieur d'un même groupe.
Équivalent : on peut le colorier avec deux couleurs, ou encore il n'a aucun cycle de longueur impaire. Les affectations agents-tâches en sont des exemples.