6270 - Théorie des graphes

Description bibliographique

Auteur :

Müller, Didier (Lycée cantonal. Porrentruy. Suisse)

Page source :

Apprendre en ligne : site personnel de D. Müller, http://www.apprendre-en-ligne.net/

Langue :

français

Date de publication :

2003/04/24

Description du contenu

Spécialité :

Sciences exactes - Mathématiques - Mathématiques appliquées

Mots clés :

graphe ; codage ; coloration de Welsh et Powell ; chaîne de Markov absorbante

Table des matières :

I - Graphes non orientés
II - Arbres
III - Arborescences
IV - Problèmes de coloration
V - Graphes orientés
VI - Problèmes de chemins
VII - Chaînes de Markov
Annexes

Résumé :

Ce cours introduit les éléments fondamentaux de la théorie des graphes. On y apprend entre autres à relier plusieurs villes par un réseau routier de coût minimum ; le codage de Huffman qui est une méthode de réduction de la longueur du codage d'un alphabet ; la méthode de coloration de Welsh et Powell ; et quelques applications des chaînes de Markov. Le document est très bien illustré et contient quelques programmes téléchargeables pour faire des animations de graphes, de nombreux exemples et exercices dont les corrigés sont disponibles, (mais seulement après demande d'un mot de passe), ainsi qu'un lexique sur les graphes.

Informations pédagogiques

Niveau d'études :

tous niveaux

Pré-requis :

Posséder des notions de calcul matriciel

Objectifs pédagogiques :

Apprendre à représenter et résoudre un problème à l'aide d'un graphe

Accès à la ressource

Format :

HTML

URL de référence :

http://www.apprendre-en-ligne.net/graphes/

Notice mise en ligne le 01/06/2004