Emergents spontanés d'une analyse praxéologique

II-2. Présentation de la théorie des graphes

Présenter le savoir savant dans un travail de recherche de mastère en didactique des mathématiques est quelque chose d'inhabituel. Car, le rapport institutionnel à l'objet « méthodologie de recherche sur la transposition didactique » nous assujettit à prendre le savoir savant comme « donné consensuel connu de tous» dans la communauté des mathématiciens et celle des enseignants de la discipline. Or, à l'exception du cours polycopié de Mr Faouzi BEN CHARRADA, enseignant au département Informatique de la Faculté des Sciences de Tunis, nous n'avons trouvé aucun autre cours complet ou manuscrit tunisien à qui on peut faire référence. Ce sont ces raisons qui nous ont motivées à échafauder une présentation du savoir savant curriculaire et qui doit, à notre sens, faire l'objet d'une unité de valeur dans les facultés des sciences et dans l'école normale en Tunisie. Nous avons, pour cela, tiré les définitions, propositions de différentes ressources (BERGE, 1967 ; SIGWARD, 2007). Le document (SIGWARD, 2007) mis en ligne nous a été d'un grand secours surtout en ce qui concerne les démonstrations, les exemples et les applications des propositions. Nous avons aussi tiré profit de certains cours mis en ligne sur la Toile, pour la finalisation de certaines démonstrations ainsi que tout ce qui concerne les formulations et la mise en application des deux algorithmes présentés. Les connaissances que nous allons présenter ne forment pas la somme des connaissances sur la théorie des graphes ; car cela aurait nécessité des centaines de pages. Il s'agit, plutôt, des connaissances ayant un lien direct avec les savoirs curriculaires, c'est à dire les savoirs du chapitre « Initiation aux graphes » de troisième année section économie et gestion. Ainsi, nous allons nous limiter aux objets du savoir suivants :

· Définitions d'un graphe et d'un graphe non orienté. Représentation d'un graphe. Modélisation d'une situation par un graphe.

· Quelques types de graphes : graphe planaire, multi graphe, graphe complet, graphe stable et graphe biparti.

· Degré d'un sommet, degré d'un graphe. Lemme des poignées de mains et ses conséquences.

· Graphe partiel et sous graphe. Liste et matrice d'adjacence.

· Chaîne, chaîne simple, chaîne élémentaire et cycle. Graphe connexe. Graphe eulérien et théorème d'Euler.

· Coloration des sommets d'un graphe. Nombre chromatique. Encadrement du nombre chromatique. Algorithme de Walsh et Powell. Arbres et forêts. Graphe pondéré. Algorithme de Moore-Djikstra.

a) Définitions

Définition d'un graphe

Un graphe orienté fini est un couple G = (V, E) défini par :

- l'ensemble fini V = {v₁, v₂, ..., v_n} dont les éléments sont appelés sommets.

- l'ensemble fini E = {e₁, e₂, ..., e_m} est un sous ensemble du produit cartésien. Les éléments de E sont appelés arcs.

Un arc e de l'ensemble E est, donc, défini par un couple de sommets (v_i,v_j) appelés les extrémités de e. v_i s'appelle extrémité initiale qu' on note I(e) et v_j est l'extrémité finale de e, notée T(e) . On dit aussi que ces sommets sont adjacents, ou incidents avec l'arc e, ou encore que l'arc e est incident avec les sommets v_i et v_j. Un sommet qui n'est adjacent à aucun autre est dit isolé. L'arc (v,v) est appelé boucle. On appelle ordre d'un graphe le nombre de sommets de ce graphe.

Représentation graphique d'un graphe

Les graphes, objets de cette théorie, tiennent leur nom du fait qu'on peut les représenter par des dessins (étymologiquement : un graphique est un ensemble de lignes). A chaque sommet de G, on fait correspondre un point distinct du plan et on relie par une courbe simple orientée du sommet initial au sommet final les points correspondant aux extrémités de chaque arc.

