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

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

1. Je vous conseille d'aller lire ce guide pour vous familiariser avec les wikis.

TD et TP

TD1 : Première feuille de TD

TD2 : Deuxième feuille de TD

TD3 : Troisième feuille de TD

TP : Énoncé des TP

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.

---

---

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 ?