Chapitre 2 Cycles

Chapitre 2 : Cycles page 21
Chapitre 2 : Cycles
Plan du chapitre 2 :
1. Nombres cyclomatique et cocyclomatique

1.1. Décomposition des cycles et des cocycles en sommes élémentaires
1.2. Lemme des arcs colorés (Minty 1960)
1.3. Base de cycles et base de cocycles
2. Planarité
2.1. Graphe Planaire
2.2. Formule d'Euler
2.3. Théorème de Kuratowski (1930)
2.4. Graphe Dual
3. Arbre
3.1. Arbre
3.2. Forêt
3.3. Arborescence
3.4. Arbre couvrant de poids minimum d’un graphe
1. Nombres cyclomatique et cocyclomatique

1.1. Décomposition des cycles et des cocycles en sommes élémentaires
1.1.1. Vecteur caractéristique de cycle
Soient G = (X, U) un graphe avec |U| = m et 𝜇 = (u1 , u2 , … , uk ) un cycle de G tel que k est
la longueur du cycle et la suite des arcs u1 , u2 , … , uk constitue le cycle 𝜇.
On choisit un sens de parcours du cycle μ. On désigne par :

 𝜇 + l’ensemble des arcs 𝑢𝑖 orientés dans le sens de parcours que le cycle 𝜇
 𝜇 − l’ensemble des arcs 𝑢𝑖 orientés dans le sens contraire du parcours que le cycle 𝜇
