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

• TD1 : représentation et parcours en largeur

• TP1 : préliminaires, parcours en largeur et résolution de labyrinthe

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)

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)

Arbres couvrants

-- Nous verrons soit Kruskal, soit Prim

¿¿ Chemin optimaux ??

-- Si le temps le permet

¿¿ Flot maximal ??

-- si le temps le permet