Théorie des graphes

Bastien Fayolle

14 juin 2024
Théorie des graphes 14 juin 2024

Table des matières

Structure de graphe 4
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Notations / Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Voisinage au sommet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Degré d’un sommet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Degré de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Graphe K-régulier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chemin (simple) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Cycle (ou circuit) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Marche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Cheminement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Tour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Sous-graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Sous graphes induits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Sous graphes couvrants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Famille et caractéristiques de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Graphe Complet Kn ou Clique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Ensemble indépendants/ Stables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Etoile K1...n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Forêts / Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Graphe connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Composant connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Graphe Biparti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Décomposition en cycles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Décomposition en chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Théorème de Veblen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Tour Eulérien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Parcours de graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Parcours Générique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
Parcours en largeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Parcours en profondeur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
Représentation en machine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Matrice d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Liste d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
Matrice d’incidence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Diamètre d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Bastien Fayolle 1
Théorie des graphes 14 juin 2024

Classement des arcs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Lemme : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Tri topologique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Composante fortement connexes d’un Graphe orienté . . . . . . . . . . . . . . . . . . . . . 23
Composante fortement connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
Graphe des composantes fortement connexes d’un graphes orienté. . . . . . . . . . . 23
Couplages (matching) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Chemin M -Alternant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Cycles alternants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
Couplage dans les graphes bipartis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
Vertex Cover (couverture de sommets) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Théorème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Preuve . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Théorème . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

Algorithme d’optimisation de graphe 28

Arbre couvrants de poids minimum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Algorithme générique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Invariant de Couleur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Algorithme de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
Algorithme de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Plus courts chemin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Plus courts chemins dans les graphes pondérés. . . . . . . . . . . . . . . . . . . . . . 31
Principe de sous-optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Inégalité triangulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Propagation d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
Algorithme de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
Algorithme de Bellman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Flots maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Chemin améliorant . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
Coupe minimum et flots maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
Algorithme de Ford-Fulkerson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Coloration de graphes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
Problème de coloration : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Construction de Mycielski . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
Coloration d’arêtes d’un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Correspondance Coloration d’arête / coloration de sommets . . . . . . . . . . . . . . 44
Théorème de Vizing : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

Bastien Fayolle 2
Théorie des graphes 14 juin 2024

Flots . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Connexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Chemins disjoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Ensemble séparateur. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
Graphe k-connexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
K-Fan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

Bastien Fayolle 3
Théorie des graphes 14 juin 2024

Structure de graphe

Introduction

Un graphe simple est un graphe sans boucle ni arête multiple. Il n’y a alors d’arêtes qu’entre des
sommets distincts, et entre deux sommets il y a au plus une arête.

Graphe G = (V, E) V : Ensemble‘ (fini) de sommets E : Ensemble (fini) d’arrêtes

Un graphe peut être orienté (on écrire alors G = (V, A)).

V

E⊆ 2 ≡ toutes les différentes paires de sommets de V

V = {a, b, c, d}

E = {{a, b}, {b, c}, {c, d}, {d, a}}

S4
a b c d

V (S4 ) = {a, b, c, d}

E(S4 ) = ∅

{a, b} ≡ {b, a} mais (a, b) ̸≡ (b, a) car (a, b) représente un arc (orienté) et {a, b} représente une arête
(pas orientée).

2
1 3 4

D = (V, A)

V = {1, 2, 3, 4}

A = {(1, 2), (2, 3), (3, 1), (3, 4)}

Bastien Fayolle 4
Théorie des graphes 14 juin 2024

S’il existe une orientation transitive, alors le graphe correspond à un ordre partiel.

Application des graphes :

• Plus cours chemin

On peut l’utiliser en :

• mathématique/ combinatoire
• algorithmique
• algebre
• probabilité

Notations / Définitions

Soit G = (Vi E) un graphe fini.

e = {v, v} et a = (v, v) sont des boucles.

Voisinage au sommet

Soit le graphe G suivant :

c d
b e a

Le voisinage au sommet de v s’exprime NG (v) = {w|{v, w} ∈ E(G)}

Degré d’un sommet

Le degré d’un sommet est noté dG (v) = |NG (v)| (c’est le nombre de voisin de v) Si G=(V,A) est orientée,
on peut distinguer le voisinage entrant et sortant :

• Voisinage entrant de v : NG− (v) = {w|(w, v) ∈ A(G)}

Bastien Fayolle 5
Théorie des graphes 14 juin 2024

• Voisinage sortant de v : NG+ (v) = {w|(v, w) ∈ A(G)}

Degré de graphe

δ(G) = degré minimum (degré du sommet qui a le moins de voisin)

δ(G) = min(dG (v)|v ∈ A(G))

∆(G) = degré maximum (degré du sommet qui a le plus de voisin) ∆(G) = maxdG (v)|v ∈ A(G)

Graphe K-régulier

Un graphe est k-régulier ssi chaque sommet est de degré k.

Chemin (simple)

Soit la séquence P = (v1 , v2 , . . . , vk ) c’est un chemin ssi (vi , vi+1 ) ∈ E(G)∀i ∈ 1, 2, . . . , k − 1.

Un chemin sur k sommets est noté Pk . On dit qu’il est maximal si on ne peut plus lui ajouter d’arêtes.

Cycle (ou circuit)

Un cycle est un chemin dans lequel les sommets de Départs et d’Arrivé sont les mêmes. Un circuit (ou
cycle) sur k sommets est noté Ck .

Marche

Une marche : chemin ou suite de chemins où les sommets et les arrêtes peuvent apparaître plusieurs
fois.

Cheminement

Marche où les sommets peuvent apparaître plusieurs fois mais les arêtes n’apparaissent qu’une seule
fois.

Tour

Cheminement fermé → Sommet de départ = arrivé

Bastien Fayolle 6
Théorie des graphes 14 juin 2024

Sous-graphes

G = (V, E) H = (W, F )

H est un sous-graphe de G ssi W ⊆ V et F ⊆ E

Sous graphes induits

H = (W, F ) est un sous-graphe induit de G(V, E) ssi W ⊆ V et F = E ∩ (W ∗ W ) noté H = G[W ]

(Un sous-graphe induit est un sous-graphe obtenu en restreignant le graphe à un sous-ensemble de
sommets et en conservant toutes les arêtes entre sommets de ce sous-ensemble.)

1 2 1 2 1 2 2

7 6 3 7 6 3 6 6

5 4 4 5 4 5 4

G G₁ G₂ G₃
Figure 1: Exemple de la relation de sous-graphe

G1, G2 et G3 sont des sous-graphes de G. G1 n’est pas un sous-graphe induit car il manque l’arête
2-6. G2 et G3 sont des sous-graphes induits.

Sous graphes couvrants

Un sous-graphe couvrant ou graphe partiel est un sous-graphe ayant le même ensemble de sommets
que le graphe qui le contient.

Famille et caractéristiques de graphes

Graphe Complet Kn ou Clique

Graphe complet, Wikipedia

Ensemble des graphes où il y a une arête entre chaque paire de Sommets. (chaque sommet est voisin
de tous les autres) Si on note n l’ordre d’un tel graphe, alors sa taille est n(n−1)
2

Bastien Fayolle 7
Théorie des graphes 14 juin 2024

Ensemble indépendants/ Stables

Ensemble de sommet dans un graphe, deux à deux non adjacents.

Etoile K1...n

Forme d’une ensemble indépendant de taille n et d’un sommet dominant.

On note Sn l’étoile avec

Figure 2: Les graphes en étoile S3 , S4 , S5 et S6

Forêts / Arbres

Forêt ≡ graphe sans cycle.

Arbre ≡ forêt connexe.

Graphe connexe

G = (V, E) est connexe si pour toute paire de sommets vi , vj ∈ V (G)vi ̸= vj , il existe un chemin dans
G de Vi à Vj .

Composant connexe

Composante Connexe ≡ sous-ensemble de sommets maximalement connexe