Dans ce graphe, on a :

-L'ensemble V des sommets est :

-L'ensemble E des arêtes est :

Dans la représentation ci-contre, on pouvait remplacer chaque flèche par une courbe orientée de l'extrémité initiale vers l'extrémité finale.

Exemple :

A

B

C

F

D

Définition de graphe non orienté

Graphe non orienté

Si le graphe G= (V,E) vérifie la propriété suivante :

(x,y) ; (x,y)E (y,x)E

alors le graphe est dit non orienté.

Dans ce cas, le lien entre les sommets x et y est représenté par une courbe non orientée (afin de ne pas encombrer le graphe par deux flèches) et on l'appelle arête.

Ainsi, les arcs (x,y) et (y,x) donnent l'arête x-y.

Dans la suite, nous allons focaliser le travail sur les graphes non orientés qui sont les objets du programme de la troisième année économie et gestion. Ces graphes non orientés sont dits aussi simples car entre deux sommets il n'existe au maximum une arête. On présentera au paragraphe suivant des graphes non simples (dits multiples).

b) Utilisation des graphes

On utilise un graphe pour modéliser une situation dans laquelle on se propose d'étudier une relation entre des objets d'intérêt. Les deux questions à lesquelles on doit répondre sont : Que doit-on considérer comme sommets ? Quelles sont les arêtes ?

Exemple de situation : Un examen comporte, outre les matières communes, six matières optionnelles : Français, Anglais, Espagnol, Mécanique, Dessin industriel et Informatique. Se présentent à cet examen un groupe de candidats ayant choisi les options F, A et M; un deuxième groupe, les options D et E; un troisième groupe, les options M, I et E; enfin, un dernier groupe, les options A et I. Chaque épreuve occupe une demie- journée et on ne peut pas programmer dans une même demie- journée, des épreuves communes à un même candidat. Quelle est la durée minimale pour organiser les examens de ces options ?

Modélisation :

Il est naturel de prendre comme sommets les matières optionnelles. Les arêtes, quant à elles, relient uniquement les matières choisies par un même groupe. Nous verrons au paragraphe 1-10 comment se résout ce problème. L'idéal est de disposer d'une stratégie sûre pour déterminer dans chaque problème quels sont les sommets et quelles sont les arêtes. Il est, cependant, certain, que le point de départ doit être l'analyse sémantique de la consigne qui devrait déboucher sur un verbe ou autre locution faisant le lien entre des objets. On pourrait, en première lecture penser que ce verbe (ou cette locution) indique les arêtes et que les objets en question sont les sommets. La fonctionnalité du choix des éléments constitutifs du graphe est l'élément déterminant quant à sa pertinence. Dans le tableau suivant on a consigné quelques exemples de situations modélisables par des graphes.

Objet d'intérêt	Lien
	existant	complémentaire
Personnes	Amitié	Pas d'amitié
Personnes	Se saluent	Ne se saluent pas
Personnes	Passent le même examen	Ne passent pas le même examen
Régions	Ont une frontière terrestre commune	N'ont pas une frontière terrestre commune
Pays	Sont en guerre	Ne sont pas en guerre

On appelle graphe complémentaire le graphe ayant les mêmes sommets et qui correspond à la relation complémentaire (ou la négation de la relation).

c) Quelques types de graphes

1- Dans ce graphe, on a :

-L'ensemble V des sommets est :

-L'ensemble E des arêtes est :

Ce graphe est planaire car deux arêtes quelconques ne se rencontrent pas.

Graphes planaires : si on arrive à dessiner le graphe sans qu'aucune arête n'en coupe une autre (les arêtes ne sont pas forcément rectilignes), on dit que le graphe est planaire.

A

B

C

F

D

Les graphes planaires sont utiles, entre autres, pour l'ingénierie des circuits imprimés.

2- Dans ce graphe, on a :

-L'ensemble V des sommets est :

