Graphes

Cours BTS

Graphes (graphes.pdf 0,7 M)
Utiliser Acrobat Reader d'Adobe. (Problèmes d'images ou de textes invisibles avec Gv, Ghostview ...)
(ancien cours BTS informatique de gestion)

Terminales ES et BTS.
Exemples et résolution d'exercices sur les graphes.

Coloriage des sommets d'un graphe Encadrement du nombre chromatique (nombre de couleurs nécessaires).

Plus court chemin Algorithme de Dijkstra. Graphe orienté ou non.
Donne les valeurs minimales et les chemins correspondants, pour tous les couples de deux sommets, losqu'un chemin existe.

Plus court chemin, graphe non orienté Algorithme de Dijkstra.
Quelques exemples avec les schémas des graphes.

Graphes probabilistes Présentation à l'aide d'un graphe à 3 sommets (3 états au plus)

Graphes probabilistes - Matrices de transition Toutes dimensions. Indiquer le vecteur P₀ des probabilités des états à l'instant 0 ainsi que la matrice carrée des probabilités de passage d'un état à un autre.
Les calculs des vecteurs P₁, P₂, ... à différents instants sont immédiats.

Cycles eulériens, chaînes

Méthode P.E.R.T. (pour BTS)

Générateur et solveur d'exemples (pour linux mais sûrement adaptable à d'autres OS : utilise sh, awk, latex ...)
Génère un tableau, le diagramme des tâches (sur les sommets), le diagramme GANTT.

README contenu de la distribution (modeste). Mode d'utilisation (texte en français)

Exemple de fichier PostScript produit (70 kb) ExamplePert.ps ou gzippé (20 kb) ExamplePert.ps.gz

pert-AWK.0.1.tar.gz

Autres programmes

Arbres phylogénétiques

Newick vers Dot Conversion d'un arbre parenthésé (treefile du programme PHYLIP) en un fichier au format dot (dot, neato de GRAPHVIZ).

Arbre vers Newick Mise au format parenthésé Newick.

Liens

Page de liens sur les graphes.

Laboratoire Leibniz, Equipe Graphes Un aperçu de la théorie des graphes.

Quelques exemples de thèmes pour des clubs de mathématiques Dont graphes eulériens, hamiltoniens, planaires ...

Königsberg (Webcam)Königsberg : Germany, (now Kaliningrad, Russia)

Problèmes divers

La promenade des demoiselles. Tournoi par paires Comment organiser les rencontres. Indice chromatique d'un graphe complet.

Groupements par quatre d'écoliers (PDF) Résolution d'un problème posé il y a une trentaine d'années par un enseignant qui désirait répartir ses élèves par groupes de quatre.

Couplages d'un graphe biparti Problèmes d'affectations. Former les couples en tenant compte des préférences.