Références.
Arnold A., Guessarian I., Mathématiques pour
l'Informatique, 4e édition, ÉdiScience, 2005.
Berge C., Graphes, 2e édition, Dunod, 1973.
Cormen T.H., Leierson C.E., Rivest R.L., Stein C., Introduction to
Algorithms, 2nd edition, 6th printing, MIT Press, 2005.
Durée: 20h cours et 14h TD
Contenu. Graphes orientés et non-orientés: adjacence, degré, voisinage, chaînes (chemins) et cycles (circuits). Composantes (fortement) connexes. Graphes eulériens. Arbres et arborescences. Algorithmes sur les graphes: parcours en largeur, composantes connexes, distances; parcours en profondeur, tri topologique, composantes fortement connexes; arbres couvrants; recherche de plus courts chemins. Flots maximaux.
Quelques exercices de TD. — Notes manuscrites de cours.
Durée: 10h cours et 10h TD
Contenu.
Graphes orientés et non-orientés: adjacence,
degré, voisinage, chaînes (chemins) et cycles
(circuits). Composantes (fortement) connexes. Graphes
eulériens. Arbres et arborescences. Algorithmes sur les
graphes: parcours en largeur, composantes connexes, distances;
parcours en profondeur, tri topologique, composantes fortement
connexes. Couplages dans les graphes bipartis, combinaisons
pondérées de couplages.
Contents. Oriented and non-oriented graphs:
adjacency, degree, neighbourhood, chains (paths) and cycles
(circuits). (Strongly) connected components. Eulerian graphs. (Rooted)
trees. Algorithms on graphs: breadth-first traversal, connected
components, distances; depth-first traversal, topological sorting,
strongly connnected components. Couplings in bipartite graphs,
weighted combinations of couplings.