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 sous-graphe est un graphe constitué d'un sous-ensemble des sommets et des arêtes d'un autre graphe.

Considérons le graphe original \(G\). Nous pouvons créer un sous-graphe \(H\) en sélectionnant uniquement un sous-ensemble des sommets (par exemple, en supprimant le sommet C) et un sous-ensemble des arêtes.

Graphe \(G\)	Sous-graphe \(H\)

Un graphe est dit simple s'il ne contient aucune boucle et s'il y a au maximum une arête reliant toute paire de sommets distincts.

Graphe simple	Pas simple (boucle)	Pas simple (double arête entre deux sommets)

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

Un arbre est un graphe connexe sans cycles.

Quelques exemples d'arbres sont montrés ci-dessous :

Un arbre couvrant d'un graphe connexe est un sous-graphe qui contient tous les sommets du graphe original et qui est un arbre (connexe et sans cycle).

Considérons le graphe suivant \(G\) :Ce graphe possède un cycle (\(A-B-C-D-A\)). Pour former un arbre couvrant, nous devons supprimer une arête pour briser le cycle tout en gardant tous les sommets connectés.
Par exemple, si nous supprimons l'arête reliant \(B\) et \(C\), nous obtenons un arbre couvrant (en bleue) :

Pour un graphe connexe pondéré, un arbre couvrant minimal (ACM) est un arbre couvrant dont la somme des poids des arêtes est minimale. Il relie tous les sommets avec le coût total le plus bas possible.

Considérons le graphe pondéré ci-dessous. L'arbre couvrant minimal est :Le poids total de l'arbre couvrant minimal est \(20 + 2 + 3 + 5 = 30\).

1. Commencer par n'importe quel sommet.
2. Choisir l'arête avec le poids le plus faible reliant un sommet de l'arbre à un sommet extérieur.
3. Ajouter l'arête et le sommet choisi. Répéter jusqu’à ce que tous les sommets soient connectés.

Appliquons l'algorithme de Prim à ce graphe.

1. Départ en A. Les arêtes connectées à A sont AB (3) et AD (15).
2. Choisir AB (poids 3) car c'est le plus faible. Notre arbre est \(\{A, B\}\).
3. Regarder les arêtes reliant \(\{A, B\}\) à l'extérieur : AD (15) et BC (5).
4. Choisir BC (poids 5). Notre arbre est \(\{A, B, C\}\).
5. Regarder les arêtes reliant \(\{A, B, C\}\) à l'extérieur : AD (15) et CD (2).
6. Choisir CD (poids 2). Notre arbre est \(\{A, B, C, D\}\).
7. Regarder les arêtes reliant \(\{A, B, C, D\}\) à l'extérieur : DE (20). Notez que AD est maintenant une arête interne (les deux extrémités sont dans l'arbre), donc on l'ignore.
8. Choisir DE (poids 20).

Tous les sommets sont connectés. Poids total : \(3 + 5 + 2 + 20 = 30\).

1. Lister (ou trier) toutes les arêtes par poids croissant (au sens large : poids égaux autorisés).
2. Commencer avec un ensemble vide d'arêtes sélectionnées (une forêt de sommets isolés).
3. Parcourir les arêtes dans cet ordre. Pour chaque arête, l'ajouter si elle relie deux composantes différentes (donc si elle ne crée pas de cycle) ; sinon l'ignorer.
4. S'arrêter lorsque \(n-1\) arêtes sont sélectionnées (ou, de façon équivalente, lorsque tous les sommets sont connectés).

Appliquons l'algorithme de Kruskal au même graphe.

1. Lister toutes les arêtes par poids (croissant) :
   • CD (2)
   • AB (3)
   • BC (5)
   • AD (15)
   • DE (20)
2. Sélectionner les arêtes dans l'ordre :
   • Choisir CD (poids 2). Pas de cycle.
   • Choisir AB (poids 3). Pas de cycle.
   • Choisir BC (poids 5). Pas de cycle.
   • Considérer AD (poids 15). Ajouter cette arête formerait un cycle (\(A-B-C-D-A\)). Rejeter.
   • Choisir DE (poids 20). Pas de cycle.

L'algorithme s'arrête lorsque \(n-1\) arêtes sont sélectionnées (ici, 4 arêtes).Poids total : \(2 + 3 + 5 + 20 = 30\).

• Un circuit eulérien est un sentier qui parcourt chaque arête du graphe exactement une fois et commence et finit au même sommet.
• Un sentier eulérien parcourt chaque arête exactement une fois mais commence et finit à des sommets différents.

• Un graphe connexe possède un circuit eulérien si et seulement si chaque sommet a un degré pair.
• Un graphe connexe possède un sentier eulérien si et seulement s'il a exactement deux sommets de degré impair.

