theorie des graphes .pdf



Nom original: theorie des graphes.pdfAuteur: Houssem Eddine

Ce document au format PDF 1.5 a été généré par Microsoft® Word 2013, et a été envoyé sur fichier-pdf.fr le 17/03/2014 à 16:52, depuis l'adresse IP 41.225.x.x. La présente page de téléchargement du fichier a été vue 858 fois.
Taille du document: 711 Ko (5 pages).
Confidentialité: fichier public


Aperçu du document


4éme Eco & info

Résumé Cours « Théorie des Graphes »

Cours : Théorie des Graphes
I.

Lexique & Définitions:
















Un graphe simple : G est un couple formé de deux ensembles : un ensemble
X={x1,x2….} dont les éléments sont appelé des sommets et un ensemble A={a1,a2,….}
partie de l’ensemble P2(X) dont les éléments sont appelé arêtes on le note G(X,A).
Sous-graphe : H(Y,B) est un sous graphes de G(X,A) si :Y X et B  A.
Ordre du graphe : c’est le nombre de sommets du graphe.
Chaîne : suite finie de sommets reliés par des arêtes.
Sommets adjacents : deux sommets adjacents sont reliés par une arrête.
Un graphe complet : un graphe où touts les sommets sont adjacents.
Un graphe connexe : entre deux sommets quelconque du graphe il existe une chaine.
Degré d’un sommet : c’est le nombre d’arrêtes dont le sommet est une extrémité.
Chaîne Eulérienne : chaine simple passant une seule fois par toutes les arêtes d’un
graphe.
Cycle Eulérien : cycle simple passant par toutes les arêtes d’un graphe une seule fois.
Longueur d’une chaine : nombre des arêtes qui compose la chaine.
Distance entre deux sommets : longueur de la plus courte chaine joignant les deux
sommets.
Diamètre d’un graphe : maximum des distances entre les sommets du graphe.
Indice chromatique : le nombre minimal de couleurs permettant de colorier les arêtes
du graphe de façon que deux arêtes adjacentes n’aient pas la même couleur.
Nombre chromatique :(G) le nombre minimal de couleurs permettant de colorier les
sommets du graphe de tel sorte que deux sommets adjacents n’aient pas la même
couleur.

Si un graphe est complet alors son nombre chromatique est égal à son ordre.

Un graphe non connexe

II.

Un complet

Une Chaine Eulérienne

Propriétés

- La somme des degrés de tous les sommets d’un graphe est égale à 2 fois la somme des arêtes du
graphe.
- Un graphe connexe admet une chaine Eulérienne si et seulement si tout ses sommets sont de degrés
paire ou bien deux seulement de ses sommets sont de degrés impaire.
- Un graphe connexe admet une cycle Eulérien si et seulement si tout ses sommets sont de degrés paire .

Par M R Houssem Eddine Fitati

1

4éme Eco & info

Résumé Cours « Théorie des Graphes »

Un graphe connexe qui n’admet
pas de cycle Eulérien

Un graphe connexe qui admet une
chaine Eulérienne

Nombre chromatique : (G)

Le nombre chromatique d’un graphe (G) est le nombre minimal de couleurs utilisé pour
colorer les sommets d’un graphe de façon que deux sommets adjacents n’aient aps la même
couleur.
On a toujours : +1  (G)  r+1 où :  est le plus grand ordre des sous graphes complets de
G et r est le plus grand degré des sommets de G.
Comment déterminer le nombre chromatique d’un graphe ?
Soit G le graphe suivant :
On commence par ordonner les sommets suivant l’ordre
décroissant de leurs degrés.

A
B

Sommet
degré

G
5

H
5

D
5

B
4

A
4

E
3

F
3

C
3

E
G

H

F
C
D

On attribut la première couleur au premier sommet ( il
n’y a pas de problème si deux sommets ou plus ont le
même degrés), les sommets non adjacents a ce sommets
on leurs attribue cette même couleur a condition qu’ils ne
soient pas adjacents :
Dans notre cas on choisie entre B et C.

A
B

E
G

H

F
C

Sommet
degré

G
5

H
5

D
5

B
4

A
4

E
3

F
3

D

C
3

Puis on passe à l’autre sommet et ainsi de suite….
Sommet G
degré
5
Donc (G)=4

H
5

D
5

B
4

A
4

E
3

F
3

A
B

C
3

E
G

H

F
C
D

Par M R Houssem Eddine Fitati

2

Résumé Cours « Théorie des Graphes »

III.

4éme Eco & info

3

Matrice associée à un Graphe non Orienté :
Soit G(X,A) un graphe ,la matrice d’adjacence (associée) du graphe G est la matrice


mi , j  1 si (xi , x j )  A (les sommets : ai et a j sont adjacents)

mi , j  0 si non

M(mi,j) tels que : 

La matrice associée à un graphe non orienté est une matrice symétrique, c'est-à-dire que
mi,j=mj,i .
Exemple :
5

1
4

3

0

0
dont la matrice associée :  1

1
1


0 1 1 1

0 1 0 0
1 0 1 1

0 1 0 1
0 1 1 0 

2

