Graphes

Graphes




I Graphes simples

II Multigraphes

III Chaînes et cycles

IV Arbres

I Graphes simples

Graphes → 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

GraphesI Graphes simples → 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 (n2)=n(n1)2 paires de sommets, il y a entre 0 et n(n1)2 arêtes.
On dit que deux sommets s et s sont voisins si {s,s} 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

Le nombre d'arêtes d'un graphe simple est égal à la demi-somme des degrés de ses sommets:

sSd(s)=2A.


Démonstration
Notons B l'ensemble des bouts, couples (s,a)S×A tels que sa. Comme chaque arête a deux bouts, on a B=2A par le principe des bergers. D'autre part, chaque sommet s appartient à d(s) arêtes. On a donc B= sSd(s), d'où le résultat.

En conséquence

Corollaire

Le nombre de sommets de degré impair d'un graphe simple est pair.
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

δ(G)=min sSd(s)

respectivement

Δ(G)=max sSd(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=S points étiquetés par les éléments de S et pour chaque arête {s,s}A, une courbe simple, par exemple un segment de droite, joignant les sommets étiquetés s et s. 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}}).

et

Un isomorphisme du graphe simple G=(S,A) sur le graphe simple G=(S,A) est une bijection ϕ:SS telle que

s,tS,{s,t}A{ϕ(s),ϕ(t)}A.

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

