Graphes

Un graphe est une structure mathématique utilisée pour modéliser des relations entre des objets. Il est composé de deux types d'éléments :

• Les sommets (ou nœuds) : ce sont les objets. On les note souvent par des lettres ($S_1, S_2, \dots$ ou $A, B, C, \dots$). L'ensemble des sommets est noté $V$ (pour Vertices).
• Les arêtes (ou liens) : ce sont les relations entre les sommets. Une arête relie deux sommets. L'ensemble des arêtes est noté $E$ (pour Edges).

Un graphe $G$ est donc défini par la paire $(V, E)$.

Représentation graphique : On représente généralement un graphe en dessinant les sommets comme des points ou des cercles et les arêtes comme des lignes reliant ces points.

Types de graphes :

• Graphe non orienté : Les arêtes n'ont pas de direction. Si une arête relie $A$ et $B$, cela signifie que $A$ est lié à $B$ et $B$ est lié à $A$. On note une arête $\{A, B\}$. C'est comme une route à double sens.
• Graphe orienté (ou digraphe) : Les arêtes ont une direction. Si une arête va de $A$ vers $B$, cela ne signifie pas nécessairement qu'il y en a une de $B$ vers $A$. On note une arête $(A, B)$ pour une arête allant de $A$ à $B$. C'est comme une rue à sens unique.
• Graphe simple : Un graphe est dit simple s'il ne contient ni boucle, ni arêtes multiples. C'est le type de graphe le plus courant en Terminale.

Soit $V = \{A, B, C, D\}$ et $E = \{\{A, B\}, \{A, C\}, \{B, D\}, \{C, D\}\}$. C'est un graphe non orienté simple.

A --- B
|     |
C --- D

Pour bien parler des graphes, il faut connaître un vocabulaire précis :

• Sommets adjacents : Deux sommets sont adjacents s'ils sont reliés par une arête. Dans l'exemple ci-dessus, $A$ et $B$ sont adjacents, mais $A$ et $D$ ne le sont pas.
• Arête incidente : Une arête est dite incidente à un sommet si ce sommet est une de ses extrémités. L'arête $\{A, B\}$ est incidente aux sommets $A$ et $B$.
• Degré d'un sommet : Pour un graphe non orienté, le degré d'un sommet $S$, noté $d(S)$, est le nombre d'arêtes incidentes à ce sommet. Une boucle compte pour deux dans le degré.
  • Théorème fondamental des graphes : La somme des degrés de tous les sommets d'un graphe non orienté est égale à deux fois le nombre d'arêtes. $\sum_{S \in V} d(S) = 2|E|$.
• Degré entrant / sortant (pour les graphes orientés) :
  • Degré entrant $d^-(S)$ : nombre d'arêtes qui arrivent au sommet $S$.
  • Degré sortant $d^+(S)$ : nombre d'arêtes qui partent du sommet $S$.
  • La somme des degrés entrants est égale à la somme des degrés sortants, et est égale au nombre total d'arêtes.
• Voisinage : Le voisinage d'un sommet $S$, noté $N(S)$, est l'ensemble de tous les sommets adjacents à $S$.
• Boucle : Une boucle est une arête qui relie un sommet à lui-même (par exemple, $\{A, A\}$).
• Arêtes multiples (ou parallèles) : Ce sont plusieurs arêtes reliant les mêmes deux sommets. Dans un graphe simple, il n'y a ni boucles ni arêtes multiples.
• Graphe pondéré : Un graphe est pondéré si chaque arête (ou sommet) est associée à un nombre, appelé poids ou coût. Ce poids peut représenter une distance, un temps, un coût, etc.

Certains types de graphes ont des propriétés spécifiques et sont très utiles :

