Théorie des graphes : Master mathematiques td2 graphes connexitè
Télécharger PDFUNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Master MatMod
2018−2019
Introduction `a
la th ́eorie des graphes
TD N◦ 2
Chemin, Cycle et Connexit ́e
1. SoientGetHdeux graphes isomorphes. Montrer queGest connexe si et seulement si
Hest connexe.
2. Montrer que siP1 etP2 sont deux chemins de longueur maximale dans un graphe
connexe, alorsP1 etP2 ont un sommet en commun.
3. Montrer que sixetysont les seuls sommets de degr ́e impair dans un graphGalorsx
etysont connect ́e dansG.
4. Montrer que siGest un graphe d’ordren>5 et contenant trois sommets distincts
x,y,ztels quedG (x,y) =dG (x,z) =n−2 alorsGest connexe.
5. SoitGun graphe d’ordren. Montrer que si pour tout couple de sommets (x,y) non
adjacents etdeg(x) +deg(y)>n−1 alorsGest connexe etdiam(G)62.
6. Montrer que siGest un graphe non connexe, alors son graphe compl ́ementaireGest connexe etdiam(G)62.
7. Montrer qu’un grapheG= (V,E) n’est pas connexe si et seulement siVpeut ˆetre
partitionn ́e en deux sous-ensemblesV1 etV2 tels que il n’existe aucune arˆete dansE
dont l’un des deux extr ́emit ́es dansV1 et l’autre dansV2 .
8. SoitGun graphe d’ordrenpair. SiGposs`ede deux composantes connexes qui sont
deux sous graphes complets. Montrer queGposs`ede au minimumn(n−2) 4
arˆetes.
9. Montrer qu’un grapheGreste connexe apr`es avoir supprim ́e une arˆeteedeGsi et
seulement sieest une arˆete d’un cycle dansG.
10. Est ce que siGest un graphe connexe et 2-r ́egulier alorsGest un cycle ?
11. SoitGun graphe acyclique d’ordrenet de taillem. Montrer quem6n−1.
12. Monter que tout graphe 4-r ́egulier contient un chemin de longueur sup ́erieure `a 4 et un
cycle de taille sup ́erieure `a 5.
13. Donner le nombre de stabilit ́e d’un cycle de longueurn.
14. SoitGest un graphe d’ordren. Montrer que si 36n <2δ(G) alorsg(G) = 3.
15. Montrer que siGest un graphek-r ́egulier (k>2) et dontg(G) = 4 alors l’ordre de
|G|>2k. Quels sont les graphe de ce type qui sont d’ordre 2K.
16. SoitG= (V,E) un graphe simple non orient ́e. On appelleexcentricit ́ed’un sommetx
deGla quantit ́ee(x) = max{dG (x,u) :u∈V}.rad(G) = min{e(x) :x∈V}d ́esigne
lerayondu grapheG. On appellecentreduG, un sommet d’excentricit ́e minimale et
sie(x) =diam(G) alors le sommetxest appel ́esommet p ́eriph ́eriquedeG.
1Mustapha KCHIKECH
UNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Master MatMod
2018−2019
Introduction `a
la th ́eorie des graphes
(a) Donner le rayon des graphesPn ,Cn ,Pn Pm ,Pn Cm etCn Cm . O`un,m>3.
(b) Montrer que pour tout graphe connexe d’ordre>2,
rad(G)6diam(G)62rad(G)
(c) Existe t-il un grapheGnon complet tel querad(G) =diam(G) ?
(d) Pourn>4, donner l’exemple d’un graphe d’ordrennon complet o`u tous ses
sommets sont des sommets centres et des sommets p ́eriph ́eriques.
17. Les graphes suivantes sont t-ils bipartis ?
18. Est ce les graphes suivants sont bipartis :Pn Pm ,Pn Cm ,Cn Cm ; Graphes circulants;
Hypercube de dimensionn.
19. SoientGetHdeux graphes isomorphes. Montrer queGest biparti si et seulement si
Hest biparti.
20. SoitGun graphe connexe biparti. Montrer queGest biparti complet si et seulement
siGne contient aucun sous graphe induit isomorphe `aP4 .
21. Le graphe biparti completK4,4 contient-il un sous graphe isomorphe au grapheK4 ?
22. Existe-t-il un grapheGbiparti tel queδ(G) + ∆(G)>|G|?
23. Montrer que siGest un graphe d’ordren>4 et de taillem >n 24 , alorsGcontient un
cycle impair.
24. Montrer que siG= (V1 ∪V2 ,E) est un graphe bipartik-r ́egulier alors|V1 |=|V2 |et
k6|G|/2.
25. SoitG= (V1 ∪V2 ,E) un graphe biparti.
(a) Montrer que∑ x∈V1 d(x) =∑ y∈V2 d(y).
(b) En d ́eduire que siGestk-r ́egulier, aveck>1, alors|V1 |=|V2 |.
(c) Montrer que|E|6|V1 |×|V2 |.
(d) En d ́eduire que|E|6|G|2 /4.
(e) D ́ecrire les graphes simples bipartisGpour lesquels il y a ́egalit ́e en (d).
26. Monter queGest biparti si et seulement siα(H)>|H| 2
, o`uα(H) est le nombre de
stabilit ́e d’un sous-grapheHdeG.
2Mustapha KCHIKECH