online kép - Fájl  tube fájl feltöltés file feltöltés - adja hozzá a fájlokat online fedezze fel a legújabb online dokumentumok Kapcsolat
   
 

Letöltheto dokumentumok, programok, törvények, tervezetek, javaslatok, egyéb hasznos információk, receptek - Fájl kiterjesztések - fajltube.com

 

Online dokumentumok - kep
   
kategória
 

Biológia állatok Fizikai Földrajz Kémia Matematika Növénytan Számítógépes
Filozófia
Gazdaság
Gyógyszer
Irodalom
Menedzsment
Receptek
Vegyes

 
 
 
 













































 
 

Grafalgoritmusok: grafok bejarasa, útmatrix, legrövidebb utak matrixanak meghatarozasa.

számítógépes

Fájl küldése e-mail Esszé Projekt


egyéb tételek

 
Tablazatok szerkesztési műveletei
Halózati operaciós rendszerek
Az ACCESS objektumai
A szamítógép-halózatok hasznalata
MILYEN HÍRFORRÁSOKAT ISMER? A HÍRFORRÁSOK KÖZÜL MELYEKET KELL ELLENŐRIZNI ÉS HOGYAN?
Az Excel alapjai
FoxPro alapok
BGP - Border Gateway Protokol
Generative Drafting Munkatér indítasa
Racsok, segédvonalak
 
 

Gráfalgoritmusok: gráfok bejárása, útmátrix, legrövidebb utak mátrixának meghatározása.

Gráfok és alkalmazásaik

G=(V,E)  egyszerű gráf (irányított),  |V| = m

A csomópontok rendezettek: v1,v2,v3, ...... ,vm

Szomszédsági mátrix:          A=(aij) szomszédsági mátrixa G-nek, ha   aij=0, ha minden vi®vj él és                    aij=0 különben.

Példa

         v1·              ·v3                     242d32c                      242d32c            0 1 1 1

                     242d32c                      242d32c                      242d32c                 A=    0 0 0 0

                     242d32c                      242d32c                      242d32c                      242d32c      0 0 0 1

         v2·              ·v4                     242d32c                      242d32c            0 0 1 0

Tétel   A a G gráf szomszédsági mátrixa. A2:= A*A, A3:=A*A*A  ..., Ak:=(ak(i,j)). Ekkor             ak(i,j) egyenlő a vi-ből vj-be vezető k hosszúságú utak számával.

Példa

A2= 0   0   1   1                     242d32c   v1®v4®v3

         0   0   0   0

         0   0   1   0

         0   0   0   1

Útmátrix: P=(pij) mátrix a G irányított gráf útmátrixa, ha pij=1, ha minden vi-ből vj-be út és                pij=0 különben.

Tétel:    pij=1 Û ha Bm=A+A2+A3+....+Am  mátrix (i,j)-ik eleme ¹ 0, ahol A a G gráf               szomszédsági mátrixa, m a csúcsok száma.

Példa

                     242d32c         ·v2                0 1 1                     242d32c    0 0 1                     242d32c      0 0 0

     v1·                     242d32c              A=  0 0 1             A2=   0 0 0                A3=   0 0 0

                     242d32c         ·v3                0 0 0                     242d32c    0 0 0                     242d32c      0 0 0

                     242d32c         0 1 2                     242d32c                      242d32c                     0 1 1    Nem minden elem

B2=A+A2+A3=    0 0 1         Összesen kétféle módon     P=   0 0 1    egyenlő 1-gyel Þ

                     242d32c         0 0 0         juthatok el v1-ből v3-ba!            0 0 0    nem szorosan összefüggő!

Warshall - algoritmus

Cél: G mátrix esetén P útmátrix meghatározása.

Az algoritmus:   1. P:=A

                     242d32c         2. FOR K=1 TO M

                     242d32c                     3. FOR I=1 TO M

                     242d32c                     4. FOR J=1 TO M

                     242d32c                     P(i,j) := P(i,j) vagy (P(i,k) és P(k,j))

Példa    Előző

              0 1 1                     242d32c           0 1 1                     242d32c      0 1 1                     242d32c      0 1 1

       P:= 0 0 1 =A              P1=    0 0 1                P2=    0 0 1                P3=    0 0 1

              0 0 0                     242d32c           0 0 0                     242d32c      0 0 0                     242d32c      0 0 0

Legrövidebb út algoritmus

(Ez az algoritmus egy módosított Warshall-algoritmus)

G súlyozott irányított gráf,  W:=(wij) súlymátrix  [wij = 0, ha nem létezik vi®vj él]

Cél: Q=(qij) mátrix megkeresése, ahol q(i,j) az vi®vj legrövidebb út hossza.