Graphe Biparti

Wikipedia : Graphe biparti

Bastien Fayolle 8
Théorie des graphes 14 juin 2024

G = (V, E) est biparti si on peut partitionner V en deux partis A et B telles que G[A] est un Stable et
G[B] est un Stable.

Figure 3: Graphe biparti : exemple

Remarque N’importe quel cycle impair n’est pas biparti.

Lemme Si G = (V, E) contient comme sous-graphe H = (W, F ) un cycle de longueur Impaire, G

n’est pas biparti.

Théorème Un graphe est biparti ssi il ne contient pas de cycle impair

Preuve

• ⇒ Par contraposée, en utilisant le lemme précédent

• ⇐ Soit G = (V, E) et soit T = (V, F ) un arbre couvrant de G

L’arbre couvrant T induit une Bipartition des sommets de G.

On choisit un sommet arbitraire x

A= l’ensemble des sommets à distance paire de x dans T

B = l’ensemble des sommets à distance impaire de x dans T

On va montrer que pour les arêtes qui ne sont pas dans T (i.e. E \ F ) la partition induite par T
sur les sommets est valide

Bastien Fayolle 9
Théorie des graphes 14 juin 2024

Supposons G sous cycle impaire et G pas biparti, il existe une arête e∈ E \ F telle que a et b
sont dans la même partie.

e = {a, b} ∈ E \ F

Comme T est couvrant , il existe un chemin reliant a à b dans T .

Donc la longueur du chemin qui relie a à b est paire dans T

Si on ferme ce chemin avec l’Arête {a, b}, on obtient un cycle de longueur impaire, Donc contra-
diction

Décomposition en cycles.

G = (V, E)

On veut trouver une partition des arêtes F = F1 , F2 , ...Fk telle que Fi forme un cycle élémentaire.

Pout qu’un graphe admette une décomposition en cycle, le degré de chaque sommet doit être pair

Pour chaque sommet v , chaque cycle qui passe par v doit pouvoir arriver et repartir

Décomposition en chemin

La décomposition en chemin est toujours possible (puisqu’une arête est un chemin).

Théorème de Veblen

Un graphe admet une décomposition en cycle ssi G est pair.

Lemme : Soit G = (V, E); un graphe, Si δ(G) ≥ 2, alors G contient un cycle

Preuve Soit P un chemin le plus long dans G (longueur maximale)

P = (v1 , v2 , v3 , ..., vk ) Comme δ(G) ≥ 2, v1 a au moins un autre voisin que v2 et vk a au moins un

autre voisin que vk−1 .

Comme P est déjà de longueur maximum, le voisin manquant de v1 est sur le chemin P \ {v2 }

On note vi le voisin de v1 (i ̸= 2) Ainsi, (v1 , v2 , . . . , vi , v1 ) forme un cycle.

Le cycle a longueur au moins 3.

Bastien Fayolle 10
Théorie des graphes 14 juin 2024

Un chemin est maximal si on ne peut pas lui rajouter des arêtes pour que ca reste un chemin

preuve du théorème de Veblen

• ⇒ Procédons par induction descendante :

– Si G est pair, δ(G) ≥ 2, par le lemme précédent, G contient un cycle C1 (base)

– E(G′ ) = E(G) \ E(C1 )
– G′ est un graphe pair, car pour chaque sommet v qui participait au cycle C1 , sont degré à
diminuer de 2 unités
– On va appliquer la récursion sur les sommets de G′ tells que dG′ (v) > 0 (G′′ ) (un graphe
avec tous les sommets qui ont un degré positif)
– G′′ , (si il a encore des sommets), est pair et δ(G′′ ) ≥ 2
– On répète le processus jusqu’à ce que toutes les arêtes soit supprimés.

• ⇐ : ε = {C1 , C2 , ..., Ck } pour chaque sommet v, si v est incident à p cycle, sont degré est 2p

Tour Eulérien

Un cheminement fermé qui passe exactement une seule fois par toutes les arêtes du graphe

(cf les ponts de Königsberg)

Bastien Fayolle 11
Théorie des graphes 14 juin 2024

Lemme :

Si G = (V, E) admet un tour Eulérien, alors G est pair

Preuve On considère un tour Eulérien, w = v1 v2 , v3 , v1 , vk A chaque occurrence de vi dans le tour,

on va avoir 2 voisins de degré 2 associés à vi

Théorème de Fleury Si G est pair, alors G admet un tour Eulérien

Algorithme (Fleury) Algorithme : calcul un tour Eulériens si G est pair

Bastien Fayolle 12
Théorie des graphes 14 juin 2024

Algorithm Algorithme de Fleur

Input: G=(V,E) un graphe connexe pair
Output: Un tour Eulérien W qui commence à u

W := u (un sommet arbitraire)

x := u(la variable de sommet)
F := G(Le graphe de travail)
While df (x) ̸= 0 do:
Choisir e=xy une arête de F telle que e n’est pas déconnectante, sauf si c’est la seule
W = W ∪ {X, Y }
x=y
F =F \e
end while
return W

Complexité : O(n + m)

Soit x un ensemble de sommets ∂(X) ensemble des arêtes avec une extrémité dans X et l’autre dans
V \X

Arête déconnectante : e = {a, b} telle G − {e} n’est plus connexe.(e est nommé Isthme, ou pont/-
bridge)

Preuve Par induction , sur le nombre d’arêtes dans W, où W un cheminement où les arêtes sont
utilises au plus une fois (car chaque arête, une fois utilisée, est supprimée de F) On s’arrête quand
dF (x) = 0; c’est un cheminement fermé

Pour prouver que toutes les arêtes sont utilisés, on fait un raisonnement par l’Absurde. On considère
l’ensemble des sommets X qui ont un degré positif à la fin de l’algorithme. Des arêtes de G n’ont pas
été sélectionnée par l’algorithme.

–> Comme W est un cheminement fermé, F [X] est un graphe pair

L’ensemble V − X est non vide car u (le sommet de départ) est dans V \ X

Comme G est connexe, dG (x) ̸= 0 par contre dF (x) = 0

Bastien Fayolle 13
Théorie des graphes 14 juin 2024

Donc la dernière arrête utilisée pour construire le tour W de dF (x) , c’était une arête déconnectante.
(a = {a, b}) Quand on était sur le sommet b et qu’on a choisi e , d’autre arêtes non-déconnectantes
étaient disponibles, contredisant les choix suivis par l’Algorithme

Remarque : il existe un autre algorithme qui est basé sur la décomposition en cycle, et qui permet de
calculer de manière incrémentale un tour Eulérien, en rajoutant un cycle à la fois.

Parcours de graphe

Il existe 3 parcours différents :

• Parcours générique
• Parcours en largeur → Plus court chemin dans des graphes unitaires
• Parcours en profondeur → Calcule de composantes fortement connexes

Les algorithmes de parcours permettent d’explorer le graphe dans un certain ordre et d’extraire des
propriétés de ce graphes

Parcours Générique

Algo (cf cours de université picardie )

Input : (G = V, E) un graphe et s un sommet de départ

Output : σ : V → N+ un ordre sur les sommets

1 L= liste des sommets à traiter

2 i=1
3 While L!=0
4 V:=un sommet de L (au hasard)
5 sigma(v) = i
6 i++
7 for each w in N (v)\L do
8 L = L union {w}
9 L = L\{v}
10 Return sigma

Ce parcours générique permet de déterminer rapidement si G est connexe. G est connexe si tous les
sommets ont un σ[v] ̸= ∅

On peut trouver un arbre couvrant de G avec le parcours générique

Pour chaque sommet V on peut associer un sommet “parent”, seulement basé sur les étiquettes
σ[V ]

Le premier sommet V aura σ[v] = 1. Pour les autres sommets w, on aura σ[w] = min(σ[v]|v ∈ NG (u))

Bastien Fayolle 14
Théorie des graphes 14 juin 2024

On peut même déduire une orientation des arcs vers le sommet de départ