Si les arcs sont numérotés 1, 2, … , 𝑚, on peut faire correspondre à tout cycle 𝜇 un vecteur
caractéristique 𝜇⃗ = (𝜇1 , 𝜇2 , … , 𝜇𝑚 ) de 𝐼𝑅 𝑚 indexé par les arcs 𝑢𝑖 du graphe G tel que :
+1 𝑠𝑖 𝑢𝑖 ∈ 𝜇 +
𝜇𝑖 = {−1 𝑠𝑖 𝑢𝑖 ∈ 𝜇 −
0 𝑠𝑖𝑛𝑜𝑛
Exemple :
Soit le graphe G = (X, U) suivant :
Matière : Théorie des graphes 2ème année Licence Informatique Responsable de la matière : Amiar Lotfi
𝜇 = (𝑢1 , 𝑢5 , 𝑢9 , 𝑢7 , 𝑢2 ) 𝑒𝑠𝑡 𝑢𝑛 𝑐𝑦𝑐𝑙𝑒 𝑑𝑒 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟 5

avec :
𝑋 = {𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹}, |U| = m = 9
et 𝜇 = (𝑢1 , 𝑢5 , 𝑢9 , 𝑢7 , 𝑢2 ) un cycle de G de longueur 5.
 𝜇 + l’ensemble des arcs 𝑢𝑖 orientés dans le sens de parcours que le cycle 𝜇 :
𝜇 + = {𝑢1 , 𝑢9 }
 𝜇 − l’ensemble des arcs 𝑢𝑖 orientés dans le sens contraire du parcours que le cycle 𝜇 :
𝜇 − = {𝑢5 , 𝑢7 , 𝑢2 }
Les arcs sont numérotés 𝑢1 , 𝑢2 , … , 𝑢9 , on peut faire correspondre au cycle 𝜇 le vecteur

caractéristique 𝜇⃗ = (𝜇1 , 𝜇2 , … , 𝜇9 ) de 𝐼𝑅 9 indexé par les arcs 𝑢𝑖 du graphe G tel que :
𝜇⃗ = (+1, −1, 0, 0, −1, 0, −1, 0, +1)
1.1.2. Décomposition des cycles

Un vecteur de cycle 𝜇 peut toujours se décomposer en une somme de vecteurs de cycles
élémentaires sans arcs communs. Il suffit de parcourir le cycle et de définir un cycle
élémentaire1 chaque fois qu'un même sommet est rencontré.
Fig.1. Exemple de décomposition de cycle 𝜇 en 2 cycles élémentaires 𝜇1 et 𝜇2

L’union de 𝜇1 et 𝜇2 est un cycle 𝜇 sans arc commun et il n’est pas élémentaire
1
Un cycle est dit élémentaire si lors de son parcours on ne rencontre pas deux fois le même sommet sauf le premier et le
dernier sommet.
1.1.3. Vecteur caractéristique de cocycle

Si les arcs 𝑈 du graphe 𝐺 = (𝑋, 𝑈) qui sont numérotés 1, 2, … , 𝑚, on peut faire correspondre
à tout cocycle 𝑤(𝐴) engendré par 𝐴  𝑋 un vecteur caractéristique 𝑤
⃗⃗⃗ = (𝑤1 , 𝑤2 , … , 𝑤𝑚 ) de
𝐼𝑅 𝑚 indexé par les arcs 𝑢𝑖 du graphe 𝐺 tel que :
+1 𝑠𝑖 𝑢𝑖 ∈ 𝑤 + (𝐴) (l’arc 𝑢𝑖 est orienté vers l’extérieur de 𝐴)

𝑤𝑖 = { −1 𝑠𝑖 𝑢𝑖 ∈ 𝑤 − (𝐴) (l’arc 𝑢𝑖 est orienté vers l’intérieur de 𝐴)
0 𝑠𝑖𝑛𝑜𝑛
Exemple :
Soit le graphe suivant :
6
4
2 3
5
Soit 𝐴 = {𝑒, 𝑑, ℎ}
Le cocycle de 𝐴 est : 𝑤(𝐴) = 𝑤 + (𝐴) ∪ 𝑤 − (𝐴) = {1} ∪ {2,6} = {1, 2, 6}
Les arcs du graphe 𝐺 = (𝑋, 𝑈) sont numérotés 1, 2, 3, 4, 5, 6 alors on peut faire correspondre
⃗⃗⃗ = (𝑤1 , 𝑤2 , … , 𝑤6 ) de 𝐼𝑅 6
au cocycle 𝑤(𝐴) engendré par 𝐴  𝑋 le vecteur caractéristique 𝑤
indexé par les arcs 𝑢𝑖 du graphe 𝐺 tel que :
𝑤
⃗⃗⃗ = (+1, −1, 0, 0, 0, −1).
1.1.4. Décomposition des cocycles
Un cocycle w(A) associé à A peut toujours se décomposer en une somme de cocycles :
∑ w(v)
v∈A
w(v) est le cocyle pour un sommet v.

Pour un arc 𝑢 = (𝑥𝑖 , 𝑥𝑗 ) ∈ 𝑈 on a :
+1 𝑠𝑖 𝑣 = 𝑥𝑖 +1 𝑠𝑖 𝑥𝑖 ∈ 𝐴 𝑒𝑡 𝑥𝑗 ∈ 𝑋 − 𝐴
𝑤𝑢 (𝑣) = {−1 𝑠𝑖 𝑣 = 𝑥𝑗 d’où : 𝑤𝑢 (𝑣) = { −1 𝑠𝑖 𝑥𝑖 ∈ 𝑋 − 𝐴 𝑒𝑡 𝑥𝑗 ∈ 𝐴
0 𝑠𝑖𝑛𝑜𝑛 0 𝑠𝑖𝑛𝑜𝑛
Seule reste la contribution des arcs sortant ou entrant dans 𝐴.
Définition 1 :
Un cocycle 𝑤(𝐴) associé à un sous-ensemble de sommets 𝐴 est élémentaire si la suppression
de 𝐴 engendre une composante connexe.
Définition 2 :
Un cocycle 𝑤(𝐴) associé à un sous-ensemble de sommets 𝐴 est élémentaire quand il est
composé d'arcs reliant deux sous-ensembles de sommets 𝐴 et 𝐵, engendrant deux sous-
graphes connexes sans sommets communs, avec 𝐴 ≠ ∅, 𝐵 ≠ ∅, 𝐴 ∩ 𝐵 = ∅ et le graphe
induit par 𝐴 ∪ 𝐵 est une composante connexe du graphe.
Exemple (cocyle non élémentaire) :
Le cocycle 𝑤(𝐴) = {1, 2, 6} associé à 𝐴 = {𝑒, 𝑑, ℎ} n’est pas élémentaire car la suppression
de 𝐴 n’engendrera pas une seule composante connexe.
6 6
4 4
1 1
2 3 2 3
5 5
En supprimant 𝐴 = {𝑒, 𝑑, ℎ} de 𝐺 (avec les arcs associés {1, 2, 6}), cela engendrera 2
composantes connexes :
- CC1 : le sous-graphes connexe engendré par le sommet isolé 𝑓
- CC2 : le sous-graphes connexe engendré par le sommet isolé 𝑏
Exemple (cocyle élémentaire) :

Le cocycle 𝑤(𝐴) = {1,2,4} associé à 𝐴 = {𝑎, 𝑐} est élémentaire car la suppression de 𝐴
engendrera une seule composante connexe.
1
a b
2
5 3
c d
4
En supprimant 𝐴 = {𝑎, 𝑐} de 𝐺 (avec les arcs associés {1,2,4}), cela engendrera une seule
composante connexe engendrée par les sommets {𝑏, 𝑑}.
Exemple (décomposition de cocycle) :
6
4
2 3
5
Soit 𝐴 = {𝑒, 𝑑, ℎ}
Le cocycle de 𝐴 est : 𝑤(𝐴) = 𝑤 + (𝐴) ∪ 𝑤 − (𝐴) = {1} ∪ {2,6} = {1, 2, 6} peut être
décomposé en une somme comme suit :
∑ w(v) = w(e) + w(d) + w(h) = {1,2} + {6} = +1 − 1 − 1 = −1

v∈A
Dans cet exemple, seule reste la contribution d’un arc entrant dans 𝐴 .
Exemple (décomposition de cocycle) :

1
a b
2
5 3
c d
4
Le cocycle 𝑤(𝐴) = {1,2,4} est associé à = {𝑎, 𝑐} . Il peut être décomposé en une somme
comme suit :
∑ w(v) = w(a) + w(c) = {1,2} + {4} = +1 − 1 + 1 = +1

v∈A
Dans cet exemple, seule reste la contribution d’un arc sortant de 𝐴 .
1.2. Lemme des arcs colorés (Minty 1960)

Etant donné un graphe orienté dont les arcs sont numérotés de 1 à 𝑚 et sont colorés par trois
couleurs, soit en ROUGE, soit en VERT, soit en NOIR. L'arc 𝑢1 est supposé être coloré en
NOIR, alors une (et une seule) des propositions suivantes est vérifiée :
1) L’arc 𝑢1 appartient à un cycle élémentaire de couleurs ROUGE et NOIR uniquement
et dont tous les arcs NOIRS sont orientés dans le même sens que 𝑢1 ;
2) L’arc 𝑢1 appartient à un cocycle élémentaire de couleurs VERT et NOIR uniquement et
dont tous les arcs NOIRS sont orientés dans le même sens que 𝑢1 .
Exemple :
Sur le graphe colorié de la figure Fig.2.. La première proposition de l’existence de cycle est
vérifiée. Le cycle (4𝑁, 2𝑅, 12𝑁, 9𝑅) contient des arcs de couleurs soit ROUGES ou bien
NOIRS uniquement, avec les arcs de couleurs NOIRS dans le même sens.
Fig.2. Exemple de cycle NOIR et ROUGE avec tous les arcs NOIRS orientés dans le même
sens
Tandis que le graphe de la figure Fig.3. vérifie la deuxième proposition uniquement. Le

cocycle (4𝑁, 12𝑁, 10𝑉) engendré par l’ensemble des sommets entourés par le grand cercle,
contient deux couleurs des arcs : NOIRS (4𝑁, 12𝑁) ou bien VERT (10𝑉).
Fig.3.Exemple de cocycle NOIR et VERT avec tous les arcs NOIRS orientés dans le même
sens
1.3. Base de cycles et base de cocycles

1.3.1. Base de cycles
Les cycles 𝜇1 , 𝜇2 , … , 𝜇𝐾 sont des cycles indépendants si une combinaison linéaire des vecteurs
associés ne peut être nulle que si chaque coefficient est nul.
Une base fondamentale de cycles est un ensemble de cycles indépendants tel que tout cycle
puisse s'écrire comme une combinaison linéaire. Le nombre cyclomatique du graphe est égal à
la dimension de la base de cycles.
Théorème 1 :
Soit 𝐺 un graphe de 𝑛 sommets, 𝑚 arcs et 𝑝 composantes connexes. La dimension d’une base
de cycles est le nombre cyclomatique de 𝐺 :
𝑣(𝐺) = 𝑚 − 𝑛 + 𝑝
Algorithme de recherche d’une base de cycles
1) On démarre avec le graphe partiel 𝐺0 = (𝑋, ∅) où : 𝑚0 = 0, 𝑝0 = 𝑛 et 𝑣(𝐺0 ) =0

poser 𝑖 = 1
2) On ajoute l’arc 𝑢 de 𝐺, tester si on crée au moins un cycle
Si oui, on choisit un linéairement indépendant des autres et 𝑣(𝐺𝑖 ) = 𝑣(𝐺𝑖−1 ) + 1

