Théorie des graphes

Ce cours est un premier aperçu de la théorie des graphes. On y présente des propriétés simples des graphes orientés et non-orientés: connexité,chemin,cycles,graphes hamiltoniens et eulériens,graphes planaires,arbres couvrants,arbres des plus courts chemins,et comment vérifier ces propriétés. On y présente également le problème classique de la coloration. Quelques algorithmes sont également expliqués.

Mots-clés : algorithme,graphe orienté,graphe non orienté,arbre,plus court chemin,chaîne de Markov,fuscia
Type de ressource : lecture,exercise
Niveau : enseignement secondaire,bac+1
Publics visés : learner
Proposition d'utilisation : Ce cours s'adresse à un large public, niveau lycée (terminale) minimum. Les corrigés des exercices sont disponibles sur simple demande auprès de l'auteur.
Auteurs ou éditeurs : Didier Müller,Institut National de Recherche en Informatique et en Automatique