Précédent / Suivant / Table des matières

 

 

 

 

EXERCICE I :

Dans le graphe ci-contre :

  a) trouver deux couplages
  b) trouver un couplage parfait

  b) donner un couplage à 3 arêtes et une chaîne alternée relativement à ce couplage.

 

EXERCICE II :

Montrer que le graphe complet K_2n (à 2n sommets) admet un couplage parfait.

 

EXERCICE III :

Soit G un graphe simple d’ordre n. Montrer que si G admet un couplage parfait alors n est pair.

 

EXERCICE IV :

Soit G=(S,A) un graphe biparti complet de bipartition {X,Y}.
  a) Montrer que G admet un couplage parfait

  b) Quel est le nombre couplages parfaits de G ?

 

EXERCICE V : (travail personnel facultatif)

Etudier l’algorithme de Ford-Fulkerson et écrire, dans votre langage favori, un programme de recherche de couplage dans un graphe biparti.