Application à la théorie des Graphes

 

Introduction et un peu d’histoire: Königsberg était une ville en Russie situé sur le fleuve Pregel, qui a servi de résidence des ducs de Russie au 16ème siècle. Aujourd'hui, la ville est appelée Kaliningrad, et est un centre industriel et commercial important de la Russie occidentale. Le fleuve Pregel a traverse la ville, la divisant en quatre régions, comme dans l'image suivante.

 

 

 

 

 

 

Au dix-huitième siècle, sept ponts ont relié les quatre régions. Les habitants de Königsberg avaient l'habitude de faire de longs tours de la ville le dimanche. Ils se sont demandés s'il était possible de commencer à un endroit dans la ville, de voyager à travers tous les ponts sans croiser n'importe quel pont deux fois et de retourner au point de départ. Ce problème a été résolu la première fois par le mathématicien suisse prolifique Leonhard Euler, qui a inventé la branche des mathématiques maintenant connue sous le nom de théorie des graphes en cours de sa solution. La solution d'Euler consistait à représenter le problème avec un ``graphe`` où les quatre régions sont représentées par quatre sommets et les sept ponts par sept arêtes  comme dans le diagramme suivant :

 

 

 

 

 

La théorie des graphes est maintenant un outil important dans  la recherche mathématique, le génie électrique, la programmation, la gestion des réseaux, l’administration d'affaires, la sociologie, les sciences économiques, la vente, les communications; la liste peut aller indéfiniment. En particulier, beaucoup de problèmes peuvent être modélisés avec des chemins (voir la définition ci-dessous) constitués par un déplacement le long des arêtes d'un certain graphe. Par exemple, des problèmes de planification efficace des routes pour la distribution du courrier, collecte d'ordures, enlèvement de neige, diagnostic dans des réseaux informatiques, et d'autres, peuvent être résolus en utilisant les modèles qui impliquent des chemins dans les graphes.

 

Les concepts de base de la théorie des graphes Avant que nous établissions le rapport entre la théorie des graphes et l'algèbre linéaire, nous commençons par quelques définitions de base de la théorie de graphes pour ceux qui ne sont pas familiers avec la matière:

 

 

 

Il y a plus qu’un chemin reliant les sommets P1 et P3. Un de ces chemins est formé par les trois points P1 P2 P3. Un autre chemin P1 à P3 est formé par les points P1 P2 P4 P5 P3.

·        Un graphe est dit connexe s’il y a au moins un chemin reliant deux sommets distincts dans le graphe. S’il existe un couple de sommets qui ne peuvent pas être reliés par au moins un chemin dans le graphe, on dit que le graphe est non connexe.

 

 

 

·        Dans un graphe G, s’il existe un chemin contenant n arêtes entre deux sommets Pi et Pj, on dit qu’il existe un chemin de longueur n de Pi à Pj. Par exemple, il y a trois chemins différents de longueur 2 entre les sommets P2 et P7 dans le graphe G1 ci-haut

 

C’est quoi alors la relation entre la théorie des graphes et l’algèbre linéaire?

 

Comme vous pouvez imaginer, les graphes peuvent être parfois très compliqués. Il faut alors trouver des moyens plus pratiques  pour les représenter. Les matrices représentent une manière très utile d'étudier des graphes, puisqu'elles transforment l'image en nombres, et alors on peut employer des techniques d'algèbre linéaire.

 

 

Étant donné un graphe G avec n sommets v1,…,vn , on définit la matrice d’adjacence de G relativement à l'énumération v1,…,vn des sommets comme étant la matrice (n×n) A=[aij], définie par :

 

 

 

