Théorie des graphes et optimisation dans les graphes Christine Solnon Table des matières 1 Motivations 3 2 Définitions 4 3 Représentation des graphes 8 3.1 Représentation par matrice d'adjacence . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Représentation par listes d'adjacence . . . . . . . . . . . . . . . . . . . . . . . . 8 4 Cheminements et connexités 10 4.1 Notions de chemin, chaine, cycle et circuit . . . . . . . . . . . . . . . . . . . . . 10 4.2 Fermeture transitive d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . 11 4.3 Notions de connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.4 Notion de graphe eulérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 4.5 Notion de graphe hamiltonien . . . . . . . . . . . . . . . . .
- longueur des routes correspondantes
- parcours en largeur
- sommets successeurs des sommets prédécesseurs
- chemin allant du sommet initial
- applications du parcours en largeur
- arêtes incidents aux sommets
- réseau routier