Graphes

Graphes

I Graphes simples

II Multigraphes

III Chaînes et cycles

IV Arbres

I Graphes simples

I-1 Définitions

I-2 Bestiaire

I-3 Sous-graphes, le théorème de Turán

I-4 Colorations

I-5 Graphes planaires

I-1 Définitions

Un graphe simple est un couple $G=(S,A)$ d'ensembles finis. L'ensemble $S$ des sommets est supposé non vide. Son cardinal, le nombre $n$ de sommets est appelé l'ordre du graphe $G$. L'ensemble $A$ des arêtes est un sous-ensemble quelconque de l'ensemble des parties à deux éléments ou paires de sommets. Les deux éléments d'une arête $a$ sont ses extrémités. Comme il y a $\left(\genfrac{}{}{0ex}{}{n}{2}\right)={\displaystyle \frac{n(n-1)}{2}}$ paires de sommets, il y a entre $0$ et ${\displaystyle \frac{n(n-1)}{2}}$ arêtes.
On dit que deux sommets $s$ et $s\prime$ sont voisins si $\{s,s\prime \}$ est une arête. Le nombre de voisins du sommet $s$ est appelé son degré et est souvent noté $d(s)$. Un sommet isolé est un sommet de degré 0, c'est-à-dire sans voisin.
Donnons tout de suite un résultat fondamental

Théorème

Démonstration
En conséquence

Corollaire

On utilise souvent des raccourcis, parlant du graphe plutôt que de ses sommets ou de ses arêtes. Par exemple, le degré minimum, respectivement maximum, du graphe $G$ est défini comme

$\delta (G)={\min }_{s\in S}d(s)$

respectivement

$\Delta (G)={\max }_{s\in S}d(s).$

Si ces deux nombres sont égaux, c'est-à-dire si tous les sommets ont le même degré $k$, on dit que le graphe est $k$-régulier.
Une représentation plane du graphe $G=(S,A)$ est un dessin plan, comportant $n=\mid S\mid$ points étiquetés par les éléments de $S$ et pour chaque arête $\{s,s\prime \}\in A$, une courbe simple, par exemple un segment de droite, joignant les sommets étiquetés $s$ et $s\prime$. Les croisements entre ces représentations des arêtes ne sont pas significatifs. Toutefois, il est souvent préférable de les éviter si possible. Un graphe planaire est un graphe qui admet une représentation plane sans croisement, mais cette notion ne jouera pas un rôle central dans ce cours. Voici deux représentations du graphe

$G=(\{a,b,c,d,e,f,g\},\{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{b,d\},\{c,d\},\{d,e\}\}).$

Un isomorphisme du graphe simple $G=(S,A)$ sur le graphe simple $G\prime =(S\prime ,A\prime )$ est une bijection $\varphi :S\to S\prime$ telle que

$\forall s,t\in S,\{s,t\}\in A\iff \{\varphi (s),\varphi (t)\}\in A\prime .$

Il est facile de voir que cela définit une relation d'équivalence sur les graphes. Par exemple, il y a $8$ graphes distincts dont l'ensemble des sommets est $S=\{a,b,c\}$: Ils se répartissent en quatre classes d'isomorphisme. On dit qu'il y a, à isomorphisme près, 4 graphes simples d'ordre 3 distincts: En effaçant les étiquettes des sommets, on obtient une représentation plane d'un graphe à isomorphisme près.

I-2 Bestiaire

