THÉORIE DES GRAPHES

PLAN

1 Généralités et définitions
2 Problèmes et complexité
3 Sous-graphes particuliers
4 Arbres et arbre couvrant

5 Centre , diamètre
6 Couplages

ENSIIE Alain Faye 1

 1

GÉNÉRALITÉS

ET

DÉFINITIONS

2
 GRAPHES ORIENTÉS

a f

b e

c d
U1  X1xX1
EXEMPLE G1 = (X1 , U1)
X1 = {sommets} = {a,b,c,d,e,f}
U1 = {arcs} =
{(a,b),(b,a),(b,c),(c,a),(c,d),(a,f),(e,f),(d,e),(e,d)} 3
G : X  P(X)
x  G(x) ou G+(x) = {successeurs de x}
G-(x) = {prédécesseurs de x}
EXEMPLE G1(b)={a,c} G1(f)={Ø}
G-1(b)={a} G-1(d)={c,e}

Chemin : suite d'arcs telle que

l'extrémité terminale d'un arc coïncide avec
l'extrémité initiale de l'arc suivant
EXEMPLE ((a,b),(b,c),(c,d)) ou (a,b,c,d)

boucle : arc du type (x,x)

x
4
 GRAPHES NON ORIENTÉS
G= (X,A) A est un ensemble d'arêtes
arête : arc "sans orientation"
G3=(X3,Y3)
A3  X3xX3
a e G3
b A3={[a,e], [b,f],
f
A3={[a,e],[a,b],[e,f],..}
[e,f], [d,f],...}
c
chaîne
Chaîne de a [a,e,f,d]
àd ou
g d [a,e],[e,f],[f,d]
([a,e],[e,f],[f,d])
Chaîne : suite d'arêtes telle que toute arête a
une extrémité commune avec l'arête précédente
(sauf la première) et l'autre avec l'arête suivante
(sauf la dernière) 5
Soit G=(X,A)
y est adjacent ou voisin de x si [x,y] A
G(x) ={voisins de x}

degré d(x) = nombre de voisins de xX

cardinal(G(x))
b est voisin
EXEMPLE de a, e et f
a e G3
b G(b)={a,e,f}
A3={[a,e], [b,f],
f [e,f], [d,f],...}
c d(b) = 3
chaîne de a à d
g d d(c) = 4
[a,e],[e,f],[f,d]
6
 d-(x) = nombre de
demi-degré intérieur
prédécesseurs de x =
Card (G- (x))

demi-degré extérieur d+(x) = nombre de

successeurs de x =
Card (G+(x))
a f
EXEMPLE
b e
d+(b)=2 d-(b)=1
d(b)=d+(b)+d-(b)=3
c d d-(f)=2 d+(f)=0
7
 UTILISATIONS DES GRAPHES

• Modélisation, représentation de problèmes

Exemple: plan de ville, arbre généalogique, jeux,
états d'un système..

• Résolution de problèmes
Exemple: plus court chemin, ordonnancement, flots, ...

• Outils
Exemple: structures de données,..

• ...
8
Sens Int erdit

G
H
E D

A
B C

F
G H D

B
C
A
G
F 9
 Amélie et
Jules

Sophie Fabien et Y David et Z Elodie et X

Marcus Norbert Zoé Loulou Bebert Charly

10
Critère 1: le temps

Critère 2 : le coût

Calcul du chemin de
temps (ou coût)
minimal
11
 Optimum
trouvé
facilement
par un
algorithme
de
graphe

12
M. Crochemore

13
 Olivier Nocent
Domaines d'applications
• Cartographie
Réseau routier, réseau internet, …
• Économie – Gestion
Planning de livraisons, gestion de flots, ordonnancement...
• Chimie – Biologie
Modélisation de molécules, ADN, …
• Sciences Sociales
Généalogie, phénomènes de masse, conflits, …
• Linguistique
Grammaire, Compilation, …
• ..... 14
 M. Crochemore

Flot de contrôle d'un programme

i 0 ; S  0

S  S+A[i]

i n Arrêt
Réseau

i i+1 Lille

Paris
Brest
Nantes Lyon
Nice
Toulouse

15
 QUELQUES DEFINITIONS
circuit : chemin dont le premier sommet
coïncide avec le dernier

a f
EXEMPLE
b e
(a,b,c,a)
circuit de G1
c d

G1 16
chemin hamiltonien :
chemin qui passe une
fois et une seule par
chaque sommet

a f
Existe-t-il un chemin
hamiltonien ? b e

c d

G1
17
chemin hamiltonien :
chemin qui passe une
fois et une seule par
chaque sommet

a f
OUI (suite)
(a,b,c,d,e,f) b e

c d

G1
18
Exemple d’application

ADN constitué de 4 nucléotides A,C,G,T

ADN constitué de 2 brins identiques
On casse les brins et ensuite on élimine les morceaux contenus
dans d’autre morceaux . Par exemple AC contenu dans TACGA
On se retrouve avec un ensemble de morceaux dits libres

Exemple:
TACGA, ACCC, CTAAAG, GACA

Comment reconstituer un brin d’ADN ?

19
cycle : chaîne dont les deux extrémités
coïncident (et qui ne passe pas
2 fois par la même arête)

a e G3
b A3={[a,e],
EXEMPLE [b,f],
f [e,f], [d,f],...}
c
chaîne de a à d
g d cycle de G3:
[a,e],[e,f],[f,d]
[aefba]

20
 Récapitulatif du vocabulaire
Correspondances orienté - non orienté

Graphe non orienté Graphe orienté

sommet, noeud sommet, noeud
arête arc
degré ½-degré intérieur, extérieur

voisin, adjacent successeur, prédécesseur

chaine chemin
cycle circuit
connexité forte-connexité