Sinon, 𝑣(𝐺𝑖 ) = 𝑣(𝐺𝑖−1 ) reste inchangé
3) Tester si 𝑖 = 𝑚
Si oui, terminer
Sinon poser 𝑖 = 𝑖 + 1 et aller en 2)
Exemple :
Soit 𝐺 = (𝑋, 𝑈) tel que 𝑋 = {𝑎, 𝑏, 𝑐, 𝑑} et 𝑈 = {1,2,3,4,5}
1
a b
2
5 3
c d
4
1) Initialisation :
𝐺0 = (𝑋, ∅) où : 𝑚0 = 0, 𝑝0 = 4 et 𝑣(𝐺0 ) = 0
poser 𝑖 = 1
Itération 1 :
2) On ajoute l’arc 1 de 𝐺, tester si on crée au moins un cycle  NON
et v(G1 ) = v(G0 ) = 0 et G1 = (X, {1}) et 𝑚1 = 1
3) Tester si (𝑖 = 1) = (𝑚 = 5)  NON
poser 𝑖 = 𝑖 + 1 = 2 et aller en 2)
Itération 2 :
2) On ajoute l’arc 2 de G, tester si on crée au moins un cycle  NON
et v(G2 ) = v(G1 ) = 0 et G2 = (X, {1,2}) et 𝑚2 = 2
3) Tester si (𝑖 = 2) = (𝑚 = 5)  NON
Itération 3 :
2) On ajoute l’arc 3 de 𝐺, tester si on crée au moins un cycle  OUI
on choisit un cycle (μ1 = (1,2,3)) linéairement indépendant des autres
le vecteur caractéristique associé est 𝑤

⃗⃗⃗μ1 = (−1, −1, −1, 0, 0)
v(G3 ) = v(G2 ) + 1 = 0 + 1 = 1 et G3 = (X, {1,2,3}) et 𝑚3 = 3
3) Tester si (𝑖 = 3) = (𝑚 = 5)  NON
Itération 4 :
2) On ajoute l’arc 4 de 𝐺, tester si on crée au moins un cycle  NON
et v(G4 ) = v(G3 ) = 1 et G4 = (X, {1,2,3,4}) et 𝑚4 = 4
3) Tester si (𝑖 = 4) = (𝑚 = 5)  NON
Itération 5 :
2) On ajoute l’arc 5 de 𝐺, tester si on crée au moins un cycle  OUI
On choisit un cycle (𝜇2 = (4,5,2)) linéairement indépendant des autres
le vecteur caractéristique associé est ⃗w
⃗⃗μ2 = (0, −1,0, −1, +1)
v(G5 ) = v(G4 ) + 1 = 2 et G5 = (X, {1,2,3,4,5}) et 𝑚5 = 5

3) Tester si (𝑖 = 5) = (𝑚 = 5)  OUI
TERMINER
⃗⃗⃗𝜇1 , 𝑤
Alors {𝑤 ⃗⃗⃗𝜇2 } est une base de cycles
La dimension de cette base de cycles (d’après le théorème 1) est le nombre
cyclomatique de 𝐺 :
v(G) = m − n + p = 5 − 4 + 1 = 2 = v(G5 )
1.3.2. Base de cocycles
Les cocycles 𝑤1 , 𝑤2 , … , 𝑤𝑗 sont des cocycles indépendants si une combinaison linéaire
des vecteurs associés ne peut être nulle que si chaque coefficient est nul.
Une base fondamentale de cocycles est un ensemble de cocycles indépendants tel que
tout autre cocycle puisse s'écrire comme une combinaison linéaire. Le nombre
cocyclomatique du graphe est égal à la dimension de la base de cocycles.
Théorème 2 :
Soit 𝐺 un graphe de 𝑛 sommets et 𝑝 composantes connexes. La dimension d’une base de
cocycles est le nombre cocyclomatique de 𝐺 :
𝜆(𝐺) = 𝑛 − 𝑝
Si le graphe n’est pas connexe, soient 𝐶1 , … , 𝐶𝑝 ses composantes connexes. Il existerait

( (|𝐶1 | − 1) + ⋯ + (|𝐶𝑝 | − 1)) = 𝑛 − 𝑝 cocycles élémentaires indépendants.
Algorithme de construction d’une base de cocycles
Supposons que le graphe 𝐺 est connexe (𝑝(𝐺) = 1) et formons les 𝑛 − 1 cocycles élémentaires indépendants
de proche en proche.
1) On prend un sommet quelconque 𝑠1 et posons 𝐴1 = {𝑠1 }. Le cocycle 𝑤(𝐴1 ) contient un cocycle

élémentaire et soit ⌈𝑠1 , 𝑠2 ⌉ une arête de ce cocycle avec 𝑠1 Î 𝐴1 et 𝑠2 Ï 𝐴1
2) On pose 𝐴2 = 𝐴1 ∪ {𝑠2 }, le cocycle 𝑤(𝐴2 ) contient un cocycle élémentaire et soit ⌈𝑥, 𝑠3 ⌉ une arête
de ce cocycle avec 𝑥 Î 𝐴2 et 𝑠3 Ï 𝐴2
3) On pose 𝐴3 = 𝐴2 ∪ {𝑠3 }, et on recommence.
4) A la fin du processus on aurait construit (𝑛 − 1) cocycles élémentaires, linéairement indépendants.
Exemple :
Soit 𝐺 = (𝑋, 𝑈) un graphe connexe (𝑝(𝐺) = 1) tel que 𝑋 = {𝑎, 𝑏, 𝑐, 𝑑} et 𝑈 = {1,2,3,4,5}
1
a b
2
5 3
c d
4
1) On prend un sommet quelconque 𝑎 et posons 𝐴1 = {𝑎}.