Complexité : O(n + m) (boucle while (O(1))exécuté exactement n fois )

ΣdG (v) + n

Parcours en largeur

Input : G = (V, E) un graphe simple et s un sommet de départ

Output : σ : v → N+ Arbre T enraciné en S

1 foreach v in V(G) do:

2 l[v]= +infini // level
3 p[v] = vide //parenté
4 sigma[v] = 0 //numéro du sommet
5 C[V] = Blanc // couleur
6 L = (s)
7 l[s]=0
8 i=1
9 while L!=vide
10 v:=prmierElement(L)
11 L:=L\{v}
12 foreach w in N(v) et c[w] ==Blanc //pour chaque voisin de u, si il
n'est pas noir
13 ajouter w a la fin de L
14 p[w] = v
15 l[w]+=1
16 c[w] = gris
17 sigma[v] = i
18 c[v] = noir
19 Return sigma

Exemple de parcours en largeur

l[v] : niveau

σ[v] : ordre de traitement des données

C[v] : couleur

1 pour chaque itération :

2 0) L=(a)
3 1) L=(i,b)
4 2) L=(b,e,h) // j'ai ajouté les voisins de i
5 3) L=(e,h,c,d)
6 4) L=(h,c,d,f)
7 5) L=(c,d,f)

Bastien Fayolle 15
Théorie des graphes 14 juin 2024

8 6) L=(d,f)
9 7) L=(f)
10 8) L=(g)
11 9) L=()

Complexité du parcours en largeur O(n + m)

Le parcours en largeur sur les graphes unitaires permet de calculer les plus courts chemins d’un sommet
vers tous les autres

Remarque La relation de parenté forme un sous-arbre couvrant de G

Le plus court chemin de x vers s est obtenu par la relation de parenté

Propriété / lemme/ preuve Notation:

δ(x, y) = longueur du plus court chemin de x à y

Lemme : Soit G = (V, E), et s un sommet de départ (S, V ) ̸∈ E(G)

σ(S, V ) ≤ δ(s, u) + 1 ∀u ∈ NG (V )

Lemme : G = (V, E) graphe et S un sommet de G (sommet de départ)

l[v] ≥ δ(S, V )∀v ∈ V (G)v ̸= s

Preuve : Par récurrence sur le nombre total de sommets insérés dans L

Base : |L| = 1, L = (s) et l[s] = 0

Recurrence :

On considère un sommet blanc V qui est découvert par le parcours en largeur.

V est découvert par l’exploration de u.

Par hypothèse de récurrence: l[u] ≥ δ(S, u) l[u] = l[u]+1 l[v] = l[u]+1 ≥ δ(S, u)+1 l[v] ≥ δ(S, u)+1
δ(S, u) + 1 ≥ δ(S, v)« par le lemme précédent l[v] ≥ δ(s, v)

Lemme : A un instant t, pour les sommets (v1 , v2 , ..., vk ) présents dans L - l[vk ] ≥ l[v1 ] + 1 (le niveau
du dernier sommet est inférieur au niveau du premier sommet +1) - l[vi ] ≥ l[vi+1 ]

Théorème

Soit G = (V, E) un graphe simple et s un sommet de départ. A la fin du parcours en largeur, on a

l[v] = δ(s, v), ∀v ∈ V (G)

Bastien Fayolle 16
Théorie des graphes 14 juin 2024

Preuve

Par récurrence Base : vraie pour S

Induction : on prouve par l’absurde

On suppose qu’il existe un sommet v pour lequel l’algo trouve une valeur v pour laquelle l[v] ̸= δ(s, v),
l[v] > δ(s, v). (v est le premier sommet avec cette propriété)

On considère le sommet u qui a permis à v d’être traité. Par le choix de v, on a σ[v] > σ[u] et donc
l[u] = δ(s, u).

On se place au moment où u est supprimé de la liste

1. SI v est noir, u a été inséré dans la liste après v , l[v] ≤ l[u] : Pas possible
2. Si v est gris, il y a un autre sommet w qui a fait entrer v dans L et σ[w] < σ[u] donc l[v] ≤ l[u]
Pas possible
3. Si v est blanc, u qui fait rentrer v dans la liste, donc l[v] = l[u] + 1 = δ(s, v)

Parcours en profondeur

avec f la date de fin d la date de début

Procédure : P P (G)

Input : G(V, E)

Output : Arborescence de G

1 foreach v in in V(G) do:

2 c(v)=Blanc
3 p[v]=vide
4
5 date=0 //variable globale
6 foreach v in V(G) do:
7 if(c(v) ==Blanc)then:
8 visiter_PP(V)
9
10
11 visiter_pp(u)
12 c(u) = "Gris"
13 date+=1
14 d(u)=date
15 foreach(u,w) in E(G)do //pour toutes les arêtes incidents à u
16 if(c(w) =="Blanc")then
17 p[w] =u
18 c[w]=="gris"
19 visiter_pp(w)
20 c[u] = noir

Bastien Fayolle 17
Théorie des graphes 14 juin 2024

21 date++
22 f(u)=date

(cfData Structure - Depth First Traversal)

(debut, fin) Noir(x,y) Gris(x, ) Blanc( , )

Pour chaque sommet V, on va associer un interval Iv = d[v], f [v])

Figure 4: parcours en profondeur

Bastien Fayolle 18
Théorie des graphes 14 juin 2024

Théorème Soit G un grahpe, et Iv ∀v les intervalles calculés par le DFS sur G. ∀v, w

• Iv et Iw sont des disjoints

• Iv ⊆
̸ Iw
• Iw ⊈ Iv

Preuve Sans perte de généralité, d[v] < d[w]

2 cas à considérer:

1. d[w] < f [v] : ca signifie que w a été exploré alors que v était déjà gris. Donc la fin du traitement
de w interviendra avant celle de v. On aura :

d[w] < f [w]wf [v]

2. Si la date de début de w est plus grande que la date de fin, (d[w] > f [v]), les intervalles sont
disjoints.

Théoreme Dans une forêt de parcours en profondeur, un sommet v est un descendant d’un sommet
u si au moment où u est exploré , il existe un chemin composé uniquement de chemins blancs de u à v
dans G

Complexité : O(n + m)

Bastien Fayolle 19
Théorie des graphes 14 juin 2024

Représentation en machine

Matrice d’adjacence

Figure 5: Matrice d’adjacence

Une matrice carrée n × n mij = 1 ssi i est adjacent j. (on remarque que la matrice est symétrique sur
la diagonale identité dans un graphe non-orientée, elle sera asymétrique dans un graphe orienté).

Pour les Algos de graphes, 2 opérations sont utilisés:

• Test d’adjacence de deux sommets (Adji,j ∈ O(1))

• La liste des voisins N (x) ∈ O(n)

Liste d’adjacence

une liste de liste. Pour chaque sommets v, on aura la liste de ses voisins. (∈ O(n + m))

Bastien Fayolle 20
Théorie des graphes 14 juin 2024

Adj(x, y) ∈ O(min(dG (x), dG (y))) N (x) ∈ O(dG (x))

Matrice d’incidence

Matrice n × m où les lignes correspondent aux sommets et les arrêtes aux colonnes

Diamètre d’un graphe

Diamètre : Plus long des plus courts chemins

diamg(G) = max{δ(x, y)|∀x, y ∈ V (G)}

Classement des arcs

• Arcs de liaison
• Arcs Arrières

Bastien Fayolle 21
Théorie des graphes 14 juin 2024

• Arcs avant
• Arcs Transverses

Liaison : relation de parenté

• Arc arrière (u,v) : relie un descendant à un de ses ancêtres.

• Arc avant : (u,v) : v est un descendant de u
• Arc Transverse : tous les autres

Lemme :

Un graphe G = (V, E) est un sous-circuit ssi lors d’un parcours en profondeur aucun arc arrière n’est
généré.

Preuve :

⇒ Supposons qu’un arcs amène (u, v) soit généré par le DFS

