News :: Erreur :: Visiteurs :: ClearType :: Imprimer ::

TRIGONOMÉTRIE | GÉOMÉTRIE EUCLIDIENNE | GÉOMÉTRIES NON-EUCLIDIENNES
GÉOMÉTRIE PROJECTIVE | GÉOMÉTRIE ANALYTIQUE | GÉOMETRIE DIFFÉRENTIELLE
FORMES GÉOMÉTRIQUES | THÉORIE DES GRAPHES

Dernière mise à jour de ce chapitre: 2017-12-31 17:58:49 | {oUUID 1.784}
Version: 3.2 Révision 8 | Avancement: ~90%
vues depuis le 2012-01-01: 12'876

LISTE DES SUJETS TRAITÉS SUR CETTE PAGE

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 du 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. Cette branche des mathématiques a connu un grand regain d'intérêt suite à l'émergence des réseaux sociaux Internet dont les connexions entre "amis" et "suiveurs" constituent des graphes dont l'analyse topologique et statistique peut nous apprendre de nombreuses choses.

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 les 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 que revêt l'aspect algorithmique dans leur domaine (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 de sorte qu'il relève d'un problème de la théorie des graphes que nous savons le plus souvent résoudre car rentrant dans une catégorie de problèmes connus.

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

Si la théorie des graphes connaît un assez grand engouement ces 30 dernières, peut-être est-ce dû au fait 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 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 reliés par un segment de droite ou autrement dit (...) d'une partie du produit cartésien  (cf. chapitre de Théorie Des Ensembles).

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

Un graphe est 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 (compte aussi pour une face la face extérieure infinie), A son nombre d'arêtes et S son nombre de sommets, nous avons alors:

  (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ésent 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 clair est la face extérieure infinie), 4 sommets et 4 arêtes:

Figure: 27.1 - Graphe à 2 faces, 4 sommets et 4 arêtes

Démonstration:

Nous démontrons cette formule en effectuant une récurrence (cf. chapitre de Théorie De La Démonstration) sur la différence A - S:

D'abord, la formule est vraie pour:

    (27.2)

car, dans ce cas, le graphe est un arbre donc il n'a qu'une seule face (la face extérieure), donc .

Figure: 27.2 - Arbre avec une arête et 2 sommets

Donc:

  (27.3)

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

Figure: 27.3 - Graphe avec au moins un cycle

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 F faces, S sommets et A arêtes et donc la formule:

F - A + S = 2   (27.4)

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