Jelölés:    Pk(i,j):=1, ha létezik vi®vj út csak v1, v2, ... ,vk csúcsokat tartalmazza, és Pk(i,j):=0 különben.

Megjegyzés: P0(i,j)=1, ha létezik vi®vj él, azaz P0=A szomszédsági mátrix. Továbbá Pm=P                      242d32c     útmátrix.

Állítás:    Pk(i,j) = 1, ha

                     242d32c     - vagy Pk-1(i,j) = 1

                     242d32c     - vagy Pk-1(i,j) = 1 és Pk-1(k,j) = 1                     242d32c            vk

                     242d32c     - vagy                      242d32c                      242d32c vagy                     242d32c      ·

                   vi·                     242d32c     ·vj                     242d32c              vi·                     242d32c                      242d32c    ·vj

                     242d32c                      242d32c         v1, ... ,vk-1 csúcsokat tartalmazó út

Azaz Pk(i,j) = Pk-1(i,j) vagy (Pk-1(i,k) és Pk-1(k,j)), ahol:

                   és    0     1                     242d32c                      242d32c            vagy   0     1

                   0     0     0                     242d32c                      242d32c               0      0     1

                   1     0     1                     242d32c                      242d32c               1      1     1

Jelölés:    Qk(i,j) := min(Qk-1(i,j));Qk-1(i,k)+Qk-1(k,j))

                 v1,...,vk-1 csúcsokat felhasználó legrövidebb út hossza

Az algoritmus:   1. Q(i,j):=W(i,j), ha W(i,j) ¹ 0  és  Q(i,j):= ¥ különben

                     242d32c         2. For K:=1 to M

                     242d32c              3. For I:=1 to M

                     242d32c                   4. For J:=1 to M

                     242d32c                      242d32c    Q(i,j):= min(Q(i,j);Q(i,k)+Q(k,j))

Példa

                 1     ·v2                     242d32c              0 1 4                     242d32c                  ¥   1  4

     v1·                2                     242d32c       W= 0 0 2                     242d32c      1.  Q=  ¥   ¥ 2

                 4     ·v3                     242d32c              0 0 0                     242d32c                  ¥   ¥ ¥

         ¥   1     4                     242d32c                  ¥   1     3                     242d32c           ¥   1   3

     2. ¥   ¥     2                     242d32c             3. ¥   ¥     2                     242d32c    4.    ¥   ¥  2



         ¥   ¥    ¥                     242d32c                 ¥   ¥    ¥                     242d32c          ¥   ¥  ¥

               v1                     242d32c                      242d32c       v1, v2                     242d32c              v1, v2, v3

Gráfok megvalósítása kapcsolt adatszerkezettel

Példa              v2

                     242d32c     ·                     242d32c                      242d32c      Csúcs     Szomszédsági lista

                     242d32c                      242d32c                      242d32c               v1        v2, v3, v4

         v1·                     242d32c       ·v3                     242d32c          v2        v3

                     242d32c                      242d32c                      242d32c               v3        v4

                     242d32c            ·v4                     242d32c                   v4

A kapcsolt adatszerkezet:

   Start                     242d32c   Csúcslista                     242d32c     Éllista

      ·                     242d32c         v1     ·     ·                     242d32c   ·     ·                 ·     ·                 ·    Æ


                     242d32c                 v2     ·     ·                     242d32c   ·     Æ


                     242d32c                 v3     ·     ·                     242d32c   ·     Æ


                     242d32c                 v4    Æ    Æ

Gráfok bejárása

Keresztirányú keresés:

              1. A kiindulópontot vizsgáljuk

              2. A szomszédjait vizsgáljuk

              3. A szomszédok szomszédjait, stb.

              Megvalósítás: sor segítségével.

Jelölés:           Egy csomópont státusza (ST) lehet

              ¾  1 - készenléti állapot (még nem vizsgált)

              ¾  2 - várakozó állapot (a sorban van)

              ¾  3 - feldolgozott állapot

Az algoritmus:

              1. Minden pont státusza legyen 1.

              2. A kiindulópont (A) elhelyezése a sorban ST(A):=2.

              3. Ismétlés, amíg a sor üres nem lesz:

                   4. A sor első elemének (N) eltávolítása, N feldolgozása, ST(N):=3.

                   5. N készenléti állapotú szomszédainak hozzácsatolása a sorhoz, státuszuk 2-re

                     242d32c      változtatása.

Megjegyzés: Ha maradnak feldolgozandó pontok, melyek A-ból nem érhetők el, egy ilyen                      242d32c     ponttal újra kell kezdeni az algoritmust.

