Accueil > Informatique > RCP101 : Recherche opérationnelle et aide à la décision > Graph Particulier

Graph Particulier

lundi 13 juillet 2009, par frederic

Graph Symétrique
– Si pour toute paire de sommets (x,y) \in X il existe autant d’arcs de la forme (x,y) que de la forme (y,x)

– Cas du 1-Graphe G=(X,U), il est symétrique ssi :
(x,y) \in U (y,x) \in U

Graph Anti-Symétrique
– Si pour toute paire de sommets (x,y) C \in X il n’existe pas autant d’arcs de la forme (x,y) que de la forme (y,x) Le graphe G est dit anti-symétrique
– Cas du 1-graphe G=(X,U) il est anti-symétrique ssi :

(x,y) \in U \Rightarrow (y,x) \in U

Graph complet

– Un graghe G est complet si :
m_{G} (x,y) = m^{+}_{G}(x,y)+m^{-}_{G}(x,y) \geq 1 pour tout x,y \in X avec x \neq y
– Si G est un 1-graphe il est complet ssi : (x,y) \notin U \Rightarrow (y,x) \in U

Les arbres :

DEFINITION :
Graphe connexe sans cycle
Soit n sommets(n>=2) on obtient un arbre en joignant les n sommets sans former de cycle. Cet arbre a (n-1) arêtes
Preuve :

  • vrai si n=2 : arbre à une arête
  • Supposons cela vrai pour (n = k-1) arêtes :
    • arbre obtenu en connectant (k-1) sommets sans jamais former de cycle, (k-2) arêtes
  • Ajoutons un keme sommet pour rendre le graphe connexe il suffit de relier le nouveau sommet à l’un des (k-1) sommets par une arête
    • (k-2)+1=k-1 arêtes
    • (k-1)+1=k sommets

Un arbre est un graphe connexe sans circuit, donc en un seul morceau et sans "boucle"
THEOREME :
Soit H =(X,U) un graphe d ’ordre card(X)=n>=2
Les propriété suivantes caractérisent un arbre :

  1. H est connexe et sans cycle
  2. H est sans cycle et admet (n-1) arêtes
  3. H est connexe et admet (n-1) arêtes
  4. H est sans cycle et en ajoutant une arête on crée un cycle et un seul
  5. H est connexe et si on supprime une arête qcq, il n ’est plus connexe.
  6. Tout couple de sommets est relié par une chaîne et une seule.

Arbre recouvrant minimal

Algorithme de Kruskal

  1. Faire le liste des arêtes par valuation croissante.
  • S ’il existe des valeurs identiques ajouter une valeur ε à la première, 2ε à la suivante. n ε à la n^{eme}. ε doit satisfaire la condition suivante : n \epsilon + v_{i} \leq v_{i} +n
  1. Choisir l’arête de valeur minimale, puis successivement, au fur et mesure de la construction de l’arbre, l’arête de valeur immédiatement supérieure dans la liste mais sans former de cycle avec les arêtes déjà retenues.
  2. Arrêt lorsque tous les sommets sont connectés nombre d’arêtes=n-1

La complexité est en O(m log m).

donc plus m grandit, plus les temps de réponse seront énormes

Liste des arêtes
ab=13 fa=7
be=5 fc=11
bd=4 ga=5
ea=19 gf=7
ec=10 hf=2
ed=5 hg=9
cd=13 hc=19
ca=23
Arbre couvrant mini
hf=2 ec=10
bd=4 fc=11
be=5 ab=13
ed=5,(1) cd=13,(1)
ga=5,(2)
gf=7 hc=19
fa=7,(1) ea=19,(1)
hg=9 ca=23

Algorithme de Sollin

je prends le premier A
Quel est l’arrête qui va vers A qui coute le moins cher ?
F=3
mon paquet devient \{A, F\}
Le point suivant c’est B, le moins cher est \{B,E\} un 2^{eme} paquet
Le point suivant est C, le moins cher est \{C,B\}, le 2^{eme} paquet devient \{C,B,E\}
Le point suivant D, le moins cher est \{D,G\}, le 3^{eme} paquet \{D,G\}
On recommence avec les 3 paquets \{A,F\}, \{C,B,E\} et \{D,G\}

c_{1}=\{A\} ;c_{2}=\{B\} ; c_{3}=\{C\} ; c_{4}=\{D\} ; c_{5}=\{E\} ; c_{6}=\{F\} ; c_{7}=\{G\} ;

c_{1} non marqué, v_{1j}=min(c_{1},j)=[A,F]marquer c_{1} et c_{6}
c_{2} non marqué, v_{2j}=min(c_{2},j)=[B,E]marquer c_{2} et c_{5}
c_{3} non marqué, v_{3j}=min(c_{3},j)=[C,B]marquer c_{3}et c_{5}
c_{4} non marqué, v_{4j}=min(c_{4},j)=[D,G]marquer c_{4}et c_{7}
Tous les c_{i} sont marqués,
U_{1}= [A,F], [B,E], [C,B], [D,G] ---> étape 2

Sous-arbres :
c_{1}=\{A,F\}, c_{2}=\{B,C,E\}, c_{3}=\{G,D\},
c_{1} non marqué, v_{1,j} =min (c_{3},j)=[B,F]marquer c_{1} et c_{2}
c_{3} non marqué, v_{1,j} =min (c_{3},j)=[G,F]marquer c_{3} et c_{1}

Sous-arbres :
c_{1}=\{A,F\}, c_{2}=\{B,C,E\}, c_{3}=\{G,D\},
c_{1} non marqué, v_{1,j} =min (c_{1},j)=[B,F]marquer c_{1} et c_{2}
c_{3} non marqué, v_{1,j} =min (c_{3},j)=[G,F]marquer c_{3} et c_{1}
Tous les ci sont marqués
U_{2}=\{U1, [B,F] ,[G,F]\}

On obtient l ’arbre recouvrant A qui est minimal \lambda(A)=16