« INFO526 : Graphes et algorithmes » : différence entre les versions
Aucun résumé des modifications |
|||
| Ligne 12 : | Ligne 12 : | ||
===TD et TP=== |
===TD et TP=== |
||
TD1 : [http://lama.univ-savoie.fr/~provencal/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] |
|||
TD3 : [http://lama.univ-savoie.fr/~provencal/INFO526/INFO526-TD3.pdf Troisième feuille de TD] |
|||
===Compléments de cours / TD / TP=== |
===Compléments de cours / TD / TP=== |
||
[http://lama.univ-savoie.fr/~provencal/INFO526/parcoursLargeur.pdf Algorithme du parcours en largeur] |
|||
-- à venir |
|||
[http://lama.univ-savoie.fr/~provencal/INFO526/parcoursProfondeur.pdf Algorithme du parcours en profondeur] |
|||
===Références=== |
===Références=== |
||
| Ligne 74 : | Ligne 78 : | ||
matrice d'adjacence |
matrice d'adjacence |
||
matrice d'incidence |
|||
Version du 11 octobre 2011 à 09:07
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 ?