Introduction à la

Théorie des graphes

Enseignante:

Olfa Layouni

E-mail:

[email protected]

Plan

 Graphes non orientés

⚫ Notions de base (Graphe partiel et sous-graphe, Degré,

Chaînes et cycles,…)

⚫ Graphes non orientés particuliers (Graphes eulériens,

Graphes Hamiltoniens Graphes planaires)

⚫ Codage d’un graphe non orienté (Matrice et listes

d'adjacences)

 Graphes orientés = diagraphes

⚫ Notions de base (Degré, Chemins, circuits,…)

⚫ Codage d’un graphe orienté (Matrice et listes d'adjacences)

Introduction

 Théorie des graphes

⚫ Depuis deuxième partie du 19ième siècle

⚫ Outil mathématique

 Application en:

⚫ Informatique

⚫ Recherche opérationnelle

⚫ Théorie des jeux

⚫ Théorie de la décision

⚫ …

Ponts de Konigsberg

La ville de Konigsberg (aujourd'hui

Kaliningrad ) est construite autour de

deux îles situées sur le Pregel et

reliées entre elles par un pont. Six

autres ponts relient les rives de le

rivière à l'une ou l'autre des deux

îles.

 Le problème consiste à déterminer s'il existe ou non une promenade dans

les rues de Königsberg permettant, à partir d'un point de départ au choix, de

passer une et une seule fois par chaque pont, et de revenir à son point de

départ (on ne peut traverser le Pregel qu'en passant sur les ponts.)

 Une telle promenade n'existe pas

 C'est Euler qui donna la solution de ce problème en caractérisant les

graphes que l'on appelle aujourd'hui « eulériens » en référence à l'illustre

mathématicien.

Concepts de base

> Graphes orientés – Graphes non orientés

⚫ Un graphe G=(V,E) est constitué d’un ensemble de points appelés sommets ou

nœuds (noté V)

⚫ Les sommets sont reliés par des arcs ou des arêtes (noté E) selon que le

graphe est orienté (diagraphe) ou non orienté.

Graphe orienté

(Diagraphe)

Graphe non orienté

• Remarque: si on fait abstraction des orientations des arcs on obtient un graphe non

orienté (avec les définitions et propriétés relatives aux graphes non orientés). Notons

que deux arcs orientés, A→B, B→ A constituent une même arête

Concepts de base

> arête – arc

 Une arête est définie par une paire

 Un arc est définie par une paire ordonnée

non-ordonnée de sommets

de sommets. Dans l'arc (A, B)

A est prédécesseur de B
B est successeur de A

 Deux sommets sont adjacents

(ou incidents) s'il existe un une

arête, les reliant

 Deux sommets sont adjacents (ou

incidents) s'il existe un arc les reliant

 Boucle: arête reliant un sommet à

 Boucle: arc reliant un sommet à lui-même

lui-même

Concepts de base

> Degré d’un sommet

•

Le degré d’un sommet A (noté d(A)):

→ Graphe non orienté: nombre d'arêtes dont le sommet A est une extrémité (Les

boucles sont comptées deux fois).

→ Graphe orienté : nombre d’arcs arrivant ou partant de A (Les boucles sont comptées

deux fois) = demi degré intérieur + demi degré extérieur d(A) = di(A) + de(A)

• Un sommet de degré 1 est appelé sommet pendant

• Un puits est un sommet d'un graphe orienté dont le degré sortant est égal à 0.

• Une source est un sommet d'un graphe orienté dont le degré entrant est égal à 0.

Concepts de base

> Propriétés

 P1: Poignées de mains : La somme des degrés des sommets d’un graphe

(orienté ou non) est égale à deux fois le nombre de ses arcs (ou arêtes).

 P2: Dans un graphe, le nombre de sommets de degré impair est toujours pair

(on ne peut donc pas avoir de graphe ayant un seul sommet de degré impair).

 P3: Un graphe ayant tous ses sommets de degré pair a un nombre de

sommets impair.

Sommet A B C D

Degré

10=5*2

Sommet A B C D

Degré

12=6*2

Connectivités

> Graphe non orientés

>> Chaînes - Cycles

⚫ Chaîne : Suite de sommets adjacents formant une suite d'arêtes connexes reliant un

sommet à un autre (par convention tout chemin contient au moins une arête).

⚫ Chaîne élémentaire : chaîne où chaque sommet y apparaît au plus une fois.

⚫ Chaîne simple si chaque arête apparaît au plus une fois.

⚫ Chaîne fermée si son sommet de départ est égal au sommet d’arrivée.

⚫ Cycle est une chaîne fermée où seul le sommet de départ apparaît deux fois

⚫ Longueur d'une chaîne : nombre de ses arêtes

⚫ Distance entre deux sommets : longueur de la chaine la plus courte les reliant.

Connectivités

> Graphe orientés

>> Chemin- Circuit

⚫ Chemin : Suite de sommets adjacents formant une suite d’arcs connexes reliant un

sommet à un autre (par convention tout chemin contient au moins un arc).

⚫ Circuit (souvent référencé par cycle par abus de langage) : chemin dont le sommet de

départ est égal à son sommet d’arrivée.

⚫ Longueur d'un chemin : nombre de ses arcs

⚫ Distance entre deux sommets : longueur du chemin le plus court les reliant.

Connectivités

> Chaîne Hamiltonienne - Chemin Hamiltonien

Chaîne Hamiltonienne : Chaîne passant

une et une seule fois par tous les

sommets d’un graphe

Chemin Hamiltonien : chemin passant

une et une seule fois par tous les

sommets d’un graphe

Il s'agit d'une généralisation du jeu bien

connu consistant à dessiner toutes les

arêtes d'un graphe avec un crayon sans

jamais le soulever, ni passer deux fois sur

la même arête.

ABCD – ABDC - ACBD

Connectivités

> Cycle – Circuit Hamiltonien

Cycle (circuit) hamiltonien : cycle passant une et une seule fois par tous les

sommets d’un graphe

Connectivités

> Chaîne Eulérienne – Chemin Eulérien

Chaîne Eulérienne : Chaîne passant une et une seule fois par toutes les arêtes

d’un graphe

Chemin Eulérien : chemin passant une et une seule fois par tous les arcs d’un

graphe

Connectivités

> Cycle Eulérien – Circuit Eulérien

Cycle Eulérien : cycle passant une et une seule fois par toutes les arêtes d’un

graphe (non orienté)

Circuit Eulérien : circuit passant une et une seule fois par tous les arcs d’un

graphe (orienté)

Concepts de base

> Ordre – Degré – Diamètre d’un graphe

 L’ordre d’un graphe (orienté ou non) est le nombre de sommets du graphe

 Le degré d’un graphe (orienté ou non) est le degré maximum de tous ses

sommets

 Le diamètre d’un graphe (orienté ou non) est la plus grande de toutes les

distances entre deux sommets quelconques du graphe

 L’ordre du graphe =4

 Le degré du graphe= 3

 Diamètre du graphe: 2

 L’ordre du graphe =4

 Le degré du graphe= 3

 Diamètre du graphe: 3 (distance entre A

et B = 3 (ACDB)

Représentation

Matrices d’adjacences

Listes d’adjacences

Représentation d’un graphe (1)

> Matrice d’adjacence

⚫ On peut représenter un graphe (orienté ou non) de n sommets par une matrice d’adjacence

(matrice de connexité) carré: n*n.

A B C D E

A B C D E F

⚫ M(i,j)=1 signifie que le sommet i est adjacent

au sommet j.

⚫ M(i,j)=1 signifie que le sommet i est

prédécesseur du sommet j.

⚫ Il n’ya que des 0 sur la diagonale sauf s’il y

une boucle (=1)

⚫ La matrice est symétrique

une boucle (=1)

⚫ La matrice n’est pas symétrique

Représentation d’un graphe (5)

> Liste d’adjacence

⚫ On peut représenter un graphe (orienté ou non) de n sommets par une liste d’adjacence

A: C, D, E

B: C

C: A, B, D, E

D: A, C, E

E: A, C, D

A: B, D, F

B: D, E

C: D

D: E

E: -

F: B

On associe à chaque sommet la liste des

sommets auxquels il est adjacent

On associe à chaque sommet la liste

des sommets qu’on peut atteindre

directement en suivant un arc (dans le

sens de la flèche)

Représentation d’un graphe (5)

> Matrice d’incidence

• Considérons un graphe orienté sans boucle G=(V,E) comportant n sommets

v1,…,vn et m arêtes e1,…,em.

• On appelle matrice d’incidence (aux arcs) de G la matrice M = (mij) de

dimension (n×m) telle que :

Représentation d’un graphe (5)

> Matrice d’incidence

Représentation d’un graphe (5)

> Quelques types de graphes

○ Un graphe est simple si au plus une arête relie deux sommets et s’il

n’y a pas de boucle sur un sommet.

○ Un multigraphe: un graphe doté d'une ou plusieurs arêtes multiples,

ou de boucles.

○ Un graphe est connexe s’il est possible, à partir de n’importe quel

sommet, de rejoindre tous les autres en suivant les arêtes

○ Un graphe non connexe se décompose en composantes connexes.

Représentation d’un graphe (5)

> Quelques types de graphes

• Un graphe est complet si chaque sommet du graphe est relié directement à tous les

autres sommets.

• Un graphe est biparti si ses sommets peuvent être divisés en deux ensembles X et

Y, de sorte que toutes les arêtes du graphe relient un sommet dans X à un sommet

dans Y. (dans l’exemple ci-dessous, on a X = {1,3,5} et Y = {2,4}, ou vice versa).