21
chaîne et cycle sont définis aussi dans un
graphe orienté (on ne tient plus compte de
l'orientation)

a f
EXEMPLE
un cycle b e
de G1:
(afedca) c d

G1
22
connexité : un graphe est
connexe si toute paire de
sommet est reliée par
une chaîne b
h
a
c
EXEMPLE
G1 et G3 connexes d
G2 non connexe e
g f
G2
23
24
 Olivier Nocent

Un peu d’Histoire…
La ville de Koeninsberg est traversée par la
Pregel, qui coule de part et d’autre de l’île
de Kneiphof, et possède sept ponts.

25
Euler (1736) : Peut-on se promener
dans la ville en traversant chaque
pont une et une seule fois ?

b c

d
26
1-graphe ou graphe simple:
une arête au plus entre 2 sommets
multigraphe ou k-graphe:
k arêtes au plus entre 2 sommets
chaîne eulérienne : chaîne qui passe une
fois et une seule par chaque arête

Théorème d'Euler
Un multigraphe connexe admet une chaîne
eulérienne si et seulement si le nombre de
sommets de degré impair est 0 ou 2
27
Peut-on se promener dans la ville en traversant
chaque pont une et une seule fois ?
NON !

3
a

3 b c3

d
5
28
En ajoutant un pont:
OUI !

4
a 4

1 5
3 b 2 c4
Départ 3
8
6
7
d
5 arrivée

29
Théorème d'Euler
Un multigraphe connexe admet une chaîne
eulérienne si et seulement si le nombre de
sommets de degré impair est 0 ou 2

C’est nécessaire car si on suit une chaîne eulérienne

- quand on traverse un sommet (on compte 2 arêtes)
- quand on ne traverse pas un sommet (il est de degré impair)
et c’est soit le début soit la fin de la chaîne

C’est suffisant pour un graphe à 1 arête ou 2 arêtes

Supposons vrai pour un nombre arêtes< m .
Soit un graphe connexe m arêtes et sans perte de généralité avec
2 sommets (uniquement) a et b de degré impair
30
Preuve th. Euler (condition suffisante suite)

Le graphe est connexe donc il existe chaîne de a à b.

Si la chaîne est eulérienne c’est fini.

Sinon, retirons cette chaîne. Tous les sommets sont alors de degré pair.
Soit C1,…,Ck les composantes connexes du graphe obtenu après retrait.
C1,…,Ck ont moins de m arêtes donc par récurrence il existe cycle eulérien
dans chacune.
Finalement, en faisant l’union de tous ces cycles eulériens et de la
chaîne initiale de a à b, on obtient une chaîne eulérienne d’extrémités a et b.

C1 C2 Ck
a b

31
Un algorithme de recherche de chaine eulérienne

Supposons (sans perte de généralité) G a exactement 2 degrés impair

G’=G
Partir d’un sommet de degré impair
Tant qu’il y a des arêtes dans G’
[Link] une arête e qui n’est pas un isthme pour G’
sauf si on est sur un sommet de degré 1 dans G’
2.G’=G’\{e}

Un isthme est une arête qui déconnecte le graphe

32
Exemple

3 1 6
5 2 4

On part de 1
On ne va pas en 2 car on traverse l’isthme rouge et dG’(1)1
On va en 3

3 1 6
5 2 4

On retire e=[1,3]

33
 3 1 6
5 2 4

On va en 5 On retire e=[3,5]

3 1 6
5 2 4

On va en 1 On retire e=[5,1]

3 1 6
5 2 4

Cette fois, dG’(1)=1 on peut traverser e=[1,2] 34

 Trouver chaine eulérienne dans ce graphe

a g
d
e
f b
j k
l

c
i h
m

35
 CONNEXITE ET FORTE CONNEXITE

sous-graphe G'=(X',A') de G (orienté ou non):

X'X A'A et "x,yX', [x,y]A  [x,y] A'
EXEMPLE
b G’4 sous-graphe de G4
G4 h
a
a
c
d c
d
e
g e
f g 36
f
sous-ensemble maximal pour une
propriété ℘: sous-ensemble tel que
l'ajout d'un élément lui fait perdre la
propriété ℘

Composante connexe de G: sous-

graphe de G connexe maximal

EXEMPLE G'4 a 2 composantes connexes

37
 Algorithme de recherche des
composantes connexes d'un graphe

entrée: graphe G=(X,A)

sortie: liste des composantes connexes
principe:
-déterminer une composante connexe C
en partant d'un sommet quelconque
-retirer C du graphe et recommencer
38
Procédure Comp_connexes
J  1;
Tant que tous les sommets n'ont pas été classés faire
Choisir un sommet de départ non classé;
S  sommet de départ;
Classer S dans la composante numéro J ;
Tant que S non fini faire
Tant que c'est possible faire
S  un voisin de S non classé;
Classer S dans J ;
Fin tant que;
Marquer S par fini;
S  sommet à partir duquel S a été classé si S n'est pas
le sommet de départ;
Fin tant que;
J  J+1;
Fin tant que;
Fin; 39
Appliquons l’algorithme

a b d

c e

40
 1 -a 2
a b d

-b 3 c e -c 4 C’est un parcours en « profondeur d’abord »

En rouge = ordre de parcours
En bleu = sommet d’où l’on vient
f

c a pour voisin b qui est déjà classé donc on passe au voisin e

41
 1 -a 2
a b d

-b 3 c e -c 4

f
-c 5

e a pour voisin b qui est déjà classé donc on revient sur c (backtrack)
Et on explore le voisin f de c

42
 1 -a 2 -b 6
a b d

-b 3 c e -c 4

f
-c 5

f n’ a pas de voisin non classé donc on revient sur c (backtrack)

Qui lui-même n’a pas de voisin non classé
Et on revient sur b (backtrack)
Qui a un voisin d non classé

Ensuite, par backtrack de d on remonte à b puis a et c’est terminé

43
Appliquer l’algorithme à ce graphe et donner les composantes connexes

a g
d
e
n
f b
j k
l

c
i h
m

44
 Forte connexité : un graphe orienté est
f-connexe si tout couple de sommet est
relié par un chemin

EXEMPLE b
G4 non f-connexe h
a
c
Mais si on d
ajoute
e
(c,d) et (c,h)
G4 devient G4 g f
f-connexe 45
Composante fortement-connexe de G:
sous-graphe de G f-connexe maximal

EXEMPLE
{a,b,d} défini un G4 b
h
sous-graphe a
f-connexe c
mais non d
maximal donc
e
ne définit pas
une g f
composante 46
Composante f-connexe de G: sous-
graphe de G f-connexe maximal

C3
G4 b
h
a
c
EXEMPLE d
G4 a 3
composantes e
f-connexes g f
C1 C2
47
 Algorithme de recherche des
composantes fortement connexes d'un
graphe

entrée: graphe G=(X,A)

sortie: liste des composantes f-connexes
principe:
-déterminer une composante f-connexe C
en partant d'un sommet quelconque
-retirer C du graphe et recommencer
48
Procédure composantes_f-connexes de G=(X,A):
*E  X;
Tant que1 E non vide faire
*marquer + et - un sommet x de E;
tant que2 c'est possible faire
*marquer par + tout successeur (non encore
marqué par +) d'un sommet déjà marqué + ;
*marquer par - tout prédécesseur (non encore
marqué par -) d'un sommet déjà marqué - ;
fait2;
*Écrire C l'ensemble des sommets marqués + et -;
*Le sous-graphe de G dont les sommets sont ceux de C
est une composante f-connexe de G;
*E  E - C; C  Ø;
fait1;
fin; 49
 Appliquons l’algorithme
a f

b c d e

50
 On part de a par exemple
+ a- f

b c d e

51
 On propage le + et le -
+ a- f

+b c- +d e

52
 On propage le + et le –
+ a- f Le – ne se propage plus
On a une cfc {a , b , c}

+b- +c - +d +e

53
 Trouver les cfc de ce graphe

1
9
10
7 2
3
8
6
4 11

5
54
 C3
G4 b
h
a
c
d
e
Graphe réduit
g f
C1 C2 G4R
C1

GR est sans circuit ! C3

C2
55
 THEOREME

Soit G un graphe connexe avec au moins

un arc, alors:
G est f-connexe
si et seulement si
par tout arc de G il passe un circuit (au
moins)
56
Tri topologique ou mise en ordre d'un graphe

Procédure Tri_topologique
début
Y  X; N  1;
tant que Y non vide faire
mettre sur le niveau N tous les sommets de Y n'ayant
aucun prédécesseur dans Y;
soit XN l'ensemble des sommets de niveau N;
Y  Y - XN;
N  N+1;
fait;
fin;

57
 Appliquons l’algorithme
1
a b
Y=a,b,c,d
N=1 a n’a aucun prédécesseur
c d

58
 Appliquons l’algorithme
1
a b
Y=a,b,c,d
N=1 a n’a aucun prédécesseur
c d
1 2
a b
N=2 Y=b,c,d
b et c n’ont aucun prédécesseur dans Y
c d
2

59
 Appliquons l’algorithme
1
a b
Y=a,b,c,d
N=1 a n’a aucun prédécesseur
c d
1 2
a b
N=2 Y=b,c,d
b et c n’ont aucun prédécesseur dans Y
c d
2
1 2
a b
N=3 Y=d
d n’a aucun prédécesseur dans Y
c d
2 3

Les prédécesseurs d’un sommet de niveau N sont de niveaux < N

60
Tri topologique ou mise en ordre d'un graphe
Mettre en niveaux ce graphe
2 7
10 8
3

6 1
9

5 0 4
61
Exploration en profondeur d'un graphe
Procédure Num_en_profondeur
Tant que tous les sommets n'ont pas été numérotés
faire
Choisir un sommet de départ S non numéroté;
Numéroter S;
Tant que S non fini faire
Tant que c'est possible faire
S  un successeur de S non numéroté;
Numéroter S;
Fin tant que;
Marquer S par fini;
S  sommet qui a permis de numéroter S si S
n'est pas le sommet de départ;
Fin tant que;
Fin tant que;
Fin;
62
Matrice booléenne associée à un graphe

b a b c d e
a a 0 1 0 0 0
c b 0 0 1 0 0
e c 0 0 0 1 0
d 0 0 0 0 0

d e 1 0 1 0 0

Matrice sommets x sommets appelée matrice d’adjacence

63
 Fermeture transitive d ’un graphe

Soit G=(X,U)

t(G)=(X,t(U)) est la fermeture transitive de G

si, pour tout (x,y) X2,

(x,y)  t(U)

il existe un chemin de x à y dans G

64
 Graphe partiel

G=(X,U) orienté ou pas

Graphe partiel de G : on retire des arcs (cas orienté)

ou des arêtes (cas non orienté)

U’U , G’=(X,U’)

Question:

Peut-on retirer des arcs à G sans altérer sa fermeture transitive ?

Et combien ?
65
 Peut-on retirer des arcs à G sans altérer sa fermeture transitive ?

B C

D E

66
 Peut-on retirer des arcs à G sans altérer sa fermeture transitive ?

B C B C

A A

D E D E

67
 Peut-on retirer des arcs à G sans altérer sa fermeture transitive ?

B C B C

A A

D E D E

B C

D E
68
 Peut-on retirer des arcs à G sans altérer sa fermeture transitive ?

B C B C

A A
G

D E D E

B C
On ne peut plus retirer d’arcs
sinon la fermeture transitive change
A
G’
G’ est t -minimal t -équivalent à G

D E
69
 Fermeture transitive d ’un graphe
t-minimalité
Deux graphes G et G ’ sont t -équivalents

t(G) = t(G ’)

Théorème

Si G est sans circuit, il n ’existe qu ’un seul

graphe t -minimal t -équivalent à G

70
 Fermeture transitive d ’un graphe
Algorithme de Roy-Warshall
Procédure fermeture_transitive

Principe
t(G) = graphe donné

pour tout sommet faire

relier chacun de ses prédécesseurs dans t(G)

à chacun de ses successeurs dans t(G) ;

t(G)  graphe ainsi obtenu

fait; 71
 Fermeture transitive d ’un graphe
Implémenter l’algorithme de Roy-Warshall
avec la matrice d’adjacence

Comment identifier les successeurs d’un sommet ?

Comment identifier les prédécesseurs d’un sommet ?

Relier les prédécesseurs d’un sommet aux successeurs ?

72
 2

PROBLEMES

ET

COMPLEXITE

48
 Des problèmes qui se ressemblent
et pourtant...

un problème "facile"
existe t'il une chaîne eulérienne dans G ?

et

un problème "difficile"
existe t'il un chemin hamiltonien dans G ?
74
Mais que veut dire "complexité" ?

Qu'est la "théorie de la complexité ?

Attention!
Nous donnons ici une
réponse INTUITIVE

Problème de Décision:
Réponse par OUI ou NON
75
 Classe NP

De manière intuitive, un problème de

décision est dans la classe NP si,
quand on sait que la réponse est OUI,
on peut facilement convaincre un tiers
que c’est vrai.

(Mais on ne peut pas forcément trouver

que la réponse est oui.)

76
Exemple si Carlos sait qu'il existe un cycle
hamiltonien dans un graphe donné, il peut
facilement vous en convaincre

Mais si le graphe
est grand,
Carlos ne pourra
pas savoir si ce
cycle existe

77
 Classe P
Un problème de NP est "facile"
(polynomial) si on peut le résoudre par
un algorithme "efficace"
(temps polynomial en fonction de la
taille de l’instance)

Exemple
L'existence d'un cycle eulérien dans un
graphe

78
Un problème est "difficile" si les seules
méthodes connues pour le résoudre
exigent un temps de calcul exponentiel
en fonction de la taille de l’instance

Exemple
L'existence d'un cycle hamiltonien dans
un graphe

79
 Classe NP-C

Un problème de NP est NP-complet si

"savoir le résoudre efficacement"
implique
"savoir résoudre efficacement TOUS les
problèmes de NP" .

80
 NP

? ?

?
?

NP-C P

Problèmes ? Problèmes non classés

81
 Pour montrer qu'un problème P est
polynomial

il faut trouver un algorithme pour le résoudre

et prouver que cet algorithme s'exécute en un
temps qui augmente de façon polynomiale en
fonction de la taille de l'instance traitée

82
 Pour montrer qu'un problème P est
NP-complet, on choisit un problème déjà
connu pour être NP-complet, soit Pnc , et on
montre que Pnc peut se "transformer" en P.

Donc, si on savait résoudre P, on saurait

résoudre Pnc.

Or, on ne sait pas résoudre Pnc : donc il va

sûrement être difficile de résoudre P.

P va, à son tour, être classé NP-complet.

83
 NP

? ?

?
?
Pnc
P

NP-C P
Si on savait résoudre facilement P on saurait résoudre
aussi Pnc; or on ne sait pas résoudre Pnc
P est donc sûrement difficile à résoudre 84
 Les problèmes sont classés de façon
incrémentale: la classe d'un nouveau
problème est déduite de la classe d'un ancien
problème.

L'établissement d'un "premier" problème NP-

complet pour classer tous les autres s'est
donc avéré nécessaire.

85
 Le problème SAT
"satisfiabilité" d'une expression logique
Exemple
(xVyVz)  (xVyVt)  (yVzVt)  (xVzVt)

x est vrai ou faux x vrai  x faux

Peut-on affecter des valeurs vrai ou faux
aux variables de telle façon que
l'expression soit vraie ?
Exemple
une solution: x=vrai y=faux t=vrai z=vrai
86
 Le théorème de Cook

Stephen Cook
a classé le
problème SAT
comme NP-complet

SAT est le premier problème

NP-complet connu

87
 Voulez-vous gagner 1 000 000 $ ?
Prix Clay

Il "suffit" de démontrer la conjecture suivante

P = NP
(ou bien de prouver que
P = NP)

Pour prouver que P = NP il faudrait résoudre

l'un des problèmes NP-complets avec un
algorithme polynomial. Faire "tomber" un seul
de ces problèmes dans la classe P ferait tomber
l'ensemble de la classe NP
88
 problèmes de décision

? ? NP
?
?
?
P
?

NP-C ?
?
fa
NP-Difficiles cil
Problèmes es
?
d'optimisation 89
Les problèmes d’optimisation sont plus difficiles
que les problèmes de décision.

Problème d’optimisation : trouver un stable max

Problème de décision :
existe-t-il un stable de taille au moins k

Si on sait résoudre (polynômialement)

le problème d’optimisation ,
on sait a fortiori résoudre le problème de décision

90
 Tous ces problèmes
(de décision ou d'optimisation)
présentent des enjeux industriels et
économiques très importants:
production, cryptographie,
écologie...

Beaucoup sont des problèmes de

graphes:
chemins, flots, ordonnancements,
planification, coloration, ...
91
 3

GRAPHES ET SOUS-GRAPHES

PARTICULIERS

Graphes sans boucle

92
 Stabilité
définition :
soit G un graphe orienté ou non orienté,
un ensemble stable de G est un sous-ensemble S
de sommets tel que deux sommets de S ne sont
jamais voisins.

1 3 S' = {1,2} stable

6 2 S" = {1,2,5}
7 stable maximal
S'''= {3,4,6,7}
5 4 stable de cardinal max
93
 Stabilité

ensemble stable : S  G(S )  

nombre de stabilité :
a(G) = cardinal du plus grand ensemble stable

1 3 S' = {1,2} stable

a(G)=4
6 2 S" = {1,2,5}
7 stable maximal
S'''= {3,4,6,7}
5 4 stable de cardinal max
94
 Stabilité

Théorème :

Dans un graphe de n sommets et de degré

maximal h, la cardinalité de tout ensemble
stable maximal est supérieure ou égale à
[n/h+1]+

[n/h+1]+ est la partie entière supérieure de n/h+1

95
 Graphe complet

graphe simple avec toutes les arêtes

Kn : n sommets et n(n-1)/2 arêtes

1 K1 un sommet et aucune arête

1 2
1 2 1 2
3 3
K2 5
K3 4
K5

Degré des sommets de Kn ?

Taille d’un stable max. de Kn ?
96
 Clique

Définition :

Soit un gaphe G non orienté,

Une clique de G est un sous-graphe complet de G

97
 Partition des sommets en cliques
P={C1, C2, … Ck}
C1, C2, …,Ck cliques de G tel que X(Ci) X(Cj)=
X(C1)X(C2)…X(Ck)=X(G)=sommets de G

Théorème:
soit un stable S de G et P une partition en cliques des
sommets de G, alors |S||P|.
Si |S|=|P| alors
S est un stable maximum et P une partition minimum

|S|=|P|=3 |S|=2 |P|=3

98
 Ensemble absorbant

Définition : soit un gaphe G orienté

Un ensemble absorbant de G est un sous-

ensemble A de sommets de G tel que
tout sommet n ’appartenant pas à A
a un successeur dans A

nombre d ’absorption :
b(G) = cardinal du plus petit ensemble absorbant
99
 6
7
1 4 5

2 3 A={1 , 3 , 5 , 7} est absorbant

2 a un successeur dans A
4 a un successeur dans A
6 a un successeur dans A

A est minimal : si on retire un sommet de A il n’est plus absorbant

Est-il minimum ?

100
 6
7
1 4 5

2 3 A={2 , 4 , 6 } est absorbant

1 a un successeur dans A
3 a un successeur dans A
5 a un successeur dans A
7 a un successeur dans A

A est minimum : il n’existe pas d’absorbant plus petit (de taille 2)

b(G) = 3

101
 Noyau

Définition : soit un gaphe G orienté

Un noyau de G est un sous-ensemble de

sommets de G qui est à la fois stable et
absorbant

102
 Noyau

a b
Graphe a 2 noyaux

d c

a b
Graphe sans noyau

c
103
 Fonction de Grundy

Définition : soit un gaphe G orienté

g est une fonction de Grundy de G si

g est une application de X dans N telle que

g(x) est le plus petit entier non attribué aux

successeurs de x

104
 Fonction de Grundy

Propriété : soit un gaphe G orienté

Si G admet une fonction de Grundy,

l ’ensemble des sommets de G tels que g(x)=0
forme un noyau de G

105
 Cycles

Cycle : chaîne qui ne contient pas deux fois

le même arc et dont le sommet initial et le
sommet terminal coïncident.

Cycle élémentaire: cycle qui passe une fois au

plus par chaque sommet.

106
 Cocycles
A ensemble de sommets
+(A)=arcs sortant de A
-(A)=arcs entrant dans A
(A)= +(A) -(A)

Cocycle : ensemble d’arcs de la forme (A)

Cocycle élémentaire: cocycle minimal au sens

de l’inclusion

107
 1
3 2

5 4
6

Cocycle
A={1,6,4} , +(A)={ (1,2) , (1,3) } ,  -(A)={ (5,1) , (5,6) , (7,4) }
(A) =  +(A)   -(A)

Cycle = { (7,5) , (5,6) , (6,4) , (4,7) }

L’arc (7,4) parcouru à l’envers  on lui affecte le signe -
108
 5 1 6 A={1,2,3}
(A)=(1,6),(3,7),(5,1),(5,2),
2 (4,2),(6,3)
3
(A) pas minimal
4 on peut retirer (3,7)
7 et (6,3)

5 1 6 A’={1,2}
(A’) =(5,1),(5,2),(4,2),(1,6)
 (A)
2 (A’) minimal
3
7
4

109
 Vecteur caractéristique
de cycle

vecteur de cycle C : vecteur  indexé par les

arcs t.q.

• a=1 si l’arc a est orienté dans le sens de

parcours de C
• a=-1 si l’arc a est orienté dans le sens
contraire du parcours de C
• a=0 si l’arc a n’est pas dans C

110
 Vecteur caractéristique
de cocycle

vecteur de cocycle (A) : vecteur  indexé par

les arcs t.q.

a=1 si l’arc a est orienté vers l’extérieur de A

a=-1 si l’arc a est orienté vers l’intérieur de A
a=0 si l’arc a n’est pas dans (A)

111
 Propriété: vecteurs de cocycles et de cycles sont 

1. Un vecteur de cocycle w(A) peut toujours se décomposer en une

somme vAw(v)
A L’arc sort de v1 est compté +1
v1 v2 Quand il rentre dans v2 compté -1
Seule reste la contribution des arcs
sortant ou rentrant dans A

112
 Propriété: vecteurs de cocycles et de cycles sont 

1. Un vecteur de cocycle w(A) peut toujours se décomposer en une

somme vAw(v)
A
v1 v2

2. Un vecteur de cycle  peut toujours se décomposer en une somme

de vecteurs de cycles élémentaires

1 2 =1+2


113
 Propriété: vecteurs de cocycles et de cycles sont 

3. Faisons le produit scalaire d’un vecteur de cycle et vecteur de cocycle

On peut déjà considérer un cycle élémentaire 

Le cocyle se décompose en vAw(v). Dans le produit scalaire, seuls les

sommets v du cycle élémentaire  interviendront :

<  | vAw(v) > = vA<  | w(v) > = 0

v v
Dans le cycle  les arcs sont comptés +1 Dans le cocycle w(v) les arcs sont comptés +1
Dans le cocycle w(v) l’un est compté -1 l’autre +1 Dans le cycle  l’un est compté -1 l’autre +1
Dans le produit scalaire -11+11=0 Dans le produit scalaire -11+11=0

114
 Cycles et cocycles

Théorème : Soit G un graphe de n

sommets, m arcs et p composantes connexes,
la dimension d’une base de cycles est le
nombre cyclomatique de G:
n(G)=m-n+p.

la dimension d’une base de cocycles est le

nombre cocyclomatique de G:
(G)=n-p.

115
 Planarité

graphe planaire: graphe qui peut être

représenté sur un plan de sorte que 2 arêtes
ne se rencontrent pas en dehors de leurs
extrémités
1 1

2 3 2 3

4 4
G4 est planaire 116
 Planarité

Face: région du plan limitée par des arêtes

dont l’ensemble constitue la frontière + face
infinie
1 1

2 3 2 3

4 4
G4 est planaire 117
Ce graphe est-il planaire ?

118
Ce graphe est planaire

119
 Frontière et contour
4
Graphe planaire topologique
7
1 est une représentation
3
f2 planaire d’un graphe planaire
2

f1 6
5
Contour de f1 = 1-4-7-6-5-1
Frontière de f1=1-3-2-1-5-6-7-4-1

La frontière dépend de la représentation pas le contour

Les contours sont des cycles élémentaires

Le contour est le cycle élémentaire qui contient en son intérieur

toutes les arêtes de la frontière
120
Théorème:
dans un graphe planaire topologique,
les contours des faces finies
constituent une base de cycles
Démonstration par récurrence sur le nombre de faces

1 1
Si le graphe n’est pas orienté
on oriente arbitrairement les arêtes
2 3 2 3

4 4
121
G4 est planaire
face: région du plan limitée par des
arêtes (+ face infinie)
formule d'Euler: Dans un graphe
planaire de n sommets, m arêtes et f
faces, on a
n-m+f = 2
1 1

2
Exemple 3 2 3
nombre de faces
f = m-n+2 =46-4+2 =4 4
122
G4 est planaire
 Graphe dual d’un graphe planaire topologique

G* graphe dual d’un graphe G planaire topologique

- Sommets de G* = faces de G
- Arêtes de G* = arêtes de G
a*=(f*,g*) est une arête de G* ssi les faces f et g de G partagent l’arête a

f0
G G* f0

f1 f1
f2
f2

G* est planaire
123
 Graphe biparti

G  ( X , Y , U ) tel que
"( x, y )  U
x  X et y  Y
a e Y
X b
f
c
d g
124
Graphe face-arêtes associé à un
graphe planaire G:

Graphe biparti H=(F,A,E) tel que

F={faces de G}
A={arêtes de G}
E={(x,y}, x dans F et y dans A
telle que y est sur le contour de x}

125
 graphe face-arêtes associé à un graphe planaire G

• Tracer H=(F,A,E) le graphe face-arête de K4

où F = faces et A = les arêtes de K4

Dans le cas général, soit H=(F,A,E) le graphe face-arête

d’un graphe G planaire qui contient au moins une face finie (un cycle) .
On note f =F le nombre de faces de G et m =A le nombre d’arêtes de G

• Quel est le degré min des sommets de F ?

• Quel est le degré max des sommets de A ?

• En déduire que 3f E 2m

126
Théorème:
Si G est un graphe simple planaire
connexe contenant au moins 1 face
finie alors m < 3n-5
Théorème:
Dans un graphe simple planaire
connexe contenant au moins 1 face
finie il existe au moins un sommet x
de degré d(x) < 6
127
Le graphe 1
complet de
5 sommets 2 3 5
n'est
pas planaire 4

Le graphe K3,3 n'est pas planaire.

128
 Une subdivision d’un graphe est obtenue en rajoutant (éventuellement)
des sommets sur les arêtes (ou les arcs) du graphe

Théorème de Kuratowski (1930):

Un multigraphe est planaire si et

seulement si il ne contient pas comme
sous-graphe partiel une subdivision
K5 ou de K3,3

129
 Coloration

Colorier les sommets de G sans que 2

voisins aient la même couleur

b
h
a
c
Une couleur
= d
un stable e
G g f
130
 Coloration
nombre chromatique: g(G)
plus petit nombre de couleurs
nécessaires pour colorier les sommets
de G sans que 2 voisins aient la même
couleur b
h
a
Trouver g(G) est c
un problème
d
"difficile" G
e
Exemple
g f
g(G) = 4 131
théorème des 4 couleurs:
Si G est un graphe planaire alors
g(G) ≤ 4
Cette carte
peut être
coloriée avec
seulement
4 couleurs ou
moins.
Graphe associé
un pays = un sommet
une frontière=une arête
132
 N
B D
L
F S O

N D clique de 4
B
sommets
L g(G) •4
O
S
F
graphe
planaire
g(G) Š 4
I 133
théorème des 4 couleurs:
Si G est un graphe planaire alors
g(G) ≤ 4

Conjecture formulée pour la première fois par

l'Écossais Francis Guthrie en 1852. (Travaux
de Paul Valéry).
(pour la coloration de cartes de géographie
Preuve en... 1976: K. Appel et W. Haken.

Premier théorème de l'histoire des

mathématiques qui a nécessité l'usage
systématique de l'ordinateur
134
 Un problème d'ordonnancement
ordonnancer n tâches sur k machines en le
minimum de temps, certaines tâches ne pouvant
être exécutées en parallèle (partage des ressources)

conflits entre les tâches graphe d’exclusion mutuelle

1 2 3

8 4

7 6 5

F. Gardi 135
 c'est un problème de coloration
lorsque toutes les tâches ont le même temps d’exécution

ordonnancement = coloration du graphe tel que chaque

couleur n’apparaisse pas plus de k fois

1 2 3
M1 1 2

M2 3 5 4 8 4
M3 6 7 8
t 7 6 5

F. Gardi 136
un algorithme « glouton » de coloration
Welsh-Powell
Début
•Soit G’ = G
•numéroter les sommets par ordre de degrés
décroissants: x1,x2,…,xn
•tant que G’ n’est pas vide faire
Sélectionner dans l’ordre de la liste tout
sommet non voisin (dans G’) d’un sommet
déjà sélectionné;
Colorier de la même couleur tout les sommets
sélectionnés;
Retirer tous les sommets sélectionnés de G’;
fait;
Fin;
Heuristique rapide mais non nécessairement optimale
137
 Borne supérieure

Supposons les sommets numérotés par degré décroissant

d1d2…dn

Thèorème: l’algorithme de Welsh-Powell colorie le graphe

avec au plus max{ min{k, dk+1}: k=1,…,n} couleurs

1
5 2

4 3

Max { min{1,5} min{2,4} min{3,4} min{4,3} min{5,3} } = 3 138

 algorithme reliement-contraction
Principe
Soit un graphe G et 2 sommets a et b non adjacents
Reliement GR = G + [a,b]
Contraction GC : un seul sommet ab relié à
G(a) U G(B)
a et b même couleur:
coloration de GC
Coloration de G
a et b de couleurs différentes:
coloration de GR
Contracter et/ou relier tant que graphe pas complet
Algorithme optimal mais exponentiel
139
 algorithme reliement-contraction

1 2 On remonte les deux colorations

et on prend la minimum=2

3
reliement 2 contraction
1 2 1-2
Graphe complet Graphe complet
K3  3 couleurs K2  2 couleurs

3 3

140
 Coloration des arêtes

2 arêtes adjacentes n’ont pas la même couleur

b
h
a

d c
e
H g f
141
 Coloration des arêtes
Indice chromatique:
Nombre minimal de couleurs pour les arêtes

Exemple: b
h
indice chromatique a
g(H) =4
d c
il y a un sommet
e
De degré 4
H g f
142
 Allocation de fréquences
Réseau de capteurs
• Les capteurs pas trop éloignés communiquent 2 à 2
• A chaque paire de capteurs pas trop éloignés est alloué une fréquence
sur laquelle ils communiquent
• Il faut des fréquences différentes pour éviter les interférences

On veut utiliser un minimum de fréquences

Même fréquence  interférences quand

C2 et C3 communiquent en même temps avec C1
C1
C2 C3 C1
C2 C3
On doit affecter des fréquences différentes
143
 Coloration des arêtes
« Line graph » ou « graphe des arêtes »

Graphe L(G)=(Y,B) associé à G=(X,A)

•Y = A (un sommet par arête de G)

•[a,b] arête de L si et seulement si a et b
ont une extrémité commune dans G

L’indice chromatique de G est égal

au nombre chromatique de L(G)
144
 Graphe G Graphe des arêtes de G
1 12
2 3 13 14

24 34
4

1 12
2 3 13 14

24 34
4

Coloration arêtes  Coloration sommets

145
 Coloration des arêtes

La recherche de l’indice chromatique

d’un graphe est un problème difficile

Mais on sait qu’il est égal soit à h soit à h+1

où h est le degré maximal du graphe ([Link] Vizing 1964)

146
Couplage d’un graphe G
sous ensemble d’arêtes de G tq. 2 arêtes quelconques sont
non adjacentes

Couplage maximum = couplage de cardinal maximum

2 couplages maximum

147
 Coloration des arêtes et couplages

Une coloration des arêtes revient à faire une partition

des arêtes en couplages
Un couplage = une couleur

4 couleurs

4 couplages

148
 4

ARBRES

ARBRE COUVRANT D’UN GRAPHE

(Algorithmes gloutons)
149
 Arbres

arbre: Graphe connexe et sans cycle

b
h
a
c
d
e
H g f
150
arbre: définitions équivalentes
H=(X,U), n sommets (n≥2)
(1) H connexe et sans cycle
(2) H sans cycle et n-1 arêtes
(3) H connexe et n-1 arêtes
(4) H sans cycle et en ajoutant une arête on crée
un et un seul cycle
(5) H connexe et si on supprime une arête , il n'est
plus connexe
(6) une chaîne et une seule entre toute paire de
sommets 151
Démonstration

Rappel
nombre cyclomatique : n(G) = m - n + p

12 H connexe et sans cycle

 H sans cycle et n-1 arêtes
23 H sans cycle et n-1 arêtes
 H connexe et n-1 arêtes
152
34 H connexe et n-1 arêtes
 H sans cycle et en ajoutant
une arête on crée un et un
seul cycle
45 H sans cycle et en ajoutant une arête
on crée un et un seul cycle
 H connexe et si on
supprime une arête , il n'est
plus connexe

153
Démonstration (fin)
56 H connexe et si on supprime une
arête , il n'est plus connexe
 une chaîne et une seule
entre toute paire de
sommets
61 une chaîne et une seule entre toute
paire de sommets
 H connexe et sans cycle

154
 Propriétés d'un arbre H
de m arêtes et n sommets

•H sans cycle
•H est connexe
•H a m=n-1 arêtes
•En ajoutant une arête à H on crée un et
un seul cycle
•Si on supprime une arête de H, H n'est
plus connexe
•Il y a dans H une chaîne et une seule
entre toute paire de sommets
155
 Théorème
Un graphe G admet un graphe partiel qui
est un arbre si et seulement si il est
connexe

Construction d’une base de cycle d’un graphe

Soit un graphe G connexe et H un arbre
couvrant de G.
Les cycles construits pas ajout des
arêtes de G n’appartenant pas à H (une
par une) forment une base de cycles.
156
LE PROBLEME DE L’ARBRE

COUVRANT MINIMAL

157
 Comment relier des objets avec un
nombre minimal de liens (choisis dans un
ensemble de liens donnés)?
b
h b
a h
c a
d c
d
e
e
g f
g f
G:graphe des liens
possibles H: arbre couvrant de158G
 PROBLEMES D ’OPTIMISATION

un problème  plusieurs solutions

une solution  une valeur
problème d'optimisation:
recherche d'une solution de valeur optimale
(min ou max)
algorithme de résolution:
• reconnaissance d'une solution
• évaluation d'une solution
• sélection d'une des meilleures solutions
159
problèmes d'optimisation
 faciles
 difficiles
---------------------------------------------------------------
EXEMPLES
E1) chemin min 3
B E
3 4
5 1
2
A C G
2 6
4
4
D F
problème facile (v=9;ABECG)
160
E2) sac-à-dos (en nombres entiers)
problème "assez" difficile
aliments A B C
poids
unitaire 6 4 3
hg
valeur
nutritive 14 10 6
unitaire
poids max des aliments: 17

