Graphes & Optimisation

Chapitre 2: Cheminements et connexités

Amira FOUGHALI & Houcemeddine FILALI

EPI-Digital School

11 mai 2024
Plan

1 Introduction

2 Graphe non-orienté

3 Graphe orienté

4 Fermeture transitive

5 Notion de graphe eulérien

6 Notion de graphe hamiltonien

7 Coloriage d’un graphe

8 Networkx

9 Conclusion
 G&opt
Introduction

Plan

1 Introduction
Rappel sur la notion de graphe
Motivations

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 3 / 67

 G&opt
Introduction
Rappel sur la notion de graphe

Graphes Non Orientés (UGrap)

Définition d’un Graphe Non Exemple de Graphe Non Orienté

Orienté
Ensemble C
S = {s1 , . . . sn } de
sommets.
A
Ensemble A de liaisons
entre les sommets : B
arêtes =
{si , sj } =∈ A ⊆ S2 ∪ S.


Sommets : S = {A, B, C }
{si , sj } est équivalent à
{sj , si }. Arcs : A =
{{A, C }, {A, B}, {B, C }}

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 4 / 67

 G&opt
Introduction
Rappel sur la notion de graphe

Propriétés des sommets dans un graphe non orienté (1/3)

Voisinage d’un sommet (NG (v ) ou N(v ))
L’ensemble de tous les voisins du sommet v dans un graphe G .

Degré d’un sommet (dG (v ) ou d(v ))

Le nombre d’arêtes du voisinage N(v ) qui sont incidentes à v .

Degré minimum (δ(G ))

Le degré le plus bas parmi tous les sommets du graphe G , défini comme
minv ∈VG dG (v ).

Degré maximum (∆(G ))

Le degré le plus élevé parmi tous les sommets du graphe G , défini comme
maxv ∈VG dG (v ).

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 5 / 67

 G&opt
Introduction
Rappel sur la notion de graphe

Propriétés des sommets dans un graphe non orienté (2/3)

Graphe régulier
Un graphe où tous les sommets ont le même degré.

Graphe r -régulier
Un graphe où chaque sommet a un degré égal à r .

Graphe cubique
Un graphe régulier où chaque sommet a un degré de 3.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 6 / 67

 G&opt
Introduction
Rappel sur la notion de graphe

Propriétés des sommets dans un graphe non orienté (3/3)

Example

N(v1 ) = {v2 , v3 } ; d(v1 ) = 2

δ(G ) = 1 ; ∆(G ) = 3 ;
Le graphe n’est pas régulier.

2 4 5

1 3

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 7 / 67

 G&opt
Introduction
Rappel sur la notion de graphe

Graphes Orientés (DGraph)

Définition d’un Graphe Exemple de Graphe Orienté

Orienté
Ensemble C
S = {s1 , . . . sn } de
sommets.
A
Ensemble A de liaisons
entre les sommets : arcs B
= (si , sj ) ∈ A ⊆ S 2 où
(si , sj ) ̸= (sj , si ) si
Sommets : S = {A, B, C }
si ̸= sj .
Arcs : A =
{(A, B), (B, C ), (C , A), (C , C )}

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 8 / 67

 G&opt
Introduction
Motivations

Motivations

Définition
Cheminement : Séquence de sommets reliés par des arêtes dans un
graphe.
Connexité : Propriété d’un graphe d’être constitué d’un seul
composant connecté, c’est-à-dire qu’il existe un chemin
entre chaque paire de sommets.

Motivations pour l’étude des cheminements et des connexités

Réseaux sociaux : Comprendre la propagation d’informations.
Transport : Optimiser les itinéraires et réduire les temps de trajet.
Informatique : Assurer la connectivité des réseaux.
Biologie et chimie : Modéliser les interactions entre molécules ou
les réseaux métaboliques.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 9 / 67

 G&opt
Graphe non-orienté

Plan

2 Graphe non-orienté
Chaîne et cycle
Chaîne élémentaire et chaîne simple
Accessibilité
distance entre deux sommets
Diamètre d’un graphe
Notion de connexité
Composantes connexes

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 10 / 67

 G&opt
Graphe non-orienté
Chaîne et cycle

Chaînes dans les Graphes Non Orientés (1/2)

Définition d’une chaîne

