Théorie des graphes : Master mathematiques 2018 2019 introduction a la theorie de
Télécharger PDFUNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Master MatMod
2018−2019
Introduction `a
la th ́eorie des graphes
TD N◦ 1
Les bases de la th ́eorie des graphes
Exercice 1́el ́ements de base d’un graphe
1. Existent-t-ils des graphes dont les sommets ont pour degr ́e les s ́equences suivantes ? Si la
r ́eponse est oui, dessiner le graphe correspondant.
(a) 1,2,2,3,4,7 (b) 1,2,3,4,4(c) 2,3,4,8,3(d) 0,3,3,3,3,3,3,3,3 (e) 1,1,3,3,4,5,6,7
(f) 1,1,3,4,5,6 (g) 3,3,4,4,6,6,6,8
2. Donner la taille d’un graphe d’ordre 6 ayant 4 sommets de degr ́e 2 et deux sommets de degr ́e
4. Dessiner ce graphe.
3. SoitGun graphe d’ordre 10, de taille 11 et dont les sommets sont de degr ́e 2 ou 3. Donner
le nombre de sommets de degr ́e 2 et de degr ́e 3. Dessiner le grapheG.
4. Est-t-il possible de construire un graphe d’ordre 10 et de taille 50 ?
5. Un graphe d’ordre 4 peut-il avoir un sommet de degr ́e 1 et 3 sommets de degr ́e 3 ?
6. Existe t-il un graphe d’ordre 4 et de taille 7 ? Justifier votre r ́eponse.
7. Montrer que siGest un graphe d’ordren>3 etδ(G)>n 2
, alorsGcontient un triangle.
Exercice 2M ́ethodes de Construction de graphes
1. Un hypercube de dimensionnnot ́eHn (appel ́e aussin-cube) est un graphe dont les sommets
sont des ensembles den-uplets de{0,1}. Deux sommets sont adjacents si et seulement si les
n-uplets correspondants diff`erent en exactement une coordonn ́ee.
(a) DessinerH1 ,H2 ,H3 ,H4 .
(b) D ́eterminer l’ordre deHn .
(c) Montrer queHn est un graphe r ́egulier. D ́eduire la taille deHn .
2. Le treillis bool ́een de dimensionnnot ́eBLn est un graphe dont les sommets sont tous le ́el ́ements deP(E) avecE={1,2,···,n}. Deux sommets sont adjacents si et seulement si
leur diff ́erence sym ́etrique est un singleton.
(a) DessinerBL1 ,BL2 ,BL3 .
(b) D ́eterminer l’ordre deBLn .
(c) Montrer queBLn est un graphe r ́egulier. D ́eduire la taille deBLn .
(d) Dessiner un sous graphe, un graphe partiel et un graphe induit duBL3 .
3. Soitn,rdeux entiers tels que 2r6n. Un graphe deJohnsonJ(n,r) est un graphe dont
les sommets sont les parties `ar ́el ́ements d’un ensemble `an ́el ́ements, deux sommets ́etant
adjacents lorsque les sous ensembles correspondants ont exactementr−1 ́el ́ements communs.
(a) DessinerJ(5,1) etJ(4,2).
(b) Donner la classe des graphesJ(n,1).
(c) Dessiner
J(5,2) le compl ́ementaire deJ(5,2).
(d) D ́eterminer l’ordreJ(n,r).
(e) Montrer queJ(n,r) est un graphe r ́egulier. D ́eduire la taille deJ(n,r).
(f) Dessiner un sous graphe, un graphe partiel et un graphe induit duJ(5,2). 1Mustapha KCHIKECH
UNIVERSITE CADI AYYAD
Facult ́e PolyDisciplinaire de Safi
Master MatMod
2018−2019
Introduction `a
la th ́eorie des graphes
4. Un grapheG= (Z/nZ,E) est ditcirculantd’ordrenet de partieS⊂Z/nZo`u 0/∈Set
x∈Simplique−x∈Set (x,y)∈Esi et seulement six−y∈S.
a.Dessiner 4 exemples de graphes circulants d’ordre 8.
b.Est-ce que les graphes circulants sont r ́eguliers.
c.Est-ce que le compl ́ementaire d’un graphe circulant est un graphe circulant ? Si oui
donner un exemple.
Exercice 3Graphes isomorphes- compl ́ementaire de graphes
1. SoitGest un graphe d’ordrenet de taillem, donner l’ordre et la taille deGle graphe
compl ́ementaire deG.
2. Dessiner un graphe isomorphe `a son compl ́ementaire.
3. Montrer que deux graphesGetHsont isomorphes si et seulement si leur compl ́ementaire
GetHsont aussi isomorphes. Donner un exemple.
4. Trouver les graphes isomorphes parmi les graphes suivants :
5. Montrer queHn etBLn sont isomorphes o`uHn est l’hypercube de dimensionnetBLn est
le treillis bool ́een de dimensionn.
6. Un grapheGest autocompl ́ementaire si
G=G. Montrer que siGest un graphe auto-
compl ́ementaire d’ordrenalorsn≡0[4] oun≡1[4]. La r ́eciproque est-elle toujours vraie?
7. Montrer que tout grapheGautocompl ́ementaire d’ordre 4k+ 1 poss`ede un sommet de degr ́e2k. 2Mustapha KCHIKECH