-On a deux arêtes qui relient les sommets A et F.

C'est un multi graphe.

On parle d'ordre de multiplicité d'une arête. L'ordre de multiplicité de l'arête e= A-F est 2, on écrit : m(e)=2.

Dans un graphe simple, toutes les arêtes sont d'ordre de multiplicité au plus égal à 1.

Multi graphes : on peut imaginer des graphes avec une arête qui relie un sommet à lui-même (une boucle), ou plusieurs arêtes reliant les deux mêmes sommets. Dans ce cas, on parle de multi graphe.

B

A

C

F

D

3- Graphe complet : c'est un graphe dont chaque sommet est relié directement à tous les autres sommets.

Dans ce graphe, on a :

-L'ensemble V des sommets est :

-Chaque arête est reliée directement à toutes les autres.

B

A

C

F

D

4- Graphe stable : C'est un graphe dont tous les sommets sont isolés. Autrement dit l'ensemble des arêtes est vide.

4- Graphe biparti : C'est un graphe dont les sommets peuvent être divisés en deux ensembles X et Y, de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet dans Y.

Dans ce graphe biparti, on a :

-L'ensemble X est :

- L'ensemble Y est :

-L'ensemble E des arêtes est :

B

A

C

F

D

Les problèmes d'affectation des personnels aux postes de travail ou aux machines de production sont des exemples de situations modélisables par des graphes bipartis.

d) Degré d'un sommet, degré d'un graphe

Degré d'un sommet : Pour un graphe ou un multi graphe, on appelle degré du sommet v, et on note d(v), le nombre d' arêtes incidentes avec ce sommet. Une boucle sur un sommet est comptée deux fois. Dans un graphe simple, on peut aussi définir le degré d'un sommet comme étant le nombre de ses voisins (la taille de son voisinage).

Degré d'un graphe : Le degré d'un graphe est le degré maximum de tous ses sommets. Dans l'exemple ci-dessus, le degré du graphe est 3.

Dans ce graphe on a :

Sommet	Sommets adjacents	Degré
A	B,C,F	3
B	A,D	2
C	A,D	2
D	C,B	2
F	A	1
H		0

B

A

C

D

H

F

Un graphe dont tous les sommets ont le même degré est dit régulier. Si le degré commun est k, alors on dit que le graphe est k- régulier.

Propositions

Proposition :

Si l'ordre d'un graphe est supérieur ou égal à 2 alors il existe au moins deux sommets différents ayant le même degré.

Preuve : Supposons que tous les sommets sont de degrés différents et posons n l'ordre du graphe. On a, moyennant ré indexation des sommets:

Donc: le degré du sommet S₁ est 0 alors que celui de S_n est n-1. En d'autres termes : le sommet S₁ est isolé et le sommet S_n est relié à tous les autres sommets. Ce qui est absurde. Ainsi, il y a au moins :

- deux personnes qui ont le même nombre d'amis.

- deux personnes qui échangent les politesses avec le même nombre de personnes.

- deux pays qui ont le même nombre de pays limitrophes.

Lemme des poignées de mains :

La somme des degrés des sommets d'un graphe est égale à deux fois le nombre d'arêtes.

Conséquences :

- Si le graphe G =(V,E) est r- régulier alors : r card(V)=2 card(E).

Graphe 3-régulier.

Graphe 2-régulier.

Graphe 1-régulier.

- En conséquence, si un graphe G=(V,E) est 2- régulier alors card(V)= card(E). La réciproque est fausse, car si card(V) = card(E) on ne peut pas conclure que le graphe est 2-régulier. Il peut être non régulier, tout simplement.

- Dans un graphe simple, le nombre de sommets de degrés impairs est pair.

e) Graphe partiel et sous- graphe

Définitions

G=(V,E)

G'=(V,E')

Soit G = (V, E) un graphe. Le graphe G' = (V, E') est un graphe partiel de G, si E' est inclus dans E. Autrement dit, on obtient G' en enlevant une ou plusieurs arêtes au graphe G.

