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

-- à venir

Compléments de cours / TD / TP

-- à venir

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)

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 faire du O(m*log(n)) ou même O(m+n*log(n))
(c'est mieux quand il n'y a pas trop d'arêtes dans le graphe)

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(n*log(n))

¿¿ Chemin optimaux ??

-- Si le temps le permet

¿¿ Flot maximal ??

-- si le temps le permet