• Graphe complet ($K_n$) : Un graphe non orienté est complet si chaque paire de sommets distincts est reliée par une arête. Un graphe complet à $n$ sommets, noté $K_n$, possède $\frac{n(n-1)}{2}$ arêtes. Chaque sommet est adjacent à tous les autres sommets.
• Graphe nul : Un graphe nul est un graphe qui ne contient aucune arête. Il peut contenir des sommets.
• Graphe biparti : Un graphe est biparti si l'ensemble de ses sommets $V$ peut être divisé en deux sous-ensembles disjoints $V_1$ et $V_2$ ($V = V_1 \cup V_2$ et $V_1 \cap V_2 = \emptyset$) tels que chaque arête relie un sommet de $V_1$ à un sommet de $V_2$. Il n'y a pas d'arêtes au sein de $V_1$ ou au sein de $V_2$.
• Graphe connexe : Voir la section "Connexité" ci-dessous.

• Chaîne (pour graphe non orienté) : Une chaîne est une séquence d'arêtes distinctes qui relie une suite de sommets. Si la chaîne va de $S_0$ à $S_k$, on la note $S_0 - S_1 - \dots - S_k$. Les sommets peuvent être répétés.
• Chemin (pour graphe orienté) : Un chemin est une séquence d'arêtes orientées distinctes $(S_0, S_1), (S_1, S_2), \dots, (S_{k-1}, S_k)$. On le note $S_0 \to S_1 \to \dots \to S_k$. Les sommets peuvent être répétés.
• Longueur d'une chaîne/chemin : C'est le nombre d'arêtes qui le compose.
• Chaîne/chemin simple : Une chaîne (ou un chemin) est dite simple si tous ses sommets (et donc toutes ses arêtes) sont distincts.
• Distance entre deux sommets : Dans un graphe non pondéré, la distance entre deux sommets $S_i$ et $S_j$, notée $d(S_i, S_j)$, est la longueur de la plus courte chaîne (ou chemin) simple les reliant. Si les sommets ne sont pas reliés, la distance est infinie.

Dans le graphe $A-B-C-D-A$, la chaîne $A-B-C$ a une longueur de 2. La chaîne $A-B-C-D-B$ est une chaîne, mais pas une chaîne simple car le sommet $B$ est répété.

• Cycle (pour graphe non orienté) : Un cycle est une chaîne simple qui commence et se termine au même sommet. La longueur d'un cycle est le nombre d'arêtes qui le composent. Les cycles doivent avoir une longueur d'au moins 3 dans un graphe simple.
• Circuit (pour graphe orienté) : Un circuit est un chemin simple (sauf le premier et le dernier sommet qui sont identiques) qui commence et se termine au même sommet.
• Graphe acyclique : Un graphe est acyclique s'il ne contient aucun cycle (ou circuit).
• Arbre : Un arbre est un graphe non orienté, connexe et acyclique. C'est une structure très importante en informatique.
  • Propriétés d'un arbre à $n$ sommets : il possède exactement $n-1$ arêtes. Il n'y a qu'une seule chaîne simple entre deux sommets quelconques.

La connexité décrit la façon dont les sommets sont "reliés" entre eux.