2 solutions optimales:
1.A + 2.B + 1.C  v = 40 (p=17)
4.B  v = 40 (p=16)
161
E3) voyageur de commerce
B 3
2 4
problème difficile 2 1
A 2 D 5 C
1 3
E 4
ici, 2 solutions optimales

ACBDEA et ACEBDA v = 12

nombre de solutions: 24 (n-1!)

---------------------------------------------------------------
162
problème de petite taille
 énumération possible
problème de grande taille
 énumération impossible

INTERDIT D'ÉNUMÉRER DANS LE

COMBINATOIRE

optimisation discrète  optimisation continue

163
 ALGORITHMES GLOUTONS
choix glouton = choix localement optimal
optimum local  optimum global

x1 x2 x3

fonction concave x1 et x3 : optima locaux

(ou convexe)
optimum local = x2 optimum global
optimum global (et local)
continu  entier 164
algorithme glouton: pas toujours optimal
EXEMPLE
un algo glouton pour le PVC:
- trier les arêtes (coûts croissants)
- sélectionner dans l'ordre les arêtes non
"parasites"
3 ([A,E],[B,D],[A,B],
B [A,D],[B,E],[A,C],
2 4 [E,D],[C,E],[C,D])
2 1
A D C [A,B,D,C,E,A]
2 5
valeur 13
1 3
E 4 (opt=12 [ACEBDA])
165
algorithme glouton: à chaque étape
choix le plus intéressant à cet instant

 facile à concevoir

 difficile de vérifier l'optimalité

 efficace (faible complexité)

