COURS DE THÉORIE DES GRAPHES



THÉORIE DES GRAPHES

1. Matrice d'adjacence

2. Catégories

L'histoire de la théorie des graphes (ou des "complexes cellulaires") débute peut-être avec les travaux d'Euler au 18ème siècle et trouve son origine dans l'étude de certains problèmes, tels que celui des ponts de Königsberg (les habitants de Königsberg se demandaient s'il était possible, en partant d'un quartier quelconque de la ville, de traverser tous les ponts sans passer deux fois par le même et de revenir à leur point de départ), la marche du cavalier sur l'échiquier ou le problème de coloriage de cartes et du plus court trajet entre deux points.

La théorie des graphes s'est alors développée dans diverses disciplines telles que la chimie (isomères), la biologie, les sciences sociales (réseaux de transports), gestion de projets (C.P.M.), informatique (topologie des réseaux, complexité algorithmique. protocoles de transferts), la physique quantique, etc.. Depuis le début du 20ème siècle, elle constitue une branche à part entière des mathématiques, grâce aux travaux de König, Menger, Cayley puis de Berge et d'Erdös.

De manière générale, un graphe permet de représenter la structure, les connexions d'un ensemble complexe en exprimant les relations entre ses éléments : réseau de communication, réseaux routiers, interaction de diverses espèces animales, circuits électriques, ...

Les graphes constituent donc une méthode de pensée qui permet de modéliser une grande variété de problèmes en se ramenant à l'étude de sommets et d'arcs.

Les derniers travaux en théorie des graphes sont souvent effectués par des informaticiens, du fait de l'importance qu'y revêt l'aspect algorithmique (voir le début du chapitre de Méthodes Numériques pour un petit exemple).

Effectivement, il s'agit essentiellement de modéliser des problèmes. Nous exprimons le problème en termes de graphes et ensuite il devient un problème de la théorie des graphes que nous savons le plus souvent résoudre car il rentre dans une catégorie de problèmes connus.

Les solutions de problèmes de graphes peuvent être faciles et efficaces (car le temps nécessaires pour les traiter informatiquement est raisonnable car il dépend polynomialement du nombre de sommets du graphe) ou difficiles (car le temps de traitement est exponentiel) dans quel cas nous utilisons une heuristique, c'est-à-dire un processus de recherche d'une solution (pas forcément la meilleure).

La théorie des graphes connaît un assez grand engouement ces 30 dernières, peut-être est-ce parce qu'elle ne nécessite pas dans ses concepts élémentaires de bagage mathématique considérable. Effectivement, il suffit d'avoir parcouru les chapitres de Probabilités, de Théorie Des Ensembles et d'Algèbre Linéaire ainsi que de Topologie présentés sur le site pour déjà se sentir à l'aise avec les différentes définitions.

Nous allons introduire le vocabulaire de base de la théorie des graphes. Les termes employés sont ceux du langage commun de la géométrie euclidienne (et malheureusement ils sont aussi en grand nombre...).

Définitions:

D1. Un "graphe" (ou "polygraphe") G est un couple equation constitué d'un ensemble X non vide et fini (les sommets), et d'un ensemble E (les arêtes) de paires d'éléments de X ou autrement dit (...) d'une partie du produit cartésien equation (cf. chapitre de Théorie Des Ensembles).

Remarque: Un graphe est souvent noté en français G=(S,A) où le S est la première lettre de Sommet et A la première lettre de Arêtes.

L'ensemble des sommets est noté G(X) et l'ensemble des arêtes G(E).

Un graphe est aussi dit "graphe planaire" quand nous pouvons le représenter dans un plan sans qu'il y ait intersection d'arêtes.

Maintenant, montrons que si F est le nombre de faces d'un graphe planaire (on compte aussi la face extérieure infinie), A son nombre d'arêtes et S sont nombre de sommets nous avons alors ::

equation   (27.1)

