23

Chapitre 3 : Graphes particuliers

I. Graphe biparti :
On appelle graphe biparti, noté G = (X1, X2, U), un graphe dont l’ensemble des
sommets est partitionné en deux ensembles (X1, X2) et tel que pour toute arête (ou
arc) ui : une extrémité est dans X1 et l’autre extrémité est dans X2.
X = (X1 ∪ X2) et si ∀ uij = (xi, xj), x i ∈ X1 ⇒ x j ∈ X2
x i ∈ X2 ⇒ x j ∈ X1
▪ Un graphe biparti complet est noté Kr,s avec r = |X1| et s = |X2|.
▪ Un graphe biparti ne possède aucun cycle impair (nombre impair d’arêtes).
▪ Un graphe biparti est 2-coloriable.
Exemple :
Graphe biparti : K2,3

Théorème de Konig : Le nombre chromatique d’un graphe G est 2 si et seulement

s’il n’admet pas de cycle de longueur impaire.

II. Graphe Planaire :

C’est un graphe qui peut être représenté sur un plan tel que deux arcs (ou arêtes) ne
se coupent pas.
▪ Tous les graphes de moins de 5 sommets sont planaires.
▪ Et aussi, tous les graphes bipartis de moins de 6 sommets,
Les autres, on connaît des algorithmes pour déterminer si un graphe est planaire.
Exemple d’application : la conception de circuits électriques.

III. Graphe Complémentaire :

On appelle graphe complémentaire (on le noté 𝐺̅ ) du graphe G le graphe dont les
sommets sont ceux de G et dans lequel deux sommets sont adjacents si et seulement
si ils ne sont pas adjacents dans G.

IV. Graphes Valués :

Un graphe valué est un A B C E F G
A 6 2
graphe orienté B 2
G = (X, U) muni d’une C
E
4
2 8
1
9
fonction f : U →R* appelée F
G 3
fonction de coût.
A. Merabet – centre universitaire de Mila – 2020
 24

Chapitre 3 : Graphes particuliers

C’est-à-dire un graphe où des réels sont associés aux arêtes.
Exemple:La matrice d'adjacence du graphe valué suivant est :

V. Graphes sans circuit :

Un graphe sans circuit est un graphe ne contenant aucun circuit.
Algorithme 4 : l’identification d’un graphe sans circuit
Entrées : G=(X ; U) un graphe orienté, Sortie : oui /
non
Début // Γ(si)= L’ensemble des successeurs de si
▪ X(0)= {si /si ∈ X, Γ(si)=∅ }
▪ X(1)= {si /si ∈ X–{X(0)} , Γ(si)⊂ { X(0)} }
▪ X(2)= {si /si ∈ X – {X(0)∪ X(1)} ,Γ(si)⊂{X(0)∪ X(1)} }
▪ …
▪ X(n)= {si /si ∈ X – {X(0)∪ X(1) ∪ … ∪ X(n-1)},
Γ(si)⊂ {X(0)∪ X(1) ∪ … ∪ X(n-1)} }
Si X=X(0)∪ X(1)∪ … ∪ X(n-1) alors
le graphe est sans circuit
Fin
Exemple 1 : soit le graphe
• X(0) = { x3 , x6}
• X(1) = { x5 , x1}
• X(2) = { x0 }
• X(3) = { x4 , x2}
Algorithme 5: l’identification d’un graphe sans circuit
Entrées: La matrice d’adjacence M d’un graphe orienté,
Sortie : oui / non
Début
1. Si ∃ une ligne i ne contient que des « 0 » alors
Supprimer la ligne i et la colonne i.
Si La matrice M ne contient que des « 0 » alors
Le graphe est sans circuit
Sinon
Allez 1 à
FinSI
Fin

A. Merabet – centre universitaire de Mila – 2020

 25

Chapitre 3 : Graphes particuliers

Exemple 1 : soit le graphe

• X(0) = { x3 , x6}
• X(1) = { x5 , x1}
• X(2) = { x0 }
• X(3) = { x4 , x2}

VI. Arbres, arborescences et forêts :

1. Définition d’un Arbre :
• Un arbre est un graphe connexe et sans cycle.
• Un arbre de n nœuds a donc
exactement n-1 arêtes.

2. Définition d’une Arborescence :

Une arborescence (G, r) est un

arbre orienté de racine r tel que :

• la racine r (ou sommet r) n’a pas de

prédécesseur
• Tout sommet s, autre que r, a un seul
prédécesseur.

3. Propriétés
• Dans un G orienté, la racine de l’arbre est un nœud qui n’a pas d’arcs entrants
(unique).
• Une feuille est un nœud de degré 1 (dans un graphe orienté : uniquement un
arc entrant et sans arcs sortants).
• Le graphe G possède au moins une feuille.
A. Merabet – centre universitaire de Mila – 2020
 26

Chapitre 3 : Graphes particuliers

• Si on ajoute une arête à un arbre, on crée un cycle (et un seul).
• Un arbre ne comporte pas de boucles. En effet, toute boucle est un cycle.
• Si on retire une arête à un arbre, on rompt la connexité.
• Dans un arbre, il y a une chaîne (et une seule) entre deux sommets.
• Dans une arborescence, il existe un chemin unique joignant la racine à tout
autre sommet.

4. Définition d’une forêt:

