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 :

Soit G un graphe simple biparti régulier de degré k>0. Montrer que G admet un couplage parfait.

 

Remarque : ce résultat est connu sous le nom de « théorème des mariages ». Il permet de résoudre des problèmes relatifs à la notion de « rencontre » tel que l’offre et la demande d’emploi.

Exemple : si dans l’ensemble des clients d’une agence de rencontre, chaque homme est compatible avec k femmes, et inversement chaque femme est compatible avec k hommes, alors il existe un couplage parfait des hommes et des femmes.

 

EXERCICE VI : (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.