Chapitre 1

Introduction et définitions

Ce cours s’adresse aux élèves-ingénieurs de 1ère année du département informatique de

Enseirb-Matmeca. Il s’inscrit dans la suite de deux enseignements algorithmiques réalisés
dans le semestre précédent : initiation algorithmique et structures arborescentes.

Ce cours concerne une nouvelle structure mathématique qui est le graphe. Cette structure
mathématique s’ajoute à celles vues dans les cours précédents : l’ensemble, le multi
ensemble, la séquence et l’arbre binaire. Le graphe peut être considéré comme le dernier
élément de cette suite. Autrement dit : tout ensemble d’informations structurées peut être
représenté à l’aide d’un graphe.

Une infinité de variétés de graphes

Il en découle qu’il existe une variété infinie de graphes. Ce cours ayant une durée limitée,
nous présentons et manipulons donc dans ce cours qu’une variété finie de graphes. Ouf !

Dans chaque variété de graphes considérées dans ce cours :

1.​ un “lien” (appelé arc ou arête) concerne au plus deux sommets. Il peut en être
autrement : voir la notion d’hypergraphe.
2.​ chaque graphe est finie : l’ensemble des sommets ainsi que celui des liens sont finis.

Un graphe se dessine mais n’est pas un dessin

Le terme “graphe” est d’origine grecque. Il signifie dessin. Nous verrons qu’il sera très utile
pour comprendre et résoudre des problèmes algorithmiques de manipuler les graphes à
l’aide de leurs représentations graphiques dites “dessins”. Attention, cependant à ne pas
confondre le graphe de l’un de ses dessins : l’un contient l’autre mais l’autre ne contient pas
l’un !

section 1 : 4 types de graphes : orientés ou non, simples ou non

Un 1er type de graphe : le graphe orienté à arcs multiples

page 1
Le graphe G001 possède 4 sommets 1,5,8,9 dessinés à l’aide de croix ainsi que 8 arcs
entre ces sommets a,b,c,d,e,f,h,k ; l’arc a a pour extrémité initiale le sommet 9 et pour
extrémité terminale le sommet 1. L’arc k est appelée une boucle.

Définition Graphe orienté à arcs multiples

Un graphe orienté à a=rcs multiples est un triplet noté G=(VG,EG,fG) où :
●​ VG est un ensemble. Ses éléments sont appelés les sommets de G.
●​ EG est un ensemble. Ses éléments sont appelés les arcs de G.
●​ fG : EG → VG2 est une fonction associant à chaque arc un couple de sommets ; le
premier est appelé extrémité initiale, le second extrémité terminale.

Exemple :
Le graphe G001 est égal au triplet (A,B,C) avec :
●​ A={1,5,9,8}
●​ B={a,b,c,d,e,f,h,k}
●​ C={(a,(9,1)),(b,(1,5)),(c,(5,1)),(d,(5,8)),(e,(1,5)),(f,(9,8)),(h,(8,9)),(k,(5,5))}

Comme on peut l’observer ici, le dessin d’un graphe permet de mieux visualiser le graphe.

De ce premier type de graphe, on peut extraire d’autres types de graphes en dégradant les
informations qu’il contient.
​
Deux dégradations sont ici possibles :
1.​ la première est d’oublier l’orientation des arcs.
2.​ la seconde est d’oublier la multiplicité des arcs.

Un 2nd type de graphe : le graphe non-orienté à arcs multiples

Voici le graphe G002 obtenu à partir de G001 en supprimant l’orientation. Un dessin de

G0002 est le suivant :

page 2
Définition Graphe non-orienté à arêtes multiples
Un graphe non-orienté à arêtes multiples est un triplet noté G=(VG,EG,fG) où :
●​ VG est un ensemble. Ses éléments sont appelés les sommets de G.
●​ EG est un ensemble. Ses éléments sont appelés les arêtes de G.
●​ fG : EG → {{a,b}∣a∈VG∧b∈VG} est une fonction associant à chaque arête un
singleton ou une paire de sommets de G ; ces sommets sont appelés extrémités de
l’arête.​

Exemple :
Le graphe G002 est égal au triplet (A,B,C) avec :
●​ A={1,5,9,8}
●​ B={a,b,c,d,e,f,h,k}
●​ C={(a,{1,9}),(,b,{1,5}),(c,{5,1}),(d,{5,8}),(e,{1,5}),(f,{9,8}),(h,{8,9}),(k,{5})}

Un 3ème type de graphe : le graphe orienté simple

Voici le graphe G003 obtenu à partir de G001 en supprimant la multiplicité des arcs. Un
dessin de G0003 est le suivant :

Définition Graphe orienté simple

Un graphe orienté simple est un couple noté G=(VG,EG) où :

page 3
 ●​ VG est un ensemble. Ses éléments sont appelés les sommets de G.
●​ EG est une partie de VG2. Chaque couple est appelé un arc de G.
Exemple :
Le graphe G003 est égal au couple (A,B) avec :
●​ A={1,5,9,8}
●​ B={(9,1),(1,5),(5,1),(5,8),(9,8),(8,9),(5,5)}

Un 4ème type de graphe : le graphe non-orienté simple

Voici le graphe G004 obtenu à partir de G001 en supprimant la multiplicité des arcs et
l’orientation Un dessin de G0004 est le suivant :