Le cocycle associé est : 𝑤(𝐴1 ) = {1, 2, 5}
⃗⃗𝑤(𝐴1 ) = (+1, −1,0, 0, −1)
soit ⌈𝑎, 𝑐⌉ l’arête n°=5 ∈ 𝑤(𝐴1 ) de ce cocycle avec 𝑎 Î 𝐴1 et 𝑐 Ï 𝐴1
2) On pose 𝐴2 = 𝐴1 ∪ {𝑐} = {𝑎, 𝑐}
le cocycle associé est 𝑤(𝐴2 ) = {1,4,2}
⃗⃗w(A2 ) = (+1, −1,0, +1, 0)
soit ⌈𝑐, 𝑑⌉ l’arête n°=4 ∈ 𝑤(𝐴2 ) de ce cocycle avec 𝑐 Î 𝐴2 et 𝑑 Ï 𝐴2
3) On pose 𝐴3 = 𝐴2 ∪ {𝑑} = {𝑎, 𝑐, 𝑑}
Le cocycle associé est 𝑤(𝐴3 ) = {1,3}
⃗⃗w(A3 ) = (+1,0, −1, 0, 0)
Soit ⌈𝑑, 𝑏⌉ l’arête n°=3 ∈ 𝑤(𝐴3 ) de ce cocycle avec d Î A3 et 𝑏 Ï A3
4) On pose 𝐴4 = 𝐴3 ∪ {𝑏} = {𝑎, 𝑐, 𝑑, 𝑏} = 𝑋
𝑤(𝐴4 ) = ∅  FIN du processus
Alors {w
⃗⃗⃗⃗𝑤(𝐴1 ) , ⃗w
⃗⃗⃗w(A2 ) , ⃗w
⃗⃗w(A3 ) } est une base de cocycles
A la fin du processus on aurait construit 𝑛 − 1 = 4 − 1 = 3 cocycles élémentaires,
linéairement indépendants.
La dimension de cette base de cocycles (d’après le théorème 2) est le nombre
cocyclomatique de 𝐺 :
𝜆(𝐺) = 𝑛 − 𝑝 = 4 − 1 = 3
2. Planarité
2.1. Graphe Planaire
Définition 3 :
Un graphe est planaire s'il peut être tracé dans un plan sans que les arêtes se croisent. Un tel
tracé est appelé une représentation planaire du graphe (ou graphe planaire topologique).
Un graphe planaire topologique est une représentation planaire d’un graphe planaire.
Exemple :
Le graphe de gauche ci-dessous (Fig.4.) est planaire parce qu’en modifiant le tracé d’une
arête, on peut obtenir le graphe de droite qui est en fait une représentation différente du
même graphe, mais sans croisement d’arête.
D’après la définition 3 ci-dessus, ces 2 graphes sont planaires, mais seul celui de droite est
planaire topologique.
Fig.4. Exemple de graphe planaire

Définition 4 :
Soit G un graphe planaire topologique. Une face 𝑓 de G est une région maximale du plan
délimité par un ensemble d’arêtes de G, et qui n’en contient aucune et de sorte que deux
points arbitraires choisis de la face puissent toujours être reliés par un trait continu ne
rencontrant ni sommets, ni arêtes.
La frontière d’une face 𝑓 de 𝐺 est l’ensemble des arêtes qui la délimitent.

On appelle contour de la face 𝑓 celui des cycles élémentaires qui contient en son intérieur
toutes les arêtes de la frontière.
Il y a toujours une face illimitée et une seule qui constitue la face infinie. Celle-ci n’admet
évidemment pas de contour. Les autres faces sont finies et admettent toutes un contour.
Le degré de 𝑓, noté 𝑑𝑒𝑔(𝑓), est le nombre d’arêtes de 𝐺 qui bordent 𝑓. Autrement dit, le
degré d'une face 𝑓 est la longueur de son cycle frontière.
Deux faces sont adjacentes si elles ont un arc en commun. Deux faces sont opposées si elles
ont un sommet commun sans être adjacentes.
Exemple :
Le contour d’une face
Fig.5. Illustration de face, contour et frontière
Dans le graphe ci-après (Fig.6.) :

le contour de la face 𝑓1 est (1 − 4 − 7 − 6 − 5 − 1)
et la frontière de 𝑓1 est (1 − 3 − 2 − 1 − 5 − 6 − 7 − 4 − 1)
Fig.6. Exemple de contour et frontière d’une face

Exemple :
Dans le graphe ci-dessous (Fig.7.), on a 6 faces notées de 𝑓1 à 𝑓6. Notons que le contour
extérieur d’un graphe planaire topologique est également une face. Il s’agit dans notre
exemple de la face 𝑓6.
Toutes les faces sont bordées par 3 arêtes du graphe exactement, c’est-à-dire qu’elles sont
toutes de degré 3 (𝑑𝑒𝑔(𝑓𝑖) = 3, ∀𝑖 = ̅̅̅̅̅
1. .6).
Une face interne
Une face externe
Fig.7. Exemple de faces d’un graphe planaire
Fig.8. Le degré de la face non bornée de ce graphe planaire est égal à 6.
2.1.1. Application des graphes planaires

- Une application des graphes planaires est la conception de circuit intégrés (sans
croisement) où on cherche à relier et à combiner les composants dans le plan pour
pouvoir fabriquer une puce avec de milliers de transistors. La question se ramène donc
à trouver si le graphe induit est planaire et à le dessiner.
- Une autre application des graphes planaires est la planification de réseaux : routiers,
de télécommunications,…
2.2. Formule d'Euler
Dans un graphe planaire topologique connexe de 𝑛 sommets, 𝑚 arêtes et 𝑓 faces, on a :
𝑛−𝑚+𝑓 = 2
Exemple :
Le nombre de faces dans le graphe ci-contre est :