166
 ARBRE COUVRANT MINIMAL
LE PROBLÈME

relier des objets avec une

longueur totale minimale des liens

graphe valué associé:

- sommets = objets
- arête = lien possible
- poids d'une arête = longueur du lien
167
--------------------------------------------------------------
EXEMPLE B
1
E
1
5
1
A 5 G
5
1 1
5
D F
---------------------------------------------------------------
solution optimale:
sans cycle et connexe  ARBRE
par tous les sommets  COUVRANT
de longueur totale min  MINIMAL
168
 ALGORITHME DE KRUSKAL

rappel: arbre  m = n-1 arêtes

entrée: G = (X,U,P)
n sommets, m arêtes

sortie: A arbre couvrant min de G

169
procedure kruskal (in G: graphe; out A: arbre):
var k: entier :=0; V: {arêtes} :=;
début
trier les arêtes de G par ordre de poids croissant ;
tant que k < n-1 faire
parcourir la liste triée ;
sélectionner la première arête qui ne forme pas de
cycle avec les précédentes, w ;
k := k+1 ;
V := V U {w} ;
fait ;
A := graphe (X,V) ;
fin ; 170
--------------------------------------------------------------
3 2
b c d
EXEMPLE 2 2 3 2 1 1
a 1 h 1 i 1 e
4 3 4 3
1
liste triée: g f
ah de di ei hi fg ab bh ci cd bc ch ef gh ag ge
1 1 1 1 1 1 2 2 2 2 3 3 3 3 4 4