• Graphe connexe (non orienté) : Un graphe non orienté est connexe si pour toute paire de sommets $S_i, S_j$, il existe au moins une chaîne qui les relie. C'est-à-dire que le graphe "tient en un seul morceau".
• Composante connexe : Si un graphe n'est pas connexe, il peut être divisé en plusieurs composantes connexes. Une composante connexe est un sous-graphe maximal connexe.
• Graphe fortement connexe (orienté) : Un graphe orienté est fortement connexe si pour toute paire de sommets $S_i, S_j$, il existe un chemin de $S_i$ vers $S_j$ ET un chemin de $S_j$ vers $S_i$. La direction des arêtes est cruciale ici.
• Graphe faiblement connexe (orienté) : Un graphe orienté est faiblement connexe si le graphe sous-jacent (obtenu en ignorant l'orientation des arêtes) est connexe.
• Pont (ou isthme) : Dans un graphe non orienté connexe, un pont est une arête dont la suppression rendrait le graphe non connexe.

La matrice d'adjacence est la représentation la plus courante d'un graphe. Pour un graphe à $n$ sommets, c'est une matrice carrée $A$ de taille $n \times n$.

• Construction :
  • Si le graphe est non orienté et simple : $A_{ij} = 1$ si les sommets $S_i$ et $S_j$ sont adjacents, et $A_{ij} = 0$ sinon.
    • La matrice est symétrique ($A_{ij} = A_{ji}$).
    • La diagonale principale est généralement composée de zéros (pas de boucles).
  • Si le graphe est orienté : $A_{ij} = 1$ s'il existe une arête de $S_i$ vers $S_j$, et $A_{ij} = 0$ sinon.
    • La matrice n'est pas nécessairement symétrique.
  • Pour les graphes avec arêtes multiples ou boucles, $A_{ij}$ peut représenter le nombre d'arêtes entre $S_i$ et $S_j$.
  • Pour les graphes pondérés, $A_{ij}$ peut représenter le poids de l'arête (souvent $\infty$ si pas d'arête).

$V = \{1, 2, 3, 4\}$, $E = \{\{1, 2\}, \{1, 3\}, \{2, 4\}, \{3, 4\}\}$

• Interprétation des coefficients : $A_{ij}$ indique la présence ou l'absence d'une arête directe de $S_i$ à $S_j$.
• Propriétés :
  • La somme des éléments d'une ligne (ou colonne) dans un graphe non orienté simple donne le degré du sommet correspondant.
  • Dans un graphe orienté, la somme d'une ligne donne le degré sortant, et la somme d'une colonne donne le degré entrant.

La matrice d'incidence est une autre façon de représenter un graphe, en mettant en relation sommets et arêtes. Pour un graphe à $n$ sommets et $m$ arêtes, c'est une matrice $M$ de taille $n \times m$.

• Construction (graphe non orienté) : $M_{ij} = 1$ si le sommet $S_i$ est incident à l'arête $e_j$. $M_{ij} = 0$ sinon.
  • Chaque colonne d'une matrice d'incidence pour un graphe non orienté simple contient exactement deux '1' (car une arête relie deux sommets).

$V = \{1, 2, 3, 4\}$, $E = \{e_1=\{1, 2\}, e_2=\{1, 3\}, e_3=\{2, 4\}, e_4=\{3, 4\}\}$

• Utilisation : Moins fréquente que la matrice d'adjacence pour les calculs de chemins, mais utile pour des problèmes spécifiques impliquant des relations sommets-arêtes.

C'est là que la matrice d'adjacence révèle toute sa puissance !

• Puissances de la matrice d'adjacence : Soit $A$ la matrice d'adjacence d'un graphe. La matrice $A^k$ (produit matriciel $A \times A \times \dots \times A$, $k$ fois) a une signification particulière : Le coefficient $(A^k)_{ij}$ représente le nombre de chemins (ou chaînes) de longueur $k$ allant du sommet $S_i$ au sommet $S_j$.

Calculons $A^2 = A \times A$ :

• $(A^2)_{11} = 2$ : il y a 2 chemins de longueur 2 de 1 à 1 (1-2-1 et 1-3-1).
• $(A^2)_{14} = 2$ : il y a 2 chemins de longueur 2 de 1 à 4 (1-2-4 et 1-3-4).

Ce calcul est très utile pour trouver des chemins, déterminer la connexité (si $(A+A^2+\dots+A^{n-1})_{ij} \neq 0$, alors $S_i$ et $S_j$ sont connectés), ou même pour des applications comme la propagation d'information.

• Algorithme de Warshall : Cet algorithme permet de déterminer la matrice de chemins (ou matrice de connectivité) d'un graphe, qui indique s'il existe un chemin entre chaque paire de sommets, quelle que soit sa longueur (positive). Il est plus efficace que de calculer toutes les puissances de la matrice d'adjacence.

Ces problèmes historiques sont des classiques de la théorie des graphes.