𝑓 = 𝑚−𝑛+2 = 6−4+2 =4
De la formule d’Euler nous pouvons déduire les deux propriétés suivantes :
Propriété 1 de la formule d’Euler :

Soit 𝐺 un graphe simple planaire connexe à 𝑛 sommets (𝑛 ≥ 3) et 𝑚 arêtes. Chaque face est
entourée de trois arêtes. Les 𝑓 faces impliquent 3 × 𝑓 arêtes, certaines étant communes, mais
pas toutes. D'où l'inégalité indiquée :
3×𝑓
𝑚≥
2
Avec la relation de Descartes-Euler :
𝑓 = 2+𝑚−𝑛
Soit l'inégalité indiquée :
2×𝑚 ≥ 6+3×𝑚−3×𝑛
Et la conclusion importante :
𝒎 ≤ 𝟑×𝒏−𝟔
(Dans un graphe planaire la quantité d’arêtes est inférieure à trois fois la quantité de
sommets).
Propriété 2 de la formule d’Euler :

Soit 𝐺 un graphe simple planaire connexe sans triangle à 𝑛 sommets (𝑛 ≥ 4) et 𝑚 arêtes. On
a:
𝒎 ≤ 𝟐×𝒏−𝟒
2.3. Théorème de Kuratowski (1930)

Une subdivision élémentaire 𝐺′ d’un graphe 𝐺 = (𝑋, 𝐸) est obtenue en remplaçant une arête
⌈𝑎, 𝑏⌉ par deux arêtes ⌈𝑎, 𝑥⌉ et ⌈𝑥, 𝑏⌉ où 𝑥 est un nouveau sommet. On a donc alors :
𝑋 ′ = 𝑋 ∪ {𝑥}
𝐺′ = (𝑋′, 𝐸′) 𝑡𝑒𝑙 𝑞𝑢𝑒 { et
𝐸 ′ = {𝐸 ∪ {⌈𝑎, 𝑥⌉ , ⌈𝑥, 𝑏⌉} \ ⌈𝑎, 𝑏⌉}
Une subdivision du graphe 𝐺 est obtenue par une succession de subdivisions élémentaires.
Exemple d’une subdivision :
𝐺 𝐺′
Fig.9. Exemple d’une subdivision 𝐺′ d’un graphe 𝐺
Remarque :
Il est clair que le fait de subdiviser une arête n’affecte pas la planarité (ou la non planarité) : si
𝐺 est planaire, toute subdivision de 𝐺 sera également planaire et si 𝐺 n’est pas planaire, toute
subdivision de 𝐺, sera également non planaire.
Puisque les graphes : 𝐾3,3 (voir Fig.10.) et 𝐾5 (voir Fig.11.) ne sont pas planaires, nous
déduisons de cette remarque que tout graphe qui contient une subdivision de 𝐾5 ou 𝐾3,3 est
non planaire.
Fig.10.Graphe complet biparti 𝐾3,3 Fig.11.Graphe complet 𝐾5
Théorème 3 :
Un graphe est planaire si et seulement s'il ne contient aucune subdivision du graphe complet à
5 sommets 𝐾5 , ou du graphe biparti complet 𝐾3,3.
2.4. Graphe Dual

Etant donné un graphe planaire 𝐺 connexe et sans sommets isolés (appelé graphe "primal"),
on peut lui faire correspondre un graphe planaire "dual" 𝐺 ∗ :
a) Chaque face 𝑓 de 𝐺 correspond un sommet 𝑠 ∗ de 𝐺 ∗ .
b) Deux sommets de 𝐺 ∗ sont reliés si et seulement si les faces correspondantes de 𝐺 ont
une arête commune (frontière).
Autrement dit, 𝑎∗ = (𝑓 ∗ , 𝑔∗ ) est une arête de 𝐺 ∗ qui relie les sommets 𝑓 ∗ et 𝑔∗ de 𝐺 ∗
si et seulement si les faces 𝑓 et 𝑔 de 𝐺 partagent l’arête 𝑎.
Le graphe 𝐺 ∗ obtenu s'appelle le graphe dual de 𝐺. Ce graphe est planaire, connexe et sans
sommet isolé.
Exemple :
Graphe primal 𝐺 Graphe dual 𝐺 ∗
Fig.12. Exemples de graphe Dual 𝐺 ∗ d’un graphe Primal 𝐺
Fig.13. Le graphe dessiné en rouge est le dual du graphe bleu dans le plan
3. Arbre, forêt et arborescence
3.1. Arbre
Définition 5 :
Un arbre est un graphe orienté ou non orienté, simple, sans boucle, connexe et sans cycle.
Exemple : L’exemple typique d’arbre est l’arbre généalogique.
Théorème 4 : soit 𝐺 un graphe d’ordre 𝑛 ≥ 2. Les propriétés suivantes sont équivalentes et

caractérisent un arbre :
i. 𝐺 est connexe et sans cycle.
ii. 𝐺 est connexe et minimal pour cette propriété (si on supprime une arête de 𝐺, il n’est
plus connexe).
iii. 𝐺 est connexe et possède (𝑛 − 1) arrêtes.
iv. 𝐺 est sans cycle et maximal pour cette propriété (si on ajoute une arête à 𝐺, il possède
un cycle).
v. 𝐺 est sans cycle et possède (𝑛 − 1) arêtes.
vi. Il existe dans 𝐺 une chaine et une seule joignant tout couple de sommets.
Remarque 1 :
Pour qu’un graphe n’ait pas de cycle, il faut globalement qu’il ait peu d’arêtes. Inversement,
pour qu’un graphe soit connexe, il faut qu’il ait globalement beaucoup d’arêtes.
Remarque 2 :
Un graphe connexe possède un graphe partiel qui est un arbre.
Remarque 3 :
Le graphe formé par un sommet est un arbre.
Propriété 1 :
Soit 𝑛 le nombre de nœuds d’un graphe 𝐺 = (𝑋, 𝐸), 𝑛 = |𝑋|. Soit 𝑚 le nombre d’arêtes de
𝐺, 𝑚 = |𝐸|. on a que :
 Si 𝐺 est connexe ⇒ 𝑚 ≥ 𝑛 − 1.
 Si 𝐺 est sans cycle ⇒ 𝑚 ≤ 𝑛 − 1.