Considérons le graphe non orienté suivant (en forme de "nœud papillon").Calculons le degré de chaque sommet (le nombre d'arêtes qui y sont connectées) :

• \(\deg(A) = 2\)
• \(\deg(B) = 2\)
• \(\deg(C) = 4\) (connecté à A, B, D, E)
• \(\deg(D) = 2\)
• \(\deg(E) = 2\)

Puisque tous les sommets ont un degré pair, le graphe contient un circuit eulérien.
Un circuit possible est : \(C \to A \to B \to C \to D \to E \to C\).

Le problème du postier chinois a été posé par le mathématicien Kwan Mei-Ko. Le problème demande : comment un facteur peut-il distribuer le courrier sur toutes les chemins d'un réseau et revenir au dépôt en parcourant la distance minimale possible ?
Mathématiquement, cela signifie parcourir chaque arête d'un graphe pondéré au moins une fois et revenir au point de départ.

Le but est de trouver la marche fermée la plus courte qui parcourt chaque arête au moins une fois.
Si le graphe n'est pas eulérien, nous devons répéter des arêtes pour rendre tous les sommets de degré pair.

1. Identifier tous les sommets de degré impair.
2. Trouver toutes les paires possibles de ces sommets impairs.
3. Pour chaque paire, trouver le chemin le plus court entre eux.
4. Sélectionner la paire qui ajoute le poids total minimum.
5. Ajouter ce poids au poids total du graphe.

Résoudre le problème du postier chinois pour le graphe pondéré suivant.

1. Poids total du graphe : \(4+3+4+3+5 = 19\).
2. Identifier les degrés impairs :
   • \(\deg(A)=2\), \(\deg(C)=2\) (Pairs).
   • \(\deg(B)=3\), \(\deg(D)=3\) (Impairs).
   Les sommets impairs sont B et D.
3. Trouver le chemin le plus court entre les sommets impairs : Les sommets impairs doivent être appariés. Comme il n'y en a que deux, la paire est (B, D).
   Chemins de B à D :
   • Direct : B \(\to\) D (poids 5).
   • Via A : B \(\to\) A \(\to\) D (poids \(4+3=7\)).
   • Via C : B \(\to\) C \(\to\) D (poids \(3+4=7\)).
   Le chemin le plus court est l'arête directe BD de poids 5.
4. Calculer la distance optimale : Total = Poids du Graphe + Ajout du Chemin le Plus Court Total = \(19 + 5 = 24\).

Pour minimiser la distance, le facteur doit parcourir l'arête BD deux fois.
Un itinéraire optimal possible est :$$ A \to B \to D \to B \to C \to D \to A $$

• Un cycle hamiltonien est un cycle qui visite chaque sommet du graphe exactement une fois.
• Un chemin hamiltonien visite chaque sommet exactement une fois mais ne retourne pas nécessairement au départ.

Considérons le graphe suivant.

• Un chemin hamiltonien : \(D \to B \to A \to C \to E\). (Il visite chaque sommet exactement une fois, mais ne retourne pas à \(D\)).
• Un cycle hamiltonien : \(A \to B \to D \to E \to C \to A\). (Il visite chaque sommet exactement une fois et retourne au départ).

Le problème du voyageur de commerce (PVC) décrit un scénario d'optimisation classique : Un vendeur doit quitter sa ville natale, visiter un ensemble précis d'autres villes exactement une fois, puis rentrer chez lui. L'objectif est de trouver l'itinéraire qui minimise la distance totale parcourue.
En termes de théorie des graphes, cela revient à trouver le cycle hamiltonien ayant le poids total minimum dans un graphe complet pondéré.

Le but est de trouver le cycle hamiltonien avec le poids total minimum dans un graphe complet pondéré.
Comme trouver la solution exacte est difficile, nous trouvons des bornes :

• Borne Supérieure (Algorithme du plus proche voisin) : Commencer à un sommet, toujours aller au sommet non visité le plus proche, et retourner au départ à la fin.
• Borne Inférieure (Algorithme du sommet supprimé) :
  1. Supprimer un sommet \(V\) et ses arêtes.
  2. Trouver l'ACM du graphe restant.
  3. Ajouter les deux arêtes les plus courtes partant de \(V\) au poids de l'ACM.

Trouver les bornes pour le tour optimal commençant en A pour le graphe suivant.

1. Borne Supérieure (Plus proche voisin depuis A) :
   • Départ A. Voisins non visités : B(10), C(8), D(15). Choisir C.
   • De C. Non visités : B(9), D(7). Choisir D.
   • De D. Non visité : B(12). Choisir B.
   • De B, retour au départ (A). Poids 10.
   • Itinéraire : \(A \to C \to D \to B \to A\).
   • Poids Total : \(8 + 7 + 12 + 10 = 37\).
2. Borne Inférieure (Supprimer le sommet A) :
   • Enlever A. Sommets restants : B, C, D. Arêtes : BC(9), CD(7), BD(12).
   • ACM du reste : Choisir CD(7), puis BC(9). Total = 16.
   • Arêtes depuis A : AB(10), AC(8), AD(15). Les deux plus courtes sont 8 et 10.
   • Poids Total : \(16 + 8 + 10 = 34\).

La solution optimale se situe entre 34 et 37.