Pour un sous-ensemble de sommets A inclus dans V, le sous- graphe de G induit par A est le graphe G' = (A, E(A)) dont l'ensemble des sommets est A et l'ensemble des arêtes E(A) est formé de toutes les arêtes de G ayant leurs deux extrémités dans A. Autrement dit, on obtient G' en enlevant un ou plusieurs sommets au graphe G, ainsi que toutes les arêtes incidentes à ces sommets. On dit aussi que G' est engendré par A.

G=(V,E)

Sous- graphe de G

Un graphe partiel d'un sous- graphe est un sous- graphe partiel de G.
On appelle clique un sous- graphe complet de G.

Si S est une partie de V. On dit que S est stable si le sous graphe engendré par S ne contient aucune arête.

Un stable S est dit maximal si : S, SU n'est pas stable. Un stable maximal de cardinalité maximum est dit stable maximum.

f) Listes et matrice d'adjacences

Définitions

On peut représenter un graphe en donnant pour chacun de ses sommets la liste des sommets auxquels il est adjacent. On les appelle listes d'adjacences. Exemple :

Sommet	Listes d'adjacences
1	3,4,5
2	3
3	1,2,4
4	1,3,5
5	1,4

3

2

1

5

4

En plus, on peut représenter un graphe par une matrice M=(m_ij) où m_ij appelée matrice d'adjacences. Dans cette matrice, les lignes et les colonnes représentent les sommets du graphe. Un 1 à i^ème ligne et j^ème colonne (m_ij =1) signifie que le sommet i est adjacent au sommet j. Voici la matrice d'adjacences d'un autre graphe:

Graphe :

S₁ S₂

S₃

S₄

La matrice d'adjacence est :

Elle est symétrique

g) Chaîne, chaîne simple, chaîne élémentaire, cycle

Soit G= (V, E) un graphe.

On appelle chaîne toute suite finie de sommets S₀, S₁, ......,S_k tels que les arêtes S₀-S₁, S₁-S₂, ......, S_k-1-S_k soient des arêtes de G. Cette chaîne est notée c= [S₀S₁.........S_k].

o La longueur de cette chaîne est le nombre de ses arêtes. Cette longueur est notée l(c).

o Les sommets S₀ et S_k sont appelés extrémité initiale et finale de la chaîne c. On dit que les sommets S₀ et S_k sont reliés par la chaîne c.

o Une chaîne est dite simple si toutes ses arêtes sont distinctes.

o Une chaîne est dite élémentaire si tous ses sommets sont distincts.

o Une chaîne est dite fermée si ses deux extrémités sont confondues.

o Un cycle est une chaîne simple fermée.

2

1

3

6

5

4

o La chaîne est élémentaire, donc simple. Elle est de longueur 4.

o La chaîne est simple et non élémentaire.

o La chaîne est un cycle.

h) Graphe connexe

Définition

Un graphe est dit connexe si toute paire de sommets est reliée par une chaîne.

La plus petite longueur des chaînes reliant deux sommets est appelée distance de ces deux sommets.

Le diamètre d'un graphe G, noté , est la plus grande distance entre deux sommets quelconque de ce graphe.

Exemple

B

Graphe G connexe, d(A,C)=3, =3.

A

C

D

E

On peut montrer facilement que la relation R dans l'ensemble V des sommets :

(S₁ R S₂) signifie (S₁ et S₂ sont relies par une chaîne)

est une relation symétrique et transitive. L'ensemble des sommets reliés entre eux engendre un sous graphe qui s'appelle composante connexe. Ainsi, un graphe connexe est un graphe qui a une seule composante connexe.

Un point d'articulation est un sommet dont la suppression augmente le nombre de composantes connexes. Un isthme est une arête dont la suppression augmente le nombre de composantes connexes. Dans le graphe connexe G ci-dessus, Le point B est une articulation et l'arête B-D est un isthme.