Soit G (S, A) un graphe non orienté, une chaîne est une succession
d’arêtes mises bout à bout. Formellement, une chaîne de longueur k est
une séquence

ui ∈ A
 ∀1 ≤ i ≤ k
< u1 , u2 , . . . , uk > où et

ui ∩ ui+1 ̸= ∅ ∀1 ≤ i < k.


Longueur d’une chaîne

La longueur d’une chaîne est le nombre d’arêtes qui la composent.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 11 / 67

 G&opt
Graphe non-orienté
Chaîne et cycle

Chaînes dans les Graphes Non Orientés (2/2)

Exemple

A C E

Exemples variés de chaînes :

Chaîne de longueur 2 : A → B → C
Chaîne de longueur 3 : A → D → C → E
Chaîne de longueur 4 : A → B → D → C → E

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 12 / 67

 G&opt
Graphe non-orienté
Chaîne et cycle

Cycle dans les Graphes Non Orientés

Définition d’un cycle
Un cycle dans un graphe non orienté G (S, A) est une chaîne fermée,
c’est-à-dire une chaîne où le premier sommet est également le dernier
sommet. Formellement, un cycle est une chaîne < u1 , . . . , uk > où
u1 ∩ uk ̸= ∅.

Exemple de Cycle dans le Graphe Non-Orienté

A C E

Exemple de cycle : A → D → C → B → A

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 13 / 67

 G&opt
Graphe non-orienté
Chaîne élémentaire et chaîne simple

Chaîne/Cycle Élémentaire & Chaîne/Cycle Simple (1/2)

Soit ch =< u1 , . . . uk > une chaîne/cycle d’un un graphe non orienté

G (S, A).

Chaîne/cycle simple
ch est simple ⇔ elle passe au maximum une seule fois par chacune des
arêtes du graphe. Formellement, ui ̸= uj pour i ̸= j.

chaîne/cycle élémentaire
ch est élémentaire ⇔ elle passe au maximum une seule fois par chaque
sommet du graphe. Formellement, ui ∩ ui+1 ̸= ∅ et ui ∩ uj = ∅ pour
j∈/ {i − 1, i, i + 1}.

ch élémentaire ⇒ ch est simple.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 14 / 67

 G&opt
Graphe non-orienté
Chaîne élémentaire et chaîne simple

Chaîne/Cycle Élémentaire & Chaîne/Cycle Simple (2/2)

Trouvez
une chaîne/cycle
Exemple simple non
B élémentaire
une chaîne/cycle
élémentaire
non-simple.
A D E
une chaîne/cycle
ni simple ni
élémentaire.
C une chaîne/cycle
simple et
élémentaire.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 15 / 67

 G&opt
Graphe non-orienté
Accessibilité

Notion d’accessibilité dans un Graphe

Accessibilité
Soit G (S, A) un graphe non orienté.
La relation d’accessibilité entre deux sommets si et sj est définie
comme suit :

1, s’il existe un chemin dans G reliant si à sj
Accessibilité(si , sj ) =
0, sinon

Graphe non-orienté ⇒ l’accessibilité est symétrique.

Exemple
Considérons le graphe suivant :

A B C D E

Accessibilité(A, E ) = 0 ; Accessibilité(A, D) = 1.
Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 16 / 67
 G&opt
Graphe non-orienté
distance entre deux sommets

Définitions Formelles
Distance entre Deux Sommets
Soit G (S, A) un graphe non-orienté.
La distance entre deux sommets si et sj , notée d(si , sj ), est la
longueur du plus courte chaîne entre si et sj .

Exemple
Considérons le graphe suivant : calculer les distances entre chaque paire
de sommets

A D E

C
Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 17 / 67
 G&opt
Graphe non-orienté
Diamètre d’un graphe

Notion de Diamètre d’un Graphe

Diamètre d’un Graphe
Soit G (S, A) un graphe. Le diamètre de G , noté diam(G ), est défini
comme la plus grande des distances entre toutes les paires de sommets
dans G . Formellement :

diam(G ) = max {d(si , sj )}

si ,sj ∈S

où d(si , sj ) représente la distance entre les sommets si et sj dans G .

Exercice
Diamètre d’un graphe biparti.
Diamètre d’un graphe complet.
Donner une borne inférieure et une borne supérieure pour le
diamètre d’un graphe d’ordre n.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 18 / 67

 G&opt