qui est la relation connue sous le nom de "formule d'Euler" ou "théorème de Descartes-Euler" (démonstration après l'exemple) et qui nous sera utile plusieurs fois sur ce site (dans le présente chapitre et lors de notre étude des polyèdres dans le chapitre sur les Formes Géométriques).

exempleExemple:

Un graphe à 2 faces (la face en gris claire est la face extérieure infinie), 4 sommets et 4 arêtes :

equation
  (27.2)

Démonstration:

Nous démontrons cette formule en effectuant une récurrence sur A-S :

D'abord, la formule est vraie pour equation car, dans ce cas, le graphe est un arbre donc il n'a qu'une seule face, donc equation, donc equation.

Puis, prenons un graphe connexe (voir définition plus loin) contenant au moins un cycle G (la figure ci-dessous est un exemple de graphe avec 3 cycles) :

equation
  (27.3)

Si nous retirons une arête e à ce cycle, nous devrions pouvoir alors par récurrence appliquer au graphe equation la même formule si elle est juste. Effectivement le graphe amputé de l'arête aura F faces, S sommets et A arrêtes et donc la formule :

F - A + S = 2   (27.4)

si nous lui remettons l'arrête alors nous écrirons  :

(F + 1) - (A + 1) + S = F - A + S =2   (27.5)

equationC.Q.F.D.

D2. Les éléments de X sont donc les "sommets" du graphe G, ceux de E sont les "arêtes" du graphe G (effectivement, une arrête est composée de deux sommets, d'où l'allusion aux paires d'éléments dans la définition précédente).

Remarque: Dans un "multigraphe", les deux sommets d'une arête peuvent être identiques (boucle) et deux arêtes distinctes peuvent avoir leurs deux extrémités communes. Un multigraphe ne satisfait plus alors la définition D1.

D3. Soit equation une arête de G, nous disons que les sommets x, y qui sont les "extrémités" de l'arête de G, sont "adjacents" ou "voisins" dans le graphe G, et que l'arête e est "incidente" aux sommets x, y.

D4. Si deux arêtes e et e' ont une extrémité en commun, nous dirons qu'elles sont "incidentes", autrement, qu'elles sont indépendantes.

Remarque: Si e est une arête de G, nous noterons equation le sous-graphe de equation. Si X ' est un sous-ensemble de X, nous noterons equation le graphe G privé des sommets de X '.

D5. Ce que nommons "ordre" du graphe est le nombre de ses sommets.

Soit G un graphe d'ordre n (donc le nombre de sommets), l'ensemble E doit être par définition choisi comme sous-ensemble de l'ensemble des paires d'éléments de l'ensemble X, donc d'un ensemble (trivial - puisque un sommet ne peut pas être voisin à lui-même) de cardinal :

equation   (27.6)

En conséquence, il existe (voir le chapitre de Probabilités : arrangements de n éléments non-distinguables par couple de deux) :

equation   (27.7)

choix possibles pour E et donc autant de graphes admettant X pour ensemble de sommets. Certains de ces graphes, sont par le fait que nous considérons leurs sommets comme non-distinguables  "automorphes" (voir la définition de ce terme un peu plus loin dans ce chapitre). 

Le résultat obtenu signifie qu'il existe environ 2 millions de graphes à 7 sommets, et quelques equation graphes à 27 sommets - chiffre à comparer avec le fait que nous estimons à moins de equation le nombre d'atomes dans l'Univers (...).

D6. Le "voisinage" d'un sommet est l'ensemble de ses voisins.

D7. Nous appelons "degré" d'un sommet s et notons D(s), le nombre de ses voisins, qui est également le nombre d'arêtes qui lui sont incidentes (un sommet de degré zéro étant appelé un "sommet isolé").

Remarque: Un sommet de degré 1 est appelé "sommet pendant".

Propriétés (sans démonstration) : 

P1. La somme des degrés des sommets est égale au double du nombre d'arêtes.

P2. Dans un graphe, le nombre de sommets de degré impair est toujours pair.

P3. Un graph ayant tous ses sommets de degré pair est d'ordre impair (excepté pour le sommet isolé).

Remarque: Un "graphe régulier" est un graphe dont tous les sommets ont même degré k. Nous disons alors que le graphe est "k-régulier".

D8. Nous dirons qu'un graphe equationest un "sous-graphe" ou "sous-graphe induit" d'un graphe equation lorsque equation et equation.

D9. Un "sous-graphe recouvrant" d'un graphe equation est un sous-graphe equation, c'est-à-dire un sous-graphe dont sont sommets tous les sommets de G et dont les arêtes sont dans E'.

D10. Pour un graphe d'ordre n, il existe deux cas extrêmes pour l'ensemble de ses arêtes : soit le graphe n'a aucune arête, soit toutes les arêtes possibles pouvant relier les sommets deux à deux sont présentes. Dans ce dernier cas le graphe est dit appelé un "graphe complet".

exempleExemple:

Voici quelques graphs complets pour lesquels nous avons bien :

equation   (27.8)

arêtes. Nous remarquons que les quatre premiers graphs sont planaires (effectivement remarquez comment il est possible de transformer le quatrième K4 de manière à ce qu'il n'y ait plus d'intersections). Le cinquième graph K5 est non-planaire (nous ne pouvons trouver des déplacements évitant les croisements).

equation
  (27.9)

Remarque: Un graphe complet est donc un graphe où chaque sommet est relié à tous les autres. Le graphe complet d'ordre n est noté equation. Dans ce graphe chaque sommet est de degré n-1 ("l'étoile de David" n'est complète que si l'on joint tous les sommets entre eux - ainsi nous perdons la géométrie de l'étoile mais obtenons un graphe equation).

D11. Un "graphe stable" est sous-graphe sans arête et une "clique" un sous-graphe complet.

D12. Dans un graphe il est naturel de vouloir se déplacer de sommet en sommet en suivant les arêtes. Une telle marche passant par n sommets est appelée une "chaîne" equation ou un "chemin" :

Un chemin ("path" en anglais) est une liste equation de sommets telle qu'il existe dans le graphe une arête entre chaque paire de sommets successifs : equation. La longueur du chemin correspond au nombre d'arêtes parcourus : k-1.

Un chemin est dit "chemin simple" si chaque arête du chemin est empruntée une seule fois. Voici par exemple une chemin simple avec 5 sommets:

equation
  (27.10)

Ainsi, nous définissons aussi un "cycle" :

equation   (27.11)

comme étant un chemin simple finissant à son point de départ tel queequation. Ainsi, s'il existe deux chaînes distinctes reliant deux sommets x et y d'un graphe G, alors ce graphe admet un cycle.

D13. Un "cycle simple" est un cycle dont toutes les arêtes sont différentes.

D14. Un "graphe orienté" est un graphe dont les arêtes ont une direction et un sens et sont dès lors appelées des "arcs" (donc à l'opposé du graph non-orienté).

Remarques:

R1. Les termes de "chemin" et de "circuit" s'emploient en propre pour les graphes orientés. Pour les graphes non orientés que nous manipulons principalement ici, nous parlons de "chaîne" et de "cycle". Cependant la définition formelle est exactement la même dans les deux cas, seule change la structure (graphe orienté ou non) sur laquelle ils sont définis.

R2. Un graphe non orienté n'est qu'un graphe orienté symétrique. Effectivement, si un arc relie le sommet a au sommet b et un autre arc relie le somme b au sommet a, nous ne traçons alors qu'un trait entre a et b que nous appelons... une arête.

D15. Un chemin equation est dit "chemin élémentaire" si chacun des sommets du parcours est visité une seule fois : equation. Un chemin élémentaire est donc un chemin simple et sans cycle.

Propriétés : Dans un graphe G d'ordre n :

P1. Tout chemin élémentaire est de longueur au plus n-1. Effectivement, Un chemin élémentaire visitant au plus 1 fois chaque sommet du graphe, sa longueur (nombre d'arêtes) ne peut effectivement excéder n-1.

P2. Le nombre de chemins élémentaires dans le graphe est fini. Effectivement, le nombre de chemins de longueur  equation est au plus la combinatoire du choix d'une suite de k+1 sommets distinguables parmi n. Il y en a donc (cf. chapitre de Probabilités):

equation   (27.12)

Les chemins élémentaires sont la restriction naturelle que nous recherchons à la notion de chemin. La question qui se pose est de savoir si nous perdons quelque chose en ne considérant que les chemins élémentaires dans un graphe : peut-on toujours remplacer un chemin du graphe par un chemin élémentaire?

Le "lemme de König" répond affirmativement à cette question : de tout chemin nous pouvons extraire un sous-chemin élémentaire.

L1. S'il existe un chemin entre 2 sommet x et y, alors il existe un chemin élémentaire entre x et y.

Démonstration:

L'idée de la preuve est de choisir un chemin particulier entre x et y et de montrer qu'il est élémentaire. Quel chemin choisir? Si un chemin comporte un circuit, ce circuit est un détour sur la route menant de x et y. Un bon candidat à être un chemin élémentaire semble donc être un plus court chemin.

Parmi tous les chemins reliant x à y, choisissons ainsi un chemin equation comportant le moins d'arêtes. Supposons par l'absurde que p n'est pas élémentaire. Il existe alors un sommet z apparaissant au moins 2 fois le long du chemin p. Soient i, j les 2 premiers indices tels que equation et equation :

equation   (27.13)

Pour obtenir une contradiction, il suffit de supprimer le cycle entre equation et equation. Alors :

equation   (27.14)

est un chemin, reliant x à y. Sa longueur est strictement inférieure à celle de p', ce qui contredit notre choix de p' comme étant un plus court chemin.

D16. Un graphe est dit "graphe connexe" si et seulement si, il existe au moins un chemin entre chaque paire de sommets (le chemin n'étant donc implicitement pas nécessairement direct - pouvant passer par un ou plusieurs sommets intermédiaires). S'il existe un chemin entre chaque paire de sommets, nous disons que nous avons un "graphe fortement connexe".

Remarques: Que se passe-t-il si le graphe G n'est pas connexe? Il apparaît alors comme un ensemble de graphes connexes mis les uns à coté des autres. Chacun de ces graphes est un sous-graphe particulier de G, appelé "composante connexe". Il est souvent utile de se placer sur les composantes connexes d'un graphe pour se ramener au cas d'un graphe connexe.

D17. Un "arbre" ou "arbre couvrant" est un graphe connexe, sans cycle simple (acyclique) et sans boucles (il s'agit donc d'une forêt connexe). Dans un arbre le nombre d'arrêtes est égal au nombre de sommets - 1.

D18. Un "arbre valué" ou "graphe valué" est un arbre (respectivement un graphe) où les arêtes ont des valeurs (pondérations) positives. La somme de toutes les valeurs qui sont sur les arêtes parcourues d'un arbre est appelé alors le "coût d'un arbre valué" (respectivement "coût d'un graphe valué").

Remarque: Les arbres valués sont utilisés dans de très nombreux domaines. Citons les réseaux informatiques dans lesquels on cherche à optimiser le nombre d'interconnexions entre machines pour éviter les redondances d'envois de paquets de données ou la gestion de projets (voir l'exemple ci-dessous).

exempleExemple:

Un excellent exemple pratique de graphe connexe valué et orienté (abrégé sous le terme de "digraphe") est celui utilisé en gestion de projets pour le calcul du chemin critique. Il s'agit d'un graphe qui représente les dépendances entre n tâches intermédiaires nécessaires pour réaliser un projet, communément appelé "diagramme de Gantt" ou en encore "graphe d'ordonnancement". La durée (poids) de chaque tâche est la valeurs des arcs incidents extérieurement au noeud correspondant. Les arcs représentent les contraintes d'enchaînement des tâches. Nous ajoutons toujours un noeud (dans le monde de la gestion de projets on parle plutôt de jalon...) initial et un noeud final. Le premier est relié par un arc de valeur nulle à tous les noeuds sans prédécesseurs, et tous les noeuds sans successeurs sont reliés au noeud final. Le graphe obtenu doit évidemment être acyclique.

Un "chemin critique" est un chemin de longueur maximale entre les deux jalons. Il peut éventuellement y en avoir plusieurs, de même longueur. Toute tâche située sur un chemin critique ne peut être retardée sans répercussion sur la durée totale du projet. En d'autres termes, sa "marge totale" est nulle (nous disons alors aussi que sa date de fin/début au plus tôt est strictement égale à sa date de fin/début au plus tard). Par ailleurs, nous définissons aussi en gestion de projets, la "marge libre" qui indique la durée sur laquelle une tâche peut glisser sans bouger la tâche successeur. La marge libre se calcule comme la différence entre la date de début au plus tôt d'une tâche sommé de sa durée et la date de début au plus tard de la tâche successeur.

Prenons pour l'exemple un projet qui se compose des tâches suivantes :

TÂCHES
TÂCHES ANTÉRIEURES
DURÉE
A
E
3
B
K,C
4
C
-
3
D
E,J
2
E
-
2
F
G,L
3
G
-
4
H
A,M,R
2
J
E
2
K
C
2
L
G
5
M
C
4
N
G
3
R
J
2
Tableau: 27.1  - Ordonnancement de tâches

Le graphe orienté valué connexe correspondant à ce tableau une fois la définition du chemin critique appliqué est le suivant en utilisant les dates de début :

equation
  (27.15)

Nous voyons dans ce graphe que les tâches equation sont critiques.

Un excellent outil d'utilisation de tels graphes est MS Project dont le diagramme correspondant à l'exemple ci-dessous est :

equation

D19.  Une "composante connexe" d'un graphe G est un sous-graphe equation connexe maximal.

Remarque: Un graphe ne possédant qu'une seule composante connexe est simplement un graphe connexe. Un sommet isolé (de degré 0) constitue toujours une composante connexe à lui seul. La relation sur les sommets "il existe un chemin entre ..." est une relation d'équivalence (réflexive, symétrique et transitive). Les composantes connexes d'un graphe correspondent aux classes d'équivalences de cette relation.

Propriété (triviale) : Un graphe G d'ordre n connexe comporte au moins n-1 arêtes.

D20. Un "cycle" est un chemin simple rebouclant sur lui-même. Un graphe dans lequel il n'existe aucun cycle possible est dit "acyclique".

Les graphes acycliques non connexes constituent une classe intéressante de graphes, avec des propriétés remarquables et un nom : les "forêts" (terme très souvent utilisé par les informaticiens réseaux)

equation
Exemple de graphe contenant un cycle
  (27.16)

 

equation
Exemple de forêt (graphe acyclique)
  (27.17)

equation
Exemple d'arbre (forêt connexe)
  (27.18)

Nous voyons ainsi qu'une forêt est un graphe dont les composantes sont des arbres. Les sommets de degré 1 sont appelées "feuilles" d'un arbre.

Propriétés :

P1. (triviale) Si dans un graphe G tout sommet est de degré supérieur ou égal à 2, alors G possède au moins un cycle.

Remarque: Cette propriété simple implique qu'un graphe sans cycle possède au moins un sommet de degré 0 ou 1. A l'inverse, nous pouvons lier cette fois l'absence de cycle dans un graphe avec le nombre d'arêtes.

P2. (triviale) Un graphe acyclique G à n sommets possède au plus n-1 arêtes.

D21. Un "cycle eulérien" est un cycle passant une et une seule fois par chaque arête du graphe et revenant au point de départ (nous verrons plus loin les propriétés que doit posséder un tel graphe pour qu'un tel cycle y existe)

D22. Un graphe est dit "graphe eulérien" s'il admet un cycle eulérien.

D23. Un "cycle hamiltonien" est un cycle simple passant par tous les sommets du graphe une et une seule fois. Pour avoir un cycle hamiltonien, le graphe doit être connexe et il ne doit pas y avoir de sommets pendant.

D24. Un "graphe hamiltonien" est un graphe qui possède un cycle hamiltonien.

Il convient d'ouvrir maintenant une parenthèse (pour les paillettes...) sur le problème le plus connu en théorie des graphes : les ponts de Königsberg.

Euler (voir page des biographies), aimait à faire une promenade dans sa bonne ville de Königsberg. Il affectionnait selon la légende tout particulièrement de parcourir les 7 ponts qui enjambent la rivière. L'âge venant (les connaissances mathématiques aussi...), il se demanda si sans sacrifier à sa promenade, il pouvait en raccourcir la longueur en ne parcourant chaque pont qu'une seule fois. Ce problème est sans doute l'un des plus anciens en théorie des graphes : celui de l'existence d'une chaîne passant une et une seule fois par chaque arête.

equation
  (27.19)

La rivière sépare la ville de Königsberg en quatre parties, a, b, c, d. Un pont relie deux de ces parties. Nous pouvons alors représenter notre problème par un graphe avec quatre sommets, où chaque arête représente l'un des sept ponts de Königsberg. Sur cet exemple le graphe n'est pas un graphe simple :

equation        equation
  (27.20)

Comment savoir si un graphe est eulérien ou non ? Si pour notre problème le graphe obtenu est eulérien, il faut exhiber un cycle eulérien, ce qui ne semble pas facile. Mais s'il ne l'est pas ? Euler a donné une caractérisation très forte des graphes eulériens donnée par l'énoncé suivant :

Théorème d'Euler : Un graphe est eulérien si et seulement s'il est connexe et tous ses sommets sont de degré pair (il y a donc un nombre pair d'arêtes qui arrivent sur chaque sommet dont la moitié d'entre elles servant à arriver sur le sommet, l'autre à en repartir) sauf au plus deux (ces deux exceptions étant les sommets de départ et d'arrivée).

De façon plus précise :

- le graphe n'a pas de sommets impair, alors il est eulérien (et la chaîne est donc cyclique)

- le graphe ne peut avoir un seul sommet impair de par la propriété (déjà énoncée plus haut) que dans un graphe, le nombre de sommets de degré impair est toujours pair.

- si le graphe a deux sommets impairs, ces sommets sont alors les extrémités de la chaîne eulérienne

Corollaire : un graphe ayant plus de deux sommets impairs ne possède pas de chaîne eulérienne.

Avec cette caractérisation (que nous allons démontrer de suite après), les sommets a, b, c, d étant de degré impair, on sait immédiatement qu'il est impossible de parcourir tous les ponts de Königsberg seulement une fois au cours d'une promenade.

Démonstration:

1. Supposons qu'un graphe G soit eulérien. Il existe alors une chaîne c parcourant une et une seule fois chaque arête (jusque là c'est facile). Bien évidemment, dans le cas d'une chaîne, les sommets se situant aux extrémités de la chaîne sont de degré impair et sont au nombre de deux.

2. Considérons maintenant un sommet x et considérons cette fois-ci un cycle eulérien. Lors du parcours du cycle, à chaque fois que nous passons par le sommet x, nous sommes au point de départ et nous pouvons repartir par 2 arêtes non encore parcourues dans le début du nouveau cycle (le chemin peut-être parcouru dans les deux sens puisque le graph est non orienté). Le sommet x est donc de degré pair et peut être défini n'importe où dans le cycle, d'où le fait que l'ensemble des sommets sont de degré pair.

3. Réciproquement considérons un graphe G connexe dont tous les sommets sont de degré pair. Nous allons montrer par induction sur le nombre d'arêtes que G est alors eulérien :

- Si G se réduit à un unique sommet isolé, il est évidemment eulérien.  Sinon tous les sommets de G sont de degré supérieur ou égal à 2. Ceci implique qu'il existe un cycle equation sur G :

- Considérons le graphe partiel H constitué des arêtes en dehors du cycle equation. Les sommets de H sont également de degré pair, le cycle contenant un nombre pair d'arêtes incidentes pour chaque sommet. Par induction chaque composante connexe equation de H est un graphe eulérien, et admet donc un cycle eulérien equation. Pour reconstruire un cycle eulérien sur G, il nous suffit de fusionner le cycle equation avec les différents cycles equation. Pour cela nous parcourons le cycle equation depuis un sommet arbitraire; lorsque nous rencontrons pour la première fois un sommet x appartenant à equation, nous lui substituons le cycle equation. Le cycle obtenu est un cycle eulérien pour G, le cycle equation et les cycles equation formant une partition des arêtes.

equation
  (27.21)

Remarque: Ce principe de décomposer un graphe en graphes connexes et de les sommer permet de construire un algorithme récursif permettant de déterminer si un graphe est eulérien ou non.

D25. Deux graphes G et G ' sont "graphes complémentaires" lorsqu'ils vérifient les conditions suivantes : 

1. Ils ont le même ensemble de sommets

2. Deux sommets x, y sont voisins dans G ne sont pas voisins dans G '

D26. Un "graphe biparti" equation est un graphe tel que nous puissions partitionner l'ensemble de ses sommets en deux classes de sorte que toute arête ait une extrémité dans chacune des deux classes.

exempleExemple:

Voici donc une représentation d'un graphe biparti K3,3 classique. Il représente le problème fameux de l'approvisionnement de trois maisons avec trois usines (eau, électricité, gaz) sans droit d'alignement des services. Nous voyons immédiatement que ce graph est non-planaire.

equation

Remarque: Le graphe biparti complet equation est un graphe de sommets equationde sorte que chacune des deux classes de cardinaux respectifs p, q de sorte que chaque sommet d'une classe soit adjacent à tous les sommets de l'autre et seulement à ceux-ci.

D27. Deux graphes sont isomorphes s'il existe une bijection f de X dans X ' telle que, pour tous sommets x et y de G :

x adjacent à y dans equation equation equation adjacent à f(y) dans G '

Nous disons aussi que f est un "isomorphisme de G sur G ' ".

S'il existe une bijection f de X dans lui-même telle que :

x adjacent à y dans equation equation equation adjacent à f(y) dans G

Nous disons alors que f est un automorphisme dans G (par permutation des sommets il existe beaucoup d'exemples possibles...).

Remarque: Attention ! Parfois nous parlons de graphes équivalents à "un isomorphisme près". Cela signifie plus clairement, qu'à l'exception d'une et unique violation parmi l'ensemble des arêtes, les graphes sont isomorphes.

Comme l'isomorphisme dans le cas des graphes va d'un ensemble à un autre de même cardinal n, le nombre de bijections possibles différentes est (voir le chapitre de Probabilité sur les arrangements) :

n!   (27.22)

Cela signifie qu'il existe au maximum n! graphes qui peuvent se regrouper dans une même classe d'équivalence - mais cependant qu'il n'en existe pas une seule (sans que cela en donne le nombre, nous en connaissons le majorant). En conséquence, il existe au minimum (minorant) le rapport du nombre total de n sommets sur le cardinal majoré de la plus grande classe d'équivalence possible (mais pas nécessairement existante) :

equation   (27.23)

En utilisant la majoration grossière equation, nous avons :

equation   (27.24)

D'où :

equation   (27.25)

Soit encore :

equation   (27.26)

Ainsi, quand n tend vers l'infini, equation admet un minorant de l'ordre de equation.


page suivante : 1. Matrice d'adjacence