« 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 12 : | Ligne 12 : | ||
#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.--> |
||
| Ligne 21 : | Ligne 18 : | ||
TD1 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD1.pdf Première feuille de TD] |
TD1 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD1.pdf Première feuille de TD] |
||
<!-- |
|||
TD2 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD2.pdf Deuxième feuille de TD] |
TD2 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD2.pdf Deuxième feuille de TD] |
||
| Ligne 26 : | Ligne 24 : | ||
TP : [http://www.lama.univ-savoie.fr/~provencal/INFO526/html/index.html Énoncé des TP] |
TP : [http://www.lama.univ-savoie.fr/~provencal/INFO526/html/index.html Énoncé des TP] |
||
--> |
|||
===Compléments de cours / TD / TP=== |
===Compléments de cours / TD / TP=== |
||
| Ligne 43 : | Ligne 41 : | ||
* (Cours 1): mercredi 12 septembre. Graphes (vocubulaire et définitions de bases), degré et adjacence, isomorphie de graphes. |
* (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. |
|||
Version du 21 septembre 2012 à 08:49
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 ?