GraphesI Graphes simples → I-2 Bestiaire
Nous allons donner des exemples de (classes d'isomorphismes de) graphes simples naturels.

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

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

Le graphe complémentaire du graphe simple G=(S,A) est un graphe G ¯ =(S,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 A ¯ =𝒫 2(S)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=(S,A) tel que SS et AA. On dit que c'est un sous-graphe couvrant si S=S. Pour toute partie S de S, on définit le sous-graphe de G induit par S et on note G(S) le graphe G(S)=(S,A), où A=A𝒫 2(S) est l'ensemble des arêtes de A dont les deux extrémités sont dans S.
On dit que G contient le graphe G s'il existe un sous-graphe de G isomorphe à G. Nous allons prouver le

Théorème [de Turán]

Soit n1 et p2 des entiers. Si le graphe simple G=(S,A) d'ordre n ne contient pas de p-clique, alors

A(11p1)n 22.


Démonstration
Par récurrence sur n et p. Pour n=1 ou p=2, il n'y a rien à démontrer. Soit donc n>1 et p>2 deux entiers, et supposons le résultat vrai pour p<p ou n<n. On considère un graphe simple G=(S,A) d'ordre n qui ne contient pas de p-clique.
Si G ne contient pas de (p1)-clique, on peut appliquer l'hypothèse de récurrence avec p=p1. On a donc

A(11p2)n 22(11p1)n 22.

Nous pouvons donc supposer que G contient une (p1)-clique, c'est-à-dire qu'il existe une partie S de S de cardinal p1 telle que tous les éléments de S sont voisins entre eux. Notons S=SS. Si S est vide, le graphe G est la clique K p1, on a n=p1 et

A=(p1)(p2)2=(p2p1)(p1) 22=(11p1)n 22.

Sinon, le graphe induit G=G(S) ne contient pas non plus de p-clique et a un ordre n=np+1<n. On peut lui appliquer l'hypothèse de récurrence et on a

A(11p1)n 22.

Les arêtes de G sont de trois sortes: celles qui ont leurs deux extrémités dans S, au nombre de (p1)(p2)2, celles dont les deux extrémités sont dans S, au nombre de A majoré ci-dessus, et celles dont une extrémité est dans S et l'autre dans S. Pour chaque sommet s de S, il y a au moins un sommet t de S qui n'est pas voisin de s, puisque autrement G(S{s}) serait une p-clique de G. Il y a donc au plus p2 arêtes de la troisième espèce qui ont s pour extrémité, et il y a au plus (p2)n arêtes de troisième espèce en tout. Au total, on a
A(p1)(p2)2+(11p1)n 22+(p2)n
==p22(p1)((p1) 2+n 2+2(p1)n)=(11p1)n 22.

On remarque que si n=q(p1) est un multiple de p1, on peut construire un graphe d'ordre n de la façon suivante: on répartit les sommets en p1 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 (p12)=(p1)(p2)2 paires de groupes et q 2 arêtes entre éléments de cette paire de groupes. On a donc

A=(p1)(p2)2q 2=(11p1)n 22

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

I-4 Colorations

GraphesI Graphes simples → I-4 Colorations

Une application f:SC 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 f(S)=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 k2 un entier et (n i) i[1,k] une famille d'entiers non nuls. On définit le graphe multiparti complet K n 1,n 2,,n k de la manière suivante. L'ensemble S des sommets a n= ini éléments. Il est partitionné en k parties (S i) i[1,k], avec S i=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 χ(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]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 χ(G) couleurs, mais cela n'a rien d'évident.

Rappelons que nous avons défini le degré maximum Δ(G) d'un graphe G comme le maximum des degrés des sommets de G. On a la

Proposition

Le nombre chromatique d'un graphe simple vérifie

χ(G)Δ(G)+1


Démonstration
En fait, quel que soit l'ordre choisi sur les sommets, l'algorithme glouton utilise au maximum Δ(G)+1 couleurs distinctes. Soit en effet k le numéro de la plus haute couleur utilisée, et s un sommet qui a cette couleur. L'algorithme glouton attribue la couleur k à s parce que les voisins de s déjà coloriés occupent toutes les couleurs de 1 à k1. Donc s a au moins k1 voisins distincts, et k1Δ(G), d'où χ(G)kΔ(G)+1.

I-5 Graphes planaires

GraphesI Graphes simples → 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: 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]

Toute carte de géographie plane peut être coloriée avec quatre couleurs de façon que deux pays limitrophes aient toujours des couleurs différentes.

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

Théorème

Si G est un graphe simple planaire, χ(G)4.

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

Graphes → 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 ϕ:A𝒫 1(S)𝒫 2(S) qui à chaque arête fait correspondre un ensemble de 1 ou 2 sommets, ses extrémités. Si ϕ(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 ϕ. 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=(S,A), où

A={a𝒫 2(S);aA,ϕ(a)=a},

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=(S,A) comme un couple (f,g), où f est une bijection de S sur S, g est une bijection de A sur A telle que

aA,ϕ(g(a))=f(ϕ(a)).

Un sous-graphe d'un multigraphe (S,A) est un multigraphe (S,A) tel que SS, AA et aA,ϕ(a)=ϕ(a). Un tel sous-graphe est couvrant si S=S. Le sous-graphe induit par SS est le multigraphe (S,A), avec

A={aA;ϕ(a)S}.

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

GraphesII Multigraphes → 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,,s n},A={a 1,a 2,,a m}.


La matrice d'incidence M du graphe est une matrice n×m définie par

m i,j={2 si a j est une boucle de base s i 1 si s i est une des deux extrémités distinctes de a j 0 si s i n'est pas une extrémité de a j.


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

Le nombre d'arètes d'un multigraphe est égal à la demi-somme des degrés de ses sommets:

sSd(s)=2A.


Démonstration
Ce nombre est égal à la somme de tous les éléments de la matrice M:

sSd(s)= i=1 nd(s i)= i=1 n( j=1 mm ij)= j=1 m( i=1 nmij)= j=1 m2=2A.


Et on a encore le

Corollaire

Le nombre de sommets de degré impair d'un multigraphe est pair.

La matrice d'adjacence A G du graphe G est une matrice n×n définie par
a ij = {aA;ϕ(a)={s i,s j}} = {Nombre de boucles de base s i si i=j Nombre d'arêtes d'extrémités s i et s j si ij.

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=(1 1 1 0 0 1 1 1 1 0 0 0 0 1 2 ),A=(0 3 0 3 0 1 0 1 1 )

II-2 Chaînes dans un multigraphe

GraphesII Multigraphes → II-2 Chaînes dans un multigraphe

Soit k 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[0,k] de k+1 sommets et d'une famille (e i) i[1,k] de k arêtes telles que pour tout i[1,k], on ait ϕ(e i)={v i1,v i}. On note

γ=(v 0,e 1,v 1,e 2,,e k,v k).

On dit que la chaîne gamma visite chacun des v i et des e i. Le sommet v 0 est l'origine de la chaîne gamma et v k est son extrémité. En particulier, si sS 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,,e k sont distinctes. Elle est élémentaire si les sommets v 0,,v k sont distincts.
Dans un graphe simple, on a forcément e i={v i1,v i}. On se contente donc de noter les sommets et on écrit γ=(v 0,v 1,,v k).
Il y a des opérations naturelles sur les chaînes: Si l'extrémité de γ=(v 0,e 1,v 1,e 2,,e k,v k) est égale à l'origine de δ=(w 0,f 1,w 1,f 2,,f l,w l), c'est-à-dire si v k=w 0, on peut définir la concaténation

γδ=(v 0,e 1,v 1,e 2,,e k+l,v k+l)

en posant e i=f ik et v i=w ik pour k<ik+l. On peut aussi définir la chaîne

γ˜=(v 0,e 1,v 1,e 2,,e k,v k)=(v k,e k,,e 1,v 0)

qui est `` gamma parcourue dans l'autre sens'' en posant e i=e k+1i et v i=v ki.

Théorème

Soit G=(S,A) un multigraphe, et A G sa matrice d'incidence. Pour tout k et tout couple (i,j)[1,n] 2, le coefficient (A G k) ij de la puissance k-ième de A G est égal au nombre de k-chaînes d'origine s i et extrémité s j.

Démonstration
Par récurrence sur k. La matrice A G 0 est la matrice identité I n, et il est clair que le nombre de 0-chaînes d'origine s i et extrémité s j vaut 1 si i=j et 0 sinon. La propriété est donc vraie pour k=0. Supposons-la vraie pour k. Une k+1-chaîne d'origine s i et extrémité s j s'écrit (v 0,,v k,e k+1,v k+1), avec v 0=s i et v k+1=s j. Si v k=s l, (v 0,,v k) est une k-chaîne d'origine s i et extrémité s l et e k+1 vérifie ϕ(e k+1)={s l,s j}. L'hypothèse de récurrence dit qu'il y a (A G k) il possibilités pour la première partie et la définition de A G dit qu'il y a (A G) lj possibilités pour la seconde. Le nombre de k+1-chaînes d'origine s i, extrémité s j et telles que le sommet v k soit s l vaut donc (A G k) il(A G) lj. le nombre total de k+1-chaînes d'origine s i et extrémité s j est donc

l=1 n(A G k) il(A G) lj=(A G k+1) ij.

II-3 Algorithmes de Moore et de Dijkstra

GraphesII Multigraphes → II-3 Algorithmes de Moore et de Dijkstra

On définit une fonction D:S×S{} 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)=.
Cette fonction n'est pas une distance au sens usuel puisque elle peut prendre la valeur infty. Mais il est facile de voir que la fonction

D˜(s,t)={D(s,t)1+D(s,t) si D(s,t) 1 si D(s,t)=

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,μ) est la donnée d'un multigraphe G=(S,A) et d'une fonction μ:A *+ appelée coût ou poids ou longueur... Le coût d'une chaîne γ=(v 0,e 1,v 1,e 2,,e k,v k) est alors défini par μ(γ)= i[1,k]μ(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 infty 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 ts 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

Graphes → III Chaînes et cycles

III-1 Connexité

III-2 Cycles

III-3 Graphes eulériens

III-4 Graphes hamiltoniens

III-1 Connexité

GraphesIII Chaînes et cycles → 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 Gt 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

La relation G est une relation d'équivalence sur S.

Démonstration
Elle est

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,tS} 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= i[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={aA;ϕ(a)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

Pour tout graphe G=(S,A), il existe une partition unique de S en p1 parties non vides telle que les sous-graphes induits G i=G(S i) soient connexes et que toute arête de G appartienne à un des G i.

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

Un graphe G=(S,A) est connexe si et seulement si pour toute partition de S en 2 parties (non vides) S et S, il existe une arête aA dont une extrémité est dans S et l'autre dans S.

Démonstration
Suppossons d'abord G connexe. Considérons une partition S en 2 parties (non vides) S et S. Comme S et S sont non vides, on peut choisir sS et tS. Comme G est connexe, il existe une chaîne γ=(v 0,e 1,,v k) d'origine s et extrémité t. L'ensemble I={i[0,k];v iS} n'est pas vide puisque v k=tS, et ne contient pas 0 puisque v 0=sS. Notons r>0 son plus petit élément. On a v r1S, donc v r1S et v rS. L'arête e r a une extrémité dans S et une autre dans S.
Réciproquement, supposons que pour toute partition de S en 2 parties (non vides) S et S, il existe une arête aA dont une extrémité est dans S et l'autre dans S. Considérons deux sommets s et t de S. Notons S l'ensemble des extrémités des chaînes d'origine s, et S le complémentaire de S dans S. Supposons que tS. Ni S ni S ne sont alors vides. On applique l'hypothèse sur G: il existe une arête e=u,v, avec u dans S et vS. Il existe une chaîne γ=(v 0,e 1,,v k) d'origine s et extrémité u, alors, l'existence de γ(u,e,v)=(v 0,e 1,,v k,e,v), d'origine s et extrémité v montre que vS, une contradiction. On a donc montré que tS, il y a une chaîne d'origine s et extrémité t. On en déduit que G est connexe.

III-2 Cycles

GraphesIII Chaînes et cycles → III-2 Cycles
Pour k1 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,,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

De tout cycle, on peut extraire un cycle élémentaire.

Démonstration
Si γ=(v 0,e 1,v 1,,e k,v k) est un k-cycle, l'ensemble des couples d'entiers (i,j) tels que 0i<jk et v i=v j n'est pas vide, puisqu'il contient (0,k). Il existe donc un tel couple (i,j) avec ji minimal. On voit que (v i,e i+1,v i+1,,v j) est un cycle élémentaire.

Proposition

De toute chaîne fermée de longueur impaire, on peut extraire un cycle de longueur impaire.

Démonstration
Par récurrence sur la longueur k de la chaîne fermée. Si k=1, la 1-chaîne fermée (s,a,s) est un 1-cycle. Supposons la propriété vraie pour toute k-chaîne fermée, avec k<k impair. Si la k-chaîne fermée γ=(v 0,e 1,v 1,,e k,v k) est simple, c'est un cycle. Sinon, il existe (i,j), avec 1i<jk tel que e i=e j. On en déduit que les ensembles {v i1,v i} et {v j1,v j} sont égaux. Il y a deux possibilités:
  1. v i1=v j1 et v i=v j. Posons alors

    γ 1=(v i1,e i,v i,e i+1,v i+1,,e j1,v j1)

    et

    γ 2=(v j1,e j,v j,,e k,v k,e 1,v 1,,e i1,v i1).

    Ce sont deux chaînes fermées extraites de gamma. La première a pour longueur k 1=ji>0 et la seconde k 2=(kj+1)+(i1)>0. On a k 1+k 2=k impair, donc l'un des deux est impair, strictement plus petit que k. On peut appliquer l'hypothèse de récurrence à γ 1 ou γ 2 pour obtenir un cycle impair extrait de gamma.
  2. v i1=v j et v i=v j1. Posons alors

    γ 1=(v i,e i+1,v i+1,,e j1,v j1)

    et

    γ 2=(v j,,e k,v k,e 1,v 1,,e i1,v i1).

    Ce sont deux chaînes fermées extraites de gamma. La première a pour longueur k 1=ji1 et la seconde k 2=(kj)+(i1). On a k 1+k 2=k2 impair, donc l'un des deux est impair, strictement plus petit que k. On peut appliquer l'hypothèse de récurrence à γ 1 ou γ 2 pour obtenir un cycle impair extrait de gamma.

Théorème

Si le degré minimum δ(G) d'un multigraphe G vaut au moins 2, alors il existe un cycle dans G.

Démonstration
Soit γ=(v 0,e 1,v 1,,e k,v k) une chaîne simple de longueur k maximale. Comme il y a au moins un sommet, et que son degré n'est pas nul, il y a au moins une arête, et k1. Si e k est une boucle, (v k,e k,v k) est un cycle. Sinon, comme d(v k)>1, il existe une arête e d'origine v k et différente de e k. Notons u le sommet tel que ϕ(e)={v k,u}. La chaîne γ=(v 0,e 1,v 1,,e k,v k,e,u) a pour longueur k+1. Elle n'est donc pas simple. On en déduit qu'il existe i, avec 1i<k tel que e i=e. Il existe donc j, avec j=i ou j=i1 tel que j<k et v j=v k. On a donc un cycle (v j,e j+1,,e k,v k).

Théorème

Si le degré minimum δ(G) d'un graphe simple G vaut au moins 2, alors il existe dans G un cycle élémentaire de longueur au moins égale à δ(G)+1.

Démonstration
Soit γ=(v 0,,v k) une chaîne élémentaire de longueur k maximale. Comme il y a au moins un sommet, et que son degré n'est pas nul, il y a au moins une arête, et k1. Soit u un voisin de v 0. La chaîne (u,v 0,v 1,,v k) a pour longueur k+1, et n'est donc pas élémentaire. On en déduit que u est égal à l'un des v i, pour un i[1,k], que nous appellerons l'indice du voisin u. Chacun des voisins de v 0 a un indice différent. L'un d'eux au moins a donc un indice iδ(G). Puisque v i est voisin de v 0, (v 0,v 1,,v i,v 0) est un cycle élémentaire, et sa longueur vaut au moins δ(G)+1.

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

Théorème

Un multigraphe G=(S,A) différent du 1-stable est biparti si et seulement si il n'existe pas dans G de cycle de longueur impaire. En particulier, il ne doit pas avoir de boucle.

Remarquons que le nombre chromatique χ(G) est inférieur ou égal ou égal à 2 si et seulement si G est biparti ou 1-stable.
Démonstration
Si G est biparti, il existe une partition S=SS telle que toute arête ait une extrémité dans S et une autre dans S. Si γ=(v 0,e 1,v 1,,e k,v k) est un k-cycle et si v 0S, on voit, par récurrence sur i, que v iS pour i pair et v iS pour i impair. On sait que v kS. Donc k est pair.
Réciproquement, supposons que G n'admette pas de cycle impair. Commençons par supposer que G est connexe et A. Choisissons un sommet sS. Notons
S = {extrémités desk-chaînes d'origines,aveckpair} S = {extrémités desk-chaînes d'origines,aveckimpair}
Comme G est connexe, il est clair que S=SS. D'autre part, tout voisin d'un élément de S est dans S et tout voisin d'un élément de S est dans S. Comme A, on voit que ni S ni S ne sont vides. Il reste donc à prouver que SS=. Si tSS il existe une chaîne paire gamma et une chaîne impaire delta d'origine s et extrémité t. La concaténation γ.δ˜ de ces deux chaînes est une chaîne fermée de longueur impaire. On peut donc en extraire un cycle impair, une contradiction. Dans le cas où G n'est pas connexe, on voit que chacune des composantes connexes de G est bipartie ou 1-stable et G lui-même est donc biparti ou 1-stable.

III-3 Graphes eulériens

GraphesIII Chaînes et cycles → 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

Soit G un multigraphe d'ordre au moins 2. Le multigraphe G est eulérien si et seulement si il est connexe et tous ses sommets sont de degré pair.

Démonstration
Remarquons d'abord qu'en ajoutant ou effaçant une boucle, on ne change pas la connexité, ni la parité du degré des sommets, ni l'existence d'un cycle eulérien. Nous pouvons donc supposer que G n'a pas de boucle. Si G est eulérien, soit γ=(v 0,e 1,v 1,,e k,v k) une chaîne eulérienne. Elle visite tous les sommets, donc pour tout couple (s,t) de sommets, elle induit une chaîne d'extrémités s et t. Le graphe G est donc connexe. Soit s un sommet de G, A s l'ensemble des arêtes incidentes à s et I s={i[1,k];v i=s}. L'application f s:A sI s qui à une arête a incidente à s fait correspondre l'unique entier i[1,k] tel que s=v i et ( a=e i ou a=e i+1) vérifie

f s 1(i)={{e i,e i+1} si i<k {e k,e 1} si i=k.

On déduit alors du principe des bergers que d(s)=A s=2I s est pair.
Réciproquement, supposons que G est connexe et que tous les sommets de G sont de degré pair. Considérons une chaîne simple de longueur k maximale γ=(v 0,e 1,v 1,,e k,v k). Nous allons montrer que gamma est un cycle eulérien.
Supposons d'abord que gamma ne soit pas fermée, c'est-à-dire que v kv 0. Posons s=v k et définissons A s l'ensemble des arêtes incidentes à s visitées par gamma, I s et f s comme ci-dessus. On voit que f s 1(k)={e k} est un singleton et f s 1(i) vaut 2 pour i<k. On en déduit que A s est impair. Comme s est de degré pair, il existe une arête a incidente à s=v k qui n'est pas visitée par gamma et γa est une k+1-chaîne simple, une contradiction. On a donc montré que gamma est un cycle.
Supposons maintenant qu'il existe une arête a non visitée par gamma, et posons {u,v}=ϕ(a). Comme G est connexe, il existe une chaîne

δ=(w 0,f 1,,f l,w l)

d'origine w 0=v 0 et extrémité w l=u. Posons f l+1=a et w l+1=v. Notons i le plus petit élément de [1,l+1] tel que f i ne soit pas visité par gamma. Il est clair que w i1 est visité par gamma. Il existe donc j[0,k] tel que v j=w i1. On voit que

(v j,,v k=v 0,,v j=w i1,f i,w i)

est une k+1-chaîne simple, une contradiction.
Supposons enfin qu'il existe un sommet s non visité par gamma. Comme G est connexe, il existe une arête e incidente à s, et cette arête n'est pas visitée par gamma, ce qui est impossible comme on vient de le voir.

Corollaire

Soit G un multigraphe d'ordre au moins 2. Le multigraphe G est semi-eulérien si et seulement si il est connexe et le nombre de ses sommets de degré impair est 0 ou 2.

Démonstration
Si gamma est une chaîne eulérienne de G=(S,A) dont les extrémités sont u et v, considérons le graphe G obtenu en ajoutant à G une arête e d'extrémités u et v. La chaîne γe est un cycle eulérien de G. On en déduit que les degrés de tous les sommets de G (autres que u et v si uv) sont pairs. La connexité de G est évidente exactement comme dans la démonstration du théorème.
Réciproquement, si G a deux sommets distincts de degré impair, u et v, le graphe G défini comme ci-dessus a tous ses sommets de degré pair. Si G est connexe, G l'est aussi et on peut appliquer le théorème à G. Si gamma est un cycle eulérien de G, il visite forcément e et, en retirant e de gamma, on obtient une chaîne eulérienne de G.

III-4 Graphes hamiltoniens

GraphesIII Chaînes et cycles → 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 n1. Un graphe hamiltonien est un multigraphe qui admet un cycle hamiltonien.

Proposition

Les graphes simples C n et K n sont hamiltoniens si et seulement si n3.

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

Théorème

Si G=(S,A) est un graphe simple d'ordre n3 tel que pour toute paire (u,v) de sommets non voisins, on a d(u)+d(v)n, alors G est hamiltonien.

Démonstration
Considérons dans G une chaîne élémentaire de longueur maximale γ=(v 0,,v k). On voit facilement que 1<k<n et que les voisins de v 0 et ceux de v k sont tous visités par gamma. Deux cas se présentent: Dans tous les cas, delta est un cycle élémentaire de longueur k+1, que nous réécrivons δ=(w 0,,w k+1), avec w k+1=w 0. Nous allons montrer que delta est un cycle hamiltonien.
Soit s un sommet qui n'est pas visité par delta. S'il est voisin d'un des w i, alors (s,w i,,w k,w 0,,w i1) est une chaîne élémentaire de longueur k+1, une contradiction. On en déduit que les voisins de s ne rencontrent pas les k+1 sommets visités par delta, donc d(s)nk1. De même, les voisins de w 0 sont parmi les k sommets visités par delta autres que w 0, et d(w 0)k. On a donc d(s)+d(w 0)<n, ce qui mène à une contradiction avec le fait que s et w 0 ne sont pas voisins.

Corollaire

Si G est un graphe simple d'ordre n3 tel que δ(G)n2, alors G est hamiltonien.

IV Arbres

Graphes → 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

GraphesIV Arbres → 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

Si G=(S,A) est une forêt, et si A n'est pas vide, alors il y a au moins deux sommets pendants dans G.

Démonstration
On rappelle que G est un graphe simple. Soit

γ=(v 0,v 1,,v k)

une chaîne élémentaire de longueur k maximale. Comme A n'est pas vide, il y a au moins une arête, donc k>0. Le seul voisin de v 0 est v 1. En effet, si u est un autre voisin de v 0, soit u est l'un des v i, avec i>1 et (v 0,v 1,,v i,u) est un cycle, une contradiction, soit non, auquel cas (u,v 0,,v k) est une une chaîne élémentaire de longueur k+1, encore une contradiction. On en déduit d(v 0)=1, et de même d(v k)=1.

Corollaire

Si G=(S,A) est un arbre d'ordre S=n, il y a dans A exactement n1 arêtes.

Démonstration
Par récurrence sur n. Pour n=1, il n'y a pas de boucle, donc A= et A=0. Si n>1, il y a au moins deux sommets. Comme G est connexe, il y a au moins une chaîne qui les joint, donc A n'est pas vide. Il y a donc aumoins un sommet pendant s. Soit e l'unique arête adjacente à s. Le graphe G=G{s}=(S{s},A{e}) est un arbre d'ordre n1. On peut lui appliquer l'hypothèse de récurrence. On a donc

m1=A{e}=G{s}1=n2,

donc m=n1.

Proposition

Soit

γ=(u=v 0,e 1,v 1,,v k=v)

et

δ=(u=w 0,f 1,w 1,w l=v)

deux chaînes simples distinctes d'origine u et extrémité v dans un multigraphe G. De la chaîne fermée γδ˜, on peut extraire un cycle.

Démonstration
Par récurrence sur p=k+l. Si p=0, il n'est pas possible que γδ, il n'y a donc rien à démontrer. Supposons la propriété vraie si la somme des longueurs est strictement plus petite que p>0. Si γδ˜ est simple, c'est un cycle. Sinon, il existe une arête visitée deux fois par γδ˜. Comme gamma et delta sont simples, une des visites est dans gamma et l'autre dans δ˜: il existe i[1,k] et j[1,l] tels que e i = f j. Il y a deux possibilités:
  1. v i1=w j1 et v i=w j. On a alors soit (v 0,,v i1)(w 0,,w j1) soit (v i,,v k)(w j,,w l). Dans les deux cas on peut appliquer l'hypothèse de récurrence pour obtenir un cycle extrait de γδ˜.
  2. v i1=w j et v i=w j1. On a alors soit (v 0,,v i)(w 0,,w j1) soit (v i1,,v k)(w j,,w l). Dans les deux cas on peut appliquer l'hypothèse de récurrence pour obtenir un cycle extrait de γδ˜.

Corollaire

Dans un multigraphe G=(S,A), il existe un cycle si et seulement si il existe deux chaînes simples distinctes qui ont même origine et même extrémité.

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

Proposition

Dans un graphe connexe, une arête est un isthme si et seulement si elle n'est visitée par aucun cycle.

Démonstration
Supposons d'abord que e est visité par un cycle. On peut écrire γ=(v 0,e=e 1,v 1,,v k), avec v k=v 0. Soit u et v deux sommets de G. Comme G est connexe, il existe une chaîne simple

δ=(u=w 0,f 1,,w l=v).

Si delta ne visite pas e, on pose δ=δ. Dans le cas contraire, il existe un unique i[1,l] tel que f i=e. On ``remplace e dans delta par le grand arc de gamma'', c'est-à-dire qu'on pose

δ=(u=w 0,,w i1=v 1,,v k=w i,,w l=v)

si w i1=v 1 et w i=v=0, et

δ=(u=w 0,,w i1=v k,e k,v k1,v 1=w i,,w l=v)

si w i1=v 0 et w i=v 1. Il existe dans tous les cas une chaîne δ de G{e}, d'origine u et extrémité v. On en déduit que G{e} est connexe et e n'est pas un isthme. Réciproquement, si e n'est pas un isthme, notons u et v les extrémités de e. Comme G{e} est connexe, il existe une chaîne simple gamma de G{e} d'origine v et extrémité u. La chaîne δ(u,e,v) est fermée et simple: c'est un cycle qui visite e.

Corollaire

Soit G 1=(S 1,A 1) et G 2=(S 2,A 2) deux arbres, composantes connexes distinctes d'une forêt G=(S,A). Soit s 1S 1 et s 2S 2. Posons e={s 1,s 2}. Le graphe simple G=(S,A{e}) est encore une forêt.

En effet, e est un isthme du graphe connexe G=(S 1S 2,A 1A 2{e}). Un cycle de G doit visiter e donc rester dans G, une contradiction.

IV-2 Caractérisation des arbres

GraphesIV Arbres → IV-2 Caractérisation des arbres

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

Théorème

Soit E un K-espace vectoriel de dimension n, et B=(b i) 1im une famille finie d'éléments de E. Les propriétés suivantes sont équivalentes:
  1. B est une base de E.
  2. Pour tout vecteur xE, il existe une famille (λ i) 1im de scalaires telle que i=1 mλ ib i=x et une seule.
  3. B est une famille génératrice de E et pour tout im la famille obtenue en enlevant b i à B ne l'est pas ( B est génératrice minimale).
  4. B est libre et quelle que soit la valeur de b m+1, la famille (b i) 1im+1 ne l'est pas ( B est libre maximale).
  5. B est une famille génératrice de E et m=n.
  6. B est une famille libre et m=n.
Le théorème suivant est tout-à-fait analogue au théorème précédent:

Théorème

Soit G=(S,A) un multigraphe. On note n=S son ordre et m=A le nombre de ses arêtes. Les propriétés suivantes sont équivalentes:
  1. G est un arbre.
  2. Pour tout couple (u,v) de sommets, il existe une chaîne simple d'origine u et extrémité v et une seule.
  3. G est connexe, et toute arête de G est un isthme ( G est connexe minimal).
  4. G est une forêt, et pour toute arête eA, (S,A{e}) admet un cycle ( G est une forêt maximale).
  5. G est connexe et m=n1.
  6. G est une forêt, et m=n1.

Démonstration

IV-3 Arbres couvrants

GraphesIV Arbres → 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 ne change pas le fait que G 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 est donc le même que celui de G. En particulier, si G est connexe, G 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=AA 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

Dans l'algorithme précédent, la boucle interne s'exécute p fois, avec

p=mn+e

n est l'ordre de G, m son nombre d'arêtes, et e son nombre de composantes connexes.

Démonstration
Notons G i=(S i,A i) les e composantes connexes d'une forêt G=(S,A) à n sommets et m arêtes. Chaque G i est un arbre, on a donc A i=S i1. Comme S est réunion disjointe des S i et A réunion disjointe des A i, on a

m=A= i=1 eA i= i=1 e(S i1)= i=1 eS ie=Se=ne.


Si maintenant G=(S,A) est un multigraphe quelconque et qu'on exécute l'algorithme, le résultat est une forêt (S,A) qui a le même nombre n de sommets et le même nombre e de composantes connexes que G. Son nombre d'arêtes est m=mp. Or on vient de montrer que m=ne, d'où le résultat.

IV-4 Théorème de Cayley

GraphesIV Arbres → 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 n3. 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,,b n2) de n2 é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 ni+1 éléments et j ne prend que ni1 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 à n1 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] n2. On a donc prouvé le

Théorème [de Cayley]

Pour tout n1, une n-clique a exactement n n2 arbres couvrants.

document sur les graphes.
: graph, interactive mathematics, interactive math, server side interactivity

The most recent version

Cette page n'est pas dans son apparence habituelle parce que WIMS n'a pas pu reconnaître votre navigateur web.
Afin de tester le navigateur que vous utilisez, veuillez taper le mot wims ici : puis appuyez sur ``Entrer''.

Veuillez noter que les pages WIMS sont générées interactivement; elles ne sont pas des fichiers HTML ordinaires. Elles doivent être utilisées interactivement EN LIGNE. Il est inutile pour vous de les ramasser par un programme robot.