n = 9  stop après 8 sélections

P(A) = (1+1+1+1+1+2+2+3) = 12
-------------------------------------------------------------- 171
procedure kruskal (in G: graphe; out A: arbre):
var k: entier :=0; V: {arêtes} :=;
début
trier les arêtes de G par ordre de poids croissant ;
tant que k < n-1 faire
parcourir la liste triée ;
sélectionner la première arête qui ne forme pas de
cycle avec les précédentes, w ;
k := k+1 ;
V := V U {w} ;
fait ;
A := graphe (X,V) ;
fin ; 172
 PREUVE DE L ’OPTIMALITE

G=(X,U) le graphe
A=(X,V) l'arbre couvrant obtenu
p(u) : poids de l'arête u

propriété 1
soit w  U -V, w=[x,y] et
cw : chaîne de x à y dans A;
cw
alors, x
p(w)  maxucw p(u) w
y
173
A': arbre optimal de poids p(A')
montrons que p(A) = p(A')
soit u  A'-A
x x
x x x C1 x x x
b b
u v
a x a x
x x C2 x x
x x x x

A'=(X,V') A=(X,V)
u  V'-V relie C1 et C2 dans A'
v  cu relie C1 et C2 dans A
174
propriété 1  p(u)  p(v) et
A' minimal  p(v) ≥ p(u)
 p(u) = p(v)

