Théorie des graphes

Les graphes sont utilisés pour montrer comment les choses sont connectées. Ils peuvent servir à résoudre des problèmes de planification ferroviaire, de flux de trafic, d'utilisation des lits dans les hôpitaux et de gestion de projet.
La théorie des graphes a été développée il y a des siècles, mais l'application des idées théoriques est relativement récente. De réels progrès ont été réalisés pendant et après la Seconde Guerre mondiale, alors que mathématiciens, techniciens industriels et membres des forces armées travaillaient ensemble pour améliorer les opérations militaires.

Un graphe (ou réseau) est une structure qui montre les connexions physiques ou les relations entre des objets d'intérêt.
Les objets d'intérêt sont représentés par des sommets (singulier : sommet), aussi appelés nœuds ou points.
Les connexions ou relations sont représentées par des arêtes, aussi appelées lignes ou arcs.

Ce graphe montre les connexions routières entre plusieurs villes. Nous pouvons voir que les villes A et B sont directement connectées, mais les villes A et C ne le sont pas.

Le degré d'un sommet, noté \(\deg(v)\), est le nombre d'arêtes qui y sont connectées.
S'il existe une boucle (une arête reliant un sommet à lui-même), elle contribue pour 2 au degré de ce sommet.

Pour le sommet A : Il a une connexion vers B et une connexion vers D. \(\deg(A) = 2\).

Dans un graphe non orienté, le mouvement est autorisé dans les deux sens le long des arêtes. La relation est symétrique.

• Des sommets adjacents sont des sommets reliés par une arête.
• Des arêtes adjacentes sont des arêtes qui partagent un sommet commun.

Dans ce graphe, A est connecté à B et B est connecté à A.

Un graphe orienté contient des flèches indiquant la direction dans laquelle nous pouvons nous déplacer le long des arcs.

• Le degré entrant est le nombre d'arêtes arrivant au sommet.
• Le degré sortant est le nombre d'arêtes partant du sommet.

Dans ce graphe, A est connecté à B et B n'est pas connecté à A.

Un graphe pondéré a des nombres assignés à ses arêtes. Ces nombres peuvent représenter le coût, le temps ou la distance.

Le poids de l'arête AD est 15.

• Une chaîne (ou chemin dans un graphe orienté) est une suite de sommets telle que chaque paire de sommets successifs soit reliée par une arête (ou un arc).
• Un sentier est une chaîne dans laquelle aucune arête n'est répétée.
• Une chaîne élémentaire (ou chemin élémentaire) est une chaîne dans laquelle aucun sommet n'est répété.
• Un circuit est une chaîne dans laquelle aucune arête n'est répétée qui commence et finit au même sommet.
• Un cycle est une chaîne dans laquelle aucun sommet n'est répété (excepté le premier et le dernier sommet) qui commence et finit au même sommet.

Dans ce graphe :

• \(A\rightarrow B\rightarrow C\) est une chaîne car il y a une arête entre \(A\) et \(B\) et une arête entre \(B\) et \(C\).
• \(A\rightarrow B\rightarrow A\) n'est pas un sentier car l'arête entre \(A\) et \(B\) est répétée.
• \(A\rightarrow B\rightarrow C\rightarrow D\rightarrow A\) n'est pas une chaîne élémentaire car le sommet \(A\) est répété.
• \(A\rightarrow B\rightarrow C\rightarrow D\rightarrow A\) est un circuit (et un cycle).

Un graphe est dit connexe s'il est possible de voyager de n'importe quel sommet à n'importe quel autre sommet via une suite d'arêtes.

Connexe	Non connexe

Dans le graphe de droite, vous ne pouvez pas passer de la paire de sommets de gauche à la paire de droite. Il a deux composantes disjointes.

Un graphe complet est un graphe simple non orienté dans lequel chaque sommet est relié par une arête à tous les autres sommets.
La notation \(K_n\) est utilisée pour décrire le graphe complet à \(n\) sommets.

Ceci est \(K_4\). Il a 4 sommets et \(\frac{4(3)}{2} = 6\) arêtes.

Pour un graphe à \(n\) sommets, la matrice d'adjacence \(M\) est une matrice \(n \times n\) où l'élément \(m_{ij}\) représente le nombre d'arêtes directes du sommet \(i\) au sommet \(j\).

Le tableau ci-dessous indique le nombre d'itinéraires à une étape entre les sommets :La matrice d'adjacence pour le graphe est donc :$$ M = \begin{pmatrix}0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix} $$Comme nous n'écrivons généralement pas les étiquettes des sommets sur la matrice d'adjacence, il est important de se rappeler à quoi font référence les lignes et les colonnes. Pour faciliter cela, nous les classons par ordre alphabétique.

Si \(M\) est la matrice d'adjacence, alors l'élément \((i,j)\) de \(M^k\) donne le nombre de chaînes de longueur \(k\) du sommet \(i\) au sommet \(j\).

Pour comprendre pourquoi les puissances de \(M\) donnent les matrices d'adjacence à plusieurs étapes, considérons la matrice à 2 étapes :L'élément à la ligne 2 colonne 4 de \(M^2\) montre qu'il y a deux itinéraires en 2 étapes de B à D.
Cette valeur provient de la multiplication ligne 2 \(\times\) colonne 4 comme suit :

• \(1 \times 1 = 1\) chemin de B vers A \(\times\) 1 chemin de A vers D
• \(0 \times 0 = 0\) chemin de B vers B \(\times\) 0 chemin de B vers D
• \(1 \times 1 = 1\) chemin de B vers C \(\times\) 1 chemin de C vers D
• \(0 \times 0 = 0\) chemin de B vers D \(\times\) 0 chemin de D vers D
• \(0 \times 1 = 0\) chemin de B vers E \(\times\) 1 chemin de E vers D

En additionnant ces termes, on obtient les deux itinéraires à 2 étapes de B à D. Les itinéraires sont \(\text{B} \rightarrow \text{A} \rightarrow \text{D}\) et \(\text{B} \rightarrow \text{C} \rightarrow \text{D}\).