• Chaîne eulérienne : Une chaîne qui passe par chaque arête du graphe exactement une fois.

• Cycle eulérien : Un cycle qui passe par chaque arête du graphe exactement une fois et qui revient à son sommet de départ.

• Condition d'existence (pour graphe connexe non orienté) :

  • Un graphe connexe admet un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
  • Un graphe connexe admet une chaîne eulérienne si et seulement s'il possède exactement deux sommets de degré impair (ces deux sommets seront les extrémités de la chaîne).
  • Pour les graphes orientés, les conditions sont similaires avec les degrés entrants et sortants.

• Chemin hamiltonien : Un chemin simple qui passe par chaque sommet du graphe exactement une fois.

• Cycle hamiltonien : Un cycle simple qui passe par chaque sommet du graphe exactement une fois (sauf le sommet de départ/arrivée qui est répété).

• Problème du voyageur de commerce (TSP) : C'est un problème célèbre lié aux cycles hamiltoniens. Le but est de trouver le cycle hamiltonien de coût minimal dans un graphe pondéré. C'est un problème très difficile (NP-complet) à résoudre pour un grand nombre de sommets.

C'est l'un des problèmes les plus courants et les plus utiles en théorie des graphes, surtout dans les graphes pondérés.

• Objectif : Trouver le chemin (ou la chaîne) entre deux sommets dont la somme des poids des arêtes est minimale.

• Algorithme de Dijkstra :

  • Permet de trouver le plus court chemin d'un sommet source donné vers tous les autres sommets dans un graphe pondéré avec des poids d'arêtes positifs ou nuls.
  • Principe : Il explore le graphe en "élargissant" progressivement un ensemble de sommets dont la distance minimale par rapport à la source est déjà connue. Il maintient une estimation de la distance minimale pour les autres sommets et la met à jour.
  • Étapes clés :
    1. Initialiser la distance de la source à 0 et des autres sommets à l'infini.
    2. Marquer tous les sommets comme non visités.
    3. Tant qu'il reste des sommets non visités : a. Choisir le sommet non visité avec la plus petite distance actuelle. b. Marquer ce sommet comme visité. c. Pour chaque voisin non visité de ce sommet : calculer la distance potentielle via le sommet actuel et mettre à jour si elle est plus petite.
  • Applications : GPS, routage réseau, etc.

• Algorithme de Bellman-Ford :

  • Permet également de trouver les plus courts chemins d'une source vers tous les autres sommets.
  • Avantage par rapport à Dijkstra : il peut gérer les poids d'arêtes négatifs.
  • Inconvénient : il est plus lent que Dijkstra et ne fonctionne pas s'il y a des cycles de poids négatifs (car un tel cycle permettrait de rendre le chemin arbitrairement court).

Ces concepts sont fondamentaux pour concevoir des réseaux efficaces.

• Arbre couvrant : Pour un graphe connexe non orienté, un arbre couvrant est un sous-graphe qui est un arbre et qui inclut tous les sommets du graphe original. Un graphe peut avoir plusieurs arbres couvrants.
• Arbre couvrant minimal (ACM) : Dans un graphe pondéré connexe non orienté, un arbre couvrant minimal est un arbre couvrant dont la somme des poids des arêtes est la plus petite possible.
• Algorithme de Kruskal :
  • Principe : C'est un algorithme glouton. Il construit l'ACM en ajoutant les arêtes une par une, en commençant par celles de plus petit poids, à condition qu'elles ne forment pas de cycle avec les arêtes déjà choisies.
  • Étapes :
    1. Trier toutes les arêtes par poids croissant.
    2. Initialiser l'ACM avec aucun sommet ni arête.
    3. Parcourir les arêtes triées : si l'ajout de l'arête ne crée pas de cycle dans l'ACM partiel, l'ajouter.
    4. Arrêter quand l'ACM contient $n-1$ arêtes (où $n$ est le nombre de sommets).