i) Graphe eulérien

Définitions

On dit qu'un graphe est eulérien s'il est possible de trouver un cycle passant une et une seule fois par toutes les arêtes. Ce cycle est dit eulérien.

On dit qu'un graphe est semi- eulérien s'il est possible de trouver une chaîne passant une et une seule fois par toutes les arêtes. Cette chaîne est dite eulérienne.

Plus simplement, on peut dire qu'un graphe est eulérien (ou semi- eulérien) s'il est possible de dessiner le graphe sans lever le crayon (et sans passer deux fois sur le même trait).

Théorème d'Euler:

Un graphe connexe est eulérien si et seulement si tous ses sommets sont de degrés pairs.

Un graphe est semi- eulérien si et seulement si tous ses sommets sont de degrés pairs ou bien il a uniquement deux de ses sommets de degrés impairs.

Preuve de la première partie :

La condition est nécessaire : en effet, si c est un cycle eulérien de G et S un sommet de E, à chaque fois qu'on arrive à S par une arête on en repart par une arête distincte de la première puisque c est un cycle. Donc S est paire.

La condition est suffisante : en effet, Si S₀ est un sommet de V, comme son degré est pair, on peut choisir une autre arête incidente à S₀ et de deuxième extrémité S₁ lequel est adjacent à un autre sommet S₂ (puisque les sommets sont de degrés pairs) et ainsi de suite jusqu'à revenir au sommet S₀. On obtient, ainsi, un cycle c=.

Si ce cycle contient toutes les arêtes du graphe alors le graphe est eulérien. Sinon, il existe une arête n'appartenant pas au cycle précédent d'extrémité un des sommets S_k de ce cycle. On continue le procédé précédent jusqu'à revenir au sommet S_k pour obtenir un cycle c' ne contenant aucune des arêtes du cycle c. La concaténation des deux cycles c et c' donne un cycle c''. Si c'' contient toutes les arêtes du graphe, on a terminé, sinon on continue le processus jusqu'à épuisement de toutes les arêtes puisque le graphe est fini.

S₁

S₀

Cycle c'

Cycle c

S_k

A titre d'exemple, le graphe G (à gauche ci-dessous) est eulérien puisque tous les sommets sont de degrés pairs. Par contre, le graphe G' (à droite ci-dessous) n'est pas eulérien car on a au moins un sommet de degré impair.

Graphe G' :

Graphe G :

La démonstration précédente est une technique pour déterminer un cycle eulérien s'il existe.

De la même manière, on peut prouver la seconde partie du théorème.

Le graphe G' ci-dessus est semi- eulérien car il a deux sommets de degrés impairs et il n'est pas difficile de déterminer dans ce graphe une chaîne eulérienne dont les extrémités sont ces deux sommets de degrés impairs.

j) Coloration des sommets

Définition de la coloration

Soit G = (V, E) un graphe. Une coloration de ce graphe est une mise en couleur de tous ses sommets de sorte que deux sommets adjacents n'ont pas la même couleur.

Comme le montre le graphe ci-dessous, un même graphe peut avoir plusieurs colorations.

B

V :vert , B :bleu , R :rouge

V :vert , B :bleu

B

V

R

V

V

V

V

B

B

On peut accorder à chaque sommet une couleur distincte des autres, ce qui montre que la coloration d'un graphe est toujours possible. Il serait intéressant de pouvoir le faire avec le minimum de couleurs.

Définition du nombre chromatique

Le nombre chromatique d'un graphe G, noté ?(G), est le plus petit nombre de couleurs nécessaires à sa coloration. Un sous-ensemble S de V est un stable s'il ne comprend que des sommets non adjacents deux à deux. Une coloration avec k couleurs est donc une partition de l'ensemble des sommets en k stables.

Exemples

Si le graphe G est un cycle alors ?(G)=2 s'il est de longueur paire et ?(G)=3 sinon.

