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

IV. Couplage

                                            

 

 

Définition 1 : (Rappel) Soit G=(S,A) un graphe simple. On appelle bipartition de G la donnée d’une partition de S en deux sous-ensembles X et Y telle que toute arête de G a l’une de ses extrémités dans X et l’autre dans Y. Si G admet une bipartition on dit qu’il est biparti.

 

Définition 2 : On appelle graphe biparti complet un graphe simple biparti G=(S,A)  de bipartition {X,Y} avec X={s₁, s₂, … ,s_n} , Y={s_n+1, s_n+2, … , s_2×n} et s_is_jA si et seulement si s_iX et s_jY pour tout i≠j).

 

 

Définition 3 : Soit G=(S,A) un graphe simple. Un couplage C=(T,B) de G est un sous-graphe de G régulier de degré 1 (1-régulier),(en d’autres termes B est un sous-ensemble d’arêtes non adjacentes).

 

Remarque 1 : Soit G=(S,A) un graphe biparti de bipartition {X,Y}. Dire que G admet un couplage c’est dire qu’il existe deux parties UX et VY telles que tout sommet de U est adjacent à un et un seul sommet de V, ce qui implique que |U|=|V|. On dit que U est couplé à V.

 

Définition 4 : Soit C=(T,B) un couplage d’un graphe simple G=(S,A) et XS. On dit que C sature un sommet s de S si d_C(s)=1 (où d_C(s) est le degré de s dans C).On dit que C sature XS si C sature tout sommet de X. Si C sature S on dit que le couplage C est parfait.

 

Définition 5 : Une chaîne c d’un graphe simple G=(S,A)  est dite alternée relativement au couplage C=(T,B) si les arêtes de c sont alternativement dans A\B et dans B.

 

Définition 6 : Soit G=(S,A) un graphe biparti de bipartition {X,Y} et soit UX. On note V(U) l’ensemble des voisins de U (C’est l’ensemble des sommets de Y adjacents à au moins un sommet de U). On appelle déficience de U le nombre : def(U)= |U| - |V (U)|. Un sous-ensemble U est dit non déficient s’il n’admet aucune partie (non vide) ayant une déficience positive. (Il est dit déficient dans le cas contraire).