Définition Graphe non orienté simple

Un graphe non orienté simple est un couple noté G=(VG,EG) où :
●​ VG est un ensemble. Ses éléments sont appelés les sommets de G.
●​ EG est un ensemble de paires ou de singletons de sommets de G. .Chacune de ces
parties est appelée une arête.
Exemple :
Le graphe G004 est égal au couple (A,B) avec :
●​ A={1,5,9,8}
●​ B={{1,9},{1,5},{5,8},{9,8},{5}}

section 2 définitions locales

Un sommet s extrémité d’un arc ou d’une arête e est dit incident à e, et [Link]
sommets distincts incidents à un même arc (ou à une même arête) sont dits adjacents.

Un sommet est isolé si il n’est adjacent à aucun autre sommet.

Une boucle est un arc (ou une arête) incident(e) qu’à un seul sommet.

Le degré d’un sommet s dans un graphe G, noté degG(s), est le nombre d’arcs (ou d’arêtes)
incidents au sommet s (en comptant double les boucles).

Soit k un entier. Un graphe est k-régulier si tous ses sommets sont de degré k.

page 4
Dans un graphe orienté, un arc d’extrémité initiale (resp. terminale) un sommet s est dit
sortant de s (resp. entrant dans s). Le nombre d’arcs sortant (resp. entrant) d’un sommet s
est appelé le degré sortant (resp. degré entrant) de s.
Clairement, le degré d’un sommet est la somme de son degré entrant et de son degré
sortant (une boucle est à la fois entrante et sortante de son unique extrémité).

Une partie U de sommets d’un graphe G est une clique si les sommets sont deux à deux
adjacents.​

section 3 : dessins de graphes

Un graphe possède plusieurs dessins :

Lorsque l’on manipule pour la première fois des graphes, plusieurs confusions sont
possibles. On confond souvent un graphe et un de ses dessins.

Voici 3 dessins différents du même graphe K4. Dessin 2 est un dessin planaire de K4 : les
arêtes ne se croisent jamais. Dessin 1 et Dessin 3 ne sont pas planaires et sont en fait
assez proches : on peut passer de l’un à l’autre en “déformant” la surface de dessin.

section 4 : isomorphisme de graphes

Une classe isomorphique de graphes possède une infinité de graphes :

Voici une définition intuitive et universelle de ce que sont deux graphes isomorphes:

Deux graphes G et H sont isomorphes si on peut obtenir un dessin de H à partir d’un dessin
de G en changeant les noms ( des sommets et éventuellement des arcs ou des arêtes).

page 5
Les deux graphes G005 et G006 sont isomorphes et sont différents : les sommets 2 et 3
sont adjacents dans G005 mais ne le sont pas dans G006.

A partir de cette conception générale de l’isomorphisme, on peut fournir une définition

mathématique “solide” mais qui devra être adaptée à chaque type de graphes. Voici la
définition pour les graphes simples non orientés, tels qu’ils ont été définis plus haut :

Définition : isomorphisme de graphes simples non orientés​

Soient G et H deux graphes simples et non orientés. G est isomorphe à H si il existe un
isomorphisme de G vers H, c’est à dire une bijection ϕ : VG→ VH vérifiant EH= ϕ(EG) .

exemple :
dans l’exemple des graphes G=G005 et H=G006, un isomorphisme ϕ de G dans H est
{(1,1),(2,2),(4,3),(3,4)}.​
fin_exemple

Notation
Dans la définition plus haut, on étend ϕ : VG→ VH à une fonction admettant en entrée des
ensembles de sommets ou des ensembles d’ensembles de sommets. Ainsi, pour tous
sommets a et b de G, ϕ({a}) désigne {ϕ(a)}, ϕ({a,b}) désigne {ϕ(a),ϕ(b)} ; puis si E désigne un
ensemble de singletons ou de paires de sommets, ϕ(E) désigne {ϕ(A)∣A∈E}.

Un peu de culture : ​
ISOMORPHISME (appelé aussi dans ce cours SONT_ISOMORPHES)​
Le problème ​
Entrée : deux graphes G et H​
Sortie : le booléen (G est isomorphe à H)
n’admet pas de solution algorithmique de complexité en temps polynomiale connue.
Autrement dit, la communauté scientifique mondiale est ignorante : en date du lundi 24
janvier 2022, elle n’a prouvé ni l’existence d’une solution algorithmique en temps
polynomiale ni son existence.

Définition : dessin d’une classe de graphes isomorphes

Il découle de ces définitions que l’on peut dessiner une classe de graphes isomorphes. Il
suffit de prendre un dessin d’un des graphes et de supprimer sur le dessin les noms des
sommets. Voir l’exemple du dessin D3 de la classe contenant G005 et G006.

page 6
Attention :
Il arrive parfois que l’on présente un graphe en fournissant un de ses dessins débarassé des
noms de ses sommets. On confond alors un graphe G (par exemple G005) et un dessin de
sa classe d’isomorphisme D (par exemple D3). Cette confusion peut jouer de mauvais tours
algorithmiques : simple conséquence du fait que ISOMORPHISME n’admet pas de solution
polynomiale connue ce jour. Autrement dit : effacer les noms d’un dessin d’un graphe se fait
en temps linéaire, les retrouver en temps exponentiel !

page 7