« INFO526 : Graphes et algorithmes » : différence entre les versions
Aller à la navigation
Aller à la recherche
Aucun résumé des modifications |
Aucun résumé des modifications |
||
| Ligne 7 : | Ligne 7 : | ||
<!-- Ce wiki est un complément de cours pour le cours « info-526 : graphes et algorithmes ». La participation au wiki est fortement encouragée. |
<!-- 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''...) |
#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 [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis. |
#Je vous conseille d'aller lire [http://meta.wikimedia.org/wiki/Aide:Contenu ce guide] pour vous familiariser avec les wikis.--> |
||
Version du 21 septembre 2012 à 08:44
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
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 ?