[PDF] exercices corrigés sur les graphes pdf

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 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 calculer le degré maximal d’un graphe ?

Supposons qu’un tel graphe existe et qu’il possède n sommets. Le degré maximal d’un sommet est donc n-1. Si tous les degrés des sommets sont distincts, on a donc nécessairement un sommet de degré 0, un sommet de degré 1, ..., un sommet de degré n-1.

Comment savoir si un graphe est connexe ?

1) Prouver que ce graphe est connexe. Déterminer son diamètre. 2) Déterminer le nombre chromatique de ce graphe. inférieurs ou égaux à 20. Ceci prouve que le graphe est connexe, et que son diamètre est au plus 2 (on peut toujours trouver une chaîne de longueur au plus 2 de i à j en passant par 1). Comme 19 et