Nous allons donner des exemples de (classes d'isomorphismes de) graphes simples naturels.

• Le $n$-stable $S_n$, ou stable d'ordre $n$ est un graphe d'ordre $n$ sans arête. Voici $S_4$:
  
• La $n$-clique, ou graphe complet d'ordre $n$ est un graphe d'ordre $n$ dans lequel deux sommets distincts sont toujours voisins. Voici $K_5$:
  
• La $n$-chaîne $P_n$ ou chaîne de longueur $n$ a pour ensemble de sommets $[0,n]$ (c'est donc un graphe d'ordre $n+1$), avec $i$ voisin de $j$ si et seulement si $\mid i-j\mid =1$. Voici $P_4$:
  
• Le $n$-cycle $C_n$ ou cycle de longueur $n$ a pour ensemble de sommets $[1,n]$ (c'est donc un graphe d'ordre $n$), avec $i$ voisin de $j$ si et seulement si $\mid i-j\mid =1$ ou $\mid i-j\mid =n-1$. Voici $C_5$:
  ou encore
• Soit $d\ge 0$ un entier. Le $d$-cube $Q_d$, ou cube de dimension $d$ est un graphe dont les sommets sont les chaînes de caractères de longueur $d$ sur l'alphabet $\{0,1\}$. Deux sommets sont voisins dans le graphe si et seulement si les chaînes correspondantes diffèrent en une seule position. Voici $Q_3$:
  ou
• Le graphe de Petersen est le graphe suivant:
  

I-3 Sous-graphes, le théorème de Turán

Le graphe complémentaire du graphe simple $G=(S,A)$ est un graphe $\overline{G}=(S,\overline{A})$ qui a les mêmes sommets que $G$, mais dans lequel deux sommets distincts sont voisins si et seulement si ils ne le sont pas dans $G$. En d'autre termes, on a $\overline{A}={𝒫}_2(S)\setminus A$. Un graphe est auto-complémentaire si et seulement si il est isomorphe à son complémentaire. Les deux figures plus haut pour $C_5$ et $K_5$ montrent que $C_5$ est auto-complémentaire.
Un sous-graphe d'un graphe simple $G=(S,A)$ est un graphe $G\prime =(S\prime ,A\prime )$ tel que $S\prime \subset S$ et $A\prime \subset A$. On dit que c'est un sous-graphe couvrant si $S\prime =S$. Pour toute partie $S\prime$ de $S$, on définit le sous-graphe de $G$ induit par $S\prime$ et on note $G(S\prime )$ le graphe $G(S\prime )=(S\prime ,A\prime )$, où $A\prime =A\cap {𝒫}_2(S\prime )$ est l'ensemble des arêtes de $A$ dont les deux extrémités sont dans $S\prime$.
On dit que $G$ contient le graphe $G\prime$ s'il existe un sous-graphe de $G$ isomorphe à $G\prime$. Nous allons prouver le

Théorème [de Turán]

Démonstration
On remarque que si $n=q(p-1)$ est un multiple de $p-1$, on peut construire un graphe d'ordre $n$ de la façon suivante: on répartit les sommets en $p-1$ groupes de $q$ éléments et deux sommets quelconques sont voisins si et seulement si ils n'appartiennent pas au même groupe. Voici l'exemple $p=5$, $q=3$:
Il est clair que ce graphe ne contient pas de $p$-clique puisque d'après le principe des tiroirs toute partie de $S$ de cardinal $p$ contient deux sommets de même groupe, donc non voisins. Comptons les arêtes du graphe. Il y a $\left(\genfrac{}{}{0ex}{}{p-1}{2}\right)={\displaystyle \frac{(p-1)(p-2)}{2}}$ paires de groupes et $q^2$ arêtes entre éléments de cette paire de groupes. On a donc

$\mid A\mid ={\displaystyle \frac{(p-1)(p-2)}{2}}{q}^2=(1-{\displaystyle \frac{1}{p-1}}){\displaystyle \frac{n^2}{2}}$

et la borne donnée par le théorème de Turán est atteinte.

I-4 Colorations

Une application $f:S\to C$ de l'ensemble des sommets d'un graphe simple $G=(S,A)$ est une coloration du graphe si l'image par $f$ d'une arête est toujours un ensemble à 2 éléments. On appelle couleur du sommet $s$ l'élément $f(s)$ de $C$ et la condition s'exprime sous la forme ``Si deux sommets sont voisins, ils sont de couleurs différentes''.
Le plus souvent, on ne s'intéresse pas aux couleurs, mais seulement à la répartition des sommets en couleurs distinctes. Les sommets d'une couleur donnée forment un stable de $G$, c'est-à-dire une partie de $S$ qui ne contient aucune paire de sommets voisins. Si $\mid f\left(S\right)\mid =k$, on dit que la coloration utilise $k$ couleurs. Les ensembles de sommets des différentes couleurs forment une partition de $S$ en $k$ stables. On dit que le graphe $G$ est $k$-parti (biparti pour $k=2$, triparti si $k=3$, etc.) s'il existe une telle partition, ou encore s'il existe une coloration de $G$ qui utilise exactement $k$ couleurs. Nous verrons plus loin une caractérisation simple des graphes bipartis.
Nous ajoutons ici un spécimen dans notre bestiaire. Soit $k\ge 2$ un entier et $(n_i{)}_{i\in [1,k]}$ une famille d'entiers non nuls. On définit le graphe multiparti complet $K_{n_1,n_2,\dots ,n_k}$ de la manière suivante. L'ensemble $S$ des sommets a $n={\sum }_{\mathrm{in}}{}_i$ éléments. Il est partitionné en $k$ parties $(S_i{)}_{i\in [1,k]}$, avec $\mid S_i\mid =n_i$ pour tout $i$. Deux sommets sont voisins si et seulement si ils n'appartiennent pas à la même partie. C'est, bien sûr, un graphe $k$-parti. Le graphe $K_{3,3,3,3}$ est représenté plus haut dans la discussion du théorème de Turán. Voici une représentation de $K_{3,3}$
Il est clair que l'application identique $I_S$ est une coloration de $G$ qui utilise $n$ couleurs. Il est alors naturel de se demander combien de couleurs sont nécessaires pour colorier un graphe $G$. Le nombre chromatique $\chi (G)$ du graphe $G$ est le plus petit entier $k$ pour lequel il existe une coloration de $G$ utilisant $k$ couleurs. La proposition suivante donne les nombres chromatiques associés aux graphes vus plus haut.

Proposition

La preuve de cette proposition sera faite en exercice.
À chaque numérotation $[1,n]\to S$ des sommets, on fait naturellement correspondre une coloration par des entiers naturels non nuls grâce à l'algorithme glouton:

pour i allant de 1 à n faire
  colorier le sommet i avec la première couleur parmi 1,2,3...
  qui n'est pas déjà utilisée par un voisin du sommet i
fin faire

Ainsi, le sommet $s_1$ est colorié avec la couleur 1, le sommet $s_2$ est colorié avec la couleur 2 s'il est voisin de $s_1$ et avec $c_1$ sinon, etc. Dans la figure suivante, nous avons appliqué cet algorithme deux fois au même graphe, mais avec des numérotations différentes des sommets. Entre parenthèses les numéros des couleurs sont indiqués. On voit que la première numérotation utilise 4 couleurs en tout alors que la deuxième en utilise 5. On peut montrer qu'il existe toujours une numérotation des sommets telle que l'algorithme glouton utilise $\chi (G)$ couleurs, mais cela n'a rien d'évident.
Rappelons que nous avons défini le degré maximum $\Delta (G)$ d'un graphe $G$ comme le maximum des degrés des sommets de $G$. On a la

Proposition

Démonstration

I-5 Graphes planaires

On rappelle qu'un graphe est planaire s'il admet une représentation plane dans laquelle les courbes qui représentent les arêtes ne se croisent pas. On dit que le graphe $K$ est un mineur du graphe $G$ si on peut obtenir un graphe isomorphe à $K$ à partir de $G$ en effectuant une suite d'opérations dont chacune est de l'un des trois types suivants:

• ablation d'une arête
• ablation d'un sommet et de toutes les arêtes dont ce sommet est une extrémité.
• suture d'une arête: on identifie les deux extrémités de l'arête, et on efface la boucle et les arêtes multiples qui découleraient de cette identification.

Par exemple, par ablation des sommets 3 et 6 et suture de l'arête $\{4,5\}$, on voit que le graphe $K_3$ est un mineur du graphe suivant.
On peut montrer qu'un graphe $G$ est planaire si et seulement si ni $K_5$ ni $K_{3,3}$ ne sont des mineurs de $G$.
Considérons une carte de géographie, divisée en un certain nombre de pays d'un seul tenant. On lui associe un graphe de la manière suivante: dans chaque pays, on met un sommet, et les sommets associés à deux pays sont voisins si ces pays ont une frontière commune --- pas seulement un point commun, une certaine longueur de frontière. Aux deux cartes suivantes,
on associe donc les deux graphes suivants:
Le graphe obtenu est planaire, et à une coloration de ce graphe on associe un coloriage de la carte dans lequel deux pays limitrophes ont des couleurs différentes.
En 1976, Appel et Haken ont démontré le

Théorème [des quatre couleurs]

Les considérations ci-dessus montrent que cet énoncé est équivalent au suivant:

Théorème

La démonstration a fait sensation à l'époque, non seulement parce que le problème datait de plus d'un siècle, mais aussi parce qu'elle se décomposait en environ 1500 cas, ce qui avait rendu nécessaire d'en faire écrire et vérifier une partie essentielle par des machines.

II Multigraphes

Un multigraphe est la donnée d'un couple $G=(S,A)$ d'ensembles finis, avec $S$ non vide, ainsi que d'une application $\varphi :A\to {𝒫}_1(S)\cup {𝒫}_2(S)$ qui à chaque arête fait correspondre un ensemble de 1 ou 2 sommets, ses extrémités. Si $\varphi (a)=s$ est un singleton, on dit que l'arête $a$ est une boucle de base $s$. On parlera en général du multigraphe $G=(S,A)$, en oubliant la fonction $\varphi$. Les représentations des multigraphes utilisent des lignes courbes. Voici un exemple de multigraphe
À tout multigraphe $G=(S,A)$, on fait correspondre le graphe simple sous-jacent $G\prime =(S,A\prime )$, où

$A\prime =\{a\prime \in {𝒫}_2(S);\exists a\in A,\varphi (a)=a\prime \},$

en d'autres termes, on efface les boucles et on consolide les arêtes multiples en une seule. Le graphe simple sous-jacent au multigraphe ci-dessus est donc
Dans toute la suite, nous utiliserons le terme graphe pour désigner un multigraphe, pour signifier qu'en réalité la situation ne concerne que le graphe simple sous-jacent.
On définit de façon naturelle un isomorphisme entre $G=(S,A)$ et $G\prime =(S\prime ,A\prime )$ comme un couple $(f,g)$, où $f$ est une bijection de $S$ sur $S\prime$, $g$ est une bijection de $A$ sur $A\prime$ telle que

$\forall a\in A,\varphi \prime (g(a))=f(\varphi (a)).$

Un sous-graphe d'un multigraphe $(S,A)$ est un multigraphe $(S\prime ,A\prime )$ tel que $S\prime \subset S$, $A\prime \subset A$ et $\forall a\in A\prime ,\varphi \prime (a)=\varphi (a)$. Un tel sous-graphe est couvrant si $S\prime =S$. Le sous-graphe induit par $S\prime \subset S$ est le multigraphe $(S\prime ,A\prime )$, avec

$A\prime =\{a\in A;\varphi (a)\subset S\prime \}.$

On peut encore dire qu'un multigraphe en contient un autre s'il admet un sous-graphe isomorphe à cet autre. Par exemple, le multigraphe $G$ contient si et seulement si il existe dans $G$ deux boucles de même base.

II-1 Matrices d'incidence et d'adjacence

II-2 Chaînes dans un multigraphe

II-3 Algorithmes de Moore et de Dijkstra

II-1 Matrices d'incidence et d'adjacence

On numérote les sommets et arêtes d'un multigraphe $G=(S,A)$:

$S=\{s_1,s_2,\dots ,s_n\},A=\{a_1,a_2,\dots ,a_m\}.$

La matrice d'incidence $M$ du graphe est une matrice $n\times m$ définie par

$m_{i,j}=\{\begin{array}{ l}2& \text{si}{a}_j\text{est une boucle de base}{s}_i\\ 1& \text{si}{s}_i\text{est une des deux extrémités distinctes de}{a}_j\\ 0& \text{si}{s}_i\text{n'est pas une extrémité de}{a}_j.\end{array}$

La somme des éléments de la colonne d'indice $j$ vaut 2. La somme des éléments de la ligne $i$ est, par définition, le degré de $s_i$: les boucles de base $s_i$ comptent pour 2, les autres arêtes d'extrémité $s_i$ pour 1. On peut alors énoncer la même relation fondamentale que pour les graphes simples:

Théorème

Démonstration
Et on a encore le

Corollaire

La matrice d'adjacence $A_G$ du graphe $G$ est une matrice $n\times n$ définie par
On voit que cette matrice est symétrique. La somme des éléments d'une ligne (ou colonne) n'est pas le degré du sommet correspondant puisque les boucles ne sont ici comptées qu'une fois.
Voici les matrices d'incidence et d'adjacence du multigraphe dessiné plus haut.

$M=\left(\begin{array}{ccccc}1& 1& 1& 0& 0\\ 1& 1& 1& 1& 0\\ 0& 0& 0& 1& 2\\ \end{array}\right),A=\left(\begin{array}{ccc}0& 3& 0\\ 3& 0& 1\\ 0& 1& 1\\ \end{array}\right)$

II-2 Chaînes dans un multigraphe

Soit $k\in \mathbb{N}$ un entier naturel. Une $k$-chaîne, ou chaîne de longueur $k$ d'un multigraphe est la donnée d'une famille $(v_i{)}_{i\in [0,k]}$ de $k+1$ sommets et d'une famille $(e_i{)}_{i\in [1,k]}$ de $k$ arêtes telles que pour tout $i\in [1,k]$, on ait $\varphi (e_i)=\{v_{i-1},v_i\}$. On note

$\gamma =(v_0,e_1,v_1,e_2,\dots ,e_k,v_k).$

On dit que la chaîne visite chacun des $v_i$ et des $e_i$. Le sommet $v_0$ est l'origine de la chaîne et $v_k$ est son extrémité. En particulier, si $s\in S$ est un sommet, $(s)$ est une $0$-chaine, d'origine $s$ et extrémité $s$. Une chaîne est fermée si $v_0=v_k$. Elle est simple si les arêtes $e_1,\dots ,e_k$ sont distinctes. Elle est élémentaire si les sommets $v_0,\dots ,v_k$ sont distincts.
Dans un graphe simple, on a forcément $e_i=\{v_{i-1},v_i\}$. On se contente donc de noter les sommets et on écrit $\gamma =(v_0,v_1,\dots ,v_k)$.
Il y a des opérations naturelles sur les chaînes: Si l'extrémité de $\gamma =(v_0,e_1,v_1,e_2,\dots ,e_k,v_k)$ est égale à l'origine de $\delta =(w_0,f_1,w_1,f_2,\dots ,f_l,w_l)$, c'est-à-dire si $v_k=w_0$, on peut définir la concaténation

$\gamma \cdot \delta =(v_0,e_1,v_1,e_2,\dots ,e_{k+l},v_{k+l})$

en posant $e_i=f_{i-k}$ et $v_i=w_{i-k}$ pour $k<i\le k+l$. On peut aussi définir la chaîne

$\tilde{\gamma }=(v{\prime }_0,e{\prime }_1,v{\prime }_1,e{\prime }_2,\dots ,e{\prime }_k,v{\prime }_k)=(v_k,e_k,\dots ,e_1,v_0)$

qui est `` parcourue dans l'autre sens'' en posant $e{\prime }_i=e_{k+1-i}$ et $v{\prime }_i=v_{k-i}$.

Théorème

Démonstration

II-3 Algorithmes de Moore et de Dijkstra

On définit une fonction $D:S\times S\to \mathbb{N}\cup \{\mathrm{\infty }\}$ appelée distance sur $G$ de la façon suivante. S'il existe une chaîne d'origine $s$ et extrémité $t$, $D(s,t)$ est la longueur minimale d'une telle chaîne. S'il n'en existe pas, on pose $D(s,t)=\mathrm{\infty }$.
Cette fonction n'est pas une distance au sens usuel puisque elle peut prendre la valeur . Mais il est facile de voir que la fonction

$\tilde{D}(s,t)=\{\begin{array}{ l}{\displaystyle \frac{D(s,t)}{1+D(s,t)}}& \text{si}D(s,t)\ne \mathrm{\infty }\\ 1& \text{si}D(s,t)=\mathrm{\infty }\end{array}$

est une distance sur $S$. Dans la pratique, on préfère utiliser $D$, qui prend des valeurs entières.
Donnons un algorithme classique de calcul de $D(s,t)$, pour un sommet fixé et tout sommet $t$, l'algorithme de Moore:

Données: Un sommet s d'un graphe (S,A)
Sortie: Pour tout dans S, D[t] contient D(s,t)
D[s] <- 0
Pour tout t dans S faire
  D[t] <- infini
fin pour
k <- 0
V <- {s} (V est un ensemble de sommets, au départ un singleton)
tant que V n'est pas vide faire
  k <- k+1
  W <- {} (ensemble vide)
  pour tout x dans V faire
    pour tout y voisin de x et tel que D[y] = infini faire
      D[y] <- k
      W <- W union {y} (on ajoute y à l'ensemble W)
    fin pour
  fin pour
  V <- W
fin tant que

En d'autre termes, $s$ est étiqueté 0, les voisins de $s$ étiquetés 1, les voisins des voisins de $s$ sauf $s$ lui-même sont étiquetés 2, et si $t$ est étiqueté $k$, ses voisins non encore étiquetés seront étiquetés $k+1$, etc. Voici un exemple d'exécution de l'algorithme de Moore
Il existe une généralisation naturelle de cette notion de distance sur un graphe. Un graphe valué $(S,A,\mu )$ est la donnée d'un multigraphe $G=(S,A)$ et d'une fonction $\mu :A\to {ℝ}^{*+}$ appelée coût ou poids ou longueur... Le coût d'une chaîne $\gamma =(v_0,e_1,v_1,e_2,\dots ,e_k,v_k)$ est alors défini par $\mu (\gamma )={\sum }_{i\in [1,k]}\mu (e_i)$. On définit la distance $C(s,t)$ entre deux sommets d'un graphe valué comme le minimum des coûts des chaînes d'origine $s$ et extrémité $t$ s'il en existe, et s'il n'en existe pas. Pour déterminer $C(s,t)$ pour un sommet fixé $s$ et chaque sommet $t$, on peut utiliser l'algorithme de Dijkstra:

Données: Un sommet s d'um graphe valué (S,A,m),
Sortie: Pour tout t dans S, C[t] contient C(s,t)
        Si 0 < C[t] < infini, T[t] contient la première étape
        dans une chaîne de coût minimal menant de t à s.
Pour tout t dans S faire
  C[t] <- infini
fin pour
C[s] <- 0
V <- {} (ensemble vide)
W <- S (tous les sommets)
tant qu'il y a dans W un sommet t tel que C[t] est fini faire
  u <- un sommet de W tel que C[u] soit minimal
  V <- V union {u}
  W <- W \ {u} (On transfère u de W vers V)
  pour chaque voisin x de u faire
    si C[u] + m({u, x}) < C[x] faire
      C[x] <- C[u] + m({u, x})
      T[x] <- u
    fin si
  fin pour
fin tant que

Pour montrer que cet algorithme est correct, il suffit de vérifier que l'invariant de boucle suivant est maintenu: si $t\ne s$ est dans V, un chemin de moindre coût de $t$ à $s$ commence par T[t] est reste dans V. On peut montrer que la complexité de cet algorithme est en $calO((n+m)\log (n))$, où $n$ est le nombre de sommets et $m$ le nombre d'arêtes.
Voici par exemple les étapes de l'algorithme sur une valuation du cube $Q_3$.
Les étiquettes des sommets représentent le tableau C et le tableau T est représenté par des flèches qui pointent de t vers T[t]. Si un sommet est dans V, le point qui le marque est plus gros.
Pour trouver comment rejoindre le coin en bas à gauche à moindre coût, suivre les flèches.

III Chaînes et cycles

III-1 Connexité

III-2 Cycles

III-3 Graphes eulériens

III-4 Graphes hamiltoniens

III-1 Connexité

Si $s$ et $t$ sont deux sommets d'un graphe $G=(S,A)$, on dira que $s$ est relié à $t$ et on écrira $s{\sim }_{G}t$ s'il existe une chaîne de $G$ dont l'origine est $s$ et l'extrémité $t$. Cela revient à dire que $D(s,t)$ est fini.

Théorème

Démonstration
Un graphe sera dit connexe si deux sommets quelconques sont toujours reliés. Il revient au même de dire que $D$ ne prend que des valeurs finies, ou encore que le diamètre $D(G)=\max \{D(s,t);s,t\in S\}$ du graphe $G$ est fini.
À toute relation d'équivalence sur un ensemble $S$, on associe une partition de $S$ en classes d'équivalence. On a donc une partition $S={\cup }_{i\in [1,p]}{S}_i$. Si deux sommets sont voisins, ils sont reliés. Toute arête de $G$ relie donc deux sommets qui appartiennent à la même classe. En posant $A_i=\{a\in A;\varphi (a)\subset S_i\}$, on a donc montré que $A$ est réunion disjointe des $A_i$. Les multigraphes $G_i=(S_i,A_i)$ ont la propriété que deux sommets quelconques de $G_i$ sont reliés dans $G_i$. Ils sont donc connexes, et on a montré le

Théorème

Les $G_i$ sont appelés les composantes connexes de $G$ et $p$ est le nombre des composantes connexes de $G$. La fonction $D$ induit une distance sur chaque composante connexe de $G$. Il est facile de voir que tous les graphes du bestiaire sont connexes, sauf le stable $S_n$ pour $n>1$, qui a $n$ composantes connexes.

Théorème

Démonstration

III-2 Cycles

Pour $k\ge 1$ un $k$-cycle ou cycle de longueur $k$ d'un multigraphe $G$ est une $k$-chaîne simple fermée de $G$. Un $k$-cycle est dit élémentaire si les sommets $(v_1,\dots ,v_k)$ sont tous distincts. L'origine (et extrémité) du cycle est plutôt appelée sa base. Remarquons qu'un $1$-cycle est associé à une boucle et qu'un 2-cycle est associé à une arête double. On en déduit que dans un graphe simple, la longueur d'un cycle est au moins 3.

Proposition

Démonstration

Proposition

Démonstration

Théorème

Démonstration

Théorème

Démonstration
Donnons enfin la caractérisation des graphes bipartis en termes de cycles:

Théorème

Remarquons que le nombre chromatique $\chi (G)$ est inférieur ou égal ou égal à 2 si et seulement si $G$ est biparti ou 1-stable.
Démonstration

III-3 Graphes eulériens

Un cycle eulérien d'un multigraphe $G$ est un cycle qui visite toutes les arêtes et tous les sommets de $G$. Un graphe eulérien est un multigraphe qui admet un cycle eulérien. Une chaîne eulérienne est une chaîne simple qui visite toutes les arêtes et tous les sommets de $G$. Un graphe semi-eulérien est un multigraphe qui admet une chaîne eulérienne.
Notons que ces chaînes passent une fois et une seule par chaque arête, et au moins une fois par chaque sommet, mais qu'elles peuvent passer plusieurs fois par le même sommet. Des trois graphes suivants, le premier est eulérien, le second est semi-eulérien sans être eulérien, et le troisième n'est pas semi-eulérien.

Théorème

Démonstration

Corollaire

Démonstration

III-4 Graphes hamiltoniens

Un cycle hamiltonien est un cycle élémentaire qui visite tous les sommets d'un graphe. Sa longueur est donc l'ordre $n$ du graphe. Une chaîne hamiltonienne est une chaîne élémentaire qui visite tous les sommets d'un graphe. Sa longueur est donc $n-1$. Un graphe hamiltonien est un multigraphe qui admet un cycle hamiltonien.

Proposition

En effet, dans un graphe simple, la longueur d'un cycle est au moins 3.

Théorème

Démonstration

Corollaire

IV Arbres

Une forêt est un multigraphe sans cycle. En particulier, c'est un graphe simple. Un arbre est un graphe connexe sans cycle. Voici quelques arbres. Le théorème suivant montre que les arbres ont une position centrale. Nous aurons besoin de quelques propositions préliminaires.

IV-1 Préliminaires

IV-2 Caractérisation des arbres

IV-3 Arbres couvrants

IV-4 Théorème de Cayley

IV-1 Préliminaires

Un sommet pendant d'un graphe est un sommet de degré 1. Si $s$ est un sommet pendant, il existe une arête $e$ incidente à $s$ et une seule.

Proposition

Démonstration

Corollaire

Démonstration

Proposition

Démonstration

Corollaire

Enfin, dans un graphe connexe $G=(S,A)$, un isthme est une arête $e$ telle que le graphe $G\setminus \{e\}=(S,A\setminus \{e\})$ ne soit pas connexe.

Proposition

Démonstration

Corollaire

En effet, $e$ est un isthme du graphe connexe $G″=(S_1\cup S_2,A_1\cup A_2\cup \{e\})$. Un cycle de $G\prime$ doit visiter $e$ donc rester dans $G″$, une contradiction.

IV-2 Caractérisation des arbres

On rappelle sans démonstration un théorème classique:

Théorème

Le théorème suivant est tout-à-fait analogue au théorème précédent:

Théorème

Démonstration

IV-3 Arbres couvrants

Un arbre couvrant d'un multigraphe $G$ est un sous-graphe couvrant de $G$ qui est un arbre. Si un graphe a un arbre couvrant, il est connexe. Le théorème précédent montre que la réciproque est vraie. Nous présentons deux algorithmes naturels pour trouver un arbre couvrant d'un multigraphe $G$ connexe.

Données: Un multigraphe connexe G = (S,A)
Sortie: Une partie A' de A telle que G'=(S, A') est un arbre.
A' <- {}
tant que $G'$ n'est pas connexe
  choisir une composante connexes C de G'
  choisir une arête e de A liant C et S \ C
  faire A' <- A' union {e}
fin tant que

L'existence de l'arête $e$ est due au fait que $G$ est connexe. L'adjonction de $e$ à $A\prime$ ne change pas le fait que $G\prime$ est une forêt. L'algorithme s'arrête donc bien quand $G$ est un arbre.
Cet algorithme a une variante adaptée aux graphes valués: on définit le poids d'un sous-graphe comme la somme des coûts de toutes les arêtes de ce sous-graphe, et on cherche un arbre couvrant de poids minimal.

Données: Un multigraphe valué connexe G = (S,A,c)
Sortie: Une partie A' de A telle que G'=(S, A') est un arbre
  et le poids total de A' est minimal.
numéroter les éléments de A par poids croissant:
  c(e_1) <= ... <= c(e_m)
A' <- {}
pour i allant de 1 à m faire
  si (e_i n'est pas une boucle et si) les extrémités de e_i
    sont sur des composantes connexes différentes de G' faire
    A' <- A' union {e_i}
  fin si
fin tant que

Cet algorithme, qui prend en priorité les arêtes de poids faible, est appelé glouton pour la même raison qui fait qu'en informatique les arbres sont représentés avec leurs racines en haut et les feuilles en bas.
Il existe une méthode duale pour extraire un arbre couvrant, qui consiste à couper les cycles tant qu'il y en a. Nous allons l'énoncer pour un multigraphe quelconque.

Données: Un multigraphe G = (S,A) à e composantes connexes.
Sortie: A' est une partie de A telle que G'=(S,A')
  est une forêt à e composantes connexes.
A' <- A
tant qu'il existe un cycle dans G'
  choisir un cycle C dans G'
  choisir une arête e visitée par C
  faire A' <- A' \ {e}
fin tant que

Comme on l'a vu plus haut, le fait d'enlever une arête visitée par un cycle ne change rien à la connexité. Le nombre de composantes connexes de $G\prime$ est donc le même que celui de $G$. En particulier, si $G$ est connexe, $G\prime$ est un arbre couvrant de $G$. En général, combien de fois la boucle interne de l'algorithme s'exécute-t'elle ? Appelons $p$ ce nombre. On voit que $p=\mid A\mid -\mid A\prime \mid$ est le nombre d'arêtes qu'on a enlevées. La proposition suivante montre que $p$ ne dépend pas des choix faits dans l'algorithme, mais seulement du multigraphe $G$. Nous appellerons $p$ le nombre de cycles indépendants de $G$.

Proposition

Démonstration

IV-4 Théorème de Cayley

On s'intéresse ici aux arbres couvrants de la clique $K_n$, ou plutôt à leur nombre. On voit facilement que $K_1$ et $K_2$ sont des arbres et que $K_3$ a trois arbres couvrants.
Il est plus difficile d'établir que les arbres couvrants de $K_4$ sont au nombre de 16, mais il n'y en a que deux à isomorphisme près. Supposons désormais $n\ge 3$. Nous allons décrire une opération de codage qui à tout arbre $T$ dont l'ensemble des sommets est $[1,n]$ fait correspondre une famille $(b_1,\dots ,b_{n-2})$ de $n-2$ éléments de $[1,n]$ de la façon suivante.

Données: Un arbre T = (S, A) d'ensemble de sommets S = [1,n]
Sortie: le tableau b contient n-2 entiers de [1,n]
pour i de 1 à n-2 faire
  s <- le plus petit sommet pendant de T
  e <- l'arête incidente à s
  b[i] <- le voisin de s dans T
  S <- S \ {s}
  A <- A \ {e}
fin pour

Voici la suite des opérations qui donne l'encodage d'un certain arbre couvrant de $K_9$.
Le résultat final est donc la famille $(4,6,6,5,4,4,5)$. L'opération de décodage se décrit de la même façon:

Données: Un tableau b de n-2 entiers de [1,n]
Sortie: T = ([1,n], A) est un arbre
A <- {}
S <- [1,n]
pour i de 1 à n-2 faire
  s <- le plus petit élément de S qui n'est égal
       à aucun b[j] avec i <= j <= n-2.
  A <- A union {{s,b[i]}}
  S <- S \ {s}
fin pour
A <- A union {S}

Comme $S$ a $n-i+1$ éléments et $j$ ne prend que $n-i-1$ valeurs, on peut toujours trouver $s$. Pour prouver que le graphe obtenu est un arbre, il suffit de remarquer qu'à tout moment $S$ contient un sommet et un seul dans chaque composante connexe de $T$. Comme $b[i]$ n'a pas pu être enlevé de $S$ aux tours précédents, il est encore dans $S$ et l'arête $\{s,b[i]\}$ réunit deux composantes connexes différentes: il ne peut se créer de cycle. Après la fin de la boucle, S ne contient que deux éléments, appartenant aux deux composantes connexes de $([1,n],A)$. Enfin, $T$ est une forêt à $n-1$ arêtes, c'est donc bien un arbre. Voici la suite d'opérations décrivant le décodage de $(4,6,6,5,4,4,5)$:
On voit que les opérations de codage et de décodage sont inverses l'une de l'autre. On a donc une bijection entre l'ensemble $T_n$ des arbres couvrants de $K_n$ et $[1,n{]}^{n-2}$. On a donc prouvé le

Théorème [de Cayley]