1- Si G est stable d'ordre non nul alors ?(G)=1.

2- Si G est biparti alors ?(G)=2.

Encadrement du nombre chromatique

Majoration

?(G) r + 1, où r est le plus grand degré de ses sommets.

Preuve :

Soit un graphe et r le degré maximum de ses sommets. Donnons-nous une palette de (r + 1) couleurs. Pour chaque sommet du graphe on peut tenir le raisonnement suivant : ce sommet est adjacent à r sommets au plus, et le nombre de couleurs déjà utilisées pour colorer ces sommets est donc inférieur ou égal à r. Il reste donc au moins une couleur non utilisée dans la palette, avec laquelle nous pouvons colorer notre sommet.

Minoration

Le nombre chromatique d'un graphe est supérieur ou égal à celui de chacun de ses sous- graphes.

Preuve :Ce résultat découle de la définition même du nombre chromatique. L'algorithme suivant est couramment utilisé pour obtenir une assez bonne coloration d'un graphe, c'est-à-dire une coloration n'utilisant pas un trop grand nombre de couleurs. Cependant il n'assure pas que le nombre de couleurs utilisé soit égal au nombre chromatique du graphe.

Algorithme de coloration de Welsh et Powell

Etape 1
Classer les sommets du graphe dans l'ordre décroissant de leur degré, et attribuer à chacun des sommets son numéro d'ordre dans la liste obtenue.
Etape 2
En parcourant la liste dans l'ordre, attribuer une couleur non encore utilisée au premier sommet non encore coloré, et attribuer cette même couleur à chaque sommet non encore coloré et non adjacent à un sommet de cette couleur.
Etape 3
S'il reste des sommets non colorés dans le graphe, revenir à l'étape 2. Sinon, la coloration est terminée.

La coloration d'un graphe est une technique efficace pour résoudre des problèmes d'incompatibilité tels que : deux personnes qui ne doivent pas figurer dans la même équipe, deux matières ne doivent pas être programmées à la même tranche de temps.

Exemple

Un formateur d'un groupe de sept étudiants A, B, C, D, E, F et H en mastère de didactique de mathématiques se propose constituer le minimum de groupes de travail sur des sujets de transposition didactique.

Or, il s'avère que :

- L'étudiant A refuse de collaborer avec les étudiants B et C.

- L'étudiant B refuse de collaborer avec les étudiants A, C, D et E.

- L'étudiant C refuse de collaborer avec les étudiants A, D, F et B.

- L'étudiant D refuse de collaborer avec les étudiants C, B, F et H.

- L'étudiant E refuse de collaborer avec les étudiants B, F et H.

- L'étudiant F refuse de collaborer avec les étudiants D, C et H.

- L'étudiant H refuse de collaborer avec les étudiants D, F et E.

Comment doit procéder ce formateur pour résoudre son problème ?

D'abord, on peut représenter cette situation par le graphe G= (V,E) où :

- V =

- La liste d'adjacence :

- A : B, C

- B : A, C, D, E

- C : A, D, F, B

- D : C, B, F, H

- E : B, F, H

- F : D, C, H

- H : D, F, E

E

B

D

H

A

C

F

En utilisant l'algorithme de Walsh et Powell, on obtient le tableau suivant :

Sommet	A	B	C	D	E	F	H
Degré	2	4	4	4	3	4	3
Ordre	7	1	2	3	5	4	6
Couleur	C3	C1	C2	C3	C2	C1	C4

Si nous procédons à un autre classement :

Sommet	A	B	C	D	E	F	H
Degré	2	4	4	4	3	4	3
Ordre	7	2	3	1	5	4	6
Couleur	C1	C2	C3	C1	C1	C2	C3

Ainsi, le nombre de couleur des sommets de ce graphe est 3. Le nombre chromatique étant supérieur ou égal à celui de ses sous graphes complets, on peut en déduire que ce nombre est égal à 3. Le formateur peut, en toute quiétude annoncer les groupes suivants :

