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

Début 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.

fin de la boite de navigation du chapitre

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