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

Cliques et stables

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.

Chemins et cycles

Projet :

Chemins le plus long

Projets :

Chemins de longueur/poids minimum

Problème et algorithmes

Projets

Arbres

TBD projets/applications Buneman ET MPCI 24-25 TBD X-arbre et représentation combinatoire des arbres par bi-partition. TBD c'est l'ET 2024-2025 TBD évolution arborée et distance d'évolution. Condition des 4-points.

Problèmes de flots

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

Principes et algorithmes

Modélisation

Graphe biparti

Une classe particulières de graphes cruciale :

Couplages

Problèmes de couplage dans un graphe. On passera un peu de temps sur le cas des graphes bi-parti avant d'aborder le cas général.

Colorabilité d'un graphe

Graphes Planaires