L'encyclopédie des Sciences
  Théorie des Graphes
 

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.

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 par informatique 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 et statistiques, 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 constitué d'un ensemble X non vide et fini (sommets), et d'un ensemble E (arêtes) de paires d'éléments de X ou autrement dit (...) d'une partie du produit cartésien  (cf. chapitre de Théorie Des Ensembles).

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 infine), A son nombre d'arêtes et S sont nombre de sommets nous avons alors ::

  (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 site (dans le présente chapitre et lors de notre étude des polyèdres dans le chapitre sur les formes géométriques).

Exemple:

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


  
(2)

Démonstration:

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

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

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) :


  
(3)

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

F - A + S = 2   (4)

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

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

C.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  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'elle sont "incidentes", autrement, qu'elles sont indépendantes.

Remarque: Si e est une arête de G, nous noterons  le sous-graphe de . Si X ' est un sous-ensemble de X, nous noterons  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 :

  (6)

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

  (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  graphes à 27 sommets – chiffre à comparer avec le fait que nous estimons à moins de  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, 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 (triviales) : 

P1. Dans un graphe, le nombre de sommets impairs est toujours pair

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

Remarque: Un "graphe régulier" est un graphe dont tous les sommet ont même degré.

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

D9. Un "sous-graphe recouvrant" d'un graphe  est un sous-graphe , 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".

Exemple:

Voici quelques graphs complets pour lesquels nous avons bien :

  (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éplacement évitant les croisements).


  
(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é . 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 ).

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" ou un "chemin" :

Un chemin ("path" en anglais) est une liste  de sommets telle qu'il existe dans le graphe une arête entre chaque paire de sommets successifs : . 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. Ainsi, nous définissons aussi un "cycle" :

  (10)

comme étant un chemin simple finissant à son point de départ tel que

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 est dit "chemin élémentaire" si chacun des sommets du parcours est visité une seule fois : . 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   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):

  (11)

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  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 et  :

  (12)

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

  (13)

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). 

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. 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 la redondances d'envois de paquets de données ou la gestion de projets (voir l'exemple ci-dessous).

Exemple:

Un excellent exemple pratique de graphe 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 des arcs incidents extérieurement au noeud correspondant. Les arcs représentent les contraintes d'enchaînes 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. Tout 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 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
  (14)

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 :


  
(15)

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

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

D19.  Une "composante connexe" d'un graphe G est un sous-graphe  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)


Exemple de graphe contenant un cycle
  
(16)

 


Exemple de forêt
  
(17)


Exemple d'arbre
  