Példa

                     242d32c                      242d32c                  A sor alakulása: ST(v1, v2, v3):=

                     242d32c              ·  v2

     v1·                     242d32c                      242d32c                 ¬     v1      ¬          ST(v1):=2

                     242d32c              · v3                  ¬     v2      v3      ¬          ST(v1):=3    ST(v2,v3):=2

                   v4 ·

                     242d32c                      242d32c                      242d32c       ¬     v3      ¬          ST(v2):=3

                     242d32c                      242d32c                      242d32c       ¬     v4      ¬          ST(v3):=3



                     242d32c                      242d32c                      242d32c       ¬               ¬          ST(v4):=3

Hosszirányú keresés:

              1. A kiindulópont feldolgozása.

              2. A-ból kiinduló egy P út teljes feldolgozása.

              3. Visszalépés P-n

              (Hasonlít a bináris fa inorder bejárásához.)

              Megvalósítás: veremmel

Az algoritmus:

              1. Minden csomópont státusza legyen 1.

              2. A kiindulópont (A) ráhelyezése a veremre, ST(A) :=2.

              3. Ismétlés, amíg a verem ki nem ürül.

                   4. A verem felső elemének (N) leemelése, N feldolgozása, ST(N):=3.

                   5. N készenléti állapotú szomszédainak ráhelyezése a veremre, státuszuk legyen 2.

Példa

                     242d32c                      242d32c                  ST(v1, ... ,v5):=1

                     242d32c              ·  v5            1.                     242d32c                     2.   

     v1·                     242d32c                      242d32c     v1        ST(v1) :=2             v5             ST(v1):=3

                     242d32c                      242d32c                      242d32c                      242d32c                  v4             ST(v3,v4,v5):=2

                     242d32c              · v4                     242d32c                      242d32c                      242d32c                      242d32c                 v3

            v2·       · v3

3.                     242d32c             4.                     242d32c                5.                     242d32c                  6.

       v4    ST(v5):=3                   ST(v4):=3                     242d32c   ST(v3):=3                     242d32c     ST(v2):=3

       v3                     242d32c             v3                     242d32c              v2

Gráfok topológiai rendezése

T.f.h. G gráf nem tartalmaz kört

Definiáljuk az alábbi a relációt: u < v, ha létezik u®v út.

Állítás: a részleges rendezési reláció:

Ui.:        1. Minden v csomópontra v ³ v  (nem reflexív)

              2. Ha u<v, akkor v ³ u  (assszimetrikus)

              3. Ha u<v és v<w, akkor u<w  (tranzitív)

Def.:           G gráf  topológiai rendezése G csúcsainak olyan lineáris sorbarendezése, melyre,       ha létezik v®u út G-ben azaz v<u, akkor v megelőzi u-t a sorban.

Példa                     242d32c         A

                     242d32c                   ·                     242d32c                      242d32c      Két topológiai rendezése a gráfnak:

         G·                     242d32c                      242d32c                      242d32c            B D G A F E C

                     242d32c         ·F               E ·              ·C              vagy

     B·                     242d32c                      242d32c                      242d32c                 E G B A D F C

                     242d32c                   ·

                     242d32c                   D

Tétel: G véges irányított gráf, mely nem tartalmaz köröket. Ekkor G-nek létezik topológiai             rendezése.

Jelölés: BE(N) : N csúcs éppen aktuális be-fokának tárolása.

Cél: G topológiai rendezése.

Megvalósítás: sor segítségével.

              1. Zérus be-fokú pont megkeresése.

              2. N és a hozzá tartozó élek törlése a gráfból.

Az algoritmus:

              1. A G gráf minden pontjának be-fokának meghatározása.

              2. A zérus be-fokú pontok elhelyezése a sorban.

              3. Ismétlés, míg a sor üres nem lesz.

                     242d32c 4. Sor első elemének eltávolítása (N).

                     242d32c 5. Az N pont minden M szomszédjára: BE(M):=BE(M)-1

                     242d32c Ha BE(M)=0, M hozzácsatlakozik a sorhoz.

Példa

                     242d32c         ·B                     242d32c          A sor alakulása: BE(A):=0   BE(B):=1

A·                     242d32c                      242d32c                      242d32c                      242d32c      BE(C):=1  BE(D):=2

                     242d32c                   ·C

                     242d32c         · D

                   1.,     ¬     A       ¬

A                2.,     ¬               ¬               BE(B):=1-1=0   BE(C):=1-1=0

                   3.,     ¬     B      C       ¬

AB              4.,     ¬     C       ¬               BE(D):=2-1=1

ABC           5.,     ¬               ¬               BE(D):=1-1=0

                   6.,     ¬     D       ¬

ABCD        7.,     ¬               ¬

a topológiai rendezés


: 1016