1. Notions Fondamentales

• Définitions : Un graphe est constitué de sommets (ou nœuds) et d’arêtes (ou liens) qui les relient. Les graphes peuvent être orientés (les arêtes ont une direction) ou non orientés.
• Propriétés : Les graphes peuvent avoir des cycles (chemins qui reviennent à un sommet) ou être acycliques (sans cycles).

2. Coloration d’un Graphe

• Objectif : Assigner des couleurs aux sommets de manière à ce que deux sommets adjacents n’aient pas la même couleur. Cela a des applications dans la planification et l’optimisation.

3. Représentation des Graphes

• Matrice d’Adjacence : Une matrice carrée où chaque cellule indique la présence ou l’absence d’une arête entre deux sommets. C’est efficace pour les graphes denses.
• Liste de Successeurs : Chaque sommet est associé à une liste de ses voisins. Cela est plus efficace pour les graphes clairsemés.

4. Chemins et Cycles

• Chemins : Une séquence de sommets où chaque paire de sommets adjacents est reliée par une arête.
• Cycles : Un chemin qui commence et se termine au même sommet.
• Graphes Eulériens : Contiennent un cycle qui passe par chaque arête exactement une fois.
• Graphes Hamiltoniens : Contiennent un cycle qui passe par chaque sommet exactement une fois.

5. Parcours de Graphe

• BFS (Breadth-First Search) :Fonctionnement : Explore les sommets couche par couche. Commence par un sommet initial, explore tous ses voisins, puis passe aux voisins des voisins.
• Utilisation : Trouver le chemin le plus court dans un graphe non pondéré.
• DFS (Depth-First Search) :Fonctionnement : Explore aussi loin que possible le long d’une branche avant de revenir en arrière. Utilise une pile (ou récursion).
• Utilisation : Identifier des cycles et des composantes connexes.

6. Recherche des Plus Courts Chemins

• Dijkstra :Fonctionnement : Utilise une approche gloutonne. À chaque étape, il choisit le sommet non marqué avec la distance la plus courte depuis le sommet de départ. Il met à jour les distances des sommets voisins.
• Limites : Ne fonctionne pas bien dans des situations en temps réel avec de nombreux sommets.
• Algorithme A* :Fonctionnement : Améliore Dijkstra en utilisant une heuristique pour estimer la distance jusqu’à l’arrivée. À chaque étape, il choisit le sommet ayant le coût total le plus bas (distance actuelle + estimation).
• Heuristiques :Admissible : Ne surestime jamais la distance réelle.
• Consistante : La distance estimée d’un sommet à l’arrivée est toujours inférieure ou égale à la somme de la distance d’un sommet à un voisin et de la distance estimée de ce voisin à l’arrivée.

7. Applications Pratiques

• Intelligence Artificielle : Utilisation des algorithmes de recherche de chemins dans des jeux vidéo et des robots autonomes.
• Planification en Robotique : Exemples comme le robot Curiosity sur Mars, qui utilise des algorithmes pour naviguer sur le terrain.

8. Algorithme Minimax

• Objectif : Utilisé dans les jeux à deux joueurs pour déterminer le meilleur coup. Chaque joueur essaie de maximiser son score tout en minimisant celui de l’adversaire.
• Élagage Alpha-Bêta : Technique pour réduire le nombre de nœuds évalués dans l’arbre de décision, rendant l’algorithme plus efficace.

1. Arbres et Arborescences

• Définition d’un Arbre :Un graphe non orienté est un arbre s’il est connexe et sans cycle.
• Conditions équivalentes :Possède ( n-1 ) arêtes pour ( n ) sommets.
• En ajoutant une arête, un cycle est créé.
• En supprimant une arête, le graphe devient non connexe.
• Il existe un unique chemin entre deux sommets.
• Feuilles : Un sommet de degré 1 est appelé une feuille. Dans l’exemple donné, les sommets A, D, F, et G sont des feuilles.
• Arborescence :Un graphe orienté avec une source unique (racine) et un chemin unique de la racine à chaque autre sommet.
• Une arborescence de ( n ) sommets a exactement ( n-1 ) arcs.

2. Propriétés des Arborescences