(u, v) est un arc arrière, et par définition, il existe un chemin de v à u car u est un descendant de v.

⇐ Par contraposée :

Si G contient un circuit C, alors un arc arrières sera généré par le DFS

Soit C notre circuit, soit V le premier sommet de C exploré par le DFS

On note u le sommet qui précède V sur C.

Au moment où V est découvert, tous les sommets de C sont blancs. Par le théorème du chemin blanc,
tous les sommets sont des descendants de V . En particulier donc (u, v) est un arc arrière

Tri topologique

Pour un graphe orienté sans circuit, un tri topologique est un ordre total (σ) des sommets tel que pour
tout sommet v, ∀v,w ∈ N + (v)

∀w ∈ N + (v), σ[w] > σ[v]

∀u ∈ N − (v), σ[u] < σ[v]

Pour résoudre les systèmes de contrainte de précédence (construire un batiment, Paquets logiciels,
makefile)

Algo tri topologique :

Bastien Fayolle 22
Théorie des graphes 14 juin 2024

1 L=vide
2 PP(G)
3 //Lorsque le traitement d'un sommet V est terminé dans PP(G),
4 Inserer V au début de L

Théorème

Tri-Topologique : calcule calcule d’un tri topologique d’un graphe orienté sans cycle

Preuve :

Considérons une application du parcours en profondeur sur G, pour calculer les dates de fin.

Soit un arc (u, v), alors on a f [u] > f [v]

On considère l’arc (u, v) lorsqu’il est exploré par le parcours en profondeur V ne peut pas être gris,
sinon, (u, v) est un arc arrière.

Si v est blanc, v est un descendant de u et on aura f [v] < f [u]

Si v est noir, alors f [v] < f [u]

Composante fortement connexes d’un Graphe orienté

Un graphe G = (V, A) orienté est fortement connexe si ∀x, y ∈ V il existe un chemin de x @ y et un

chemin de y vers x

Composante fortement connexe

Une composantes fortement connexe est un sous ensemble de sommet maximal qui induit un graphe
fortement connexe

Graphe des composantes fortement connexes d’un graphes orienté.

G = (V, A) le graphe orienté

GCF C sera son graphe des composante fortement connexes

Les sommets de GCF C sont les composantes fortement connexes de G

On a un arc entr deux sommet ci et cy de GCF C ssi il existe un arc (u, v) ∈ A(G)tel que u ∈ Ci etv ∈
Cj

Les arcs de GCF C sont les arcs reliant les différentes CF C dans G.

Bastien Fayolle 23
Théorie des graphes 14 juin 2024

GCF C est sans-circuit (car si circuit : on peut en faire une grande composante connexe (faire un
schéma))

• Nombre min de CF C : 1
• Nombre max de CF C : n -> Graphe sans circuit

Algo CFC

Input : G = (vi , A =) Output : C = c1 , c2 , ...ck les CFC dans G

1 1) PP(G) //pour avoir les dates de fin

2 2) Trouver G^T, le transposé de G
3 3) PP(G^T) // en commencant avec les dates de fin les plus grandes
calculé à l'étape 1)
4 4) Renvoie la forêt de PP(G^T)

Transposé du graphe : arcs dans l’autre sens

L’opération GT conserve les mêmes CF C

Ainsi, l’ordre topologique est : C1-> C2 -> C3 -> C4 (C2-> C4)

GCF C (GT ) : (dessin)

Pour un ensemble de sommets U d(U ) = min(d[u], ∀u ∈ U ) f [u] = max(f [u], u ∈ U )

Lemme Soient C et C ′ 2 CFC d’un graphe orienté G(V, A) et on a un arc (u, v) ∈ A(G) spdg : u ∈
C et v ∈ C ′ alors f (C ′ ) > f (C)

Preuve

1) d(C) < d(C ′ ) : Soit le sommet de C tel que d(x) = d(C) (c’est le premier sommet de C qui a
été exploré par le parcours en profondeur). Tous les sommets de C sont des descendants de x
(Thm chemin blanc). De même que tous les commet de C ′ d(C) = d[x] < d(C ′ ) Donc tous les
sommets de C’ sont aussi des descendants de x (à cause de l’arc (u, v))

Le traitement de tous les sommets de C ′ sera terminé avant la fin du traitement de x. Donc on a
f (C) > f (C ′ )

2. d(C) > d(C ′ ) Soit y le sommet de C ′ tq d[y] = d(C ′ ) au moment d[y] tous les sommets de C ′
sont blancs, les sommet de C ′ sont les descendants

Comme il n’y a aucun Arc de C ′ vers C, le traitement des sommets de C ′ sera terminé avant de
commencer à explorer C => f (C ′ ) = f [y] f [y] < d[x] < f [x] Donc f (C) > f (C ′ )

Dans un graphe orienté sans circuit, on distingue 2 type de sommets : - les sources : sommets pour
lesquels il n’y a pas de voisin entrrants - les puits : pas de voisins sortans - (les intermédiaires : tous les
autres)

Bastien Fayolle 24
Théorie des graphes 14 juin 2024

Avec le parcours en profondceur, on identifie les GCF C une source s quand on fait le parcours dans
GT à partir de s.

Couplages (matching)

Soit G = (V, E) un graphe et soit M = {e1 , e2 ...ek } un ensemble d’arêtes tel que ∀i, jei ∩ ej = ∅

On va chercher à trouver dans le graphe un couple de cardinalité maximum.

Un couplage est parfait s’il couvre toutes les sommets.

Chemin M -Alternant

G = (V, E) un graphe et M un couplage quelconque.

Si P = V1 , V2 , V3 , ..., Vk est M -alternant si exactement une arête sur deux le long de P appartient et
n’appartient pas au couplage M .

On dit qu’un chemin est augmentant si la première et la dernière arrête ne sont pas dans M .

En présence d’un chemin augmentant, on peut inverser la longueur du chemin les arêtes qui sont dans
M et celle qui ne sont pas dans M

Cycles alternants

C = V1 , V2 , V3 , ..., Vk , V1 $ où une arête sur deux est dans le couplage et l’autre pas.

Les cycles alternants sont de cardinalités paires.

Théorème Soit G = (V, E) un graphe et M un couplage, M est maximum ssi G ne contient pas de
chemin M -augmentant.

Preuve : ⇒ par contraposée

Si ∃P un chemin M -augmentant :

Par définition, de chemin M -augmentant, on a {v1 , v2 } ̸∈ M et {vk−1 , vk } ̸∈ M

On obtient un couplage M ′ en inversant les arêtes de M et non M

La longueur de P est |M ′ | = |M | + 1, donc M n’est pas maximum.

⇐ Par l’absurde

Bastien Fayolle 25
Théorie des graphes 14 juin 2024

On suppose qu’il n’y a pas de chemin M -augmentant et M n’est pas maximum.

Comme M n’est pas maximum, on note M ∗ un couplage maximum.

On définit un graphe H[M ∆M ∗ ]

∆ : différence symétrique. A∆B = A \ B ∪ B \ A

On garde les arêtes qui sont dans M et pas dans M ∗ et celles qui sont dans M ∗ mais pas dans M .

Les composantes connexes de H[M ∆M ∗ ]

∆(H) = 2 (le degré maximal)

Car chaque composante connexe est soit: - Un chemin - Un cycle (de taille paire)

Comme |M ∗ | > |M |, il existe un chemin de H[M ∆M ∗] où il y a plus d’arêtes de M ∗ que de M par le

principe (tiroir chaussette). Ce chemin est un chemin augmentant

Couplage dans les graphes bipartis

B = (X, Y, E).

Existe t’il toujours un couplage qui couvre tous les sommets de X ?

Théorème de Hall 1935 Soit G = (V, E) un graphe biparti, il admet un couplage qui couvre tous les
sommets de X ssi |N (S)| ≥ |S| ∀S ⊆ V

Autrement dit:

Soit G = (V, E) un graphe biparti, avec les ensembles de sommets X et Y . Alors, G admet un couplage
qui couvre tous les sommets de l’ensemble X si et seulement si, pour chaque sous-ensemble S de
X, le nombre de voisins de S dans l’ensemble Y , noté N (S), est supérieur ou égal à la taille de S,
c’est-à-dire |N (S)| ≥ |S|.

Preuve : ⇒ Si G admet un couplage M qui couvre tous les sommets de X. La propriété est vérifié
pour X.

|N (X)| ≥ |X| comme il y a un couplage chaque sommet x a un voisin qui lui est propre dans Y .

Il y a au moins autant de sommets dans Y que dans X grâce au couplage.

La propriété reste vrai pour tous les sous-ensembles S.

⇐ (par contraposée)

Bastien Fayolle 26
Théorie des graphes 14 juin 2024

Soit G un graphe biparti qui n’admet pas de couplage qui couvre tous les sommets de X. Soit M ∗ un
couplage de cardinalité maximum dans G.

On considère u un sommet non couvert par M ∗ . On considère tous les sommets de G accessibles à
partir de u par des chemins M ∗ alternant. Seul u ne sera pas couvert.

On note Z l’ensemble des sommets qui sont accessibles par ces chemins R = X ∩ Z B = Y ∩ Z

Tous les sommets de R sauf u sont couverts par M ∗ . (par construction : l’accessibilité par un chemin
M ∗ -alternant).

Tous les sommets de B sont couverts par M ∗ pour la même raison.

Tous les voisins de u dans Y sont aussi dans $B£ et donc tous les voisins de V sont couverts par M ∗
sinnon on pourrait augmenter la taille du couplage

|B| = |R \ {u}| |B| = |R| − 1

pour cet ensemble R, on a N (R) = B

Vertex Cover (couverture de sommets)

Un vertex cover est un sous-ensemble de sommets X tel que chaque arête de G a au moins une
extrémité dans X.

On note β(G) la taille du Vertex Cover Minimum

Théorème

Pour tout graphe G = (V, E), on a β(G) ≤ 2α′ (G) (avec α le couplage maximum)

Preuve

Soit M ∗ un couplage maximum de G, en considérant chacun des extrémités de M ∗ , on obtient un

ensemble de sommets S de V (M ∗ ) par construction : toutes les arêtes de G touchent au moins un
sommet de S

Théorème

Kőnig-Egerváry

Dans les graphes Bipartis, on a α′ (G) = β(G)

Bastien Fayolle 27
Théorie des graphes 14 juin 2024

Algorithme d’optimisation de graphe

Arbre couvrants de poids minimum

Soit G = (V, E, w) un graphe pondéré w : E → R

Le problème de l’arbre couvrant de poids minimum est de trouver un Arbre T = (V, F ), où T un arbre
couvrant et de poids minimum (i.e. w(T ) = Σe∈E(T ) w(e))

Premier algo proposé : Boruvka 1926, pour electrifier la Moravie du Sud

Algorithme générique

Règle bleue: On sélectionne une coupe ∂(x) (les arêtes sortantes de X) sans arête bleu, on sélectionne
l’arête non coloriée de poids minimum et on la colorie en bleue

Règle Rouge : Cycle C sans arête rouge et parmi les arêtes non coloriées, on met en rouge l’arête de
points maximum

Invariant de couleurs : Toutes les arêtes qui sont bleues forment la solution

On applique une règle si c’est possible.

Mais cet algorithme n’est pas un algorithme déterministe.

Lemme On est capable de colorier toutes les arêtes du graphe (soit en rouge, soit en bleue).

Preuve Par l’absurde, on suppose qu’a la fin de l’algorithme, il reste des arêtes non coloriées et
qu’aucune règles ne peut s’appliquer.

On a quelques arêtes bleues, quelques arêtes rouges et des arêtes non coloriées (au moins une). Soit
e = {x, y} une arête non coloriée. Les arêtes bleues forment une forêts.

1. Si les deux extrémités sont dans la même CC de la forêt, ca forme un cycle avec les arêtes bleues.
Comme e est la seule arête non colorié, on applique la règle rouge.
2. Si les deux extrémités sont dans 2 CC différentes , Ci et Cj : On peut appliquer la règle bleue.
On applique la règle bleue sur Ci (ou Cj ) de manière indiférenciée. Comme e est présente dans
∂(Ci ) en appliquant la règle bleue, on va colorier au moins une arête en bleu.

Invariant de Couleur

A la fin de l’algorithme, les arêtes de la solution sont bleues. Les arêtes rejetées sont rouges.

Bastien Fayolle 28
Théorie des graphes 14 juin 2024

Démonstration Règle bleue : Soit e l’arête sur le point d’être coloriée en bleue par l’algorithme. Soit
T l’arbre qui respecte l’invariant de couleur.

Avant d’appliquer la règle :

1. Si e ∈ T après application de la règle : OK

2. Si e ̸∈ T après la règle : on considère ∂(x) qui permet de colorier e. e = x, y et dans T, il existe
un unique chemin P de x à y et soit i l’arête de P qui traverse ∂(x) e est non coloriée. On a
w(e′ ) > w(e) pour le choix de e, T ′ = T − {e′ } ∪ {e}

Règle rouge :

Soit e = {x, y} l’arête sur le point d’être colorié en rouge :

1. Si e ̸∈ T : OK
2. Si e ∈ T : Si on supprime e de T, on obtient une forêt avec 2 sous arbres T1 et T2 Le Cycle C
sur lequel on a appliqué la règle comporte au moins une autre arêtes, e′ (sans couleur) comme
l’invariant de couleur est respecté, on a w(e′ ) < w(e). Si on enlève e à T et qu’on rajoute e′ , on a
un arbre de poids moindre.

Algorithme de Kruskal

Algo de Kruskal

Bastien Fayolle 29
Théorie des graphes 14 juin 2024

Algorithme de Kruskal
Input: G = (V, E, u)un graphe pondéré
Output: T = (V, F ) un arbre couvrant de poids minimum

Soit L la liste des arêtes de E triées par ordre croissant

For e ∈ L (pris dans l’ordre)
If e forme un cycle do :
c(e) = rouge
else
c(e) = bleu
F = F ∪ {e}
End If
End For
Return F

Complexité Complexité : O(n · log2 (n)) + O(n + mα(n, m)) Tri : O(m.log2 n) Reste de l’algo :
O(n + mα(n, m))

avec α(n, m) : fonction inverse dAckerman

Remarque

L’algorithme de Kruskal permet de trouver l’optimum si la structure du problème est un matroïde

Algorithme de Prim

Algorithme de prim - Wikipedia

Bastien Fayolle 30
Théorie des graphes 14 juin 2024

Algorithme de Prim
Input: G = (V, E, w)un graphe pondéré
Output: T = (V, F ) un arbre couvrant de poids minimum

Soit s un sommet
F =∅
C = {s}
̸ n do:
While|C| =
Appliquer la règle bleue sur ∂(C)
soite = {x, y} l’arête choisie
F = F ∪ {e}
C = C ∪ {x, y}
C(e) = bleue
End While
Return T = (V, F )

Complexité Tas binaire 0(n + m · log2 n) Tas de Fibonacci : O(m + nlogn)

Plus courts chemin

Plus courts chemins dans les graphes pondérés.

Soit G = (V, E, w) un graphe pondéré w : E → R+

Si remplace une arête pondéré à 1000 par 1000 arêtes log2 (w(e)) pour stocker les poids
P
e∈E

N = n + 1000 M = m + 1000

Donc impossible, trop complexe

Principe de sous-optimalité

Lemme Soit G = (V, E, w) un graphe. Soit P un plus court chemin de x à y. alors tous les sous
chemins Pαβ , αβ sommets de P sont aussi des plus courts chemins.

Bastien Fayolle 31
Théorie des graphes 14 juin 2024

Preuve Par l’absurde, on suppose qu’il existe une paire de sommets de P, α, β telle que Pαβ la
restriction de P au segment αβ n’est pas le plus court.

