[PDF] les graphes conceptuels exercices corrigés

Comment associer un graphe à une figure ?

Solution Exercice 22. On peut associer un graphe à cette figure (en réalité un multigraphe car nous aurons des arêtes multiples) de la façon suivante : les sommets représentent les régions (y compris la région extérieure) et deux sommets sont reliés par autant d’arêtes que le nombre de segments communs de leurs régions (voir ci- dessous).

Comment savoir si un graphe est régulier ?

Un graphe est dit régulier s'il est simple et si tous ses sommets ont le même degré. On s'intéresse dans cet exercice aux graphes réguliers dont les sommets sont de degré 3. Que dire du nombre de sommets d'un tel graphe? Démontrer que, pour tout p? 2 p ? 2, il existe un graphe régulier d'ordre 2p 2 p dont les sommets sont de degré 3.

Comment faire un graphe simple connexe ?

On donne un graphe simple connexe G. Le joueur A débute la partie en choisissant un sommet. Les deux joueurs jouent alternativement en choisissant un sommet non choisi précédemment avec la contrainte de choisir un sommet voisin du dernier sommet sélectionné par l’autre joueur (autrement dit, et B construisent ensemble un chemin).

Comment faire un graphe de 9 personnes ?

Revenons au cas des 9 personnes, cette fois avec une table de 4 places et une table de 5 places... Il s’agit toujours de décomposer le graphe complet en ensembles disjoints de 9 arêtes, mais cette fois, chaque ensemble doit correspondre à un cycle de 4 arêtes + un cycle de 5 arêtes.