INFO526 : Graphes et algorithmes

Module INFO526 Graphes et Algorithmes

Cours du semestre 5 de la licence STIC INFO.

• Responsable pour 2012--2013: Xavier Provençal.
• Xavier Provençal (C/TD/TP), Pierre-Étienne Meunier (TP).

TD et TP

TD1 : Première feuille de TD

Compléments de cours / TD / TP

Algorithme du parcours en largeur

Algorithme du parcours en profondeur

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...

Déroulement (2012-2013)

• (Cours 1): mercredi 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes.
• (Cours 2): mardi 18 septembre. Lemme des poignées de mains, représentations de graphes (listes VS matrice), composantes connexes.
• (TD 1): mercredi 19 septembre. Représentation de graphes, propriétés élémentaires de graphes, modélisation par des graphes.

---

---

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

Question : quelle est la meilleure représentation ?