Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Cours de Recherche Opérationnelle Année 2002 - 2003 THEORIE DES GRAPHES I. Défi

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 E B  (A) = {B, C}  (B) = {E, D} A  (C) = {E}  (D) = {C} 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 B A C - arcs : A  B A pas d’arcs B A  B Notation (A, B) ou A  B ou AB D E - 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 A A A - 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. (A, B, D) est un circuit 2 formes :  forme booléenne  forme explicite (matrice ou arcs) 3. Exemples A B C D 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 E 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 GRAPHE 1 A C D 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 D A B E F GRAPHE 2 Dictionnaire des précédents : (graphe 2) X Prec(X) A 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)  A B C D E A A A B A C A E B B B B C C C D D D A D E E E E A C Chemin de taille 2 – 2 arcs : (graphe 1)  A B C D E A2 A A E A A B B A B C A E C A C D B B B B B B C B C D C C D A C D E uploads/s3/ cours-de-recherche-operationnelle-annee-2002-2003-theorie-des-graphes.pdf