Introduction à la théorie des graphes/Graphes et sous-graphes

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

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

Définition

Le graphe G'=(V',E') est le sous-graphe de G=(V,E) induit par V', si $V'\subset V$ et $E'=\{\{u,v\}\in E|u\in V',v\in V'\}$

Début de l'exemple

Exemple

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 $V'=V\backslash \{e\}$

Fin de l'exemple

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 :

Définition

Le graphe G'=(V',E') est un graphe partiel de G=(V,E), si V' = V et $E'\subset E$

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

Stable

Définition

Un stable de G est sous-graphe de G sans arête.

Notons qu'un stable est donc 0-régulier.

Début de l'exemple

Exemple

Dans l'exemple précédent, le sous-graphe induit par V'={a,d} est un stable de G.

Fin de l'exemple

Clique

Définition

Une clique de G est un sous-graphe complet de G.

Début de l'exemple

Exemple

Dans l'exemple précédent, le sous-graphe induit par V'={a,b,c} est une clique de G.

Fin de l'exemple

Chaine et connexité

Définition

Une chaîne W de G est un sous-graphe partiel de G défini par une séquence W=$v_{1}e_{1}v_{2}...e_{n}v_{n+1}$ alternée de sommets et d'arêtes, telle que, pour $1\leq i\leq n$, les extrémités de $e_{i}$ sont $v_{i}$ et $v_{i+1}$.

Dans un graphe simple, une chaîne pourra être simplement définie par une séquence de sommets.

Début de l'exemple

Exemple

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.

Fin de l'exemple

Définition

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.

Début de l'exemple

Exemple

Dans l'exemple précédent, le graphe G est connexe. Mais le stable induit par {a,d} ne l'est pas.

Fin de l'exemple

Cycle

Définition

Un cycle C est une chaîne C=$v_{1}e_{1}v_{2}...e_{n}v_{n+1}$ telle que $v_{1}=v_{n+1}$.

On dit aussi qu'un cycle est une chaîne fermée.

Début de l'exemple

Exemple

Dans l'exemple précédent, la séquence W= b d e c b est un cycle.

Fin de l'exemple

Faites ces exercices : Graphes et sous-graphes.

Début d’un principe

Exercices sur les cycles

Trouver un exemple de cycle qui n’est pas 2-régulier.

Fin du principe

Forêt et arbre

Définition

Une forêt est un graphe sans cycle.

Définition

Un arbre est une forêt connexe.

Début de l'exemple

Exemple

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.

Fin de l'exemple