Graphes-Cours

Julien Chauveau

Informations

• Publié par: Theyr
• Nombre de lectures: 18
• Langue: Français

Extrait

est un graphe orienté (simple). E est l'ensemble des sommets de G. R est l’ensemble des arcs de G. Notation < x, y > R xRy x→y (x est le prédécesseur de y, y est le successeur de x) R(x) = { y | < x, y > R } est l’ensemble des successeurs de x -1R (y) = { x | < x, y > R } est l’ensemble des prédécesseurs de y y x -1x y x yR(x) R (y) y x Exemple 3 1 2 5 7 46 E = { 1, 2, 3, 4, 5, 6 , 7 } R = { < 1, 3 >, < 1, 6 >, < 3, 1 >, < 3, 7 >, < 4, 5 >, < 5, 5 > < 6, 1 >, < 6, 3 >, < 6, 7 > } R(1) = { 3, 6 } R(2) = Ø R(3) = { 1, 7 } … R(6) = { 1, 3, 7 } R(7) = Ø -1 -1 -1 -1 -1R (1) = { 3, 6 } R (2) = Ø R (3) = { 1, 6 } … R (6) = { 1 } R (7) = { 3, 6 } Définition 2 : demi-degrés et degré d’un sommet Soit G = < E, R > et x E. -1d (x) = |R (x)| est le demi-degré intérieur de x.i d (x) = |R(x)| est le demi-degré extérieur de x.e d(x) = d (x) + d (x) est le degré de x (la somme des demi-degrés intérieur et extérieur).i e Définition 3 : sous-graphe Soit G = < E, R > et A E. Le sous-graphe engendré par A est le graphe G = < A, R > tel A A que R = R { A x A } i.e. les sommets de E - A et les arcs associés sont supprimés.A Exemple avec le graphe précédent et A = { 1, 2, 3, 5, 7 } 3 1 2 5 7 M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 1<| <} „ <{ ‰ ‰ „ et L R, le graphe partiel engendré par L (sous-ensemble d'arcs) Lest le graphe G = < E, L > Exemple avec L = { < 1, 3 > , < 1, 6 > , < 5, 5 > , < 6, 1 > , < 6, 7 > } 3 1 2 5 7 46 Définition 5 : chemin Un chemin de longueur k ≥ 0 est une suite d'arcs ( α , α , … ,α ) telle que1 2 k α ( 1 ≤ i ≤ k - 1 ), l'extrémité de α est l'origine de α .i i i+1 !! ! k1 2 x xx x x k-1 k0 1 2 Remarques • Si α ≠ α pour i ≠ j alors le chemin est simple (élémentaire)i j • Pour k > 0, le chemin peut-être codé par la suite des sommets ( x , x , … , x ) telle que0 1 k α = ( x , x )i i-1 i Définition 6 : cycle (ou circuit) Un chemin non vide codé par ( x , x , … , x ) est un cycle (ou circuit) si x = x . Si x ≠ x 0 1 k 0 k i j pour ( i, j ) ≠ ( 0, k ) alors le cycle est élémentaire (chaque sommet n’apparaît qu’une fois). Définition 7 : circuit hamiltonien Un cycle élémentaire d’un graphe G est dit hamiltonien s’il contient tous les sommets de G. Remarque — TSP (Traveling Salesman Problem) — Etant donné un graphe G, déterminer parmi tous les circuits hamiltoniens, un circuit particulier qui minimise un coût (distance). Définition 8 : fermeture transitive + +La fermeture transitive de G = < E, R > est le graphe G = < E, R > tel que + + + i xR y R un chemin non vide de x à y R = R 2 i i ≥ 1 xRy xR y … xR y … R R1 2 +i.e. si x z y alors ! R Rappel Soit R et R deux relations binaires sur l’ensemble E,1 2 le produit R1·R2 = { < x, y > | z tel que < x, z > R et < z, y > R }1 2 2Si R = R = R alors on note R·R par R .1 2 M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 2<} <{ ‰ <} ‰ ‰ Exemple + +G R 3 1 2 5 +<1,7>!R ? oui +<3,6>!R ? oui 7 46 + 2R = R " R +R = R " {<1,7>, <3,6>, <1,1>, <6,6>, <3,3> } Définition 9 : fermeture transitive réflexive * *La fermeture transitive réflexive de G est G = < E, R > telle que *xR y x = y ou un chemin non vide de x à y Définition 10 : équivalence Soit G = < E, R > x, y E ⎧∃ un chemin de x à y x et y sont équivalents si x = y ou ⎨ ∃ un chemin de y à x⎪⎩ Exemple 1 et 6 sont équivalents. {1, 3, 6} est une classe d’équivalence. Définition 11 : forte connectivité Une composante fortement connexe de G est un sous-graphe de G engendré par une classe d’équivalence. Remarque un chemin entre 2 sommets quelconques d’une composante fortement connexe. Définition 12 : graphe non orienté Soit E un ensemble fini. Si R = { {x, y} | x E et y E } alors G = < E, R > est un graphe non orienté. E : ensemble de sommets R : ensemble d’arêtes Exemple 3 1 2 5 7 46 Définition 13 : graphe valué Soit G = < E, R > un graphe orienté (ou non orienté), V et V deux ensembles,s a une valuation des sommets caractérisée par la fonction v : E → Vs s une valuation des arcs (ou des arêtes) caractérisée par la fonction v : E → Va a alors G = < E, R, V , V , v , v > est un graphe valué (pondéré).s a s a M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 3<| ˆ <} ‰ ‡ un graphe. Si une partition de E en E et en E ( E E = Ø et E E = E ) 1 2 1 2 1 2 telle que x, y E ( i = 1, 2 ) ( x et y ne sont pas incidents / adjacents dans Ei - {x, y} R )i alors G est un graphe bipartite. E1 E2 Définition 15 : isomorphisme G = < E, R > et G’ = < E’, R’ > sont isomorphes si une bijection f : E → E’ telle que : (u, v) R (f(u), f(v)) R’ Exemple 21 f 1 2 3 4 5 6 u v w x y z3 u v w x y z6 5 4 Définition 16 : graphe complet (clique) G = < E, R > est un graphe complet si et seulement si x, y E, x≠y {x, y} R Remarque — Problème MaxClique — Etant donné un graphe G = < E, R >, déterminer le sous-graphe complet (clique) de taille maximum. Exemple MaxClique M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 4 est un hypergraphe, E : ensemble des sommets, F : ensemble des arêtes. Exemple ⎧ ⎫s1,s2,s3,s4 s1,s2,s3 s2,s3 s1,s4 s4{ } { } { } { } { }⎪ ⎪ , , , ,⎨ ⎬ E E1 E2 E3 E4⎪ ⎪⎩ ⎭ s3 s2 s1 s4 Définition 19 : arbre Un arbre est un graphe sans cycle. M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 5‰ un graphe, le graphe complémentaire de G est le graphe G = < E, R > tel que ∀ u,v∈E, (u,v)∉R⇔ (u,v)∈R s s1 1G GG G s s s s ss s s2 3 3 3 32 2 2 s s s s ss s s4 4 4 1 45 5 1 Définition 23 : ensemble indépendant Soit G = < E, R > un graphe, un ensemble indépendant S de G est un sous-ensemble de E tel que u, v S, (u, v) R Définition 24 : clique Soit G = < E, R > une clique de G est un sous-graphe complet de G. Théorème Soit G’= < E’, R’> une clique du graphe G alors E’ est un ensemble indépendant de G. M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 6<{ Cas particuliers de la coloration • Graphe planaire (théorème de 4 couleurs, 1974) : tout graphe planaire peut être colorié avec au maximum 4 couleurs. • Graphe complet (clique) : le nombre chromatique d’une clique de taille n est égal à n. K KK3 54 • Graphe bipartite : χ = 2 PVC (Problème du Voyageur de Commerce) — TSP (Traveling Salesman Problem) Etant donné un graphe valué sur les arêtes (arcs) représentant les distances ( ≥ 0 ), déterminer un circuit hamiltonien de longueur minimum. Remarque 1. « Très difficile » 2. Par contre, le plus court chemin entre 2 sommets (distincts) est facile. Représentation des graphes 1. Matrice d’adjacence Soit G = < E, R >, on utilise une matrice T de |E| × |E| telle que T[i, j] = 1 x Rxi j x x x x1 2 3 4 x x1 2 ! $x 0 1 1 01 # &T = x 1 0 0 12 # & # &x 0 1 0 03 # &x x3 4 x 0 0 0 0# &" %4 Remarque 1. Si le graphe est non orienté, la matrice est triangulaire 2. Si le graphe est valué (sur les arcs/arêtes), les valeurs de T sont les valuations 3. Cette représentation est particulièrement intéressante quand le graphe est dense. 2. Liste d’adjacence Un graphe est représenté par un tableau dont chaque élément correspond à un sommet as- socié à une liste chaînée comprenant les sommets adjacents. x xx 2 31 x xx 1 42 xx 23 x4 M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 7‰