(F + 1) - (A + 1) + S = F - A + S =2   (27.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 arête est composée de deux sommets reliés par un segment de droite, d'où l'allusion aux paires d'éléments dans la définition précédente).

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'elles 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 nous nommons "ordre" du graphe est le nombre de ses sommets.

Soit G un graphe d'ordre n, 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 de cardinal:

  (27.6)

Il s'agit d'un résultat relativement trivial puisque chacun des sommets est lié à tous les autres sommets sauf lui-même (d'où le numérateur) et on divise par deux simplement pour ne pas compter les sommets voisins deux fois (et ils le sont tous lorsque nous les parcourons tous).

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

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

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.

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 graphes complets pour lesquels nous avons bien:

  (27.8)

arêtes. Nous remarquons que les quatre premiers graphes sont planaires (effectivement remarquez comment il est possible, par projection d'un sommet dans le plan, de transformer le quatrième K₄ en de manière à ce qu'il n'y ait plus d'intersections). Le cinquième graphe K₅ est non-planaire (nous ne pouvons trouver des déplacements évitant les croisements).

Figure: 27.4 - Exemples de graphes complets

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.

Ainsi, un cas sympathique à traiter est "l'étoile de David":

Figure: 27.5 - Étoile de David

qui n'est évidemment un graphe complet par définition que si l'on joint tous les sommets entre eux (ainsi nous perdons la géométrie de l'étoile mais obtenons un graphe ):

Figure: 27.6 - Étoile de David sous forme de graphe complet

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 parcourues: k-1.

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

Figure: 27.7 - Exemple de chemin simple

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

  (27.9)

comme étant un chemin simple finissant à son point de départ tel que. 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 graphe non orienté).

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

  (27.10)

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

  (27.11)

comportant le moins d'arêtes. Supposons par l'absurde que p n'est pas élémentaire. Il existe alors dans ce chemin un sommet z apparaissant au moins 2 fois le long du chemin p.

Soient i, j les 2 premiers indices tels que et :

  (27.12)

Pour obtenir une contradiction, il suffit de supprimer le cycle entre et . Alors, nous avons un nouveau chemin:

  (27.13)

est un chemin, reliant x à y. Sa longueur est strictement inférieure à celle de p, ce qui contredit notre choix initial 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".

D17. Un "arbre" ou "arbre couvrant" est un graphe connexe (non orienté), sans cycle simple (acyclique) et sans boucles. Dans un arbre le nombre d'arêtes est égal au nombre de sommets - 1. Une arbre couvrant avec les poids minimaux d'un graphe value est appelé "arbre couvrant minimal":

Figure: 27.8 - Exemple d'un arbre couvrant (source: Wikipédia)

Si vous imaginez que chaque point est une ville, est qu'une Nation n'a pas assez d'argent pour la maintenant de toutes les routes actuellement existante entre plusieurs villes, alors l'arbre couvrant minimal représente les routes à préserver qui minimisent les coûts tout en connectant toutes les villes entre elles.

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

Exemple:

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 valeur 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ée 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:

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:

Figure: 27.9 - Exemple de représentation d'un planning sous forme de graphe

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

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

Figure: 27.10 - Même graphe mais vu dans MS Project

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

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 composés d'arbres 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).

Figure: 27.11 - Exemple d'un graphe connexe contenant un cycle

Figure: 27.12 - Exemple d'un arbre (graphe connexe ne contenant pas de cycle)

Ci-dessous un exemple de forêt (composée d'arbres, chaque arbre étant connexe mais l'ensemble formant un graphe acyclique et non-connexe):

Figure: 27.13 - Exemple d'une forêt (3 composantes connexes)

Nous voyons ainsi qu'une forêt est un graphe dont les composantes sont des arbres. Les sommets de degré 1 sont appelés "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.

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 sommet 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 traversant 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.

Figure: 27.14 - Carte de la ville de Königsberg

La rivière sépare la ville de Königsberg en quatre parties, a, b, c, d. Chaque 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:

       
Figure: 27.15 - Représentation des sept ponts de Königsberg

La question est donc ici de savoir si le graphe est eulérien ou non? Si pour notre problème le graphe obtenu est eulérien, il faut pouvoir 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 pour un graphe connexe:

- le graphe n'a pas de sommets impairs, 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 (comme nous allons le 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 supposons cette fois-ci non pas un graphe eulérien mais un cycle eulérien. Lors du parcours du cycle, à chaque fois que nous passons par le sommet x, nous nous retrouvons au point de départ et pour effectuer un nouveau tour chacune des 2 arêtes s'offre à nous (le chemin pouvant être parcouru dans les deux sens puisque le graphe 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 H sont également de degré pair, le cycle contenant un nombre pair d'arêtes incidentes pour chaque sommet. Par induction chaque composante connexe  de H est 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.

Figure: 27.16 - Graphe Eulérien?

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 respectivement de cardinal p et q de sorte que toute arête ait une extrémité dans chacune des deux classes.

Exemple:

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

Figure: 27.17 - Exemple de graphe biparti

Remarque: Le graphe biparti complet est un graphe de sommets de sommets configuré de telle 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 à y dans   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...).

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

Cela signifie qu'il existe au maximum n! graphes qui peuvent se regrouper dans une même classe d'équivalence. 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):

  (27.15)

En utilisant la majoration grossière , nous avons:

  (27.16)

D'où:

  (27.17)

Soit encore:

  (27.18)

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

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 d'un graphe formel 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).

Voyons un exemple à la fois abstrait mais facilement applicable à de nombreux domaines de l'industrie, de la sociologie et de la biologie. Considérons le graphe orienté suivant et observons qu'il n'est pas antiréflexif ni symétrique:

Figure: 27.18 - Exemple de chaîne de Markov (graphe antiréflexif ni symétrique)

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

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, voire impossible pour un être humain dans un temps raisonnable.

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

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

  (27.19)

Pour tout entier naturel k, alors le nombre de chemins de longueur k d'un sommet  à un sommet  est donné par:

  (27.20)

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

Démonstration:

Effectuons une récurrence sur k:

  (27.21)

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:

  (27.22)

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

  (27.23)

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:

  (27.24)

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:

  (27.25)

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

C.Q.F.D.

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

  (27.26)

et n'est ni symétrique, ni antiréflexive comme nous en avions déjà fait mention.

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

  (27.27)

en utilisant par exemple la fonction PRODUITMAT( ).

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 3 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 i-ème colonne de la matrice M, alors:

  (27.28)

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

  (27.29)

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 a une autre approche très intéressante dans certains domaines étudiant le comportement d'individus dans diverses situations (achats, tourismes, accidents, etc.).

Si au lieu de noter dans la matrice M le nombre de chemins possibles 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 (valeurs imposées par l'expérience!) la matrice:

  (27.30)

qui est déjà la matrice stochastique transposée du graphe visible ci-dessous (conformément à la théorie des chaînes de Markov, nous avons vu qu'il fallait prendre la transposée de la matrice stochastique pour calculer les probabilités d'états).

En considérant que ces probabilités ne changent pas au cours du temps, nous avons alors une chaîne de Markov homogène (sans cycles). Nous voyons alors que:

1. La somme des probabilités de transitions au départ de chaque sommet (état) doit toujours logiquement être égale à 1 (ce que nous avions déjà mentionné dans le chapitre de Probabilités)

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

Le graphe équivalent devient alors:

Figure: 27.19 - Graphe équivalent à la matrice

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:

  (27.31)

donne la somme des probabilités de transition que ce qui part de E1 arrive en 2 étapes en respectivement E1(0), E2(0.662), E3(0.218)... (la distribution du vecteur initial peut être quelconque tant que la somme des valeurs de la colonne est égale à 1)!

Si nous multiplions ensuite encore une fois:

  (27.32)

donne la somme des probabilités de transition que ce qui part de E1 arrive en 3 étapes en respectivement E1(0), E2(0.691), ... 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é.

En continuant encore longtemps ainsi... nous trouvons que la mesure d'équilibre qui satisfait (cf. chapitre de Probabilités):

est:

  (27.33)

quelle que soit la distribution du vecteur de départ. Propriété que l'on appelle "ergodique" dans le domaine des chaînes de Markov.

Ce qui signifie 45% de probabilité de se trouver en E5, 32% de probabilité de se trouver en E7 et 23% de probabilité de se trouver en E6. Une autre manière de voir les choses est de dire que si une cohorte de 100 individus part de l'étape E1 avec les probabilités constantes dans le temps entre les transitions d'étapes, à l'équilibre nous aurons 45 personnes en E5, 32 personnes en E7 et 23 personnes en E6.

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:

  (27.34)

nous disons alors qu'elles forment un chemin de longueur 2 de A vers C.

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:

Figure: 27.20 - Exemple de graphe de catégorie

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: À 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.

Plus généralement, un chemin (de longueur n) de A vers  est une suite de n flèches consécutives:

  (27.35)

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   (27.36)

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.

Figure: 27.21 - Exemple de diagramme commutatif

Définition (simpliste): Nous disons  que le diagramme fléché ci-dessus est "un diagramme commutatif" si tous les chemins que nous empruntons 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:

Figure: 27.22 - Autre exemple de diagramme fléché

Ce diagramme étant commutatif si et seulement si .

- Théorie des graphes, O. Cogis + C. Robert, Éditions Vuibert, ISBN 2711753212

- Social Media Mining, R. Zafarani + M. Ali Abbasi, H. Liu, Éditions Cambridge University Press, ASIN B00IO0E5L8

11   2

Notée par 32 visiteur(s) 12345 PageRater 0.5.0 Commentaires: [0]