Graphe non-orienté
Notion de connexité

Notion de Connexité dans un Graphe Non-Orienté (1/3)

Définition de Connexité
Un graphe non-orienté G (S, A) est connexe si et seulement si il existe
une chaîne entre n’importe quelle paire de sommets de S. Formellement
∀si , sj ∈ S : accessiblité(si , sj ) = 1

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 19 / 67

 G&opt
Graphe non-orienté
Notion de connexité

Notion de Connexité dans un Graphe Non-Orienté (2/3)

Exemple de Graphe Connexe

Considérons le graphe suivant :

B
A D E
C

Dans ce graphe, il existe une chaîne reliant chaque paire de sommets,

donc le graphe est connexe.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 20 / 67

 G&opt
Graphe non-orienté
Notion de connexité

Notion de Connexité dans un Graphe Non-Orienté (3/3)

Exemple de Graphe Non Connexe

Considérons le graphe suivant :

A B C D E

Dans ce graphe, il existe des sommets qui ne sont pas reliés par une
chaîne, donc le graphe est non connexe.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 21 / 67

 G&opt
Graphe non-orienté
Composantes connexes

Composantes Connexes dans un Graphe Non-Orienté

Composantes Connexes
Dans un graphe non-orienté G (S, A), une composante connexe est un
sous-graphe G ′ (S ′ , A′ ) tel que :
1 Connectivité Pour chaque paire de sommets si , sj ∈ S ′ , il existe une
chaîne reliant si à sj dans G ′ (accessibilitéG ′ (si , sj ) = 1)
2 Maximalité G ′ n’est inclus dans aucun autre sous-graphe connexe
G ′′ (S ′′ , A′′ ) de G tel que S ′ ⊂ S ′′ .

Exemple
Considérons le graphe suivant :

Composante 1 Composante 2

A B C D E

Dans ce graphe, il y a deux composantes connexes : Composante 1 (A, B, C)

et Composante 2 (D, E).
Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 22 / 67
 G&opt
Graphe orienté

Plan

3 Graphe orienté
Chemin et circuit
Chemin élémentaire et chemin simple
Accessibilité
Distance entre Deux Sommets
Diamètre d’un graphe orienté
Notion de forte connexité
Composantes Fortement Connexes

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 23 / 67

 G&opt
Graphe orienté
Chemin et circuit

Chemins dans les Graphes Orientés (1/2)

Définition d’un chemin

Soit G (S, A) un graphe orienté, un chemin est une séquence d’arcs
reliant des sommets de manière ordonnée. Formellement, un chemin de
longueur k est une séquence

vi ∈ A
 ∀1 ≤ i ≤ k
< v1 , v2 , . . . , vk > où et

source(vi+1 ) = destination(vi ) ∀1 ≤ i < k.


Longueur d’un chemin

La longueur d’un chemin est le nombre d’arcs qui le composent.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 24 / 67

 G&opt
Graphe orienté
Chemin et circuit

Chemins dans les Graphes Orientés (2/2)

Exemple

A C E

Exemples variés de chemins :

Chemin de longueur 2 : A → B → C
Chemin de longueur 3 : A → D → C → E
Chemin de longueur 4 : A → B → D → C → E

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 25 / 67

 G&opt
Graphe orienté
Chemin et circuit

Circuits dans les Graphes Orientés

Définition d’un circuit
Un circuit dans un graphe orienté G (S, A) est un chemin fermé où le
premier sommet est également le dernier sommet. Formellement, un
circuit est un chemin < v1 , . . . , vk > où source(v1 ) = destination(vk ).

Exemple de Circuit dans le Graphe Orienté

A C E

Exemple de circuit : A → D → C → B → A

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 26 / 67

 G&opt
Graphe orienté
Chemin élémentaire et chemin simple

Chemin/Circuit Élémentaire & Chemin/Circuit Simple (1/2)

Soit ch =< v1 , . . . vk > un chemin/circuit dans un graphe orienté

G (S, A).

Chemin/circuit simple
ch est simple ⇔ il passe au maximum une seule fois par chacun des arcs
du graphe. Formellement, vi ̸= vj pour i ̸= j.

Chemin/circuit élémentaire
ch est élémentaire ⇔ il passe au maximum une seule fois par chaque
sommet du graphe. Formellement, et vi ∩ vj = ∅ pour j ∈
/ {i − 1, i, i + 1}.

