online kép - Fájl  tubefájl feltöltés file feltöltés - adja hozzá a fájlokat onlinefedezze fel a legújabb online dokumentumokKapcsolat
  
 

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
  

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

számítógépes



Fájl küldése e-mail



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



: 1553