Il existe donc un chemin P ′ allant de α à β tq δp′ (α, β) < δp (αβ).

Il existe un chemin P ′′ de x à y qui passe par P ′′ pour aller de x à α ,par P ′ pour aller de α à β et par P
pour aller de β à y . La longueur de P ′′ est strictement plus petite que celle de P , CONTRADICTION

Dans les algos qu’on va présenter, on va calculer une valeur d[v] qui représente une borne sup sur la
longueur de s à v

Inégalité triangulaire

Version arête : ∀{u, v} ∈ E(G), δ(s, v) ≤ δ(s, u) + w(u, v)

Version chemin δ(s, v) ≤ δ(s, u) + δ(u, v); (u, v) ̸∈ E(G)

Operation de mise à jour de distance : Pour un sommet u et v un voisin de u, la mise à jour consiste à
voir si on peut améliorer la distance de v en passant par u.

Si d[u] > d[u] + w(u, v) alors p[v] = u

Propagation d’optimalité

Si P = s ⇝ u → v est un plus court chemin de s à v. Si la mise à jour de v intervient après le moment

où on a d[u] = δ(s, u) alors on aura d[v] = δ(s, u) + 1

Bastien Fayolle 32
Théorie des graphes 14 juin 2024

Algorithme de Dijkstra

Algorithm Algo
Input: G = (V, E, w), s et t des sommets
Output: Arborescence du plus court chemin enraciné en s

foreach v ∈ V (G)
d[v] = ∞
p[v] = ∅
End For
d[s] = 0
In = ∅
Out = V (G)

While |In| < n do:

x = sommmet ∈ Out tq d[x] est minimum
Out = Out \ {x}
In = In ∪ {x}
Foreach z ∈ (N (x) ∩ Out) :
k = d[x] + w(x, z)
if (k < d[z]) :
p[z] = x
d[z] = k
End If
End For
End While
Returnd, p

Bastien Fayolle 33
Théorie des graphes 14 juin 2024

Complexité : O(m + nlog2 n) : avec des tas de Fibonacci O(m.log2 n + n) : avec un tas binaire

Théorème L’algorithme de Dijkstra calcule les plus courts chemins à partir d’une source unique s

Preuve

Par récurrence sur le nombre de sommet ajoutées dans In.

Base : d[s] = 0 In ← s

Induction

Si c’est vrai à l’étape i, ce sera vrai à l’étape i + 1, π ⇒ π+1

Par l’absurde, il existe un sommet u pour lequel on a d[u] ̸= δ(s, u); d[u] > δ(s, u)

On suppose que u est le premier sommet pour lequel on a d[u] > δ(s, u), (touts les autres sommets
avant ont recus la bonne distance)

Comme d[s] = 0 = δ(s, s), u ̸= s ⇒ In = ̸ ∅ On a un chemin de s à u donné par la relation de

parenté qui n’est pas le plus court , et on a un chemin P , le plus court chemin possible de s à u
P :s⇝x→y⇝i

x ∈ In et y ∈ Out

Lorsque l’on traite u dans l’algorithme d[y] = δ(s, y)

Par propagation d’optimalité, on a d[y] < d[u]. Au moment où on exécute l’algo, on doit préférer y à u
(Contradiction)

Bastien Fayolle 34
Théorie des graphes 14 juin 2024

Algorithme de Bellman

Algorithme de Bellman
Input : G = (V, E, w) un graphe orienté valué, s un sommet de départ
Output : Une arborescence de plus courts chemins, faux sinnon
For: v ∈ V (G) do :
d[v] = ∞
p[v] = ∅
End For
For i = 0 → |V (G)| − 1 do:
For (u, v) ∈ E(G) do :
If d[v] > d[u] + w(u, v) then:
d[v] = d[u] + w(u, v)
p[v] = u
End if
End for
End for
For (u, v) ∈ E(G) do:
if d[v] > d[u] + w(u, v)then:
Return "Il y a une cycle négatif (absorbant)"
Return d, p

Complexité : O(n × m)

Flots maximum

Problème de flot maximum | Wikipedia

G = (V, E, c) orienté

On a deux sommets identifiés :

• s:source
• t: puits

c : E → R+ fonction de capacité (La quantité maximum qui peut transiter sur un arc).

Bastien Fayolle 35
Théorie des graphes 14 juin 2024

(On note la capacité sur la graphe par /[lacapacité] ).

On cherche à calculer la quantité maximum que l’on peut faire transiter de s à t.

On cherche à trouver une fonction f , tq

f : E → R+

On a deux contrainte :

• Le respect de la capacité , tq
∀e ∈ E, f (e) ≤ c(e)

• Le respect des lois de Kirchhoff

X X
∀v ∈ V (G) \ {s, t}, f (u, v) = f (v, u)
u∈N − (v) u∈N + (v)

Par convention, f (u, v) = −f (v, u)

On dit que l’arc (u, v) est saturé si : f (u, v) = c(u, v).

a 2/2 b
3/3 3/3
S 1/2 / 6 1/1 t

3/5
d
4/4 c 3/3

Chemin améliorant

C’est un chemin entre s et t dans un graphe G = (V, E, c) avec un flot f qui transite sur G.

P = s, v1 , v2 , . . . , vi , t

Bastien Fayolle 36
Théorie des graphes 14 juin 2024

∀(vi , vi+1 ), f (vi , vi+1 ) < c(vi , vi+1 )

Variation de flot : min(c(vi , vi+1 ) − f (vi , vi+1 )), ∀i ∈ {0, . . . , t}

Pour trouver un chemin améliorant pour un graphe G = (V, E, c) avec un flot f :

On construit le réseau résiduel Gf = (v, E ′ , c′ ) c′ : E → R+ , Et

∀e ∈ E(G), c′ (e) = c(e) − f (e)

a 5/5 b
5/8 5/7
S 0/4 0/2 0/5 t

5/7 5/8
d
5/10 c

Figure 6: Le graphe de flux initial

Puis on fait le graphe résiduel :

Bastien Fayolle 37
Théorie des graphes 14 juin 2024

a
5 b 5
5 2
3
S 4 2 5 t

2 3
5
5 d 5 c

5
Figure 7: Le graphe résiduel

Le réseau résiduel GF permet de mettre en correspondances les chemins améliorant de G(f ) avec
les chemins de s à t dans Gf . Un chemin de s à t dans Gf peut être trouvé en temps linéaire avec un
parcours (Largeur ou profondeur)

Coupe minimum et flots maximum

La coupe minimum d’un graphe G = (V, E, c).

Soit S un ensemble de sommets avec s ∈ S , et t ∈ S̄.

On note c(S, S̄) la capacité de cette coupe.

Une coupe (S, S̄) est minimum si ∀(S ′ , S̄ ′ ) autres coupe, on a c(S, S̄) ≤ c(S ′ , S̄ ′ ).

Le nombre de coupe maximum est peut être 2n−2

Remarque : La valeur de f est toujours inférieur ou égale à c(S, S̄)∀S

Théorème : Si f est un flot dans un graphe G = (V, E, c) alors les conditions suivantes sont équiva-
lentes :

1) f est un flot de valeurs maximum.

2) Le réseau Gf ne contient aucun chemin améliorant.
3) La valeur de f = c(S, S̄) pour une certaine coupe

Bastien Fayolle 38
Théorie des graphes 14 juin 2024

Preuve :

(1) ⇒ (2) : par l’absurde :

supposons f maximum et Gf contient un chemin de s à t. Soit k la valeur min du chemin de s à t dans

Gf . On peut augmenter la valeur du flot de k unités, donc f n’est pas maximum.

(2) ⇒ (3) : Soit S l’ensemble des sommets de Gf accessibles depuis s. (tous les arcs de S à S̄ sont
saturés, par définition du réseau résiduel)

(3) ⇒ (4) : par la remarque précédente, la valeur de f ne peut excéder la valeur de c(S, S̄), ∀(S, S̄). Si
la valeur est atteinte, i.e. ie |f | = c(S, S̄) le flot maximum