• Circuits : Une arborescence ne peut pas contenir de circuits.
• Prédécesseurs : Chaque sommet (sauf la racine) a un unique prédécesseur.
• Chemins : Il existe au plus un chemin entre deux sommets.

3. Optimisation dans les Graphes Pondérés

• Arbres Couvrants de Poids Minimum (ACPM) :Problématique : À partir d’un graphe connexe pondéré, construire un sous-graphe connexe de poids total minimum.
• Applications : Réseaux de communication, construction de routes, etc.

4. Algorithme de Kruskal

• Principe :Commence avec un graphe vide.
• Sélectionne les arêtes par ordre de poids croissant.
• Ajoute une arête si elle ne crée pas de cycle.

1. Étapes :Créer un arbre vide ( A ).
2. Trier les arêtes par poids.
3. Pour chaque arête, vérifier si son ajout crée un cycle.

• Complexité : ( O(E \log E) ), où ( E ) est le nombre d’arêtes.

5. Algorithme de Prim

• Principe :Commence avec un sommet et construit progressivement un arbre en ajoutant le sommet le moins coûteux à connecter.

1. Étapes :Créer un graphe vide ( A ).
2. Choisir un sommet initial et le marquer.
3. Ajouter le sommet non marqué le moins coûteux à ( A ) jusqu’à ce que tous les sommets soient connectés.

• Représentation : Utiliser des listes d’adjacence pour une efficacité optimale.

6. Exemples d’Applications

• Installation de Câbles : Optimiser le réseau de câbles pour minimiser la longueur totale.
• Réseaux Cyclables : Construire un réseau de pistes reliant plusieurs villages.

1. Problèmes de Flots

• Définition : Les problèmes de flots concernent la circulation de biens ou de flux physiques dans un réseau. Ils sont souvent modélisés à l’aide de graphes orientés, où les sommets représentent des points de transit (comme des sources et des puits) et les arêtes représentent les capacités de circulation.

2. Graphe de Flots

• Caractéristiques :Sans boucle : Le graphe ne doit pas contenir de cycles.
• Connexe : Tous les sommets doivent être accessibles.
• Orienté et pondéré : Les arêtes ont des capacités qui représentent le maximum de flux pouvant passer par elles.
• Source et Puits : Un sommet source (s) d’où le flux sort et un puits (p) où le flux arrive.

3. Flots

• Flot : Une fonction qui associe à chaque arc une quantité de flux positive.
• Flot entrant et sortant : Le flot entrant en un sommet est la somme des flots entrants, tandis que le flot sortant est la somme des flots sortants.
• Débit total : La quantité de flux sortant de la source, qui est la valeur du flot.

4. Flots Réalisables

• Conditions :Respect des capacités : Le flot sur chaque arc ne doit pas dépasser sa capacité.
• Conservation de Kirchhoff : Pour tout sommet autre que la source et le puits, le flot entrant doit être égal au flot sortant.

5. Problème du Flot Maximum

• Objectif : Déterminer la quantité maximale de flux pouvant être transportée du sommet source au sommet puits.
• Graphe Résiduel : Indique les arcs sur lesquels le flot peut être augmenté ou diminué tout en maintenant un flot réalisable.

6. Algorithme de Ford-Fulkerson

• Principe :Commence avec un flot nul ou réalisable.
• Tant qu’un chemin augmentant est trouvé, le flot est modifié sur ce chemin.
• Recherche de Chemins Augmentants : Utilisation d’un algorithme de recherche (comme BFS) pour trouver des chemins de la source au puits.

7. Applications des Problèmes de Flots

• Réseaux de Transport : Utilisés pour modéliser des systèmes comme les pipelines, les réseaux électriques, et la circulation de biens.
• k-Arête-Connexité : Mesure de la résistance d’un réseau aux coupures d’arêtes.
• Couplage dans un Graphe Biparti : Utilisé pour des problèmes d’affectation, comme l’affectation de personnes à des tâches.

8. Exemples d’Applications

• Problèmes d’Offre et de Demande : Modélisation de la circulation de produits d’un ensemble de sources à un ensemble de puits.
• Optimisation des Coûts : Trouver des chemins de coût minimum dans un réseau.