For example, pour le graphe G1 ci-haut, la matrice d’adjacence (relativement à l'énumération  de ces sommets) est

 

 

 

 

 

Notez que pour un graphe simple (non orienté), comme G1, la matrice d’adjacence est  symétrique (c’est à dire égale à sa matrice transposée) mais ce n’est pas nécessairement le cas pour un graphe orienté comme G2.

 

Notez aussi qu’une matrice booléenne carrée (ses entrées sont  0 ou 1) avec des 0 sur la diagonale principale détermine un graphe orienté d’une façon unique.

 

Le théorème suivant donne une utilité importante des puissances de la matrice d’adjacence d’un graphe :

 

Si A est la matrice d’adjacence d’un graphe G ( avec sommets v1,…, vn), alors l’entrée  (i, j) de Ar représente le nombre de chemins distincts  de longueur r du sommet vi au sommet vj dans le  graphe.

 

En prenant le carré de la matrice M1 ci-haut, on trouve:

 

 

Cette matrice nous donne le nombre de chemins distincts de longueur 2 entre deux les sommets du graphe G1. Par exemple, il y a deux chemins distincts de longueur 2 reliant les sommets P2 et P7 dans le graphe ci-haut; par contre on ne peut pas passer de P1 à P5 en utilisant deux arêtes seulement.

 

Exemple Le diagramme suivant représente la carte routière d'une compagnie de la livraison

 

 

où A, B, C, D, E sont les villes servies par la compagnie. La matrice d’adjacence M de ce graphe  est:

 

 

 

 

 

d’où M2 est la matrice:

 

 

 

 

 

et M3 est la matrice:

 

 

 

 

Si la compagnie est surtout intéressée par les connections entre les villes A et B, on peut voir que le nombre de connections directes (avec une arête seulement) entre A et B est 1; le nombre de connections indirectes avec deux arêtes est 1, mais le nombre de connections indirectes avec trois arêtes entre les deux villes est 4. Ces 4 connections indirectes peuvent être données explicitement:

 

 

1.      AC→E→B

2.      A→B→D→B

3.      A→D→A→B

4.      A→C→A→B

 

 

 

 

Graphe orienté de Dominance  Un  graphe orienté G est appelé un graphe orienté de dominance si u→v ou v→u est vrai pour n’importe quelle paire (u, v) de sommets distincts de G (ici la notation u→v signifie qu’il existe une arête de u à v)

 

Le diagramme suivant est un exemple d’un graphe orienté de dominance :

 

 

 

Dans le graphe ci-dessus, les sommets A, C et E ont la propriété suivante: de chacun sommet, il y a un chemin de longueur 1 ou un chemin de longueur 2 reliant le sommet à n'importe quel autre sommet dans le graphe. Dans un tournoi sportif, ces sommets correspondraient aux équipes les plus puissantes dans le sens que ces équipes battent n'importe quelle autre  équipe donnée ou battent une autre équipe qui batte l'équipe donnée. Le graphe ci-dessus n'est pas unique avec cette propriété. Le théorème suivant garantit cela:

 

Dans n’importe quel graphe orienté de dominance, il y a au moins un sommet à partir duquel il y a un  chemin de longueur 1 ou un chemin de longueur 2 à n’importe quel autre sommet dans le graphe

 

Dans un graphe orienté de dominance, on définit la puissance d’un sommet comme étant le nombre total de chemins de longueur 1 ou 2 reliant le sommet aux autres sommets du graphe. En utilisant la matrice d’adjacence  M du graphe, on peut trouver la puissance d’un sommet Pi de la façon suivante: la somme des entrées sur la ième ligne de M est le nombre total de chemins de longueur 1 reliant Pi avec d’autres sommets, et la somme des entrées sur la ième ligne de M2 est le nombre total de chemins de longueur 2 reliant Pi avec d’autres sommets. Par conséquent, la somme des entrées sur la ième ligne de la matrice  A=M+ M2 est le nombre total de chemins de longueur 1 et 2 reliant Pi avec d’autres sommets du graphe.

 

Dans un graphe orienté de dominance, on voudrait localiser les sommets avec puissance maximale. Pour faire cela, on calcule la matrice A=M+ M2 et une ligne de A avec la plus grande somme d'entrées correspond à un tel sommet.

 

Exemple Supposez que les résultats d’un tournoi de base-ball de cinq équipes A, B, C, D et E sont donnés par le graphe orienté de H ci-dessus. La matrice d ‘adjacence M de H est :

 

 

 

 

 

donc M2 est la matrice

 

 

 

 

et la matrice A=M+ M2 est :

 

 

Comme la première ligne de A a la plus grande somme des entrées, le sommet A peut être relié à n’importe quel autre sommet par un chemin de longueur 1 ou un chemin de longueur 2. Le classement des équipes selon les puissances des sommets correspondants   est : 

 

Équipe A (premier), Équipe C (deuxième), Équipes B et D (troisièmes) et Équipe E (dernier).