Propriété 2 :
Il existe une relation très forte entre le nombre d'arêtes et le nombre de sommets d'un arbre :
un arbre 𝑇 = (𝑉, 𝐸) comporte exactement |𝑉| − 1 arêtes.
Exemples :
Fig.14. Un graphe orienté 𝐺 connexe Fig.15. Arbre extrait de 𝐺
Fig.16. Exemple d’un arbre non Fig.17. Exemple d’un graphe non orienté qui n’est
orienté pas un arbre
3.2. Forêt
Définition 6 :
Une forêt étant un graphe sans cycle, dont chacune de ses composantes connexes est un arbre.
La définition d'une forêt correspond donc bien au sens usuel d'un ensemble d'arbres, chacune
de ses composantes connexes étant un arbre.
Exemple :
Fig.18. Exemple de forêt
Remarques :
 La forêt est obtenue si on relâche la contrainte de connexité dans un arbre, c'est-à-dire,
si on supprime un arc dans un arbre.
 Tout graphe partiel d’un arbre est une forêt.
3.3. Arborescence
Définition 7 :
Un graphe orienté 𝐺 = (𝑋, 𝑈) avec |𝑋| ≥ 2 sommets est une arborescence de racine 𝑟 si :
 𝑟 est une racine de 𝐺,
 𝐺 est un arbre.
Le choix d'une racine revient dans un certain sens à orienter l'arbre dans le même sens, la
racine apparaissant comme l'ancêtre commun à la manière d'un arbre généalogique. Le
vocabulaire de la théorie des graphes s'en inspire directement : on parle de fils, de père, de
frère,...
Les conditions suivantes sont équivalentes et caractérisent une arborescence de racine 𝑟 :

i. 𝐺 est un arbre admettant le nœud 𝑟 comme racine
ii. ∀ 𝑥 ∈ 𝑋 il existe un chemin unique dans 𝐺 joignant 𝑟 à 𝑥
iii. 𝐺 admet 𝑟 comme racine et est minimal pour cette propriété (si on supprime un arc,
𝑟 n'est plus racine)
iv. 𝐺 est connexe et 𝑑 − (𝑟) = 0 et 𝑑 − (𝑥) = 1, ∀ 𝑥 ≠ 𝑟
v. 𝐺 admet 𝑟 comme racine et est sans circuit
vi. 𝐺 admet 𝑟 comme racine et possède (𝑛 − 1) arcs.
Exemples :
Fig.19. Exemples d’arborescences Fig.20. Exemples de graphes qui ne sont pas

des arborescences
Définition 8 :
Pour une arborescence 𝑯 de racine 𝒓 :
 Le père d'un sommet 𝒙 est l'unique voisin de 𝒙 sur le chemin de la racine 𝒓 à 𝒙. La racine
𝒓 est le seul sommet sans père.
 Les fils d'un sommet 𝒙 sont les voisins de 𝒙 autres que son père.
 Une feuille est un sommet sans fils. Les feuilles correspondent aux sommets de degré 1.
 La hauteur 𝒉(𝑯) de l'arborescence 𝑯 est la longueur du plus long chemin de la racine à
une feuille.
Remarques :
- Dans une arborescence, si on ignore l'orientation des arcs (i.e. si on considère des arêtes,
soit un graphe non orienté), alors 𝐺 est un arbre.
- Une arborescence est un arbre mais la réciproque est fausse.
Anti-arborescence :
Si on inverse le sens des arcs d'une arborescence, on obtient une anti-arborescence.
Un graphe 𝐺 est une anti-arborescence admettant 𝑟 comme anti-racine si :
 𝐺 est un arbre.
 𝑟 est une anti-racine.
Exemple :
Fig.21. Exemple d’arborescence et anti-arbrescence
3.4. Arbre couvrant de poids minimum d’un graphe

3.4.1. Problème
On souhaite relier différentes villes via un réseau électrique, mais en investissant le moins de
fonds possibles. Pour ce faire, des études préliminaires sont faites sur le terrain afin de savoir
quels sont les coûts de constructions de ces lignes entre les différentes villes. Disposant de ces
études préliminaires, comment connecter toutes les villes en minimisant le coût total du
réseau ?
En théorie des graphes, on modélise une telle situation par un graphe valué 𝐺 = (𝑋, 𝐸). Les
sommets du graphe sont les villes, et les arêtes du graphe sont les éventuelles lignes à
construire. Ces arêtes sont valuées par le coût 𝑐(𝑒) de construction de ces lignes.
Connecter toutes les villes correspond à sélectionner un ensemble d'arêtes 𝑬’ de 𝑮 tel que le
graphe partiel 𝑻 = (𝑿, 𝑬’) induit est connexe. Le poids de cette solution 𝒄(𝑻) est définie
comme la somme des poids de ses arêtes 𝑐(𝑇) = ∑𝑒′∈𝐸′ 𝑐(𝑒 ′ ). Le but est donc de
sélectionner un arbre maximum dans le graphe 𝐺 et qui soit de poids minimum (le plus
économique).
Il existe deux algorithmes célèbres pour résoudre le problème de l'arbre couvrant de poids
minimum.
3.4.2. Algorithme de Prim -1957-

Principe :
- on part d’un arbre initial A réduit à un seul sommet s (e.g., 𝑠 = 1) ;
- ensuite, à chaque itération, on augmente l’arbre 𝐴 en le connectant au « plus proche »
sommet libre au sens des poids.
ALGORITHME Prim
ENTREES 𝑮 = (𝑿, 𝑬) un graphe connexe avec une valuation positive des arêtes
SORTIE 𝑻 = (𝑨, 𝑬’) un arbre couvrant de poids minimum
𝑨 : ENSEMBLE des sommets marqués