Algorithme de Ford-Fulkerson

Algorithm Algorithme de Ford Fulkerson

Input: G = (V, E, c), s et t des sommets
Output: f, un flot maximum

f =∅
Gf = G
while il existe un chemin P de s à t dans Gf do:
augmenter le flot le long du chemin P avec la valeur cf (p)
mettre à jour Gf
end while
Return c

cf (p) = min c′ (e) , ∀e ∈ E(p) (la capacité résiduelle du chemin augmentant p est égale à la capacité
résiduelle minimum de ses arcs.)

Edmond-Karp :

On prend toujours le plus court chemin en nombre d’arrête → O(nk ) , k constante

Coloration de graphes.

• coloration de sommets
• Coloration d’arêtes

Bastien Fayolle 39
Théorie des graphes 14 juin 2024

Soit G = (V, E) un graphe.

On cherche une fonction c : V → {1, . . . , k} telle que : ∀vi , vj ∈ E(G) on a c(vi ) ̸= c(vj )

Si la fonction c respecte la contrainte précédente, alors la coloration est dite propre.

On cherche à minimiser le nombre de couleurs utilisées .

Le nombre chromatique du graphe, noté χ(G) correspond au plus petit nombre de couleurs nécessaire
pour colorier le graphe.

Borne supérieure :
Sur le nombre chromatique χ(G) ≤ n

χ(Kn ) = n (graphe complet à n sommets. )

Borne inférieur

• ω(G) ≤ χ(G)

(ω(G) : la taille de la clique maximum contenue dans G. )

• n
α(G) ≤ χ(G)

(α(G) la taille du stable maximum)

Soit c une fonction de coloration propre de G avec :

c[i] = {v|c(v) = i}

alors c[i] forme un stable

Le problème de Coloration revient à couvrir l’ensemble des sommets par k stables (avec le plus petit k
possible)
Coloration de Carte par Francis Guthrie, vers 1850:

(cf Théorème de quatre couleurs | Wikipedia)

Est ce que 4 couleurs suffisent pour colorier n’importe quelle carte ?

Problème de coloration :

le problème de coloration est NP difficile

Problème de décision. Soit G = (V, E) un graphe et k ???? .

Question : est il possible de colorier le graphe avec au plus k couleurs.

Le problème de coloration n’a pas d’algo polynomial, mais on a des Heuristiques :

Bastien Fayolle 40
Théorie des graphes 14 juin 2024

Heuristique gloutonne

Algorithm
Input: G = (V, E) un graphe non orienté
Output: c : V → N+

Π = v1 , v2 , . . . , vn une permutation (aléatoires) des sommets

For vi ∈ Π do:
c(vi ) = la plus petite couleur disponible parmi les voisins de vi
end for
return c

Avec le graphe précédent, en commencent par h,

Théorème : χ(G) ≤ ∆(G) + 1

Preuve Par récurrence sur le nombre de sommets déjà coloriés.

Base : Pour v1 : c(v1 ) = 1 ,1 ≤ ∆(G) + 1

Récurrence : Pi−1 ⇒ Pi

∀j ∈ {1, . . . , i − 1}, c(vj ) ≤ ∆(G) + 1

On se place au moment où on colorie vi

On doit donc montrer qu’il existe une couleur dans l’ensemble {1, . . . , ∆(G) + 1} disponible pour
vi .

d(vi ) ≤ ∆(G)

Si d(vi ) = ∆(G) et tous les voisins de vi sont déjà coloriés avec des couleurs toutes différentes, alors
il y a au plus ∆(G) couleurs utilisés. Donc il y a au moins une couleurs disponible dans l’ensemble
{1, . . . , ∆(G) + 1} disponible pour vi .

Remarque : si G = Kn ou G = C2k+1 (cycle impair)

χ = ∆(G) + 1

∆(Kn ) = n − 1, χ(Kn ) = n

Bastien Fayolle 41
Théorie des graphes 14 juin 2024

∆(C2k+1 ) = 2, χ(C2k+1 ) = 3

Théorème de Brooks:

Si G n’est ni un graphe complet à n sommets ni un cycle impaire, χ(G) ≤ ∆(G)

Preuve

1. Si G nest pas régulier :

∃x tq dG (x) < ∆(G)

On effectue un parcours en profondeur à partir de X, pour obtenir l’arbre de parcours en profon-

deur.

On construit une permutation des sommets v1 est une feuille de T . On construit la permutation
en enlevant successivement des feuilles de T

On ré-applique l’heuristique gloutonne sur σ (l’ordre définis précédemment).

On colorie donc v1 , v2 , . . . , vi , vk , x

Le pire des cas : les voisins avant vi sont de couleur différente

2. Si G est régulier

1. si G possède un sommet qui est déconnectant Alors on enlève ce sommet, créant donc 3
composantes connexes, que l’on augment en re-mettant x le sommet déconnectant.

On a donc :
∆(Gi ) = k, ∀i ∈ {1, 2, 3}

d(Gi ) < k

Pour chaque graphe Gi , on est dans le cas d’application du cas 1, G n’est pas régulier et
∆(Gi ) = ∆(G) pour chaque Gi , on a (Gi ) ≤ ∆(G)→on peut fusionner les coloration de
chaque Gi pour n’utiliser que max(Gi ).

2. S G n’a pas de sommets déconnectant.

On prend un parcours en profondeur σ enraciné en x.

Résultat : tout parcours en profondeur est un chemin Hamiltonien ssi G est un graphe
complet Kn ou un Biparti complet Kn,n .

SI G = Kn (on est pas concerné).

SI G = Kn,n , (G) = 2 donc ok.

On peut supposer qu’on a un arbre de DFS tq on choisit x tq x a 2 enfants y et z.

Bastien Fayolle 42
Théorie des graphes 14 juin 2024

Comme G est 2-connexe, G − y et G − z sont également connexes, et y et z ont des

descendants propres qui sont connectés aux ancêtres de x.

On peut enraciner l’arbre DFS en x et on colorie x et y avec la même couleur.

Il existe des graphes avec un nombre chromatique arbitrairement grand

ω(G) ≤ (G)