ch élémentaire ⇒ ch est simple.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 27 / 67

 G&opt
Graphe orienté
Chemin élémentaire et chemin simple

Chemin/Circuit Élémentaire & Chemin/Circuit Simple (2/2)

Exemple

Trouvez
un chemin/circuit
E simple non élémentaire
un chemin/circuit
élémentaire non-simple
B D
un chemin/circuit ni
simple ni élémentaire
A C un chemin/circuit
simple et élémentaire

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 28 / 67

 G&opt
Graphe orienté
Accessibilité

Notion d’Accessibilité dans un Graphe Orienté

Accessibilité
Soit G (S, A) un graphe orienté.
La relation d’accessibilité entre deux sommets si et sj est définie
comme suit :
(
1, ssi il existe un chemin dans G reliant si à sj
Accessibilité(si , sj ) =
0, sinon

Graphe orienté ⇒ l’accessibilité n’est pas nécessairement symétrique.

Exemple
Considérons le graphe suivant :

A B C D E

Accessibilité(A, E ) = 1 ; Accessibilité(B, E ) = 0.
Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 29 / 67
 G&opt
Graphe orienté
Distance entre Deux Sommets

Définitions Formelles
Distance entre Deux Sommets
Soit G (S, A) un graphe orienté.
La distance entre deux sommets si et sj , notée d(si , sj ), est la
longueur du plus court chemin entre si et sj .

Exemple
Considérons le graphe suivant : calculer les distances entre chaque paire
de sommets

B D E

A C

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 30 / 67

 G&opt
Graphe orienté
Diamètre d’un graphe orienté

Diamètre d’un Graphe Orienté

Soit G (S, A) un graphe orienté. Le diamètre de G , noté diam(G ), est
défini comme la plus grande des distances entre toutes les paires de
sommets dans G . Formellement :

diam(G ) = max {d(si , sj )}

si ,sj ∈S

Example
où d(si , sj ) représente la distance entre les sommets si et sj dans G .
Considérons le graphe orienté suivant :

B D E

A C

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 31 / 67

 G&opt
Graphe orienté
Notion de forte connexité

Notion de forte Connexité dans un Graphe Orienté (1/3)

Définition de Connexité
Un graphe orienté G (S, A) est fortement connexe si pour chaque paire
de sommets si , sj ∈ S, il existe un chemin orienté de si à sj ainsi qu’un
chemin orienté de sj à si . Formellement,
∀si , sj ∈ S : Accessibilité(si , sj ) = 1 et Accessibilité(sj , si ) = 1.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 32 / 67

 G&opt
Graphe orienté
Notion de forte connexité

Notion de forte Connexité dans un Graphe Orienté (2/3)

Exemple de Graphe Fortement Connexe

Considérons le graphe suivant :

A B

D C

Dans ce graphe, il existe un chemin orienté reliant chaque paire de

sommets, donc le graphe est fortement connexe.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 33 / 67

 G&opt
Graphe orienté
Notion de forte connexité

Notion de forte Connexité dans un Graphe Orienté (3/3)

Exemple de Graphe Non Fortement Connexe

Considérons le graphe suivant :

A B

D C

Dans ce graphe, il existe des sommets qui ne sont pas reliés par un
chemin orienté, donc le graphe n’est pas fortement connexe.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 34 / 67

 G&opt
Graphe orienté
Composantes Fortement Connexes

Composantes Fortement Connexes dans un Graphe Orienté

(1/2)

Composantes Fortement Connexes

Dans un graphe orienté G (S, A), une composante fortement connexe est un
sous-graphe G ′ (S ′ , A′ ) tel que :
1 Connectivité Pour chaque paire de sommets si , sj ∈ S ′ , il existe un chemin
orienté reliant si à sj et un chemin orienté reliant sj à si dans G ′ .
2 Maximalité G ′ n’est inclus dans aucun autre sous-graphe fortement
connexe G ′′ (S ′′ , A′′ ) de G tel que S ′ ⊂ S ′′ .

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 35 / 67

 G&opt
Graphe orienté
Composantes Fortement Connexes

Composantes Fortement Connexes dans un Graphe Orienté

(2/2)

Exemple
Considérons le graphe suivant :

A B D F

C E G H

Dans ce graphe, il y a 3 composantes fortement connexes

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 36 / 67

 G&opt
Fermeture transitive

Plan

4 Fermeture transitive
Explication de la fermeture transitive
Applications pratiques

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 37 / 67

 G&opt
Fermeture transitive

Fermeture Transitive d’un Graphe (1/4)

Définition
La fermeture transitive d’un graphe G (S, A) est un graphe G ′ (S, Af ) où
(si , sj ) ∈ Af si et seulement si l’accessibilité de si à sj dans G est égale à 1.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 38 / 67

 G&opt
Fermeture transitive

Fermeture Transitive d’un Graphe (2/4)

Calcul de la Fermeture Transitive

Pour calculer la fermeture transitive d’un graphe G , on peut utiliser
l’algorithme de Warshall :
1 Initialiser une matrice d’adjacence M avec les arêtes de G .
2 Mettre à jour M en calculant les puissances successives de M jusqu’à ce
que la fermeture transitive soit obtenue.
Mathématiquement, cela peut être exprimé par la relation :
n
_
(k) (k−1)
Mij = (Mil ∧ Mlj )
l=1

(k) W
où Mij représente l’élément de la matrice M à la k-ème puissance, et et ∧
représentent respectivement les opérations de disjonction et de conjonction
logiques.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 39 / 67

 G&opt
Fermeture transitive

Fermeture Transitive d’un Graphe (3/4)

Exemple (1)
Pour illustrer cela, considérons le graphe suivant :

A B C D

La fermeture transitive de ce graphe peut être calculée comme suit :

     
0 1 0 0 0 1 1 0 0 1 1 1
(1)
0 0 1 0 (2)
0 0 1 1  (3)
0 0 1 1
M = 0
, M = 
0 0 0 1  , M = 0
  
0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 40 / 67

 G&opt
Fermeture transitive

Fermeture Transitive d’un Graphe (4/4)

suite
Ainsi, la fermeture transitive du graphe est :

A B C D

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 41 / 67

 G&opt
Fermeture transitive
Explication de la fermeture transitive

Explication de la fermeture transitive

La fermeture transitive d’un graphe est une extension de ses arêtes qui
capture toutes les connexions possibles entre les sommets.
Elle permet de déterminer tous les chemins possibles entre chaque
paire de sommets.
En ajoutant des arêtes pour refléter les chemins indirects, elle rend le
graphe complet.
La fermeture transitive est souvent utilisée pour trouver les
composantes connexes d’un graphe.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 42 / 67

 G&opt
Fermeture transitive
Applications pratiques

Applications pratiques

La fermeture transitive trouve de nombreuses applications pratiques dans

divers domaines :
Réseaux sociaux : identification de relations indirectes entre
utilisateurs.
Base de données : optimisation des requêtes de chemins entre
entités.
Analyse des dépendances : détection de dépendances indirectes entre
variables.
Systèmes de recommandation : identification de produits ou
d’éléments similaires par des chemins indirects.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 43 / 67

 G&opt
Notion de graphe eulérien

Plan

5 Notion de graphe eulérien

Définitions et propriétés

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 44 / 67

 G&opt
Notion de graphe eulérien
Définitions et propriétés

Notion de graphe eulérien (1/3)

Définitions
Une chaîne eulérienne dans un graphe non orienté passe une et une
seule fois par chaque arête du graphe.
De même, un cycle eulérien dans un graphe non orienté passe une et
une seule fois par chaque arête du graphe.
Un graphe est dit eulérien s’il contient une chaîne ou un cycle
eulérien.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 45 / 67

 G&opt
Notion de graphe eulérien
Définitions et propriétés

Notion de graphe eulérien (2/3)

Propriétés
Un graphe (simple ou multiple) connexe possède un cycle eulérien si et
seulement s’il ne contient pas de sommet de degré impair. Formellement :

Un graphe connexe G (S, A) admet un cycle eulérien ⇔ ∀si ∈ Sd(si ) ∈ 2N

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 46 / 67

 G&opt
Notion de graphe eulérien
Définitions et propriétés

Notion de graphe eulérien (3/3)

Exemple
Considérons le graphe suivant :

C D

A B

Ce graphe est eulérien car tous ses sommets ont un degré pair.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 47 / 67

 G&opt
Notion de graphe eulérien
Définitions et propriétés

Graphe Eulérien : cas orienté (1/2)

Chemin Eulérien et Circuit Eulérien

Dans un graphe G (S, A) (simple ou multiple) connexe :
Un chemin eulérien est un chemin qui emprunte une et une seule
fois chaque arête du graphe.
Un circuit eulérien est un circuit qui emprunte une et une seule fois
chaque arête du graphe.

Conditions pour une Chaîne Eulérienne

Un graphe G (S, A) (simple ou multiple) connexe admet une chaîne
eulérienne entre deux sommets u et v si et seulement si le degré de u et
le degré de v sont impairs, et les degrés de tous les autres sommets du
graphe sont pairs.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 48 / 67

 G&opt
Notion de graphe eulérien
Définitions et propriétés

Graphe Eulérien : cas orienté (2/2)

Exemple
Considérons le graphe suivant :

1 2 3 4

10 A B C D E

J I H G F 5
9 8 7 6

Ce graphe est eulérien car il est possible de parcourir toutes les arêtes
exactement une fois, formant ainsi un cycle eulérien.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 49 / 67

 G&opt
Notion de graphe hamiltonien

Plan

6 Notion de graphe hamiltonien

Définitions et propriétés

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 50 / 67

 G&opt
Notion de graphe hamiltonien
Définitions et propriétés

Notion de graphe hamiltonien (1/3)

Définitions
Une chaîne hamiltonienne dans un graphe simple non orienté
comportant n sommets est une chaîne élémentaire de longueur
n − 1. Autrement dit, une chaîne hamiltonienne passe une et une
seule fois par chacun des n sommets du graphe.
De même, un cycle hamiltonien dans un graphe simple non orienté
comportant n sommets est un cycle élémentaire de longueur n.
Un graphe possédant un cycle hamiltonien sera dit graphe
hamiltonien.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 51 / 67

 G&opt
Notion de graphe hamiltonien
Définitions et propriétés

Notion de graphe hamiltonien (2/3)

Exemple
Considérons le graphe suivant :

d c

a b

Ce graphe ne possède pas de cycle hamiltonien, mais possède une chaîne

hamiltonienne :
⟨a, b, e, d, c⟩

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 52 / 67

 G&opt
Notion de graphe hamiltonien
Définitions et propriétés

Notion de graphe hamiltonien (3/3)

Exemple
Considérons le graphe suivant :

a b

e c

Ce graphe possède un cycle hamiltonien

⟨a, e, b, d, c, a⟩

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 53 / 67

 G&opt
Coloriage d’un graphe

Plan

7 Coloriage d’un graphe

Applications pratiques

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 54 / 67

 G&opt
Coloriage d’un graphe

Coloriage d’un graphe (1/1)

Coloriages
Un coloriage du graphe G est une manière d’attribuer une couleur à
chacun de ses sommets. On dit qu’un coloriage est propre si deux
sommets reliés par une arête ont des couleurs différentes. Le graphe G
étant fini.

Remarque
Le problème du coloriage d’un graphe avec un nombre limité de couleurs
est un problème combinatoire (on dit qu’il s’agit d’un problème
NP-complet). Cela signifie que tout algorithme résolvant ce problème de
façon exacte pourra prendre un temps exponentiel par rapport au nombre
de sommets du graphe (de l’ordre de 2n pour n sommets). Le problème
de déterminer le nombre chromatique d’un graphe est également
exponentiel, et est en fait encore plus difficile.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 55 / 67

 G&opt
Coloriage d’un graphe

Nombre chromatique d’un graphe (1/2)

Définition
On peut définir le nombre chromatique X (G ) d’un graphe fini G comme
le plus petit nombre n tel que G puisse être colorié avec n couleurs.

Propriétés
Le nombre chromatique est le plus petit nombre de couleurs
permettant de colorier tous les sommets du graphe sans que deux
sommets adjacents soient de la même couleur.
Le nombre chromatique d’un graphe est inférieur ou égal au plus
grand degré de ses sommets k majoré par 1 : X (G ) ≤ k + 1.
Le nombre chromatique d’un graphe est supérieur ou égal à l’ordre
de tous ses sous-graphes complets.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 56 / 67

 G&opt
Coloriage d’un graphe

Nombre chromatique d’un graphe (2/2)

Exemple
Considérons le graphe G (S, A) suivant :

1 2 3

Le nombre chromatique de ce graphe est X (G ) = 2, car il faut au moins

2 couleurs pour colorier tous les sommets de manière à ce que deux
sommets adjacents ne soient pas de la même couleur.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 57 / 67

 G&opt
Coloriage d’un graphe

Algorithme de Welch-Powell

Coloration d’un graphe

Colorer un graphe c’est colorer les sommets de telle façon que deux sommets distincts
et adjacents aient toujours des couleurs différentes.

Algorithm 1: Algorithme glouton de Welch-Powell

Input: Un graphe G
Result: Une coloration des sommets de G
1 Ranger les sommets par ordre décroissant de leurs degrés;
2 Choisir une couleur;
3 Affecter cette couleur au premier sommet de la liste non encore coloré;
4 Suivre la liste en attribuant cette même couleur à tout sommet qui :
n’est pas encore coloré ;
et qui n’est pas adjacent à un sommet coloré avec cette couleur.
Continuer jusqu’à ce que la liste soit finie;
while il reste des sommets non colorés do
Choisir une couleur qui n’est pas encore utilisée;
Recommencer les étapes 3 et 4 pour chaque sommet non coloré;

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 58 / 67

 G&opt
Coloriage d’un graphe
Applications pratiques

Applications pratiques

Planification des horaires : éviter les conflits, maximiser l’efficacité.

Assignation de ressources : minimiser les interférences, optimiser
l’utilisation.
Coloration de cartes géographiques : faciliter la visualisation, éviter
la confusion.
Problèmes de compilation : minimiser le nombre de registres
nécessaires.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 59 / 67

 G&opt
Networkx

Plan

8 Networkx

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 60 / 67

 G&opt
Networkx

Trouver des chaînes dans un graphe

1 import networkx as nx
2

3 G = nx.Graph()
4 G.add_edges_from([(1, 2), (2, 3), (3, 4), (4, 5)])
5 nx.draw(G, with_labels=True, node_color='skyblue',
,→ node_size=1500, font_size=15, font_weight='bold')
6

7 for path in nx.all_simple_paths(G, source=1, target=5):

8 print(path)

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 61 / 67

 G&opt
Networkx

Trouver des cycles dans un graphe

1 import networkx as nx
2

3 G = nx.cycle_graph(4)
4 nx.draw(G, with_labels=True, node_color='skyblue',
,→ node_size=1500, font_size=15, font_weight='bold')
5

6 cycles = nx.cycle_basis(G)
7 print(cycles)

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 62 / 67

 G&opt
Networkx

Trouver les composantes connexes d’un graphe

1 import networkx as nx
2

3 G = nx.Graph()
4 G.add_edges_from([(1, 2), (2, 3), (4, 5)])
5 nx.draw(G, with_labels=True, node_color='skyblue',
,→ node_size=1500, font_size=15, font_weight='bold')
6

7 components = nx.connected_components(G)
8 print(list(components))

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 63 / 67

 G&opt
Networkx

Trouver des sous-graphes eulériens

1 import networkx as nx
2

3 G = nx.complete_graph(5)
4 nx.draw(G, with_labels=True, node_color='skyblue',
,→ node_size=1500, font_size=15, font_weight='bold')
5

6 for eulerian_subgraph in nx.eulerian_circuit(G):

7 print(eulerian_subgraph)

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 64 / 67

 G&opt
Networkx

Appliquer des algorithmes de coloriage

1 import networkx as nx
2

3 G = nx.complete_graph(4)
4 nx.draw(G, with_labels=True, node_color='skyblue',
,→ node_size=1500, font_size=15, font_weight='bold')
5

6 colors = nx.greedy_color(G)
7 print(colors)

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 65 / 67

 G&opt
Conclusion

Plan

9 Conclusion

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 66 / 67

 G&opt
Conclusion

Conclusion

Chemins et chaînes : séquences de sommets reliés par des arêtes.

Circuits et cycles : chemins et chaînes qui se terminent au même
sommet.
Importants pour comprendre la connectivité et la structure des
réseaux.
Concepts fondamentaux en théorie des graphes pour modéliser
divers problèmes.

Amira FOUGHALI & Houcemeddine FILALI G&opt EPI-Digital/Prépa-TIC 67 / 67