La théorie des graphes: généralités et problèmes de cheminement

Thèmes abordés

Théorie des graphes, graphe, problèmes de cheminement, graphe orienté, arc

Résumé du document

Un graphe orienté est déterminé par la donnée d'un ensemble fini X dont les éléments sont appelés sommets ou nœuds, et d'un ensemble U dont les éléments sont des couples ordonnés de sommets appelés arcs. On le note G = (X, U).

Extraits

[...] Exemple X1 X6 X5 X2 x3, x6} est une clique Définition Un stable sur un graphe G est un sous-graphe sans arête. Remarque : Un sommet isolé est à la fois une clique et un stable. Par abus de langage, l'ensemble des sommets d'un stable (respectivement d'une clique) est appelé stable (respectivement clique) de sorte que, on dit que S est un stable de G = si S X et y U. c'est-à-dire deux sommets quelconques de S ne sont pas adjacents. Définition Le nombre de stabilité d'un graphe G est le cardinal maximal d'un stable de G. [...]

[...] Algorithme de Bellman Poser = 0 et = { n}. k=1. A l'itération faire = 0 et pour tous les xj, poser = Min { + l(xij) avec P(xj) Si = stop. si k n-1 faire k k et aller à 2. Si k = stop il existe un circuit absorbant. Convergence : représente la longueur du chemin de x1 à xi de longueur minimale et ne contenant pas plus d'un arc. Dans l'étape représente la valeur du chemin de x1 à xi de longueur minimale et ne contenant pas plus de k arcs. [...]

[...] On considère les notations suivantes : 26 Notation : On note par le plus petit entier supérieur ou égal à et par le plus grand entier inférieur ou égal à , c'est-à-dire la partie entière de . On montre que : Proposition Soit un graphe sans boucle d'ordre n. On a : ɤ(G) d+1 où d = max : x X}. Démonstration Notons { } une partition de X en k parties stables avec . Alors : n , étant des entiers naturels, l'inégalité de gauche est établie. Construisons une partition de X en sous ensembles stables de la manière suivante. [...]

[...] N0 constitue l'ensemble des sommets de G de niveau 0. Barrer dans le dictionnaire des précédents les éléments de N0 partout où ils se trouvent. Si un sommet a tous ses éléments barrés il est de niveau 1. On réitère cette procédure en augmentant de la valeur des niveaux jusqu'à ce que tous les sommets soient barrés. b. A l'aide de la matrice booléenne L'ensemble N0 des sommets de niveau 0 est l'ensemble des sommets dont les colonnes sont nulles 35 Barrer dans la matrice booléenne les colonnes et les lignes correspondant aux éléments de N0. [...]

[...] Proposition Le graphe réduit est sans circuit. Définition Un graphe G est dit quasi-fortement connexe si y il existe un sommet d'où partent à la fois un chemin allant à x et un chemin allant à y Proposition Un graphe fortement connexe est quasi fortement connexe. Un graphe quasi fortement connexe est connexe Graphes non orientés Dans l'étude de certaines propriétés des graphes, il arrive que l'orientation des arcs c'est-à-dire la distinction entre extrémité initiale et extrémité terminale ne joue aucun rôle. [...]