- c’est une matrice carré.
-si 1 existe sur la diagonale cela signifie une boucle.
-on pose M k=(mki,j) le terme mki,j indique le nombre de chemin de longueur k reliant le sommet
ai au sommet aj. Pour tout k entier naturel.
IV. Graphe Orienté :
 Un graphe est dit orienté est un graphe où on a donné un sens à ses arêtes.
 Un arc est une paire ordonnée de sommets
 Soit v u des sommets d’un graphe orienté : on note d+(v) le degré extérieur de v c’est le
nombre d’arcs ayant v comme extrémité initiale, et d-(v) est le degré intérieur de v,
on a d(v) = d+(v) + d-(v).
 Un chemin ou un circuit conduisant du sommet a au sommet b est une suite d’arcs
conduisant de a à b.
 On appelle distance entre deux sommets la longueur du plus petit chemin les reliant. S’il
n’existe pas de chemin entre a et b on dit que d(a,b)=.
 La matrice associée à un graphe orienté est une matrice carré (ai,j ) tels que ai,j = 1 si le
sommet Si est adjacent au sommet Sj et tels que Si est l’origine et Sj est l’extrémité. Si
non ai,j=0
On remarque que :
n

 ai , j  d  ( S j ) c' est le nombre d' arcs aboutissan t au sommet S j





i 1

La somme des termes de la matrice associée au graphe est le nombre des arcs du
graphe.

 

on note aik, j  M k où k est un entier naturel; le terme ai,k j est le nombre de chemins
de longueur k partant de S i et aboutissant à S j

Par M R Houssem Eddine Fitati

4éme Eco & info

Résumé Cours « Théorie des Graphes »

2

1

4

5

V.

0

0
0
La matrice associée à ce graphe M= 
0
0

0


6

3

4

1 0 1 0 1

0 0 1 1 0
0 0 1 0 0

0 0 0 1 0
0 0 0 0 0 
1 0 0 0 0 

Graphe Pondéré :
Un graphe est dit pondéré est un graphe dont les arêtes sont afféctées de coéficients
positifs applés poids.
Le poids d’une chaine est la somme des poids de cette chaine.
Le plus cout chemin entre deux sommets est le poids minimal d’une des chaines reliants
ces deux sommets .
Un graphe oienté et pondéré est un graphe orienté dont les arrêtes sont afféctées de
coeficients positifs appelés couts.
Un plus court chemain entre deux sommets est le chemin reliant les deux sommets et
admettant le cout minimale.

VI.

Algorithme de Dijkstra ( 1930 -2002):
Dijkstra Edgser Wybe a proposé en 1959 un algorithme permettant de calculer le plus
court chemin entre un sommet particulier et tout autre. Le résultat est une arborescence
On numérote les sommets de 1 à n et on s’intéresse au chemins partant de 1.On
construit le vecteur =((1), (2),…, (n)) avec j= à la longueur de la plus courte
chaine allant de 1 à j donc la matrice des couts du graphe à pour première ligne définie
0
si i  j

Par ci , j   si i  j et S i et S j ne sont pas adjacents

 (i, j) si non où  (i, j) est le poids de l' arc (i, j)
On définie un autre vecteur p pour mémoriser le chemin pour aller du sommet 1au
sommet voulu la valeur p(i) donne la somme qui précède (i) dans le chemin.

 

- Trouver le trajet le plus court en partant de E pour arriver à S.
1

B
2
E

2

6

A

4

8

2

3

D
9

8
1

F

G

S

7

C

Par M R Houssem Eddine Fitati

4éme Eco & info

Résumé Cours « Théorie des Graphes »

5

On se propose d’utiliser l’algorithme de Dijkstra

E
0

VII.

A

B

C







6(E)
6(E)
5(D)

2(E)

8(E)
8(E)
8(E)
7(A)

D




3(B)

F




11(D)
9(A)
10(C)

G





12(D)
12(D)
12(D)

S

Sommet sélectionné

14(C)

E
B(2)
D(3)
A(5)
C(7)
G(12)







Graphe Probabiliste:
-Un graphe probabiliste est un graphe orienté et valué dont la somme des coûts des arcs
issus de chaque sommet vaut 1.
La matrice de transition d’un graphe probabiliste G=(X,A,) est d’ordre n , est la
n
 ( i , j ) si (i, j)  A
avec  pi , j  1
matrice P(pi,j) où : pi , j  
0 si (i, j)  A
j 1
-Les graphes probabilistes sont utilisés pour modéliser l’évolution d’un individu
pouvant changer aléatoirement d’état: les sommets sont des états possibles et le coût de
l’arc (i,j) est la probabilité de transition de l’état i à l’état j.
-L’état probabiliste de l’individu à l’instant n ℕ est une loi de probabilité sur
l’ensemble des états possibles et qui est représentée par un vecteur stochastique n .
Lorsque les hypothèse de d’indépendance et d’homogénéité sont vérifiées ( définition de
la chaine de Markov ) on a alors : n=0Pn .

Par M R Houssem Eddine Fitati


theorie des graphes.pdf - page 1/5


theorie des graphes.pdf - page 2/5


theorie des graphes.pdf - page 3/5

theorie des graphes.pdf - page 4/5

theorie des graphes.pdf - page 5/5


Télécharger le fichier (PDF)


theorie des graphes.pdf (PDF, 711 Ko)

Télécharger
Formats alternatifs: ZIP



Documents similaires


theorie des graphes
graphe
graphes
2016 chapitre 3 graphes op rations de base video
serie d exercices graphes bac eco gestion 1
chapitre 2 problemes de graphes

Sur le même sujet..