La théorie des graphes - publié le 03/02/2015

Thèmes abordés

Informatique - Électronique, théorie des graphes, arbres, arborescences, représentations des graphes, algorithmes, ordonnancement, flots de valeur maximale

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 des sommets ou des nœuds, 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

[...] Un circuit ω est dit absorbant si l(ω) = [...]

[...] Dans les différents algorithmes de détermination de flot complet et de modification de flux, on considère l'arc retour comme un arc direct de la chaîne améliorante et donc le flux y est augmenté de la quantité δ Flots bornés ou canalisés On suppose ici que dans le réseau R outre les capacités, chaque arc est doté d'une autre grandeur 0 dite borne de l'arc u. On le note alors le réseau R c). On notera Rc le réseau canonique associé. Définition : Etant donné Rc, on appelle flot canalisé un flot qui doit satisfaire outre les contraintes de Kirchhoff en tout point x X et de capacité : u des contraintes dites de bornes f(u). [...]

[...] On parle alors de graphe non orienté. Définition Un graphe non orienté G est constitué d'un ensemble X = xn} l'ensemble des de points et U = P2(X) υ P1(X) où P2(X) (respectivement est l'ensemble des paires (respectivement des singletons) de X. Les éléments de X sont appelés sommets du graphe et ceux de U les arêtes. Si U est un élément de P1(X) par exemple on dit que u est une boucle. Si U est un élément de P2(X) avec u=,,., les sommets x et y sont appelés extrémités de l'arête u. [...]

[...] iv) en réitérant un nombre fini de fois une telle procédure, on parvient à un flot ℱ et un graphe partiel Gp de G ne possédant aucun chemin de s à p. Et donc fp est flot complet sur R. Exemple Détermination d'un flot de valeur maximale Conditions d'optimalité On considère le réseau R = c). Définition Une coupe de R est un ensemble est un ensemble de sommets contenant s et ne contenant pas p. On appelle capacité d'une coupe la somme des capacités des arcs sortants de On note = c(u). on a la proposition suivante : Proposition : soit f et une coupe de R. [...]

[...] A l'aide du dictionnaire des précédents. Soit N0 l'ensemble des sommets de G qui n'ont pas de précédents. 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 Barrer dans la matrice booléenne les colonnes et les lignes correspondant aux éléments de N0. [...]