o Groupe1 : A, D, E

o Groupe2 : B, F

o Groupe3 : C, H

Cet exemple montre que la procédure donnée l'algorithme de Welsh et Powell dépend du classement choisis pour les sommets de même ordre et donne parfois un nombre de couleurs supérieur au nombre chromatique. Remarquons qu'on pouvait trouver directement le nombre chromatique par la recherche du minimum de stables. On a trois stables: , et .

Exemple intéressant

La coloration du graphe suivant par l'algorithme de Welsh et Powell ne donne jamais le nombre chromatique.

En effet, l'algorithme de Welsh et Powell donne toujours 3 couleurs alors que le nombre chromatique est 2.

k) Arbres et forêts - Algorithme de plus court chemin

Un arbre est un graphe simple connexe et qui ne contient aucun cycle. Une forêt est un graphe simple dont les composantes connexes sont des arbres.

Un arbre :

Une forêt :

Proposition :

· Si G=(V,E) est un arbre alors :

· Toute arête d'un arbre est un isthme.

· Si Card(V)=n alors Card(E)=n-1.

· Si on ajoute une arête à G alors on obtient un graphe G' qui ne contient qu'un seul cycle.

· Le nombre chromatique de G est égal à 2.

· G contient au moins deux sommets d'ordre 1 (on dit pendants).

Conséquence :

Si G=(V,E) est une forêt qui contient p composantes connexes alors : Card(E)= Card(V)-p.

Graphe pondéré (ou valué) :

Un graphe G= (V,E) est dit pondéré s'il est muni d'une application :

(appelé poids de l'arc )

Si G' est un sous graphe de G alors :est appelé poids de G'.

La longueur d'un chemin C est la somme des poids des arêtes qui le constituent. On le note l(C).

Exemple

L'application p est définie par :

p(B-C)=2; p(D-C)=-1;

p(A-D)=4; p(H-F)=1;

p(H-K)=3; p(K-F)=5.

l(A-D-C-B)=4-1+2=5.

B A

2

C F

-1 4 1

5 H

D 3

K

On peut observer :

· Qu'il existe un chemin entre le sommet A et chacun des sommets : B, C et D.

· Qu'il n'existe pas de chemin entre le sommet A et les sommets : F, H et K.

· Le plus court chemin entre :

- Les sommets F et K est : F-H-K. Il est de longueur 4

- Les sommets A et C n'existe pas. Car, on peut suivre le chemin A-D-C qui est de longueur 3, ou bien A-D-C-D-C qui est de longueur 1, etc.

Dans la suite, on va supposer que tous les poids sont positifs ou nuls.

Proposition

Tout sous chemin d'un plus court chemin est un plus court chemin.

Preuve : En effet, Supposons que : S₁-S₂-.........-S_k-......S_p-......-S_m est le plus court chemin entre les sommets S₁ et S_m. avec k<p<m.

S₁ S₂ S₃ S_k

S_p S_m

Alors le sous- chemin entre les sommets S_k et S_p est le plus court ; car, sinon, on aurait un autre chemin plus court entre S₁ et S_m utilisant un autre détour.

L'algorithme suivant permet de déterminer le plus court chemin (s'il existe) entre un sommet s choisi et chacun des autres sommets d'un graphe G=(V,E). Le résultat est une arborescence.

Algorithme de Moore- Dijkstra

Initialisation :

Itérations : Tant que faire :

On détermine les sommets tels que l'arc qui relie soit un élément de E. On prendra : .

On garde l'arête qui a permis d'avoir ce minimum. On choisit un nouveau sommet tel que et on posera : .

Nous allons illustrer le mécanisme de cet algorithme à l'aide d'un exemple. Remarquons que l'idée centrale de cet algorithme réside dans le fait que le plus court chemin entre deux sommets est la concaténation des plus courts chemins intermédiaires.

Exemple :

