Les Graphes
1. Graphes non orientés
1
.. Un graphe est constitué de som me ts reliés par
des arêtes. 2 • Deux som me ts reliés par une arête
son t adjacents. 3 • L'ordre du graphe est le
nom bre de sommets. 4 .. Le degré d'un som me t
est le nom bre d'arêtes don t ce som me t est une
extrémité. s
Exemple:
• Le graphe G est d'ordre S. 6 • Les sommets A et B
son t adjacents. 7 • Le degré du som me t A est 3. a
❖ Lem me des poignées de ma ins • La som me
des
degrés d'un graphe non orie nté est égale à deux fois
le nom bre d'arêtes. 9
• La matrice associée à un graphe non orienté est
symétrique. • Un sous-graphe est composé de
certains som me ts de G et des arêtes qui les reli er -1,
10 • Un graphe com ple t a tous ses sommets
le nombre d'arêtes. 9
• La matrice associée à un graphe non orienté est
symétrique. • Un sous-graphe est composé de
certains sommets de G et des arêtes qui les relient.
10 • Un graphe complet a tous ses sommets
adjacents. • Une chaîne est une liste ordonnée de
sommets adjacents. 11 • Un graphe est connexe s'il
existe une chaîne entre deux sommets quelconques.
12 • Une chaîne fermée a son origine et son
extrémité confondues. 13 • Un cycle est une
chaîne fermée avec des arêtes distinctes. 14 • Une
chaîne eulérienne contient chaque arête une seule
fois. 1s Un cycle eulérien est une chaîne eulérienne
fermée. 16
❖ Théorème d'Euler• Un graphe connexe admet une
chaîne eulérienne si le nombre de sommets de degré
impair est O ou 2. 11 • Un graphe connexe admet un
cvcle eulérien si tous ses sommets sont de degré pair.
18
• La distance entre deux sommets est la plus courte
longueur des chaînes qui les relient. 19 • Le
diamètre d'un graphe est la plus grande distance -!,
entre deux sommets. 20
• La distance entre deux sommets est la plus court
longueur des chaînes qui les relient. 19 • Le
diamètre d'un graphe est la plus grande distance
entre deux sommets. 20
• La coloration d'un graphe consiste à affecter une
couleur à chaque sommet de sorte que deux
sommets adjacents ne portent pas la même couleur.
21 • Le nombre chromatique est le plus petit
nombre de couleurs permettant la coloration. 22
2. Graphes orientés
' Un graphe orienté a des arêtes orientées. 23
Une boucle est une arête orientée dont l'origine et
l'extrémité sont les mêmes. 24 ' Une chaîne
orientée eulérienne passe une fois par chaque arête.
2s ' Un cycle orienté eulérien est une chaîne
orientée eulérienne fermée. 16
❖ Un graphe connexe orienté admet un cycle orienté
eulérien si pour tout sommet X, le nombre d'arêtes
sortantes est égal au nombre d'arêtes entrantes.
3. Algorithme de
Dijkstra-Moore 26
• Utilisé pour trouver les chemins de longueur
minimale. 26 • On affecte le poids O au sommet
initial et le poids maximal aux autres sommets. 27
• On diminue les poids provisoires jusqu'à ce qu'ils
deviennent définitifs. 2a
4. Graphes
probabilistes
• Un graphe probabiliste est un graphe orienté et
pondéré où la somme des poids des arêtes sortant de
chaque sommet vaut 1. 29 4 Utilisé pour modéliser
l'évolution d'un individu changeant d'état
aléatoirement. • La matrice de transition donne les
probabilités de transition entre états.
Exercice:
11 RPnrP<PntPr [;, sit11;,tion rl'11n ç;,rrliPn rlP h11t ;,vpc
Exercice :
1) Représenter la situation d'un gardien de but avec
un graphe probabiliste. 30 2) Calculer la probabilité
qu'il arrête le troisième tir après avoir encaissé le
premier.
Exercice·
1) Analyser un graphe de liaisons aériennes entre
villes. 2) Détermine r le nombre minimal de couleurs
pour les aéroports. 31 3) Construire la matrice
associée et compter les chemins de longueur 8. 4)
Montrer qu'il est possible de construire un itinéraire
fermé en ajoutant une liaison. 32
r/:J J'aime
Expliquer le théorème d'Euler pour les graphes
Le théorème d'Euler pour les graphes non orientés
traite des conditions nécessaires pour qu'un graphP
connexe possède une chaîne eulérienne ou un cy _j,.
eulérien. 1 Voici les deux parties principales du
Le theoreme d'culer pour les graphes non orientes
traite des conditions nécessaires pour qu'un graphe
connexe possède une chaîne eulérienne ou un cycle
eulérien. 1 Voici les deux parties principales du
théorème:
1. Chaîne eulérienne :
• Un graphe connexe admet une chaîne
eulérienne (une chaîne qui passe une fois et
une seule par chaque arête du graphe) si et
seulement si le nombre de sommets de degré
impair est Oou 2. 1
• Cela signifie que pour qu'un graphe ait une
chaîne eulérienne, il doit avoir soit aucun
sommet de degré impair, soit exactement deux
sommets de degré impair. 1
2. Cycle eulérien :
• Un graphe connexe admet un cycle eulérien
(une chaîne eulérienne fermée) si et seulement
si tous ses sommets sont de degré pair. 2
• En d'autres termes, pour qu'un graphe ait un
cycle eulérien, chaque sommet du graphe doit
avoir un nombre pair d'arêtes. 2
Ces con d't' , '
I ions sont necessa1res et su ff'1santes pou, t
avoir un nomb re pair d'arêtes. 2
Ces condi tions sont nécessaires et suffisantes pour
déter mine r l'existence de chaînes et de cycles
euléri ens dans un graph e non orienté. 1
Quelles sont les conditions pour qu'un graphe connexe
admette une chaîne eulérienne?
Pour qu'un graph e conne xe adme tte une chaîne
eulérienne, les condi tions suivantes doive nt être
remp lies:
• Le graph e doit être connexe, c'est-à-dire qu'il
doit exister une chaîne entre chaque paire de
somm ets. 1
• Le nomb re de somm ets de degré impa ir doit
être exact emen t O ou 2.
Si ces condi tions sont satisfaites, alors le graphe
conne xe adme t une chaîne eulérienne, c'est-à-dire
une chaîne qui passe une fois et une seule par ch, -!,
arête du graphe. 2
