INFO526 : Graphes et algorithmes
Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». 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.
Administration
TD et TP
TD1 : Première feuille de TD TD2 : Deuxième feuille de TD TD3 : Troisième 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...
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 ?