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 operationnelle annee 2002 2003 theorie des graphes

Cours de Recherche Opérationnelle Année - THEORIE DES GRAPHES CI Dé ?nition vocabulaire Dé ?nition Un graphe est dé ?nit comme un ensemble de sommets ou objets reliés entre eux Extrémité Variable Terminaison valeur ?? A B C E B ?? C E ?? D C ?? B E D A ?? E ? Il existe l ? application interne ?? A ? D C C ?? B A ? Mathématiquement un graphe G est complément dé ?ni - 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 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 C- 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 A B D est un circuit - arête arc non orienté A ?? B - cha? ne succession d ? arêtes successives chemin cha? ne circuit cycle circuit hamiltonien arcs arrête matrice associées un graphe peut être dé ?ni par sa matrice associée C formes ? forme booléenne ? forme explicite matrice ou arcs ? ? Exemples A B C D Forme Matrice Booléenne ? ABCD A B C D Forme Matrice en arcs ? A B C D A AB B BC CC CD D DB II Exercices Graphe B E A C GRAPHE D D A E A E A est-il un chemin simple non car on passe plusieurs fois par le même chemin D A E A est-il un chemin élémentaire non car il passe deux fois par le sommet A D A E est-il un chemin élémentaire oui Donner la matrice aux arcs ? A B C D E A AB AC AE B BB BC ? C CD CD DA DE E EA EC Donner la matrice booléenne ? A B C D E A B C D E C Graphe C D A B E F GRAPHE Dictionnaire des précédents graphe X Prec X A B A C F CD DE E F B FB Dictionnaire des suivants graphe X Prec X CAB B E F CB DC ED F B E Chemin de longueur B ?? taille graphe ? ABCDE A AA A BC E A B BB BC C C D D D D A E E EE CAC Chemin de taille ?? arcs graphe ?