soit A"=A'+{v}-{u}: p(A")=p(A')

 A"optimal et v  A"

soit u' A"-A,... (idem...  A''')

...
fin: A''¨'' = A et p(A''¨'') = p(A') = p(A)
175
difficultés:

• implémentation

• complexité O(m logm) (TRI)

PREUVE DE L ’OPTIMALITE…
176
 graphes orientés

racine : sommet r tel qu'il existe un chemin de r à

tout autre sommet du graphe

degré intérieur([Link]érieur): d'un sommet x:

nombre d'arcs d'extrémité terminale (resp.
initiale) x notés d-(x) et d+(x)

177
arborescence: définitions équivalentes
H=(X,U) n sommets (n ≥ 2)
(1) H arbre avec une racine r
(2) H arbre et $ r  X, relié à tout x  X
par un chemin unique
(3) H connexe et
$ r  X t.q. d-(r)=0 et
d-(x)=1 pour tout x ≠ r

178
(4) H sans cycle et $ un sommet r X t. q. d-
(r)=0 et d-(x)=1 pour tout x ≠ r

c f
a r
g
d e
b
H, une arborescence
179
 arborescence =
"arbre enraciné" (rooted tree)
= "arbre" en informatique

Ex: arbre généalogique, tournois, arbre des

espèces animales,...

180
arborescence binaire:

A racine
sens
a b
implicite
c d e f

g h i

181
 5

Centre

Diamètre

182
 Centre , diamètre
• La distance d(x,y) entre 2 sommets x,y d’un graphe est
le nombre minimum d’arcs pour aller de x à y.
• L’écartement e(x) du sommet x est la distance max entre
x et les autres sommets du graphe
• Le (ou les) centre du graphe est le (ou les) sommet
d’écartement min
• Le rayon (G) d’un graphe G est l’écartement d’un
centre
• Le diamètre (G) est la distance max entre deux
sommets du graphe

183
graphe G B C

A D E

e(A)=2
A est le centre de G
e(B)=4
 (G)=2
e(C)=4
(G)=4
e(D)=3
e(E)=4

184
• Rayon fini si G admet une racine (un
sommet x0 t.q. il existe un chemin de x0
vers chacun des autres sommets

• Diamètre fini si G est fortement connexe

185
• Intérêt d’un centre
– placer un équipement dans un réseau qui
soit le plus « proche » des autres sommets

- le plus « proche » = la distance la plus longue

est minimale

- on place l’équipement sur un centre

186
 d+(x) = demi-degré extérieur de x = nombre d’arcs sortant de x

Théorème 1: Soit G(X,U), X=n

Soit p=max {d+(x): xX} et p2

(G)Log(1-(1-p)n) / Log(p) - 1

Exemple:
p=2, n=5 (G)Log(6) / Log(2) - 1  =1,58 =2

187
 Théorème 2: Soit G(X,U), X=n, U=m
G fortement connexe

(G)  (n – 1) / (m-n+1)

Exemple:
n=5, m=7 (G)4 / 3  =1,33 =2

188
 x
Rosace
x x

c c centre
(G) = 4
x x

x x

Borne théorème 1: p=2, n=8 (G)Log(9) / Log(2) - 1  =2,16 =3

Borne théorème 2: n=8, m=9 (G)7 / 2  =3,5 =4

189
 Graphe non orienté
• Les notions précédentes s’étendent aux
graphes non orientés
• d(x,y) = nombre min d’arêtes pour aller de
xày
• Écartement, rayon, diamètre se
définissent ensuite de la même façon

190
 a b

c d g

e f h

d(x,y) a b c d e f g h e(x)
a 1 1 2 2 2 3 3 3
Centre =c,d,f,e
b 1 1 1 2 2 2 3 3
Rayon =2
c 1 1 1 1 1 2 2 2 Diamètre =3
d 2 1 1 2 1 1 2 2
e 2 2 1 2 1 2 2 2
f 2 2 1 1 1 1 1 2
g 3 2 2 1 2 1 2 3
h 3 3 2 2 2 1 2 3 191
 6

COUPLAGES

192
• On doit former des équipes de 2 personnes
• L’ensemble des personnes A,B,C,D,E,F
• Compatibilités entre les personnes
Former un maximum d’équipes

compati A B C D E F
bilité
A - + +
B - - + +
C - - - +
D - - - - +
E - - - - - +
F - - - - - -

193
Graphe des compatibilités

A
C B

E F
D

3 équipes
A
C B

E F
D
194
Couplage d’un graphe G
sous ensemble d’arêtes de G tq. 2 arêtes quelconques sont
non adjacentes

Exemples de couplages

195
Couplage maximal = maximal pour l’inclusion d’arêtes

A
C B

E F
D

Ce couplage en rouge est maximal . L’ajout d’une autre arête fait

qu’il n’est plus un couplage
196
Couplage d’un graphe G
sous ensemble d’arêtes de G tq. 2 arêtes quelconques sont
non adjacentes

Couplage maximum = couplage de cardinal maximum

couplages maximum

197
 Sommet saturé par un couplage

Un sommet est dit saturé par un couplage K

s’il est l’extrémité d’une arête de K

1 2 1 2
5 5
3 4 3 4

1 , 2 , 4 , 5 saturés par le couplage rouge

198
Couplage parfait = couplage qui sature tous les sommets

Un couplage parfait est maximum

X1 X2 X3 X4
Le couplage (rouge) est parfait
Tous les sommets saturés
X5 X6 X7 X8

199
 Théorème.
Le cardinal d’un couplage maximal vaut au moins la moitié
du cardinal d’un couplage maximum

Dans l’exemple du graphe des compatibilités

- K couplage maximal |K|=2
- K* couplage maximum |K*|=3
- 2=|K|  ½|K*|=1,5
En effet, soit K un couplage maximal, et K* couplage maximum.
Pour une arête e de K, 3 possibilités :
- soit c’est une arête de K*
- soit elle rencontre 1 arête de K* (rencontre=adjacente=extrémité commune)
- soit elle rencontre 2 arêtes de K*
Car si e ne rencontre pas d’arêtes de K*, K* ne serait pas maximum (on pourrait rajouter e à K*)
De plus, si une arête e de K* n’est pas rencontrée par une arête de K, alors K n’est pas maximal
car on pourrait rajouter e à K.

Donc quand on compte une arête de K, on comptabilise 1 ou 2 arêtes de K* et

si on parcourt toutes les arêtes de K on parcourt toutes les arêtes de K*
Donc |K*|2|K| 200
Soit 2 couplages K0 et K1 de G et soit A=(K0-K1)(K1-K0)
Graphe partiel G’=(X,A)

K0 K1

G’=(X,A)

201
Rappel
Une chaine élémentaire est une chaine qui ne repasse pas deux fois
par le même sommet
Cycle élémentaire idem

Soit 2 couplages K0 et K1 de G et soit A=(K0-K1)(K1-K0)

Graphe partiel G’=(X,A)

Théorème: G’=(X,A) est fait des composantes connexes de 3

types:
- des points isolés
- des cycles élémentaires pairs faits d’arêtes alternativement
dans K0 et K1
- des chaines élémentaires faites d’arêtes alternativement
dans K0 et K1
202
Soit K un couplage de G=(X,E)
Une chaine alternée est une chaine composée
alternativement d’arêtes de K et de E-K
Note: une chaine alternée est nécessairement élémentaire sinon K n’est pas un couplage

K un couplage de G

une chaine alternée

203
Théorème: Un couplage K est maximum si et seulement si
il n’existe pas de chaine alternée ayant ses 2 extrémités
non saturées par K.

un couplage K de G

chaine alternée avec les 2 extrémités non saturées par K

donc le couplage K est non maximum 204
 G

un couplage K de G

chaine alternée avec les 2 extrémités non saturées par K

donc le couplage K est non maximum

un couplage K de G
plus grand de taille 4.
On remplace les noires
par les rouges dans la chaine alternée 205
Recherche d’un couplage maximum

On part d’un couplage maximal

Puis augmente sa cardinalité en cherchant des
chaines alternées augmentantes c’est-à-dire avec les extrémités
non saturées par le couplage courant

Transfert le long de la chaine augmente le cardinal du couplage de 1

Dans les graphes bipartis la recherche de chaînes alternées

augmentantes est simplifiée
206
 Couplage maximum dans un graphe biparti G=(X,Y,E)
Partir d’un couplage maximal K, STOP=false
Tant que pas STOP
chaine augmentante trouvée=false
marquer + tout sommet de X insaturé

tant que marquage possible et pas chaine augmentante trouvée

marquer +x tout sommet de Y relié à xX par arête K
marquer -y tout sommet de X relié à yY par arête K
si on a marqué un sommet de Y non saturé par K
alors chaine augmentante trouvée = true
fin tant que

Si pas chaine augmentante trouvée alors K est maximum, STOP=true

sinon soit  la chaine trouvée,
effectuer un transfert le long de cette chaine  :
arête K est mise dans K et arête K est sortie de K
effacer marquage
Fin tant que 207
 1 5
2 6 couplage 3 arêtes rouges
3 7 maximal

4 8

1 5
(-6) 2 6 (+3)
marquage chaine augmentante trouvée
(-7) 3 7 (+4)

(+) 4 8 (+2)

1 5
(-6) 2 6 (+3)
transfert 4 arêtes rouges
(-7) 3 7 (+4)

(+) 4 8 (+2) 208