Introduction à la théorie des graphes/Graphes et sous-graphes
La majorité des problèmes de théorie des graphes consiste en l'étude, l’existence ou l'optimalité de certains sous-objets contenus dans un graphe. Nous allons définir ici ces sous-objets et nous en donnerons quelques exemples.
Sous-graphe et graphe partiel
[modifier | modifier le wikicode]
Le graphe G'=(V',E') est le sous-graphe de G=(V,E) induit par V', si et
Un sous-graphe de G est donc uniquement défini par un sous-ensemble de sommets de G. L'ensemble des arêtes d'un sous-graphe n'est donc que la conséquence du choix des sommets. Ainsi on garde toutes les arêtes dont les deux extrémités sont dans le sous-ensemble de sommets.
Dans notre exemple à gauche, nous avons le graphe G=(V,E), et à droite son sous-graphe induit par
En ce qui concerne un graphe partiel de G, c’est tout à fait l'inverse. Ici on garde tous les sommets de G et on enlève quelques arêtes. Voici la définition :
Le graphe G'=(V',E') est un graphe partiel de G=(V,E), si V' = V et
On parle aussi de graphe couvrant, particulièrement quand le graphe partiel est un arbre.
Un sous-graphe partiel sera un graphe partiel d'un sous-graphe.
Graphes et sous-graphes particuliers
[modifier | modifier le wikicode]Stable
[modifier | modifier le wikicode]Un stable de G est sous-graphe de G sans arête.
Notons qu'un stable est donc 0-régulier.
Dans l'exemple précédent, le sous-graphe induit par V'={a,d} est un stable de G.
Clique
[modifier | modifier le wikicode]Une clique de G est un sous-graphe complet de G.
Dans l'exemple précédent, le sous-graphe induit par V'={a,b,c} est une clique de G.
Chaine et connexité
[modifier | modifier le wikicode]Une chaîne W de G est un sous-graphe partiel de G défini par une séquence W= alternée de sommets et d'arêtes, telle que, pour , les extrémités de sont et .
Dans un graphe simple, une chaîne pourra être simplement définie par une séquence de sommets.
Dans l'exemple précédent, la séquence W=e c a b d est une chaîne. On dit que W relie e à d.
Un graphe G=(V,E) est connexe si, pour tout couple (u,v) de sommets de G, il existe une chaîne reliant u à v.
Dans l'exemple précédent, le graphe G est connexe. Mais le stable induit par {a,d} ne l'est pas.
Cycle
[modifier | modifier le wikicode]Un cycle C est une chaîne C= telle que .
On dit aussi qu'un cycle est une chaîne fermée.
Dans l'exemple précédent, la séquence W= b d e c b est un cycle.
 Faites ces exercices : Graphes et sous-graphes.
|
Trouver un exemple de cycle qui n’est pas 2-régulier.
Forêt et arbre
[modifier | modifier le wikicode]Une forêt est un graphe sans cycle.
Un arbre est une forêt connexe.
Dans l'exemple précédent, le sous-graphe de G induit par {a,d,e} est une forêt mais ce n’est pas un arbre.