• Algorithme de Prim :
  • Principe : Également un algorithme glouton. Il construit l'ACM en "grandissant" un seul arbre à partir d'un sommet de départ arbitraire.
  • Étapes :
    1. Commencer par un sommet arbitraire et l'ajouter à l'ACM.
    2. À chaque étape, ajouter à l'ACM l'arête de plus petit poids qui relie un sommet déjà dans l'ACM à un sommet qui n'y est pas encore.
    3. Répéter jusqu'à ce que tous les sommets soient dans l'ACM.
  • Applications : Conception de réseaux (câblage, fibre optique) pour minimiser les coûts.

Les graphes sont l'outil idéal pour modéliser tout type de réseau.

• Réseaux sociaux : Les sommets sont les personnes, les arêtes représentent les amitiés, les relations, les suivis. Permet d'analyser la centralité, la propagation d'informations, la détection de communautés.
• Réseaux de transport : Les sommets sont les villes/gares/aéroports, les arêtes sont les routes/voies ferrées/lignes aériennes, souvent pondérées par la distance, le temps ou le coût. Utilisé pour la planification d'itinéraires (GPS), l'optimisation des flux.
• Réseaux informatiques : Les sommets sont les ordinateurs/serveurs, les arêtes sont les connexions. Utilisé pour le routage de données, la sécurité réseau.
• Flux et capacités : Dans certains graphes orientés et pondérés, les poids peuvent représenter des capacités maximales de "flux" (par exemple, quantité d'eau dans un tuyau, bande passante). Les algorithmes de flot maximal permettent d'optimiser le transport de ressources.

Les graphes sont essentiels pour planifier et gérer des projets complexes.

• Graphe des tâches : Les sommets représentent les tâches d'un projet, et les arêtes (orientées) représentent les dépendances entre les tâches (une tâche doit être finie avant qu'une autre ne commence). Les poids des arêtes ou des sommets peuvent représenter la durée des tâches.
• Méthode PERT (Program Evaluation and Review Technique) :
  • Utilise un graphe orienté sans cycle (DAG) pour représenter les tâches et leurs dépendances.
  • Permet de déterminer la durée totale minimale du projet et d'identifier le chemin critique.
• Chemin critique : C'est le chemin le plus long dans le graphe des tâches, et donc la séquence d'activités qui détermine la durée minimale du projet. Tout retard sur une tâche du chemin critique retarde l'ensemble du projet.
• Diagramme de Gantt : Bien que non directement un graphe, il est souvent généré à partir des informations obtenues par l'analyse du graphe des tâches pour visualiser le calendrier du projet.

La coloration de graphes est un domaine fascinant avec des applications inattendues.

• Coloration de sommets : Attribuer une "couleur" à chaque sommet de telle sorte que deux sommets adjacents n'aient jamais la même couleur. L'objectif est souvent de minimiser le nombre de couleurs utilisées.
• Nombre chromatique ($\chi(G)$) : C'est le nombre minimum de couleurs nécessaires pour colorer les sommets d'un graphe $G$.
• Applications :
  • Emploi du temps : Les sommets sont les cours, une arête existe si deux cours ne peuvent pas être donnés en même temps (par exemple, même professeur, même salle). Les couleurs sont les créneaux horaires.
  • Allocation de fréquences radio : Les sommets sont les émetteurs, une arête existe si deux émetteurs sont trop proches et interfèrent. Les couleurs sont les fréquences.
  • Problèmes de registres dans les compilateurs : Allocation de ressources informatiques.
• Théorème des quatre couleurs : Un théorème célèbre qui stipule que toute carte géographique peut être colorée avec au plus quatre couleurs de telle sorte que deux régions adjacentes aient des couleurs différentes. Ce fut le premier théorème majeur à être prouvé avec l'aide d'un ordinateur.

J'espère que ces fiches de révision t'aideront à bien comprendre les concepts fondamentaux des graphes. C'est un domaine riche et très pertinent pour de nombreuses applications !