C’est un graphe non orienté

sans cycle (pas forcément
connexe). Chaque composante
connexe d’une forêt est un
arbre.

5. Problème de l’arbre minimal

Le problème de l’arbre de coût minimum (ou maximum) consiste à trouver un
arbre (Graphe partiel de G), dont la somme des poids des arcs est minimale (ou
maximale). En pratique, les problèmes se ramène plutôt à trouver l’arbre de coût
minimum, ce qui ne change pas fondamentalement le principe des algorithmes
proposés ici.

A. Merabet – centre universitaire de Mila – 2020

 27

Chapitre 3 : Graphes particuliers

Exemple d’application : minimiser le coût d’installation de lignes électriques entre
des maisons peut être modélisé par la recherche d’un arbre de coût minimum. En
effet, on veut :

• Utiliser moins de câbles possibles (chercher à minimiser la longueur

totale de câble utilisé).
• Connecter toutes les maisons entre elles sans avoir de lignes inutile.
Remarque :
• Le nombre d’arrêtes dans un ACPM (Arbre couvrant de poids minimum) est n-1

5.1. Algorithme de Kruskal

L’idée de l’Algorithme de Kruskal est de trier les arcs par ordre croissant de
leur poids. Ensuite dans cet ordre, les arcs sont ajoutés tant qu’il n’y a pas de cycle
introduit, sinon on passe à l’arc suivant dans l’ordre de tri.
Algorithme 6 : permet d’extraire l’arbre de poids minimum
Entrées : G=(X ; U) orienté, Sortie : Arbre = ( X, U’)
Début
▪ Supprimer toutes les boucles.
▪ Supprimer toutes les arêtes parallèles entre deux
sommets sauf l’arête au poids minimum.
▪ trier les arêtes en ordre de poids croissant et les
ranger dans une liste L.
▪ U’  {}
Pour tous les arcs ui de U : i allant de 1 à m faire
Si G = (X ; U’∪ ui) ne contient pas un cycle alors
U’ U’∪ ui
FinSI
Si |U’|= m - 1 alors RETOURNER Arbre = (X,U’) et Quitter
Finpour
Fin

Dans l’exemple précédant : On trie les arêtes du graphe. On obtient l'ordre

suivant : {7, 8} < {3, 9} = {6, 7} < {1, 2} = {3, 6} < {7, 9} < {8, 9} = {3, 4} <
{2, 3} = {1, 8} < {4, 5} < {5, 6} < {2, 8} < {4, 6}.

A. Merabet – centre universitaire de Mila – 2020

 28

Chapitre 3 : Graphes particuliers

On ajoute alors : successivement dans l'Arbre les arêtes : {7, 8}, {3, 9}, {6, 7},
{1, 2}, {3, 6}, {3, 4}, {2, 3}, {4, 5}.
5.2. Algorithme de Prim

Le principe de Prim est de partir d'un arbre initial réduit à un seul sommet, puis
d'augmenter à chaque itération la taille de l'arbre en le connectant au plus proche
voisin libre.
Algorithme 7:permet d’extraire l’arbre de poids minimum
Entrées : G=(X ; U) orienté, Sortie : Arbre = ( X, U’)
Début
1. Supprimer toutes les boucles.
2. Supprimer toutes les arêtes parallèles entre deux
sommets sauf l’arête au poids minimum.
3. X’  {}
4. Choisir arbitrairement un sommet s non traité et
ajouter le à X’
X’  X’ + {s}
5. Examiner toutes les arêtes connectées à l'arbre X’
et Choisir l’arête ui avec le poids plus faible.
Ajouter cette arête à l’arbre
U’  U’ + ui
Si tous les sommets sont examinés : X’ = X alors
Retourner Arbre = ( X, U’)
Sinon
Allez à 4
FinSi
Fin

A. Merabet – centre universitaire de Mila – 2020

 29

Chapitre 3 : Graphes particuliers

5.3. Algorithme de SOLLIN

L’idée de cet algorithme est une combinaison entre l’algorithme de Kruskal et
l’algorithme de Prim. Le principe est de réduire G, à chaque fois que l'on en
choisit une arrête, on fusionne les nœuds que cette arête relie. Ainsi, il ne reste
plus qu'un sommet à la fin.
Algorithme 8 : extraire l’arbre de poids minimum
Entrées : G = (X ; U) orienté, Sortie : Arbre = (X, U’)
Début
U’  {},
Répéter
1. X’  X
2. Supprimer toutes les boucles.
3. Supprimer toutes les arêtes parallèles entre
deux sommets sauf l’arête au poids minimum.
Tant que X’ ≠ ∅ faire
a. Choisir arbitrairement un sommet s non traité, s
∈ X’
b. Examiner toutes les arêtes connectées au sommet
s et Choisir l’arête ui avec le poids le plus
faible.
c. Ajouter cette arête à l’arbre : U’  U’ + ui
d. Retirer de X’ les extrémités de ui
Fin TQ
Fusionner les sommets de la même composante en un
seul sommet
Jusqu’à G est réduit à un seul sommet.
Retourner Arbre = ( X, U’)
Fin

A. Merabet – centre universitaire de Mila – 2020

 30

Chapitre 3 : Graphes particuliers

Exemple :

A. Merabet – centre universitaire de Mila – 2020