𝑬’ : ENSEMBLE des arêtes de l'arbre
Initialiser 𝐸’ à vide
Marquer arbitrairement un sommet 𝑥 : 𝐴 = {𝑥}
Tant Que il existe un sommet non marqué adjacent à un
sommet marqué (𝐴 ≠ 𝑋)
Sélectionner un sommet 𝒚 non marqué adjacent à un sommet marqué 𝒙
tel que (𝒙, 𝒚) est l'arête sortante de plus faible poids
𝐸’ ∶= 𝐸’ ∪ {(𝒙, 𝒚)}
Marquer 𝒚 : 𝐴 = 𝐴 ∪ {𝑦}
Fin TantQue
Retourner 𝑻 = (𝑿, 𝑬’)
Exemple :
Appliquons l’algorithme de Prim sur le graphe suivant :
Initialisation :
Marquer arbitrairement un sommet 𝑥 : 𝐴 = {𝑥1 }
Initialiser 𝐸’ = ∅
Itération 1 :
𝐸’ ∶= 𝐸’ ∪ {(𝑥1 , 𝑥2 )} = {(𝑥1 , 𝑥2 )}
𝐴 = {𝑥1 , 𝑥2 }
Itération 2 :
𝐸’ ∶= 𝐸’ ∪ {(𝑥2 , 𝑥3 )} = {(𝑥1 , 𝑥2 ), (𝑥2 , 𝑥3 )}
𝐴 = {𝑥1 , 𝑥2 , 𝑥3 }
Itération 3 :
𝐸’ ∶= 𝐸’ ∪ {(𝑥1 , 𝑥5 )} = {(𝑥1 , 𝑥2 ), (𝑥2 , 𝑥3 ), (𝑥1 , 𝑥5 )}
𝐴 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥5 }
Itération 4 :
𝐸’ ∶= 𝐸’ ∪ {(𝑥5 , 𝑥4 )} = {(𝑥1 , 𝑥2 ), (𝑥2 , 𝑥3 ), (𝑥1 , 𝑥5 ), (𝑥5 , 𝑥4 )}
𝐴 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥5 , 𝑥4 }
Itération 5 :
𝐸’ ∶= 𝐸’ ∪ {(𝑥5 , 𝑥6 )} = {(𝑥1 , 𝑥2 ), (𝑥2 , 𝑥3 ), (𝑥1 , 𝑥5 ), (𝑥5 , 𝑥4 ), (𝑥5 , 𝑥6 )}
𝐴 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥5 , 𝑥4 , 𝑥6 }
Itération 6 :
𝐴 = 𝑋  STOP

𝑋 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥5 , 𝑥4 , 𝑥6 }
𝐸’ = {(𝑥1 , 𝑥2 ), (𝑥2 , 𝑥3 ), (𝑥1 , 𝑥5 ), (𝑥5 , 𝑥4 ), (𝑥5 , 𝑥6 )}
𝒄(𝑻) = 2 + 1 + 5 + 4 + 7 = 19
3.4.3. Algorithme de Kruskal - 1956-

Principe :
On numérote les arêtes 𝑒𝑖 selon un ordre croissant de leurs valuations ( la valuation 𝑐(𝑒𝑖 ) de
l’arête 𝑒𝑖 vérifie : 𝑣(𝑒𝑖 ) ≤ 𝑣(𝑒𝑖+1 )). On construit alors un arbre couvrant du graphe 𝐺 en
considérant les arêtes 𝑒𝑖 dans l’ordre de numérotation, et en retenant 𝑒𝑖 si elle ne forme pas de
cycle avec les arêtes préalablement sélectionnées.
ALGORITHME Kruskal
ENTREES 𝑮 = (𝑿, 𝑬) un graphe connexe avec une valuation positive des arêtes
SORTIE 𝑻 = (𝑨, 𝑬’) un arbre couvrant de poids minimum
Début
Trier les arcs de 𝐺 dans l’ordre croissant des poids;
[On les notera 𝑒1 , 𝑒2 , . . . , 𝑒𝑚 .]

Initialiser 𝐸’ à vide
pour 𝑖 = 1 à 𝑚 faire
si le graphe (𝑋 ; 𝐸’ ∪ {𝑒𝑖 }) ne contient pas de cycle alors
𝐸’ = 𝐸’ ∪ {𝑒𝑖 } ;
fin si
fin pour
Fin
Exemple :
Appliquons l’algorithme de Kruskal sur le graphe suivant :
Trier les arcs de 𝐺 dans l’ordre croissant des poids :
𝑒1 = (𝑥2 , 𝑥3 ) = 1
𝑒2 = (𝑥1 , 𝑥2 ) = 2
𝑒3 = (𝑥1 , 𝑥3 ) = 3
𝑒4 = (𝑥4 , 𝑥5 ) = 4
𝑒5 = (𝑥1 , 𝑥5 ) = 5
𝑒6 = (𝑥3 , 𝑥4 ) = 6
𝑒7 = (𝑥5 , 𝑥6 ) = 7
𝑒8 = (𝑥1 , 𝑥6 ) = 8
𝑒9 = (𝑥2 , 𝑥6 ) = 9
𝑒10 = (𝑥2 , 𝑥4 ) = 10
𝑒11 = (𝑥1 , 𝑥4 ) = 11
𝑒12 = (𝑥3 , 𝑥5 ) = 12
Initialiser 𝐸’ = ∅
Itération 1 :
Le graphe (𝑋 ; 𝐸’ ∪ {𝑒1 }) ne contient pas de cycle
𝐸’ = 𝐸’ ∪ {(𝑥2 , 𝑥3 )} = {(𝑥2 , 𝑥3 )}
Itération 2 :
𝐸’ = 𝐸’ ∪ {(𝑥1 , 𝑥2 )} = {(𝑥2 , 𝑥3 ), (𝑥1 , 𝑥2 )}
Itération 3 :
Le graphe (𝑋 ; 𝐸’ ∪ {𝑒3 }) contient de cycle
Itération 4 :
𝐸’ = 𝐸’ ∪ {(𝑥4 , 𝑥5 )} = {(𝑥2 , 𝑥3 ), (𝑥1 , 𝑥2 ), (𝑥4 , 𝑥5 )}
Itération 5 :
𝐸’ = 𝐸’ ∪ {(𝑥1 , 𝑥5 )} = {(𝑥2 , 𝑥3 ), (𝑥1 , 𝑥2 ), (𝑥4 , 𝑥5 ), (𝑥1 , 𝑥5 )}
Itération 6 :
Itération 7 :
𝐸’ = 𝐸’ ∪ {(𝑥5 , 𝑥6 )} = {(𝑥2 , 𝑥3 ), (𝑥1 , 𝑥2 ), (𝑥4 , 𝑥5 ), (𝑥1 , 𝑥5 ), (𝑥5 , 𝑥6 )}
Itération 8 :
Itération 9 :
Itération 10 :
Itération 11 :
Itération 12 :

