Scribd
Importer
189 vues10 pages

Théorie des Graphes Simplifiée

Ce document présente les notions de base sur la théorie des graphes. Il définit ce qu'est un graphe et donne le vocabulaire associé comme les sommets, arcs, chemins, circuits. Il présente également des exemples de graphes sous forme matricielle.

Transféré par

BADR styloos
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
189 vues10 pages

Théorie des Graphes Simplifiée

Ce document présente les notions de base sur la théorie des graphes. Il définit ce qu'est un graphe et donne le vocabulaire associé comme les sommets, arcs, chemins, circuits. Il présente également des exemples de graphes sous forme matricielle.

Transféré par

BADR styloos
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Cours de Recherche Opérationnelle

Année 2002 - 2003

THEORIE DES GRAPHES


I. Définition & vocabulaire
1. Définition
Un graphe est définit comme un ensemble de sommets (ou objets) reliés entre eux.

Extrémité = Variable Terminaison = valeur

 (A) = {B, C}

 (B) = {E, D}

 (C) = {E}

 (D) = {C}

 (E) = 

Il existe l’application interne :

 (A) = 
 (B) = {A}

…..

Mathématiquement un graphe G est complément défini :

- si on connaît l’ensemble des sommes X = {A, B, C, D, E}

- si on connaît l’application 

donc G = {X, }

U = { (A,B), (A,C), (B,E), (C,E), (B,D), (D,C) } = ensemble des arcs

2. Vocabulaire

- arcs : A  B A pas d’arcs B A  B

Notation (A, B) ou A  B ou AB

- sommet adjacents : deux sommets reliées par un arc

- chemin Hamiltonien : un chemin qui passe une fois et une seule fois par tous les
sommets (et qui comprend l’ensemble des sommets)

- chemin simple : un chemin qui passe qu’une et une seule fois sur un arc
- chemin élémentaire : un chemin qui passe qu’une et une seule fois par les sommets
qu’il utilise

- circuit : un chemin qui se referme sur lui-même

(A, B, D) est un circuit


-

arête : arc non orienté A – B

- chaîne : succession d’arêtes successives.

circuit
hamiltonien

chemin chaîne circuit cycle

arcs

arrête

- matrice associées : un graphe peut être défini par sa matrice associée.


2 formes :

 forme booléenne

 forme explicite (matrice ou arcs)

3. Exemples
A

Forme Matrice Booléenne :

 A B C D

A 0 1 0 0

B 0 0 1 0

C 0 0 0 1

D 0 1 0 0

Forme Matrice en arcs :

 A B C D

A AB

B BC
C CD

D DB

II. Exercices
1. Graphe 1
B

A C GRAPHE 1

1. {D, A, E, A, E, A} est-il un chemin simple ?

non car on passe plusieurs fois par le même chemin

2. {D, A, E, A} est-il un chemin élémentaire ?

non car il passe deux fois par le sommet A

3. {D, A, E} est-il un chemin élémentaire ?

oui

4. Donner la matrice aux arcs

 A B C D E

A AB AC AE

B BB BC

C CD
D DA DE

E EA EC

5. Donner la matrice booléenne

 A B C D E

A 0 1 1 0 1

B 0 1 1 0 0

C 0 0 0 1 0

D 1 0 0 0 1

E 1 0 1 0 0
2. Graphe 2
C

GRAPHE 2

Dictionnaire des précédents : (graphe 2)

X Prec(X)

B A,C,F

C D

D E

E F,B

F B

Dictionnaire des suivants : (graphe 2)

X Prec(X)
A B

B E,F

C B

D C

E D

F B,E

Chemin de longueur B – taille 1 : (graphe 1)

 ABCDE

A AA A
BC E

B BB
BC

C C
D

D D D
A E

E E E
A C

Chemin de taille 2 – 2 arcs : (graphe 1)

 ABCDE

A2 AAAA
EBBC
ABCD
A
A
E
C

B BBB
BBC
BCD

C C C
D D
A E

Vous aimerez peut-être aussi