Théorie des graphes : Master mathematiques 2018 2019 introduction a la theorie de
Télécharger PDFIntroduction à la théorie des graphes
TD N°1 : Les bases de la théorie des graphes
Exercice 1Éléments de base d’un graphe
1. Existent-ils des graphes dont les sommets ont pour degré les séquences suivantes ? Si la réponse 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é 2 et deux sommets de degré 4. Dessiner ce graphe.
3. Soit G un graphe d’ordre 10, de taille 11 et dont les sommets sont de degré 2 ou 3. Donner le nombre de sommets de degré 2 et de degré 3. Dessiner le graphe G.
4. Est-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é 1 et 3 sommets de degré 3 ?
6. Existe-t-il un graphe d’ordre 4 et de taille 7 ? Justifier votre réponse.
7. Montrer que si G est un graphe d’ordre n > 3 et δ(G) > n/2, alors G contient un triangle.
Exercice 2Méthodes de construction de graphes
1. Un hypercube de dimension n noté Hn (appelé aussi n-cube) est un graphe dont les sommets sont des ensembles de n-uplets de {0,1}. Deux sommets sont adjacents si et seulement si les n-uplets correspondants diffèrent en exactement une coordonnée.
(a) Dessiner H1, H2, H3, H4.
(b) Déterminer l’ordre de Hn.
(c) Montrer que Hn est un graphe régulier. Déduire la taille de Hn.
2. Le treillis booléen de dimension n noté BLn est un graphe dont les sommets sont tous les éléments de P(E) avec E = {1, 2, ..., n}. Deux sommets sont adjacents si et seulement si leur différence symétrique est un singleton.
(a) Dessiner BL1, BL2, BL3.
(b) Déterminer l’ordre de BLn.
(c) Montrer que BLn est un graphe régulier. Déduire la taille de BLn.
(d) Dessiner un sous-graphe, un graphe partiel et un graphe induit du BL3.
3. Soit n, r deux entiers tels que 2r ≤ n. Un graphe de Johnson J(n, r) est un graphe dont les sommets sont les parties à r éléments d’un ensemble à n éléments. Deux sommets sont adjacents lorsque les sous-ensembles correspondants ont exactement r−1 éléments communs.
(a) Dessiner J(5, 1) et J(4, 2).
(b) Donner la classe des graphes J(n, 1).
(c) Dessiner J(5, 2) et son complémentaire.
(d) Déterminer l’ordre de J(n, r).
(e) Montrer que J(n, r) est un graphe régulier. Déduire la taille de J(n, r).
(f) Dessiner un sous-graphe, un graphe partiel et un graphe induit du J(5, 2).
4. Un graphe G = (Z/nZ, E) est dit circulant d’ordre n et de partie S ⊂ Z/nZ où 0 ∉ S et pour tout x ∈ S, −x ∈ S, si (x, y) ∈ E si et seulement si x − y ∈ S.
(a) Dessiner 4 exemples de graphes circulants d’ordre 8.
(b) Est-ce que les graphes circulants sont réguliers ?
(c) Est-ce que le complémentaire d’un graphe circulant est un graphe circulant ? Si oui, donner un exemple.
Exercice 3Graphes isomorphes - Complémentaire de graphes
1. Soit G un graphe d’ordre n et de taille m. Donner l’ordre et la taille de Gc, le graphe complémentaire de G.
2. Dessiner un graphe isomorphe à son complémentaire.
3. Montrer que deux graphes G et H sont isomorphes si et seulement si leurs complémentaires Gc et Hc sont aussi isomorphes. Donner un exemple.
4. Trouver les graphes isomorphes parmi les graphes suivants.
5. Montrer que Hn et BLn sont isomorphes, où Hn est l’hypercube de dimension n et BLn est le treillis booléen de dimension n.
6. Un graphe G est autocomplémentaire si G = Gc. Montrer que si G est un graphe autocomplémentaire d’ordre n, alors n ≡ 0 [4] ou n ≡ 1 [4]. La réciproque est-elle toujours vraie ?
7. Montrer que tout graphe G autocomplémentaire d’ordre 4k + 1 possède un sommet de degré 2k.
FAQ
Qu’est-ce qu’un graphe régulier ? Un graphe est dit régulier si tous ses sommets ont le même degré.
Comment déterminer l’ordre et la taille d’un graphe complémentaire ? L’ordre reste inchangé, tandis que la taille est donnée par mc = n(n−1)/2 − m, où m est la taille du graphe initial.
Quelle est la différence entre un sous-graphe et un graphe partiel ? Un sous-graphe est formé d’un sous-ensemble des sommets et des arêtes d’un graphe, tandis qu’un graphe partiel est un sous-graphe qui peut inclure un sous-ensemble des arêtes.