𝑋 = {𝑥1 , 𝑥2 , 𝑥3 , 𝑥5 , 𝑥4 , 𝑥6 }
𝐸’ = {(𝑥2 , 𝑥3 ), (𝑥1 , 𝑥2 ), (𝑥4 , 𝑥5 ), (𝑥1 , 𝑥5 ), (𝑥5 , 𝑥6 )}
𝒄(𝑻) = 1 + 2 + 4 + 5 + 7 = 19

Chapitre 2 Cycles

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 2 Cycles

Transféré par

Informations du document

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Chapitre 2 Cycles

Transféré par

Droits d'auteur :

Formats disponibles

Chapitre 2 : Cycles page 21

1. Nombres cyclomatique et cocyclomatique

1. Nombres cyclomatique et cocyclomatique

On choisit un sens de parcours du cycle μ. On désigne par :

𝜇 = (𝑢1 , 𝑢5 , 𝑢9 , 𝑢7 , 𝑢2 ) 𝑒𝑠𝑡 𝑢𝑛 𝑐𝑦𝑐𝑙𝑒 𝑑𝑒 𝑙𝑜𝑛𝑔𝑢𝑒𝑢𝑟 5

Les arcs sont numérotés 𝑢1 , 𝑢2 , … , 𝑢9 , on peut faire correspondre au cycle 𝜇 le vecteur

𝜇⃗ = (+1, −1, 0, 0, −1, 0, −1, 0, +1)

1.1.2. Décomposition des cycles

Fig.1. Exemple de décomposition de cycle 𝜇 en 2 cycles élémentaires 𝜇1 et 𝜇2

1.1.3. Vecteur caractéristique de cocycle

+1 𝑠𝑖 𝑢𝑖 ∈ 𝑤 + (𝐴) (l’arc 𝑢𝑖 est orienté vers l’extérieur de 𝐴)

w(v) est le cocyle pour un sommet v.

Seule reste la contribution des arcs sortant ou entrant dans 𝐴.

Exemple (cocyle élémentaire) :

∑ w(v) = w(e) + w(d) + w(h) = {1,2} + {6} = +1 − 1 − 1 = −1

Exemple (décomposition de cocycle) :

∑ w(v) = w(a) + w(c) = {1,2} + {4} = +1 − 1 + 1 = +1

Dans cet exemple, seule reste la contribution d’un arc sortant de 𝐴 .

1.2. Lemme des arcs colorés (Minty 1960)

Tandis que le graphe de la figure Fig.3. vérifie la deuxième proposition uniquement. Le

1.3. Base de cycles et base de cocycles

Algorithme de recherche d’une base de cycles

1) On démarre avec le graphe partiel 𝐺0 = (𝑋, ∅) où : 𝑚0 = 0, 𝑝0 = 𝑛 et 𝑣(𝐺0 ) =0

Si oui, on choisit un linéairement indépendant des autres et 𝑣(𝐺𝑖 ) = 𝑣(𝐺𝑖−1 ) + 1

le vecteur caractéristique associé est 𝑤

v(G5 ) = v(G4 ) + 1 = 2 et G5 = (X, {1,2,3,4,5}) et 𝑚5 = 5

Si le graphe n’est pas connexe, soient 𝐶1 , … , 𝐶𝑝 ses composantes connexes. Il existerait

Algorithme de construction d’une base de cocycles

1) On prend un sommet quelconque 𝑠1 et posons 𝐴1 = {𝑠1 }. Le cocycle 𝑤(𝐴1 ) contient un cocycle

4) A la fin du processus on aurait construit (𝑛 − 1) cocycles élémentaires, linéairement indépendants.

1) On prend un sommet quelconque 𝑎 et posons 𝐴1 = {𝑎}.

Fig.4. Exemple de graphe planaire

La frontière d’une face 𝑓 de 𝐺 est l’ensemble des arêtes qui la délimitent.

Le contour d’une face

Fig.5. Illustration de face, contour et frontière

Dans le graphe ci-après (Fig.6.) :

Fig.6. Exemple de contour et frontière d’une face

Une face interne

Une face externe

Fig.7. Exemple de faces d’un graphe planaire

Fig.8. Le degré de la face non bornée de ce graphe planaire est égal à 6.

2.1.1. Application des graphes planaires

Le nombre de faces dans le graphe ci-contre est :

De la formule d’Euler nous pouvons déduire les deux propriétés suivantes :

Propriété 1 de la formule d’Euler :

Propriété 2 de la formule d’Euler :

2.3. Théorème de Kuratowski (1930)

Exemple d’une subdivision :

Fig.9. Exemple d’une subdivision 𝐺′ d’un graphe 𝐺

Fig.10.Graphe complet biparti 𝐾3,3 Fig.11.Graphe complet 𝐾5

2.4. Graphe Dual

Graphe primal 𝐺 Graphe dual 𝐺 ∗

Fig.12. Exemples de graphe Dual 𝐺 ∗ d’un graphe Primal 𝐺

Théorème 4 : soit 𝐺 un graphe d’ordre 𝑛 ≥ 2. Les propriétés suivantes sont équivalentes et

Fig.14. Un graphe orienté 𝐺 connexe Fig.15. Arbre extrait de 𝐺

Fig.18. Exemple de forêt

Les conditions suivantes sont équivalentes et caractérisent une arborescence de racine 𝑟 :

Fig.19. Exemples d’arborescences Fig.20. Exemples de graphes qui ne sont pas

Fig.21. Exemple d’arborescence et anti-arbrescence

3.4. Arbre couvrant de poids minimum d’un graphe