Théorie des Graphes

Université de Strasbourg

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.


L3 d'Informatique:
Graphes

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.

Contrôles


L2 de Mathématiques:
Théorie des Graphes

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.

Contrôles


Retour à la page de Christian Ronse / Back to my page