Graphes-Cours
20 pages
Français

Graphes-Cours

-

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

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 yy x-1x y x yR(x) R (y)y xExemple31 2 57 46E = { 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 sommetSoit G = < E, R > et x E.-1d (x) = |R (x)| est le demi-degré intérieur de x.id (x) = |R(x)| est le demi-degré extérieur de x.ed(x) = d (x) + d (x) est le degré de x (la somme des demi-degrés intérieur et extérieur).i eDéfinition 3 : sous-grapheSoit G = < E, R > et A E. Le sous-graphe engendré par A est le graphe G = < A, R > tel A Aque R = R { A x A } i.e. les sommets de E - A et les arcs associés sont supprimés.AExemple avec le graphe précédent et A = { 1, 2, 3, 5, 7 }31 2 57M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes ...

Sujets

Informations

Publié par
Nombre de lectures 27
Langue Français

Exrait

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 ‰ R d’un graphe G = < E, R >i,j ⎧ci,j ≥ 0 ⇔ ∈R Représentation par matrice de distance : ⎨ ci,j = ∞ ⇔ ∉R⎪⎩ W = { x E | le plus court chemin de s à x est connu } p[x] = la distance du plus court chemin de s à x passant uniquement par les sommets de W L’idée de l’algorithme On part avec W = {s}, p[s] = 0, ⎧cs,y ≥ 0 si ∈ R p[y] = ⎨ cs,y = ∞ sinon⎪⎩ On étend W par un sommet x E - W tel que p[x] = min { p[y] | y E - W } Mise à jour de p pour tout y E - W ⎧p[x] + cx,y si p[x] + cx,y < p[y] p[y] = ⎨ p[y] sinon⎪⎩ E-W y xW y y p[x]=5 c =2x,y s y yp[y]=10 s Algorithme de Dijkstra Input : - Graphe G = < E, R >, avec c ≥ 0u,v - Un sommet initial s Output : p : vecteur de taille | E | , p[x] = la distance du plus court chemin de s à x, x E M1 Info 2005 / 2006 — Université d’Angers — Algorithmique des graphes 10