Théorie des graphes : Master mathematiques introduction a la theorie des graphes
Télécharger PDFUNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Master MatMod
2018−2019
Introduction `a
la th ́eorie des graphes
TD N◦ 3
Connectivit ́e, Graphes eul ́eriens, Graphes hamiltoniens
1. SoitGle graphe suivant :
(a) Donner le diam`etre, la maille, la taille de la clique maximale et le nombre chroma-
tique deG.
(b) Est-ce queGposs`ede chemin Eul ́erien ? Est-ce queGest un graphe planaire,
Eul ́erien, Hamiltonien ?
(c) Calculerκ(G) etλ(G).
2. SoitGun graphe de Petersen.
(a) Est-ce queGest Hamiltonien ?
(b) Monter que deux sommets deGnon adjacents poss`edent un et un seul voisin encommun. 3. Est-ce queH3 est graphe eul ́erien ou hamiltonien ?
4. Calculerκ(H3 ) etλ(H3 ).
5. Dans un graphe connexe, montrer que deux chemins de longueur maximale ont un
sommet en commun.
6. SoitGun graphek-r ́egulier.
(a) Est-ce queGest un graphe connexe ?
(b) Est-ce queGest un graphe Eul ́erien, Hamiltonien ?
7. Montrer que siGest un arbre d’ordren>2 alorsGest un graphe biparti.
8. Montrer que siGest un graphe 2-connexe alorsGcontient au moins un cycle.
9. Montrer que siG= (V,E) est un arbre d’ordren>3 alors le nombre de feuilles
(sommets de degr ́e 1) est 2 +∑ x∈Vd G
(x)>3(d G(x)−2). 10. Monter que siGest un graphe connexe d’ordrenet de taillemalors les assertions
suivantes sont ́equivalentes :(a)n=m, (b)Gcontient un et un seul cycle,
1Mustapha KCHIKECH
UNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Master MatMod
2018−2019
Introduction `a
la th ́eorie des graphes
(c) il existe une arˆeteedansGtelle queG−eest un arbre.
11. SoitGle graphe dit graphe deGr ̈otzschrepr ́esent ́e comme suit :
(a) D ́eterminer le diam`etre, la maille, la taille de la clique maximale et le nombre
chromatique deG.
(b) Est-ce queGest Eul ́erien? contient t-il un chemin eul ́erien ?
(c) Est-ce queGest Hamiltonien?
(d) Calculerκ(G) etλ(G).
2Mustapha KCHIKECH