Théorie des graphes

Cette introduction a pour but d'exposer quelques définitions, concepts et méthodes de résolution de problèmes propre aux graphes.

Il a pour principal objectif d'allumer la petite flamme de l'intérêt pour cette structure, à la fois riche en problèmes intéressants et en solutions élégantes ; à la fois théorique — à l'intersection des mathématiques discrètes et de l'informatique théorique — et au cœur de nombre d'applications de tous les jours.

Le cours va être séparé en petites entités qui se suivent pour former un tout que l'on espère cohérent.

Structure d'un graphe

1. Structure d'un graphe
2. Encodage de graphes
3. Chemins, cycle et connexité

Parcours

Un parcours d'un graphe est une suite de sommets ou d'arêtes ayant un propriété donné. On en verra plusieurs types ayant chacun leur propre intérêt.

Types de parcours

1. Largeur et profondeur
2. Eulérien
3. Hamiltonien

Projets

1. Mots de Bruijn
2. Problème du postier chinois

Chemins de longueur/poids minimum

Problème et algorithmes

1. Chemin de poids minimum
2. Algorithme de Dijkstra et $A^\star$
3. Algorithmes généraux

Projets

1. Projet chemins de poids minimum
2. Projet graphe géographique
3. Projet chemins avec hubs

Problèmes de flots

Problèmes de flots. Définition, algorithmes et applications

Principes et algorithmes

1. Les problèmes de flots
2. connectivité

Projets

1. exercices de modélisation
2. bataille de la marne

Arbres

TBD : mettre chemin au-dessus

Un cas particulier d'intérêt : l'arbre et les chemins.

Sous la forme d'exercices.

1. arbre planté algorithmique arborescence du parcours en largeur/profondeur + propriétés ?
2. arbre et graphe
3. arbres binaires de recherche
4. chemins et arborescences

TBD
combien d'arbre ? Encodage prüfer et application à un arbre aléatoire (!= différent de la structure).