Embed Size (px)
Citation preview
Partie 1
Marie-Christine Costa
ENSTA-UMA-CEDRIC-Paris
Optimisationdans lesGraphes
2014-2015 MPRO - OG
Marie-Christine Costa, Cédric Bentz, Christophe Picouleau
2
Avertissement
Ce polycopié est celui de la vidéo-projectionutilisée en cours. Il est incomplet et ne peutremplacer l'assistance aux cours.
Les démonstrations et les corrigés des exercicesseront faits au tableau.
Sauf indication contraire, les graphes considérés,G=(V,E), sont des graphes simples, sans boucle,non orientés et comportant au moins un sommet.
3
PLAN0. Quelques définitions de théorie des graphes
1. Connectivité et coupes• Quelques propriétés
• Connectivité
• Coupes
2. Couplages et facteurs• Quelques propriétés
• Couplages dans les graphes bipartis
• Couplages, couvertures et stables
0
Quelques définitions de lathéorie des graphes
à connaître avant le débutdu cours
5
Graphe orienté ou DigraphUn graphe orienté G = (V,E) est défini par:
-un ensemble V dont les éléments sont appelés sommets-un ensemble E, E VxV, dont les éléments sont appelés arcs
x est appelé extrémité initiale de l'arc (x,y) (on pourra noter xy quand il n'y a pas d'ambiguïté)y est appelé extrémité terminale de l'arc (x,y)
Successeur: à tout sommet x de V on associe, par l'application multivoque G, l'ensemble de ses successeurs G(x), c.a.d. des sommets qui sont extrémitéterminale d'un arc dont x est extrémité initiale. On peut définir G=(V,G).
Chemin: séquence d'arcs de E telle que l'extrémité terminale d'un arc coïncide avec l'extrémité initiale de l'arc suivant (sauf, éventuellement, pour ledernier).
Circuit: chemin dont le premier sommet coïncide avec le dernier
chemin (resp. circuit) hamiltonien: chemin (resp. circuit) qui passe une fois et une seule par chaque sommet.
chemin (resp. circuit) eulérien: chemin (resp.) circuit qui passe une fois et une seule par chaque arc.
arête: arc "sans orientation", paire de sommets notée en général [x,y] (on pourra noter xy quand il n'y a pas d'ambiguïté)
Graphe non orienté: G= (V,A) t.q. A est un ensemble d'arêtes.
Voisin: à tout sommet x de V on associe, par l'application multivoque N, l'ensemble de ses voisins N(x), c.a.d. des sommets qui sont extrémité d'une arêtedont x est l'autre extrémité. On peut définir G=(V,N).
Chaîne séquence d'arêtes (resp arcs) telle que toute arête (resp arc) a une extrémité commune avec l'arête (resp arc) précédente (excepté la première) etl'autre avec l'arête (resp arc) suivante (excepté la dernière).
Cycle: chaîne dont les deux extrémités coïncident (et qui ne passe pas 2 fois par la même arête). En général on considère qu'un cycle ne passe pas 2 fois parle même sommet.
Connexité: un graphe est connexe si toute paire de sommet est reliée par une chaîne au moins.
Forte connexité: un graphe orienté est fortement connexe si entre tout couple (x,y) de sommets il existe un chemin de x à y (et donc aussi de y à x).
6
Sous-graphe induit: G' est un sous-graphe de G=(V,E) si G'=(V',E') avec V' V et E' E et les arcs de E' sont les arcs de E qui ont leurs 2 extrémités dansV'. (Il s'obtient en supprimant certains sommets et les arcs dont une extrémité au moins a été supprimée).
Graphe partiel: G" est un graphe partiel de G=(V,E) si V"=V et E" E. (Un graphe partiel s'obtient en supprimant certains arcs). On peut considérer dessous-graphes partiels obtenus en supprimant des sommets et des arcs.
P propriété maximale (resp. minimale) pour un ensemble B A: Il n'existe pas C A tel que B C (resp C B) et C vérifie P
Composante connexe (resp. f-connexe) de G: sous-graphe connexe (resp f-connexe) maximal (c.à.d. non inclus dans un autre sous-graphe connexe).
Un arc est incident intérieurement à son extrémité terminale et incident extérieurement à son extrémité initiale.
Degré: d(x)=nombre d'arcs (ou d'arêtes) incidents à xDemi-degré intérieur (resp extérieur): d-(x) (resp d+(x)) = nombre d'arcs incidents intérieurement (resp extérieurement) à x.
Graphe réduit : étant donné un graphe G=(X,E), on appelle graphe réduit de G le graphe Gr=(Fr,Er) où Fr est l'ensemble des composantes fortementconnexe de G (Fr = {C1, C2, ..,Cn}) et où (Ci,Cj) Er si et seulement si il existe un sommet a de Ci et un sommet b de Cj tels que (a,b) E.
Graphe complet Kn=(V,E): x V et y V, (x,y) E
Graphe biparti G= (V,E)= (X,Y,E) tel que V=X Y et si (x,y) E alors, x X et y Y.
Graphe biparti complet Knn=(X,Y,E): x X et y Y, (x,y) E
Théorème d’EulerUn multigraphe connexe G admet une chaîne eulérienne si et seulement si le nombre de sommets de degré impair est 0 ou 2.
Fermeture transitive de G=(V,E) t(G)=(V,t(E)) tel que pour tout (x,y) V2: (x,y) t(E) il existe un chemin de x à y dans G
Ensemble stable de G = (V, G) S V tel que deux sommets distincts de S ne sont jamais adjacents, soit si N(S) S = .
Clique de G Sous-graphe G' de G tel que tous les sommets de G' sont reliés 2 à 2
7
Graphe planaire il est possible de le représenter sur un plan de sorte que deux arêtes ne se rencontrent pas en dehors de leurs extrémités.
Théorème de Kuratowski Un (multi)graphe est planaire si et seulement si il n'admet pas comme sous-graphe partiel un graphe réductible à K5 ou ungraphe réductible à K3,3. (K5 graphe complet de 5 sommets. K3,3 graphe biparti complet de 3+3 sommets).
Formule d’Euler Dans un graphe planaire connexe possédant n sommets, m arêtes et f faces, on a n - m + f = 2
Nombre chromatique de G g(G), le plus petit nombre de couleurs nécessaires pour colorier les sommets de G de sorte que 2 sommets adjacents nesoient pas de même couleur.
Arbre H est connexe et sans cycle ; admet n-1 arêtes ; en ajoutant une arête on crée un et un seul cycle ;si on supprime une arête quelconque, il n'est plus connexe ; tout couple de sommets est relié par une chaîne et une seule
Racine d’un graphe orienté: sommet r tel qu'il existe un chemin de r à tout autre sommet du graphe.
Arborescence arbre orienté muni d'une racineil existe un sommet r qui est relié à tout autre sommet par un chemin unique ; il existe un sommet r tel que d-(r)=0 et d-(x)=1 pour tout x ≠ r
Line graph (graphe dual, graphe aux arêtes) d'un graphe G=(V,E): L(G)=(E,A): les sommets de L(G) sont les arêtes de G et une arête de L(G) relie 2arêtes adjacentes de G.
Couplage Ensemble d'arêtes disjointes Couplage parfait: couplage qui sature tous les sommets Arête saturée: arête du couplage
Chaîne alternée Chaîne dont les arêtes sont alternativement saturée et non saturée. Chaîne alternée augmentante a ses deux extrémités non saturées.
Transfert le long d'une chaîne alternée pour un couplage M échange le long de cette chaîne entre les arêtes du couplage et celles hors du couplage
Couverture des arêtes par les sommets (vertex cover) : sous-ensemble C de sommets tel que chaque arête a au moins une extrémité dans C.
Couverture des sommets par les arêtes (edge cover): sous-ensemble d'arêtes A tel que tout sommet est extrémité d'une arête de A.
Algorithmes à connaître : Décomposition en composantes connexes ou fortement connexes, Mise en ordre (ou niveau), Recherche de chemins min ou max,flot et coupe (Ford-Fulkerson), arbre couvrant.
Bibliographie :
Graphes C. Berge DunodIntroduction to graph theory West Prentice HallGraphes et algorithmes Gondran et Minoux Eyrolles
8
d(G) = degré min de G = min{d(x), xV}D(G) = degré max de G = max{d(x), xV}
a(G) = cardinal maximal d'un stable de G
n (G) = cardinal maximal d'un couplage de G
t(G) = cardinal minimal d'une couverture des arêtes par lessommets ou transversal ou "vertex cover" de G
r(G) = cardinal maximal d'une couverture des sommets par lesarêtes ou "edge cover" de G
c(G) = cardinal maximal d'une coloration des sommets de G
w(G) = cardinal maximal d'une clique de G
Notations (Schrijver)
9
G =(V,E) et si ambigüité G =(V(G),E(G)) ou G=(VG,EG)
Eventuellement, par abus, G pourra désigner soit V soit E et onpourra noter pour, XE, G-X = le sous-graphe induit par V-X.
Sauf indication contraire, les graphes considérés sont des graphessimples, sans boucle, non vide (V>0) et en général, non orientés.
Notations suite
1
Connectivitéet
Coupes
11
Graphe k-régulier G t.q. d(G) = D(G) = k
Proposition 1.1.1 Tout graphe a un nombre pair desommets de degré impair.
Corollaire Le nombre de sommets d'un graphe régulier de degréimpair est pair.
Proposition 1.1.2 Tout graphe comprend une chaîne delongueur supérieure ou égale à d(G)
Corollaire Si d(G)≥2 alors G contient un cycle de longueursupérieure ou égale à d(G)+1
1.1 Quelques propriétés
12
"Pigeon hole principle" (généralisé)Si un ensemble partitionné en n classescontient au moins kn+1 éléments alorsl'une des classes contient au moins k+1éléments.
Proposition 1.1.3 Tout graphe simple d'au moins 2sommets a au moins 2 sommets de même degré.
Proposition 1.1.4 Le nombre maximal d'arêtes d'ungraphe sans triangle est
4
2n
13
Graphe r-parti G=(V,E) tel que V peut être partitionné enr ensembles stables V1,…,Vr .
Graphe de Turàn Tn,r : graphe r-parti complet de nsommets avec b parties de taille a+1 et r-b parties de
taille a avec a = et b=n-ra
r
n
T8,3
14
Théorème de Turàn Tn,r est le graphe qui a le plusd'arêtes parmi les graphes simples d'ordre n, sans cliquede taille r+1.
Si G sans clique de taille r+1, G admet au plusn2 (r-1)/2r arêtes.
15
Graphe biparti
Proposition 1.1.5 G est un graphe biparti G n'admet pas de cycle impair
16
Graphe biparti
Proposition 1.1.5 G est un graphe biparti G n'admet pas de cycle impair
hyper-cube
n-cube Qn
cycle pair
arbre
17
Graphe biparti
Proposition 1.1.5 G est un graphe biparti G n'admet pas de cycle impair
Proposition 1.1.6 G est un graphe biparti La matrice d'incidence de G est TU
cycle pair
arbre
hyper-cube
n-cube Qn
18
Rappel G est connexe si toute paire de sommets de G est reliée parune chaîne. Composantes connexes: sous-graphes connexesmaximaux de G.
Proposition 1.2.1 G graphe simple d'ordre n vérifiantd(G) ≥ (n-1)/2 G connexe
RemarqueIl existe des graphes non connexes tels que
1.2 Connectivité
12
)(
nG
19
Ensemble d'articulation de G=(V,E) connexe: AV tel que le sous-graphe induit par V-A n'est plus connexe. Point d'articulation:sommet d'un ensemble d'articulation de cardinal 1.
k-connexité G (non complet) est k-connexe si toutensemble d'articulation admet au moins k sommets
Connectivité de G connexe :k(G) = minA{ensembles d'articulation}|A| si G non completk(G) = n-1 si G completet G non connexe k(G) = 0
Proposition 1.2.3 G connexe k(G) ≤ d(G)
20
Soit un réseau représenté par un graphe. Les nœuds (ousommets) peuvent tomber en panne.
Question:
Comment construire le graphe de n sommets et m arêtesle plus "solide" possible ? (solide = ayant uneconnectivité maximale)
ou
Comment construire un graphe de n sommets et deconnectivité k ayant le plus petit nombre d'arêtespossible?
21
Théorème de Harary La connectivité maximale d'ungraphe connexe de n sommets et m arêtes est:
n
m2*
H8,4 H9,5
H8,5
16m
20m
23m
Hn,k*
22
Théorème de Harary (bis) Le nombre minimum d'arêtesd'un graphe k-connexe est:
2*
nkm
H8,4 H9,5
H8,5
16m
20m
23m
Hn,k*
23
l(x,y) nombre maximal de chaînes sommets-disjointesreliant x à y.
k(x,y) cardinal du plus petit ensemble d'articulation quisépare x et y.
Théorème de Menger Si x et y sont non adjacents alorsl(x,y) = k(x,y)
24
Rappel Soit G=(V,E) connexe. FE est un ensemble déconnectantsi G'=(V,E-F) n'est pas connexe. Soient SV et TV t.q. ST=alors on note [S,T] l'ensemble des arêtes de E ayant une extrémitédans S et l'autre dans T.
Coupe: CE, C=[S,V-S], S≠, SV
Arête-connectivité de Gk' (G) = cardinal minimal d'une coupe de G
k'G (x,y) = cardinal minimal d'une coupe séparant x de y
1.3 Coupes
25
Théorème de Whitney k (G) ≤ k' (G) ≤ d (G)
(G) = k' (G) = d (G) si:• G est complet• G est biparti complet• G est un hypercube• G est graphe de Harary
26
(G) = k' (G) = d (G) si G est graphe de Harary
H8,4
16m
27
Line graph d'un graphe G=(V,E): L(G)=(E,A): lessommets de L(G) sont les arêtes de G et une arête deL(G) relie 2 arêtes adjacentes de G.
Tout graphe n'est pas un Line graph. Reconnaître si ungraphe est un Line graph est facile. Excepté pour letriangle, l'antécédent d'un Line graph est unique.
"Line graph" (graphe dual) et connectivité
28
"Line graph" (graphe dual) et connectivité
b
a
c
d
fx
e
y
G
29
"Line graph" (graphe dual) et connectivité
b
a
c
d
f
s
x
e
y
t
lG (x,y) = lG' (x,y) et k'G (x,y) = k'G' (x,y)
G'
30
"Line graph" (graphe dual) et connectivité
xa
xd
ad
ab
de
bd
cd
cf
ef
fy
ey
yt
sx
bc
xb
b
a
c
d
f
s
x
e
y
t
G'
L(G')
31
"Line graph" (graphe dual) et connectivité
xa
xd
ad
ab
de
bd
cd
cf
ef
fy
ey
yt
sx
bc
xb
b
a
c
d
f
s
x
e
y
t
G'
L(G')
32
"Line graph" (graphe dual) et connectivité
xa
xd
ad
ab
de
bd
cd
cf
ef
fy
ey
yt
sx
bc
xb
b
a
c
d
f
s
x
e
y
t
(Relation utile pour prouver les propriétés suivantes)
G'
L(G')
33
"Line graph" (graphe dual) et connectivité
Soient G=(V,E) et deux sommets x et y de V.Soit G' = (V',E') avec V'=V{s,t} et E'=E {sx,yt}.
lG (x,y) = lG' (x,y) et k'G (x,y) = k'G' (x,y)
Soit L(G') le Line graph de G'.
Une coupe de G séparant x de y correspond à unensemble d'articulation de L(G') séparant sx de ty
Des chaînes arêtes-disjointes de G reliant x et ycorrespondent à des chaînes sommets-disjointes de L(G')reliant sx et yt.
l'G (x,y) = lL(G') (sx,ty) et k'G (x,y) = kL(G') (sx,ty)
34
Théorème de Ford-Fulkerson
Soient s et t deux sommets d'un graphe G.
La cardinalité d'une coupe minimale de G séparant s et test égale au nombre maximal de chaînes arêtes-disjointesreliant s et t.
Si G est un graphe orienté dont les arcs sont valués:La capacité d'une coupe minimale de G séparant s de t estégale à la valeur d'un flot maximal de s à t.
Rappel: capacité d'une coupe [S,T] = somme des valeurs des arcs de la coupe.
35
Isthme (cut edge)
Arête de G telle que le nombre de composantes connexesde G augmente de 1 si on la supprime.
Proposition 1.3.2 Soit G=(V,E) connexe.xyE n'est pas un isthme il passe un cycle par xy
Théorème 1.3.3 Soit G=(V,E) connexe.G est 2-arêtes connexe
par chaque arête il passe un cycle.
Proposition 1.3.4 Soit k ≥ 2 et G=(X,Y,E) connexebiparti et k-régulier. G n'admet pas d'isthme.
36
Isthme (cut edge)
Proposition 1.3.4 Un graphe dont tous les sommets sontde degrés pairs n'admet pas d'isthme.
Un graphe (2k+1)-régulier avec un isthme: (exemple avec k=2)
37
Théorème de Robbins
Soit G=(V,E) un graphe simple connexe non orienté.Il est possible de trouver une orientation des arêtes defaçon à rendre le graphe fortement connexe si etseulement si G est 2-arêtes-connexe.
38
Blocs
Un bloc de G est un sous-graphe connexe sans sommetdéconnectant maximal.Par définition, K1 et K2 sont des blocs
39
Blocs
Un bloc de G est un sous-graphe connexe sans sommetdéconnectant maximal.Par définition, K1 et K2 sont des blocs
Remarque: xy est un bloc de G xy est un isthme
b
ae
d
g
fc
h
B1
B4
B2 B3
40
Blocs
Proposition 1.3.5 Deux blocs d'un graphe ont au plus unsommet commun.
b
ae
d
g
fc
h
B1
B4
B2 B3
Corollaire L'ensemble des blocs forme une partition del'ensemble des arêtes du graphe.
41
Graphe Blocs/Sommets déconnectants Graphe biparti:H=(X,Y,A) X={sommets déconnectants} Y={blocs}
(xBi) A x Bi
b
ae
dg
fc
h
B1
B4
B2 B3
d
c
B1
B4
B2
B3
H
Cactus Graphe connexe dont chaque bloc est une arêteou un cycle.
2
Couplageset
Facteurs
43
2.1 Quelques propriétés
Graphe de Petersen
Ensemble d'arêtesnon adjacentes
CouplageG
n(G)=4
Un couplage maximal
Un couplage de cardinalmaximal
Un couplage parfait
44
2.1 Quelques propriétés
chaîne augmentantechaîne alternée commençant et
finissant par un sommetinsaturé,
le long de laquelle on peut faireun transfert améliorant le
couplage
Couplages
G
n(G)=4
45
Un 2-facteur
k-facteur sous-graphe couvrant k-régulier1-facteur couplage parfait2-facteur collection de cycles (disjoints)
46
Proposition 2.1Soit G=(V,E) un graphe simple, soient M0 et M1 deuxcouplages de G et soit H= (V,A) le graphe partiel de Gdéfini par
A= (M0 M1) - (M1 M0) = M0DM1
Les composantes connexes de H sont de l'un des 3 typessuivants:• point isolé• cycle élémentaire pair dont les arêtes sont
alternativement dans M0 et dans M1
• chaîne élémentaire dont les arête sont alternativementdans M0 et dans M1 et dont les extrémités distinctes sontinsaturées pour l'un des 2 couplages.
47
48
Théorème de BergeSoit G=(V,E). Un couplage M est un couplage
maximum si et seulement si il n'existe pas de chaînealternée reliant deux sommets insaturés.
CorollaireSoit M un couplage maximum (card max) de
G=(V,E). Tout couplage maximum M' de G peuts'obtenir à partir de M par une suite de transfert le longde chaînes alternées deux à deux disjointes et qui sont• soit des cycles alternés élémentaires pairs• soit des chaînes alternées paires commençant
(ou finissant) par un sommet insaturé.
49
YyXxUyxUYXG et),(quetel),,(
a
b
c
d
g
f
e
X
Y
2.2 Couplages dans les graphes bipartis
hypothèse: |X|≤|Y|(sans perte de généralité)
Couplage de X dans Y:sature tous les sommets de X
n(G)= |X|
n(G)= cardinal d'un couplage maximum.
50
Théorème de Hall
G admet un couplage de X dans Y
|N(S)| ≥ |S| S X
Corollaire (König)
Tout graphe k-régulier biparti admet k couplages parfaitsdisjoints.
51
Algorithmes de couplage dans les graphes bipartis
Rappel: problème de flot maximal dans un graphe bipartiaugmenté d'une entrée et d'une sortie. Algorithmes demarquage de type FF. Efficacité selon le choix deschaînes augmentantes.
Principe des algorithmes efficaces:• Construction de couplages successifs• Etape i → Mi
Rechercher l'ensemble le plus grand possible (t) dechaînes augmentantes de longueur minimale etsommets-disjointes: m1,m2 ,…,mt
Mi+1 = Mi D m1 D m2 D…D mt
52
procedure CouplMaxBip algo gourmand (in G=(X,Y,A) biparti; out M: couplagemaximum):
début
déterminer un couplage maximal M ;
si X ou Y saturé alors FIN: M est maximum.
tant que Non_FIN faire
marquer + tout sommet de X insaturé ;
tant que marquage possible et pas de chaîne augmentante trouvée faire
- marquer +x tout sommet de Y relié à un sommet x déjà marqué par une arête insaturée;
- marquer -y tout sommet de X relié à un sommet y déjà marqué par une arête saturée;
- si on a marqué un sommet y* de Y non saturé, alors on a trouvé une chaîne
augmentante.
fait ;
si pas de chaîne augmentante trouvée alors FIN: M est maximum
sinon soit µ une chaîne augmentante.
M := couplage obtenu par un transfert dans M le long de µ.
Effacer tous les marquages.
finsi ;
fait ;
fin ;
53
a
b
d
c
e
f
g
i
h
j
a
b
d
c
e
f
g
i
h
j
Exemple
chaîne augmentanteµ=[a f b g d i]
54
Algorithmes de couplage dans les graphes bipartis
Algorithme de Hopcroft et Karp en O( )
Voir présentation de Sankovski et Leonardi
Algorithmes de couplage dans les graphes quelconques
Fondés sur la construction d'arbres alternés ou de chaînesaméliorantes disjointes.
Algorithme d'Edmonds en O(n3)Algorithmes de Even et Karv ou de Bartnik en O(n2.5)
nm
55
COUPLAGES ou MARIAGES STABLESdans un graphe biparti G=(H,F,A).
Pour tout v de HUF, > relation d’ordre sur les voisins de v
xN(v), y N(v) et x >y signifie que v préfère x à y.
Couplage stable:couplage M A tel que si [u,v]A\M alors:
[u,y]M et u préfère y à vou [x,v]M et v préfère x à u (ou non exclusif)
Autrement dit: il n'y a pas d'arêtes uv hors de M telle que u préfèrerait v à l'élémentqui lui est associé dans M et v préfèrerait u à l'élément qui lui est associé dans M.
56
a
b
c
f
g
h
(f>g)
(f>g>h)
(g>h>f)
(c>a>b)
(a>c>b)
(c>b)
stables ?
a
b
c
f
g
h
Mariage stable: couplage M A tel que si [u,v]A\Malors: [u,y]M et u préfère y à v
ou [x,v]M et v préfère x à u
57
a(G) = cardinal maximal d'un stable de G
n(G) = cardinal maximal d'un couplage de G
t(G) = cardinal minimal d'une couverture des arêtes parles sommets ou "vertex cover" de G
r(G) = cardinal maximal d'une couverture des sommetspar les arêtes ou "edge cover" de G
2.3 Couplages, couvertures et stables
58
ensemble stable S: sous-ensemble de sommets non reliésdeux à deux.
nombre de stabilité :a(G) = cardinal du plus grand ensemble stable de G
Stabilité
a(G)=4
)(SS
1
76
3
2
5 4
S= {3,4,6,7}stable de cardinal max
a(G)=4
59
xa
xd
ad
ab
de
bd
cd
cf
ef
fy
ey
bc
xb
b
a
c
d
fx
e
y
G
L(G)
Remarque: un couplage de G = un stable de L(G)
60
clique: sous-ensemble C de sommets tel que le sous-grapheinduit par C est complet.
S stable de G S clique du complémentaire de G
Stable et Clique
1
76
3
2
5 4
S= {3,4,6,7}
1
2
3
4
5
6 7
clique: sous-ensemble C de sommets tel que le sous-grapheinduit par C est complet.
S stable de G S clique du0 complémentaire de G
Stable et Clique
Conséquence: les résultats sur les cliques se transposent auxstables et réciproquement.
62
VC : ensemble C de sommets tel que toute arête de G a aumoins l'une de ses extrémités dans C
Couverture des arêtes par les sommetsVertex Cover (VC)
1
76
3
2
5 4
C* = {1,2,5}
t(G)=C* = 3
vertex cover de cardinal min
63
EC : ensemble E d'arêtes tel que tout sommet de G estexrémité d'au moins une arête de E
Couverture des sommets par les arêtesEdge Cover (EC)
1
76
3
2
5 4
E* = {13,17, 24, 56}
r(G)=E* = 4
edge cover de cardinal min
64
Proposition 2.3.1 La cardinalité de tout couplage Md'un graphe est inférieure à celle de toute couverture Cdes arêtes par les sommets (vertex cover) |M| ≤ |C |
n(G) = |M*| ≤ t(G) = |C*|
|M*|=3 < | C* |=4
65
Théorème de König et d'Egevàry
Si G est un graphe biparti alors la taille maximale d'uncouplage est égale à la taille minimale d'une couverture
G biparti n(G) = t(G)
66
Proposition 2.3.2 La cardinalité de tout ensemble stableS d'un graphe est inférieure à celle de toute couverture E
des sommets par les arêtes (edge cover) |S| ≤ | E |a(G) = |S*| ≤ r(G) = |E* |
|S*|=3 < | E* |=4
67
Proposition 2.3.3 La cardinalité de tout couplageM d'un graphe est inférieure à celle de toute couvertureC' des sommets par les arêtes (edge cover) |M| ≤ | E |
n(G) = |M*| ≤ r(G) = |E* |
|M*|=3 < | E * |=4
68
Proposition 2.3.4 Soient G=(V,E) et SV.S stable V-S vertex cover
a(G) + t(G) = n
a(G) + t(G) = 3 + 4 = 7 = n
69
Théorème de Gallai Soient G=(V,E) sans sommet isolé.n(G) + r(G) = n
n(G) + r(G) = 4 + 9 = 13 = n
Couplage
Edge cover
70
Corollaire si G est un graphe biparti sans sommet isoléalors n(G) = t(G) ≤ a(G) = r(G)
Rappel si G est un graphe quelconque alorsa(G) ≤ r(G)n(G) ≤ t(G)n(G) ≤ r(G)
71
Algo Blocs_de_G in G=(V,E) connexe
initialisation: xV; H={x}; actif←x; uvE, uv est non traitée;
tant que non fini fairev←actif;si v est extrémité d'une arête vw non traitée alors
si wH alors H ← H{vw}; vw est traitée; actif←w;sinon vw est traitée; --w est ascendant de v dans Hfinsi
sinon si v≠x alors soit y le père de v; actif←y;si aucun sommet du sous-arbre T de racine v n'a une arêtetraitée reliée à un ascendant de y alors T {y} est un bloc.L'enregistrer et le supprimer de H
sinon fini --v=xfinsi
finsifait ;
72
Proposition 2.3Soient M un couplage maximal, P une chaîneaugmentante de M de longueur minimale et Q une chaîneaugmentante de MDP, alors |Q|≥|P|+ |PQ|. Si de plus Qest de longueur minimale pour MDP alors,|Q|=|P|P et Q sont sommets-disjointes et Q est unechaîne augmentante de M de longueur minimale
Remarque: propriété utilisée pour construire des algorithmesefficaces de recherche d'un couplage maximum.
73
"Expansion lemma" Soit G un graphe k-connexe et G'obtenu à partir de G en ajoutant un sommet y à G tel qued(y)≥ k, alors G' est k-connexe
x,U-Fan xV, UV, xU Ensemble de chaînesdisjointes de x aux différents sommets de U
U
h
gcd
f
i
bx
e
a
x,U-Fan pour U={d,f}
x,U-Fan theorem (Dirac) G est k-connexe G a au moins k+1 sommets et pour tout (x,U) t.q. x Uet |U|=k, il existe un (x,U)-Fan.
74
n(G)= cardinal d'un couplage maximum.
Proposition 2.2Soient M et N deux couplages tels que |M|<|N|. MDNadmet |N|-|M| chaînes augmentantes de M sommets-disjointes.
CorollaireSoient M et M* deux couplages tels que |M|<|M*|=n(G).Il existe une chaîne augmentante de M de longueur au
plus .12*
MM
M
