INFO505 : algorithmes de graphes
Ce wiki est un complément de cours pour la seconde partie du cours « info-505 : graphes et algorithmes ». Cette seconde partie traite de la partie algorithmique plus que de la partie théorique des graphes. La participation au wiki est fortement encouragée.
Pour pouvoir modifier les pages, inscrivez-vous (lien en haut à droite) pour obtenir un login et mot de passe. (Choisissez un login du style PrenomNom...)
Je vous conseille d'aller lire ce guide pour vous familiariser avec les wikis.
Exercice : si vous n'en avez pas, créez-vous un compte et essayez de modifier cette page (correction de fôtes d'aurtograffe, rajout de détails, mise en page, ...)
Vous pouvez aussi utiliser la page de discussion pour ... discuter. (Ou poser des questions, faire des commentaires etc.)
Administration
TD et TP
Compléments de cours / TD / TP
Références
La partie « Algorithmes sur les graphes » du livre « Introduction à l'algorithmique » de Cormen, Leiserson et Rivest est un bon complément. Il contient des exemples, applications et preuves de certaines propriétés des algorithmes étudiés en cours...
Introduction, quelques dates
Euler, problèmes des ponts de Königsberg (1736), notion de graphe eulérien def : un graphe est eulérien si ... def : un graphe est hamiltonien si ... problèmes de complexité
Kuratowski 1930, notion de graphe planaire, contre exemple : K_5 et K_{3,3}
exemple des maisons et des usines
théorème de Kuratowski
Appel et Haken 1976, théorème des 4 couleurs (preuve par ordinateur)
problématiques de graphes dans les réseaux (Internet, télécommunications, ...)
Graphes et arbres, préliminaires
Définitions
...
- Vocabulaire :
- sommets adjacents
- arêtes adjacentes
- arête incidente
- degré d'un sommets, degré entrant / degré sortant
Arbres
...
Représentation des graphes
listes d'adjacence matrice d'adjacence matrice d'incidence
Question : quelle est la meilleure représentation ?
Parcours de graphes : largeur et profondeur
Parcours en largeur
Principe du parcours
on utilise une file pour les prochains sommets à traiter on garde un tableau d'états pour ne pas parcourir plusieurs fois les sommets (sinon, on risque de faire des boucles et le parcours ne s'arrêtera jamais) on essaie de partir de tous les sommets pour être sûr de parcourir tout le graphe (si par exemple, le graphe est non connexe)
Algorithme
Complexité
complexité en O(n+m) pour des graphes en listes d'adjacence complexité en O(n*n) pour des graphes en matrice d'adjacence
Application
calcul des distances à un sommet donné calcul des distances entre deux sommets donnés tester si un graphe est biparti (pas vu en cours)
Parcours en profondeur
Principe
on pourrait utiliser une pile pour parcourir les sommets, mais c'est plus simple si on écrit un algorithme récursif en plus des états et de la foret couvrante, on garde un « temps de parcours » pour chaque sommet (temps de début et temps de fin)
Algorithme
Complexité
O(n+m) pour des graphes en listes d'adjacence
Application
calcul des composantes fortement connexes dans un graphe orienté (en TP) tri topologique dans un graphe acyclique
Arbres couvrants
-- Nous verrons en fait uniquement l'algorithme de Prim
But : trouver un arbre de poids minimal sur un graphe non-orienté avec des poids sur les arêtes
Algorithme de Prim
Algorithme
on construit un arbre en partant d'un sommet et en rajoutant des arêtes adjacentes
Complexité
O(n*n) pour la variante simple, mais on peut descendre jusqu'à O(m*log(n)) ou même O(m+n*log(n))
Algorithme de Kruskal
Algorithme
on construit un arbre en regroupant petit à petit des des morceaux d'arbre (on part avec un arbre trivial pour chaque sommet)
Complexité
O(n*m) ; mais si on se débrouille bien : O(m*log(n))
¿¿ Chemin optimaux ??
-- Si le temps le permet
Algorithme de Dijkstra
Algorithme de Bellman
¿¿ Flot maximal ??
-- si le temps le permet