Master mathematiques introduction a la theorie des grap

Théorie des graphes : Master mathematiques introduction a la theorie des graphes

Télécharger PDF

Introduction à la théorie des graphes

TD N° 3 : Connectivité, Graphes eulériens, Graphes hamiltoniens

Exercices sur la théorie des graphes

1. Soit G le graphe suivant :

(a) Donner le diamètre, la maille, la taille de la clique maximale et le nombre chromatique de G.

(b) Est-ce que G possède un chemin eulérien ? Est-ce que G est un graphe planaire, eulérien ou hamiltonien ?

2. Soit G un graphe de Petersen.

(a) Est-ce que G est hamiltonien ?

(b) Montrer que deux sommets de G non adjacents possèdent un et un seul voisin en commun.

3. Est-ce que H₃ est un graphe eulérien ou hamiltonien ?

4. Calculer κ(H₃) et λ(H₃).

5. Dans un graphe connexe, montrer que deux chemins de longueur maximale ont un sommet en commun.

6. Soit G un graphe k-régulier.

(a) Est-ce que G est un graphe connexe ?

(b) Est-ce que G est un graphe eulérien ou hamiltonien ?

7. Montrer que si G est un arbre d’ordre n > 2 alors G est un graphe biparti.

8. Montrer que si G est un graphe 2-connexe alors G contient au moins un cycle.

9. Montrer que si G = (V, E) est un arbre d’ordre n > 3 alors le nombre de feuilles (sommets de degré 1) est égal à 2 + ∑_{x∈V, deg(x) > 3} (deg(x) − 2).

10. Montrer que si G est un graphe connexe d’ordre n et de taille m alors les assertions suivantes sont équivalentes :

(a) n = m,

(b) G contient un et un seul cycle,

11. Soit G le graphe dit graphe de Grötzsch représenté comme suit :

(a) Déterminer le diamètre, la maille, la taille de la clique maximale et le nombre chromatique de G.

(b) Est-ce que G est eulérien ? Contient-il un chemin eulérien ?

(d) Calculer κ(G) et λ(G).

FAQ

Qu’est-ce qu’un graphe eulérien ?

Un graphe est dit eulérien s’il existe un chemin eulérien, c’est-à-dire un chemin qui utilise chaque arête exactement une fois.

Qu’est-ce qu’un graphe hamiltonien ?

Un graphe est hamiltonien s’il contient un cycle hamiltonien, c’est-à-dire un cycle qui passe par chaque sommet exactement une fois.

Quelle est la différence entre le diamètre et la maille d’un graphe ?

Le diamètre est la plus grande distance entre deux sommets, tandis que la maille est la longueur du plus court chemin cyclique dans le graphe.