(ω(C2k+1 ) = 2 χ2k+1

Construction de Mycielski

Pour toute valeur entière k positive, on note M (k) un graphe sans triangle(K3 ) dont le nombre chro-
matique est k.

Soit v1 , v2 , . . . , vn les sommets de Mk pour construire Mk+1 , on va ajouter les sommets u1 , u2 , . . . , un

(la relation d’adjacence de vi et ui est la même )

On connecte ui aux voisins de vi . On ajoute un sommet x connectés à tous les sommets ui (sommet
“universel”).

Remarque :

Dans Mk−1 les sommets u forment un stable.

Lemme Pour tout k ≥ 1Mk est un graphe sans K3 inclut.

Preuve Par récurrence sur k

Base : M1 est sans triangle, M2 est sans triangle

Récurrence : Mk ⇒ Mk+1

Par l’absurde : Mk ⇒ Mk+1

Mk ∧ M¯k+1 Supposons que Mk+1 contienne un triangle a, b, c

x ne peut pas participer à un K3 , tous les sommets a, b, c ne peuvent pas être identifié à des sommets
de u.

Si Mk+1 contient un graphe K3 comme sous graphe induit, K3 contient au plus un sommet u1 nommé
ui . ui a exactement les mêmes voisins que vi (sauf x). ⇒ vi vj vk forment un triangle dans Mk+1 ,
contredisant l’hypothèse de départ □.

Bastien Fayolle 43
Théorie des graphes 14 juin 2024

Coloration d’arêtes d’un graphe

Soit G = (V, E) un graphe et on souhaite colorier les arêtes de G telle que 2 arêtes qui partagent
soient de couleurs différentes.

On note χ′ (G) le nombre chromatique d’arête le nombre minimum de couleur par arête colorier G.

Chaque classe de couleur forme un couplage.

∆(G) ≤ χ′ (G)

Correspondance Coloration d’arête / coloration de sommets

Construction d’un line graphe. On a un graphe G = (V, E) et on construit L(G) = (E, f (E)).

f (E) = {ei , ej }ei ∩ ej ̸= ∅

La coloration de sommets de L(G) peut être transformée en une coloration d’arêtes de G (ssi).

Les line graphes sont des graphes particuliers

La coloration d’arête est un cas particulier de la coloration de sommets.

Propriété simple des lines Graphes

Le voisinage de chaque sommet v de L(G) peut être partitionné en 2 cliques.

(une clique qui part d’un extremétié de l’arête, l’autre qui part de l’autre extrémité)

Remarque : ∆(G) ≤ χ′ (G) Nombre maximum de couleur pour colorier les arrêtes de G

ω(L(G)) = ∆(G) (taille de la clique maximum = degré max du graphe)

Le line-graphe d’un cycle a k sommet est un cycle a k sommet

D’après le thm de Brooks, χ(G) ≤ ∆(G) ssi G pas complet ni cycle.

Or : δL(G) ≤ 2(∆(G) − 1) (car on associe une arête à deux autre).

Ainsi, ∆(L(G)) ≤ 2∆(G) − 2

Bastien Fayolle 44
Théorie des graphes 14 juin 2024

Lemme
Si G n’est pas un cycle impair (ni une clique), alors χ′ (G) ≤ 2∆(G) − 2

Théorème de Vizing :

Le thm de Vizing dit : χ′ (G) ≤ ∆(G) + 1

Et ainsi, en combinant les équation, on a ∆(G) ≤ χ′ (G) ≤ ∆(G) + 1
Thm : Si G est biparti
X ′ (G) = ∆(G)
Preuve :
Par récurrence sur le nombre d’arêtes coloriées.
Base : Si on colorie une arête, alors on a ∆(G) ≥ 1
Récurrence : On veut colorier une nouvelle arête e = {x, y}
2 cas :

1. S’il existe une couleur c ≤ ∆(G) disponible en x et y, si c est disponible en x et y, aucune arête
incidente à x ni y n’utilise cette couleur donc on peut l’utiliser pour e.
2. La couleur c est disponible en x mais pas en y Par hypothèse, les arêtes coloriées utilisent au
plus ∆(G) couleurs.
Et donc, ∃c′ = {1, . . . , ∆(G)} qui est disponible en y( car dG (y) ≤ ∆(G) − 1), donc au plus
∆(G) − 1 couleurs sont incidentes à y. )
et c′ n’est pas disponible le au niveau de x.
SI non, on se ramène au cas n°1.
On considère que le graphe est constitué uniquement des couleurs c et c′ qui partent de x et de
y.
La structure de Cx et de Cy . (Cx (resp Cy ) composante connexe qui contient x resp. y) dans ce
graphe.

1. Cx est différente de Cy . Sur une des deux composantes connexes, (spdg x) on échange les
2 couleurs, c′ devient dispo en x et l’était déja en y.

1 $C_x$ et $C_y$ ne forment qu'une seule composante. Le chemin de

$x$ à $y$ contient auatant d'arêtes de couleur $c$ que de
couleurs $c'$ (par la propriété de l'alternance des couleurs,
la longueur du chemin est pair )

Bastien Fayolle 45
Théorie des graphes 14 juin 2024

Donc P ∪ {e} forme un cycle impair ⇒ contradiction.

Flots

Couplage maximum dans un biparti.

On transforme un graphe biparti en un problème de flot en lui ajoutant une source, un puit, et une
capacité à chaque arête (1 pour chaque).

Thm : G admet un couplage de taillle k ssi G′ admet un flot de valeur k

Connexité

3.• Sur les sommets

• Sur les arêtes

Chemins disjoints

G = (V, E) un graphe (non orienté).

Pour une paire de sommet s et t, on veut trouver deux chemins P et P ′′ disjoints entre s et t.

2 chemins P et P ′′ sont sommet (respectivement arrêtes) disjoint si aucun sommet (resp. arrêtes) de
P et P ′′ sont communs (sauf s et t).

Il existe des grpahes arêtes disjoint mais pas sommet disjoints

Si P1 et P2 sont sommets disjoints alors P 1 et P 2 sont arêtes disjoints.

Mais deux chemins arêtes disjoint peuvent partager des sommets.

On cherche à trouver le nombre maximum de chemins disjoints (sommets ou arêtes). entre 2 sommets.
→ algo polynomiale pour les 2 sommets.

On cherche la Connectivité locale d’un graphe

p(x, y) = nombre maximum de chemin sommets disjoints x et y.

Puis la connectivité du graphe

κ(G) = min{p(u, v)|u, v ∈ V (G), u ̸= v}

Pour le graphe complet :

κ(Kn ) = n − 1

Bastien Fayolle 46
Théorie des graphes 14 juin 2024

Ensemble séparateur.

S ⊊ V (G) est un ensemble séparateur si le nombre de cc de G − S est plus grand que celui de G:

cc(G − s) > cc(G)

a, b séparateur un ensemble séparateur S est un a, b séparateur si a et b sont dans 2 CC différentes

G − S (on prend le a, b séparateur minimal).

Pour une paire de sommet x, y, on note c(x, y) la taille du plus petit x − y séparateur.

Théorème de Menger

Si x et y ne sont pas relié par une arête, alors on a : c(x, y) = p(x, y)

(C’est à dire : la taille du plus petit ensemble de sommets x − y séparateur est e nombre maximum de
chemin sommet disjoints entre x et y).

Si G comporte au moins une paire de sommet non-adjacents„ on a

κ(G) = min{p(u, v)|un, v ∈ V, u ̸= v et uv ̸∈ F (G)}

Graphe k-connexe

• 1-connexe = connexe_ç
• 2-connexe = pas de sommet déconnectant
• k-connexe : Si ∀x, y, x =
̸ y, il existe k chemin disjoints entre x et y. Si pour la suppression de tout
sous-ensemble X de sommets, de taille au plus k − 1, G − X reste connexe

Remarque

SI G et k connexe alors G et k − 1connexe.

Lemme

Si G est k − 1 connexe et soit H le graphe obtenu à partir de G, où on ajoute un sommet y et y est

connecté à au moins k sommets de G. Alors H et k-connexe

Preuve

Soit S un sous-ensemble de sommets de taille k − 1. On doit montrer que H − S est connexe.

1. Si y ∈ S

On a donc |S ∩ V (G)| − k − 2, et donc H − S = G − S

On sait que G est k-connexe, donc supprimer k − 2 sommets de G laisse G connexe.

Bastien Fayolle 47
Théorie des graphes 14 juin 2024

2. Si y ̸∈ S

G − S reste connexe car |S| ≤ k − 1

On doit montrer qu’il reste un chemin entre y et les sommets de G − S. Par construction y a au
moins k voisins dans G.

Pire des cas : S ⊊ N (y) mais sommet dH (y) ≥ k et |S| ≤ K + 1, il reste au moins un sommet x
de G qui est voisin de y.

Comme G − S est connexe et y est connecté à au moins un voisin x de G − S ⇒ H − S est

connexe □

Théorème : Soit G = (V, F ) un graphe k-connexe et soient X et Y des sous-ensemble de sommets

tels que |X| ≥ k et |Y | ≥ k alors il existe k chemins disjoints entre X et Y .

Preuve:

On ajoute 2 sommets, x et y, tq x est connecté à tout sommets de X et y connecté à tout sommets de

Y . Le graphe obtenu est k-connexe, p(x, y) ≥ k

Théorème : Si G = (V, F ) est k-connexe, et X un ensemble de taille k, alors il existe un cycle de

taille k qui passe par tous les sommets de X.

K-Fan

(x, Y ) est un k-fan si x est un sommet et Y un ensemble de taille k. Les k chemins disjoints de x vers
Y

Preuve:

Par induction sur k :

Base : k = 2

Bastien Fayolle 48