Catégorie : Graphes

Les graphes cordaux

On s’intéresse à une famille de graphes dont les graphes d’intervalles font partis. Il s’agit des graphes cordaux. Tout comme les graphes d’intervalles, on présente un algorithme de coloration pour cette famille. Exercice Un graphe est dit cordal si pour tout cycle de taille supérieur ou égale à 4, il existe une corde. C’est à […]

Les graphes d’intervalles

On sait que le problème de coloration des graphes est difficile. Cependant, il existe certaines familles de graphes pour lequel le problème de coloration est polynomial. C’est le cas pour les graphes d’intervalles que nous étudions ici. Exercice On considère un ensemble d’intervalle fermé $\left(I_k\right)_{k \leq n}$. On appelle graphe d’intervalles associé, noté $G=(A,S)$, le […]

Le problème des 3 couleurs (3-COLOR)

Notre but ici est de montrer que le problème de coloration avec trois couleurs est NP-complet que ce soit dans le cas des graphes planaire ou non planaire. Nous souhaitons le prouver pour le cas des graphes quelconque et pour le cas des graphes planaires. Ces résultats sont dus à Garey, Johnson et Stockmeyer. Dans […]

Formule de Cayley

Exercice La formule de Cayley affirme que pour $n \gt 1$, le nombre $C_n$ d’arbres qu’on peut construire sur $n$ sommets est $n^{n-2}$. Le matrix tree theorem ou théorème de Kirchhoff, déjà présenté en exercice, nous permet de calculer directement cette valeur. $1)$ Prouver la formule de Cayley à l’aide du Matrix Tree Theorem. Une […]

Théorème de Kirchhoff

On présente ici un résultat important de la théorie des graphes pourtant méconnus des étudiants. Le but de cet exercice est de démontrer le théorème de Kirchhoff, aussi appelé matrix tree theorem. Ce théorème donne une formule pour compter le nombre d’arbres couvrants d’un graphe. Cet exercice nécessite une bon maîtrise mathématique de la notion […]