(18)

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 une 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 une 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 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.


  
(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 :

       
  
(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 sauf au plus deux

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 une 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 le chaîne eulérienne

Corollaire : une 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  sur G :

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


  
(21)

Remarque: Ce principe de décomposer un graphe en graphes connexes et de les sommer permet de constuire 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" 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.

Exemple:

Voici donc une représentatio d'un graphe biparti K3,3 classique. Il représente la 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.

Remarque: Le graphe biparti complet est un graphe de sommets de 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   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 à ydans   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!   (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) :

  (23)

En utilisant la majoration grossière , nous avons :

  (24)

D'où :

  (25)

Soit encore :

  (26)

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

D28. Une "étoile"  d’ordre n dont un sommet est voisin à tous les autres dont il est lui-même l’unique voisin .

matrice d'adjacencE

Au plan formel, un graphe est aussi un ensemble sur lequel nous avons défini une relation binaire, antiréflexive (aucun élément n’est en relation avec lui-même) et symétrique (si x est en relation avec y, alors y est en relation avec x). La structure de graphe peut alors sembler particulièrement pauvre.

Mais nous pouvons aussi associer à un graphe G de sommets  une matrice carrée M de dimensions  appelée "matrice d'adjacence" du graphe et dont les éléments valent 0 ou 1. En notant  le terme située au croisement de la ligne i (représentant le sommet ) et de la colonne j (représentant le sommet ), M est défini par :

 si et seulement si  sont adjacents

De par cette définition et celle du graphe lui-même, il vient que dans une matrice d'adjacence que les éléments diagonaux pour lesquels  valent tous 0 et que .

Rappelons qu'une telle matrice est dite "symétrique" (cf. chapitre d'Algèbre linéaire).

Remarque: Nous savons aussi que les graphes sont représentés par des matrices dans le cadre de l'étude des chaînes de Markov dans le domaine des probabilités (cf. chapitre de Probabilités)

Voyons un exemple à la fois abstrait mais facilement applicable à n'importe à de nombreux domaines de l'industrie, de la sociologie et de la biologie. Considérons le graphe orienté suivant.


  
(27)

Nous pouvons représenter ce diagramme sous forme d'un tableau dans lequel nous noterons "1" dans un cas quand une transition est possible de l'état mentionné en haut de cette case vers celui mentionné au début de la ligne et "0" sinon:

E1

E4

E2

E3

E5

E7

E6

E1

0

0

0

0

0

0

0

E4

0

0

1

0

0

0

0

E2

1

1

1

1

0

0

0

E3

0

0

1

0

0

0

0

E5

0

0

0

1

0

0

0

E7

0

1

1

1

0

0

0

E6

0

1

1

1

0

0

0

  (28)

Il est indispensable de comprendre parfaitement la signification des valeurs se trouvant dans ce tableau! Mais à ce niveau du site cela ne devrait pas poser de difficulté majeure.

Maintenant évaluons le nombre de manières permettant d'aller:

1. De E2 vers E2 en deux étapes

2. De E3 vers E4 en deux étapes

3. De E2 vers E7 en deux étapes.

Il est facile dans le cas particulier ci-dessus de dénombrer ces possibilités. Mais dans le cas d'un graphe plus complexe cela devient difficile voir impossible pour un être humain dans un temps raisonnable.

Nous devons faire appel alors au théorème suivant:

Soit un graphe orienté avec  sommet de matrice d'adjacence :

  (29)

Pour tout entier naturel k, alors le nombre de chemins de longueur k du sommet  au sommet  est donné par:

  (30)

où l'exposant sur M dénote la puissance de k de la matrice d'adjacence.

Démonstration:

Effectuons une récurrence sur k:

  (31)

désigne bien le nombre de chemins allant de  à  (où i et j peuvent être égaux). Supposons le résultat vrai pour l'entier k-1, avec  comme:

  (32)

nous avons alors (par construction de la multiplication matricielle):

  (33)

Par hypothèse de récurrence,  est le nombre de chemins de longueur k-1 allant de  à  et  est nous le savons (par construction) le nombre de chemins de longueur 1 allant de  à  et en particulier il est égal à 1 si  est une arête du Graphe et 0 sinon!

Donc le produit:

  (34)

donne pour une valeur de l donnée le nombre de chemins de longueur k allant de  à  dont la dernière arête est .

La somme:

  (35)

donne donc toutes les possibilités (chemins) de longueur k allant de  à  quelque soit le point de début de la dernière arête!

C.Q.F.D.

Ainsi, dans notre exemple, la matrice M est donnée par:

  (36)

Donc si nous la mettons à la puissance k, chaque composant donnera toutes les possibilités (chemins) de longueur k allant de  à . Et nous avons:

  (37)

Nous avons alors la réponse à nos trois questions en lisant la matrice ci-dessus:

1. De E2 vers E2 en deux étapes nous avons donc trois possibilités.

2. De E3 vers E4 en deux étapes nous avons donc 1 possibilité.

3. De E2 vers E7 en deux étapes nous avons donc 3 possibilités.

Il est possible de gagner un peu de temps dans ce genre de calculs. Si nous notons , la troisième colonne de la matrice M, alors:

  (38)

soit la i-ème colonne de la matrice M au carré. Et ainsi de suite:

  (39)

Donc nous obtenons systématiquement le nombre de chemins de longueur k d'un point de départ donné correspondant à la colonne i.

Cet exemple à une autre approche très intéressant dans certains domaines étudiant le comportement d'individus dans diverses situations (achats, tourismes, accidents,…).

Si au lieu de noter dans la matrice M le nombre de chemins possible d'un sommet à l'autre nous notons la probabilité (la partie) du nombre total d'individus qui partent de ce même sommet pour en arriver à un autre alors nous avons par exemple (pris au hasard):

  (40)

Nous voyons que:

1. La somme des probabilités de transitions au départ de chaque sommet (état) doit toujours logiquement être égale à 1

2. Tout le monde part de la première étape E1

3. Certains stagnent (s'arrêtent) à une certaine étape

4. Ceux qui arrivent à une étape de fin E5, E6 ou E7 y restent et ne reviennent pas sur leurs pas.

Le graphe équivalent devient alors:


  
(41)

En appelant N (au lieu de M pour ne pas confondre) la matrice construite à partir du graphe ci-dessus nous voyons que si  est une des colonnes de la matrice M alors par exemple:

  (42)

donne les probabilités de transition que ce qui part de E2 arrive en 1 étape en respectivement E1 (0), E2 (0.662), …

Si nous multiplions ensuite encore une fois:

  (43)

donne les probabilités de transition que ce qui part de E2 arrive en 2 étapes en respectivement E1 (0), E2 (0.0662), … et ainsi de suite. Nous pouvons ainsi savoir qu'elle est la probabilité qu'un individu arrivant à E2 puisse arriver à un des sommets terminaux (E5, E6 ou E7) en un nombre d'étapes donné.

Remarque: la somme des probabilités des colonnes T obtenues est toujours égale à 1. Ce qui signifie tout simplement que nous retrouvons ainsi tout l'ensemble de la population de département répartis dans les différents sommets avec une certaine probabilité.

CATÉGORIES

L'introduction des catégories à travers la "théorie des catégories" par Eilenberg et MacLane en 1942 avait pour but de transformer de difficiles problèmes de Topologie en problèmes plus abordables d'algèbre. Plus tard, la théorie des catégories s'est beaucoup développée, à la fois pour elle-même et pour ses applications dans les domaines les plus variés des mathématiques (par exemple en géométrie différentielle). Même si une partie de son développement autonome a parfois été critiquée, les catégories sont maintenant reconnues comme un langage puissant pour développer une sémantique universelle des structures mathématiques. On les utilise aussi en logique et plus récemment en physique, et une collaboration fructueuse semble se développer entre catégoriciens et informaticiens.

Définitions:

D1. Intuitivement une "catégorie" est juste un graphe orienté sur lequel nous nous sommes donné une loi pour composer des flèches consécutives, vérifiant certains axiomes.

D2. Un "graphe orienté" est formé d'un ensemble d'objets, appelés sommets du graphe, avec des liens entre eux, représentés par des flèches d'un sommet A vers un sommet B, ce que nous notons  . Nous disons que A est la "source" de la flèche, et B son "but". Il peut y avoir plusieurs flèches de même source et de même but (nous les disons "parallèles") et il peut y avoir des flèches "fermées", dont la source et le but sont confondus.

D3. Deux flèches f, g sont dites "flèches consécutives" si le but de la première est en même temps la source de la seconde:

  (44)

Nous disons alors qu'elles forment un chemin de longueur 2 de A vers C. Plus généralement, un chemin (de longueur n) de A vers  est une suite de n flèches consécutives :

  (45)

Une catégorie est donc un graphe dans lequel nous définissons une composition de flèches, associant à tout chemin (f , g) de longueur 2 de A vers C une flèche du graphe de A vers A, dite composée du chemin, et notée fg :

Cette composition vérifie les axiomes suivants:

A1. Associativité : Si fgh est un chemin de longueur 3, les deux composés f(gh) et (fg)h que nous en déduisons sont associatifs. Il s'ensuit qu'à tout chemin de longueur n est aussi associé un seul composé de sommets (invariance de l'itinéraire).

A2. Identités : A tout sommet A est associée une flèche fermée de A vers A, dite "identité" de A et notée , dont le composé avec une flèche de source ou de but A est égal à cette autre flèche.

Remarques:

R1. Les sommets du graphe sont aussi appelés "objets" de la catégorie et ses flèches des "morphismes" (ou simplement "liens") dans le cadre de la théorie des catégories 

R2. Une flèche f est un isomorphisme (cf. chapitre de Théorie Des Ensembles) s'il existe une flèche g  (appelée "inverse") telle que les composés fg et gf soient des identités (cet inverse est alors unique).

Ainsi, une catégorie est formée par des objets (les sommets du graphe) et des liens entre eux (les flèches ou morphismes), mais l'idée essentielle est de privilégier les liens sur les objets. En fait, le succès des catégories dans les domaines les plus variés est dû à la richesse des informations sur les objets qui peuvent être déduites de la seule considération des liens et des opérations sur ceux-ci, quelle que soit la nature et l'anatomie de ces objets.

Dans les quelques lignes qui suivent, nous expliquerons comment lire les graphes orientés que nous pouvons rencontrer parfois dans les livres de math. Ceci sera un bon exemple de la théorie des catégories car nous avons déjà rencontrés de tels graphes sans les décrire dans les chapitres sur les nombres et la cryptographie par exemple.

Pour simplifier nous allons expliquer ces diagrammes lorsque les objets de base sont les ensembles (ce qui est le cas le plus courant sur l'ensemble du site de toute manière).

Considérons trois ensembles A, B, et C et trois applications :

,  et   (46)

Nous pouvons considérer les applications f, g et h comme des flèches qui relient les objets (ensembles) A, B, et C pour former un triangle.

  (47)

Définition (simpliste): Nous disons  que le diagramme fléché ci-dessus est "un diagramme commutatif" si tous les chemins que nous empreintons pour aller d’un objet (ensemble) à un autre représentent la même application.

Remarque: Il existe deux façons d’aller de A à C . Nous pouvons y aller directement par g ou bien suivre d’abord f puis h. Ce dernier chemin est représenté par l’application composée  (cf. chapitre de Théorie Des Ensembles). Ainsi le diagramme ci-dessus est commutatif si .

Nous pouvons donc introduire la définition plus formelle :

Définition: Le diagramme ci-dessus est commutatif si .

Remarque: Rappelons que ceci veut dire que pour tout élément .

Nous pouvons compliquer à souhait les diagrammes en considérant plus d’ensembles et de flèches (applications) les reliant. Par exemple :

  (48)

Ce diagramme étant commutatif si et seulement si .

Remarques :

R1. Généralement dans la littérature mathématique lorsque de tels diagrammes sont sous-entendu comme étant commutatifs.

R2. Comme déjà mentionné, les objets de ces diagrammes peuvent plus généralement être des groupes des anneaux des espaces topologiques etc. Dans ces cas, les flèches ne sont plus des applications quelconques mais respectivement des homomorphismes de groupes, des homomorphismes d’anneaux, des applications continues, etc.
 
  nombre de visiteurs venus 726238 visiteurs (2523009 hits) Ici!

Tracked by Histats.com
Recherche personnalisée
$value) { if ($param == 'client') { google_append_url($google_ad_url, $param, 'ca-mb-' . $GLOBALS['google'][$param]); } else if (strpos($param, 'color_') === 0) { google_append_color($google_ad_url, $param); } else if ((strpos($param, 'host') === 0) || (strpos($param, 'url') === 0)) { google_append_url($google_ad_url, $param, $google_scheme . $GLOBALS['google'][$param]); } else { google_append_globals($google_ad_url, $param); } } google_append_url($google_ad_url, 'dt', round(1000 * array_sum(explode(' ', microtime())))); return $google_ad_url; } $google_ad_handle = @fopen(google_get_ad_url(), 'r'); if ($google_ad_handle) { while (!feof($google_ad_handle)) { echo fread($google_ad_handle, 8192); } fclose($google_ad_handle); } ?>
 
 
Ce site web a été créé gratuitement avec Ma-page.fr. Tu veux aussi ton propre site web ?
S'inscrire gratuitement