Considérons le graphe pondéré suivant :

A 4 B

2 4

S₀ 1 3 7 C

4

1

5 D

F

On se propose de déterminer, à l'aide de cet algorithme, les plus courts chemins du sommet S à tous les autres sommets.

S0	A	B	C	D	F	xp	S
0	2, S0 2, F 2	4, F 4, F 4	8, B 8	6, F 6, F 6, F 6, F 6	1, S0 1	S0 F A B C D	S0 S0,F S0,F,A S0,F,A,B S0,F,A,B,C S0,F,A,B,C,D

Ainsi, le plus court chemin de S₀ au sommet :

ü A est de longueur 2

ü B est de longueur 4

ü C est de longueur 8 ; il s'agit du chemin : S₀-F-B-C.

ü D est de longueur 6

ü F est de longueur 1

L'arborescence qui permet de suivre ces chemins est :

A 4 B

2 4

S₀ 1 3 7 C

4

1

5 D

F

l) Graphes isomorphes

Considérons le graphe G= (V,E) défini par : V= et l'ensemble des arêtes E= . On peut présenter ce graphe de plusieurs manières. Par exemple :

D

F

B

A

F

A

D

C

B

C

Ces deux graphes représentent la même situation. On dit qu'ils sont isomorphes.

En ré -indexant^1(*) la représentation graphique donnée à droite on obtient deux graphes qui correspondent à une même situation (avec des noms de sommets différents) et sont donc isomorphes.

P

S

T

R

Q

A

D

B

C

F

D'une manière générale, on dit que deux graphes G=(V,E) et G'=(V',E') sont isomorphes s'il existe deux bijections : et de sorte que si alors et .

Ainsi, si deux graphes sont isomorphes alors :

· Ils ont le même nombre de sommets.

· Ils ont le même nombre d'arêtes.

· Ils ont même nombre de sommets de degré donné.

· Ils ont le même nombre de composantes connexes.

· Ils ont le même nombre de sous graphes complets d'ordre donné.

· Si l'un est eulérien l'autre l'est aussi.

· Etc.

En conséquence, il est souvent plus aisé de montrer que deux graphes ne sont pas isomorphes que de prouver qu'ils le sont.

Exemples :

o Les deux graphes suivants ne sont pas isomorphes car ils n'ont pas le même nombre de sommets.

o Les deux graphes suivants ont le même nombre de sommets et le même nombre d'arêtes. Ils ne sont pas isomorphes pour les raisons suivantes (une suffit !) :

- L'un (celui de gauche) a un sommet de degré 3 et l'autre n'en a pas.

- L'un un sous graphe complet d'ordre 3 et l'autre n'en a pas.

- L'un est semi- eulérien non eulérien et l'autre est eulérien.

m) Comparaison des terminologies sur les graphes orientés et les graphes non orientés

Les graphes orientés présentent certaines particularités que les graphes non orientés n'ont pas. Par exemple, si l'arc (A,B) peut relier le sommet A au sommet B on ne peut pas affirmer autant sur le lien de B vers A comme c'est le cas des graphes non orientés. Cette particularité doit se traduire dans la terminologie afin de pouvoir situer le discours. On sait déjà qu'au terme arc des graphes orientés correspond le terme arête dans les graphes non orientés. Dans le tableau suivant on a consigné les correspondances terminologiques entre le concept orienté et le concept non orienté.

Concept non orienté	Concept orienté
Arête	arc
Chaîne	Chemin
cycle	Circuit
Connexité	Forte connexité^2(*)

A signaler que la plupart des propositions présentées sur les graphes non orientés sont applicables aux graphes orientés, notamment les deux algorithmes de coloration et de Moore- Dijkstra.

* ¹ Ré -indexer un graphe signifie affecter aux sommets d'autres étiquettes.

* ² Un graphe orienté est dit fortement connexe si pour tout couple de sommets x et y il existe un chemin de x vers y (et donc un chemin de y vers x).