Informatikai Alkalmazások Mőszaki menedzser szak. Galambos Gábor SZTE Az anyag elsajátításához szükséges ismeretek

Az anyag elsajátításához szükséges ismeretek

Informatikai Alkalmazások Mőszaki menedzser szak

Mátrixok, mőveletek mátrixokkal. (Matematika III.) Lineáris algebra alapjai: lineáris függetlenség, n-dimenziós vektortér, vektorok elıállítása, bázis.( Matematika II.) Lineáris egyenletrendszerek megoldásai. (Matematika III.)

http://jgypk.u-szeged.hu/tanszek/szamtech/oktatas/Infalk.pdf

Galambos Gábor SZTE 2012-2013 Informatikai Alkalmazások

1

Informatikai Alkalmazások

2

1

Ajánlott irodalom

A feldolgozott témák

Operációkutatás I. (Szerk.: Dr. Tóth Irén) Matematika közgazdászoknak. Nemzeti Tankönyvkiadó, Bp. 2003. Operációkutatás II. (Szerk.: Dr. Csernyák László) Matematika Közgazdászoknak. Nemzeti Tankönyvkiadó, Bp. 2003., Operációkutatás elmélet és példatár I. - II. kötet. (Szerk.: Dr. Felber Mária) Fıiskolai jegyzet, BGF KVIFK, Bp. 2004 Dr. Csernyák László – Dr . Jánosa András: A gazdasági optimalizálás módszerei II. . Nemzeti Tankönyvkiadó (42612) Bp. 2004.

Az optimumszámítás alapfogalmai Célfüggvénnyel bıvített lineáris egyenlıtlenségrendszerek és grafikus megoldásaik. A hozzárendelési feladat A szállítási feladat Gráfokkal megoldható feladatok


3


4

2

Optimumszámítási modellek

Készítsük el a feladathoz tartozó matematikai modellt. Vezessük be a következı jelöléseket:

Vizsgáljuk meg a következı feladatot: Egy gyárnak kétféle félkész termékbıl (vascsıbıl és bútorlapból) háromféle iskolapadot kell elıállítani. Az ismert, hogy az egyes késztermékek egy-egy darabjában mennyi a felhasználandó félkész termék. Az is tudott, hogy a félkész termékekbıl mennyi raktárkészlet van. A gyár gazdasági vezetése ismeri az egyes késztermékek eladási hasznát darabonként. Kérdés: Mennyi készterméket állítsanak elı az egyes iskolapadokból, ha a cél a profit maximalizálása?

F1, F2

Nyersanyagok

K1 , K2 , K3

Késztermékek

aij

Az i. nyersanyag mennyisége a j. késztermék egységnyi mennyiségében

bi

Az i. félkésztermékbıl rendelkezésre álló mennyiség

ci

Egységnyi i. késztermék eladásából származó haszon

Jelölje továbbá x1, x2, x3 az egyes késztermékekbıl gyártandó mennyiségeket. Informatikai Alkalmazások

5


6

3

Ha x1, x2, x3 az egyes késztermékekbıl gyártandó mennyiségek, akkor az F1 félkésztermékbıl összesen

A gyakorlati problémánkhoz rendelt matematikai modell tehát: feltételrendszer

mennyiséget használunk el. Hasonló meggondolás alapján az F2 félkésztermékbıl elhasznál mennyiségek: Ezekrıl a rendelkezésre álló raktárkészlet „véges” volta miatt tudjuk, hogy

célfüggvény

Mivel c1, c2, c3 az egyes késztermékek egységnyi eladásából származó haszon, ezért a cél

Ilyen típusú feladatok megoldása során a következı lépéseket hajtjuk végre: probléma feltárás matematikai (optimumszámítási) modell felállítása megoldó algoritmus kidolgozása



7

8

4

Az optimumszámítási modellek osztályozása:

Térjünk vissza a bevezetı feladathoz:

Tevékenységek típusa alapján folytonos diszkrét vegyes és vezessük be a következı jelöléseket: A modellben szereplı paraméterek alapján determinisztikus sztochasztikus A feltételek és a célfüggvény alapján lineáris nem lineáris

Ekkor a feladat mátrix alakba is felírható:


9


10

5

Grafikus megoldás kétdimenziós esetben 2

2

x1 + x2 ≤ 6 x1 ≤4

3

-x1 + x2 ≤ 4

1

Vizsgáljuk meg a különbözı megoldásokat:

x1, x2 ≥ 0

-x1 - 2x2 =z(x) → min

6

z(x)=-8

A z(x)= -11 egyenes egyenletét egyetlen pont elégíti ki. Nincs olyan x∈L, amely kielégítené a z(x)<-11 egyenlıtlenséget. Az optimum egyértelmő.

4

z(x)=-4 2

3

z(x)=-11

L

2

4

6

Az optimális megoldás: x1=1 x2=5 z(x)=-11

8

Tekintsük pl. a –x1 -2x2 = -4 egyenest. Több olyan pont is van az L-ben, amely kielégíti egy adott egyenes egyenletét.

Mi

a helyzet, ha a célfüggvény 1 párhuzamos egyenlettel? Több optimális megoldás van.

az

z(x)=0 1 Informatikai Alkalmazások

11


12

6

Grafikus megoldás háromdimenziós esetben

Két dimenzióra visszavezethetı háromdimenziós eset 1 2 3 4

x1 + x2 – x3 ≤ 7 x1 – x2 + 3x3 ≤ 4 -x1 + x2 + 2x3 ≤ 4 -x1 + x2 + x3 = 2 x1, x2, x3 ≥ 0

x3

1 2

6

x2 5

4

-x1 - 2x2 – 5x3 = z(x) → min Ilyen esetben úgy járunk el, hogy az egyenlıséget tartalmazó feltételbıl kifejezzük az egyik változót, azt behelyettesítjük a többi egyenletbe, a kapott kétváltozós feladatot megoldjuk, a végén még meghatározzuk a kifejezett változó értékét, és a három változóval meghatározzuk a célfüggvény értékét is. Informatikai Alkalmazások

13

x1+2x2+ x3 ≤ 4 x1 – x2+2x3 ≤ 5 xi ≥ 0 _____________________ -3x1 – x2 – x3= z(x)→min

3

Az optimális megoldás: x1=4 x2=0 x3=0 z(x)=-12

2 4 3 1 2 1

1

2

3

4

5

6


7

8

x1

14

7

A lineáris programozás általános feladata:

Az (x1, x2, …,xm) vektort a lineáris programozási (LP) feladat lehetséges megoldásának nevezzük, ha a vektor a feltételrendszer minden egyenlıtlenségét kielégíti.

≤

Két lineáris programozási feladatot ekvivalensnek nevezünk, ha a két feladat lehetséges megoldásainak a halmaza megegyezik, a célfüggvények értékei a lehetséges megoldások halmazán egyenlıek.

=

≥


15


16

8

Egy standard feladatot lehetséges kanonikus alakúnak nevezzük, ha sor- és oszlopcserékkel, valamint a változók átjelölésével az alábbi alakra hozható:

Szimplex algoritmus Az

alakú lineáris programozási feladatot standard feladatnak nevezzük. Tétel: Bármely LP átalakítható standard feladattá úgy, hogy a kiinduló LP és a származtatott standard feladat ekvivalensek lesznek, továbbá a két feladat optimális megoldásai egyidejőleg léteznek, és ezek közvetlenül származtathatók egymásból. Következmény: Elegendı standard feladatok megoldásával foglalkozni. Informatikai Alkalmazások

Megjegyzés: A lehetséges kanonikus alakú feladatnál a feltételek is elıírtak!

17


18

9

A lehetséges kanonikus alakú feladat tehát egy olyan speciális standard LP, amelyben

Ha valamely 1 ≤ i ≤ n értékre beszélünk.

, akkor degenerált bázisról

a feltételrendszer mátrixában van egy n-dimenziós egységmátrix, az egységmátrix alatti célfüggvény együtthatók értéke zérus.

Vegyük észre, hogy az bázisváltozóhoz az együtthatómátrixban az n-dimenziós vektortér i-dik egységvektora tartozik.

Tétel: Egy lehetséges kanonikus alakú feladathoz mindig megadható egy triviális megoldás.

Tétel: Egy lehetséges kanonikus alakú feladat bázismegoldásához tartozó célfüggvényérték . Biz.

Biz. Legyen az

A célfüggvény értéke:

egy olyan n+m dimenziós vektor, amelyre: (i = 1,2,…,n)

és

(t = 1,2,…,m)

A feladathoz tartozó triviális megoldást bázismegoldásnak nevezzük, és az (i = 1,2,…,n) változók a bázisváltozók. Informatikai Alkalmazások

19

Itt az elsı összeg azért egyenlı nullával, mert minden ci értéke nulla, a második összeg pedig azért, mert minden xi értéke nulla. Így


20

10

Tétel (Optimum kritérium): Egy lehetséges kanonikus alakú feladat bázismegoldása egyben optimális megoldás is, ha cn+t ≥ 0

Tétel (Bázisváltoztatás tétele): Ha egy lehetséges kanonikus alakú feladat célfüggvényében van egy olyan j index, amelyre n+1 ≤ j ≤ n+m, amelyre cj < 0, és létezik a

teljesül minden t = 1, 2, …, m értékre. Biz. Elegendı azt belátni, hogy ha X egy lehetséges megoldás, akkor z(X) ≥ α. Mivel X lehetséges megoldás, ezért X ≥ 0. De ekkor minden koordinátájára igaz, hogy xi ≥ 0, i = 1, 2, …, n+m. A feltétel szerint cn+t ≥ 0, minden t = 1, 2, …, m értékre. Ezért

mennyiség, akkor megadható egy olyan – az eredeti feladattal ekvivalens másik lehetséges kanonikus alakú feladat, amelynek X* bázismegoldására teljesül A tételt nem bizonyítjuk, de megadjuk a konstrukciót, amely a tétel bizonyításához vezet.


21


22

11

Jelölje si a lehetséges kanonikus alakú feladat i. sorát, és a származtatott feladat i. sorát. Hasonlóan jelölje z és a két feladat célfüggvényeit. Tegyük fel, hogy a tétel feltétele teljesül, és a minimum a k. sorban lévı elemre (is) fennáll. Ekkor az új feladatot a következıképpen konstruáljuk:

Határozzuk meg a következı LP optimális megoldását szimplex algoritmussal: 3

-x1 + 2x2 ≤ 4 3x1 + x2 ≤ 5

1

1

2

x1, x2 ≥ 0

-x1 - x2 =z(x) → min

2

1

Az átalakítás során akj-t generáló elemnek, az k. sort pedig a generáló elem sorának nevezzük. Informatikai Alkalmazások

23

1

2

2


3

24

12

Használjuk a „klasszikus“ bázistranszformációkat:

u1

u2

x1

x2

1 0

0 1

-1 3

0

0

-1

x2 u2

x1

Hogyan lehet áttérni a szimplex táblára?

u1

u2

x1

x2

2 1

b 4 5

½ -½

0 -½ 1 7/2

1 0

b 2 3

-1

0

½

0 - 3/2

0

2

u1

1 0

0 -½ ½ 1 7/2 -½

0

0

- 3/2 ½

b 2 3 2

x2 u2

x1

u1

b

3/7

1 1/7 0 2/7

0 1 -1/7

17/7

0

0

2/7

23/7

3/7

6/7

A megoldás: x1=6/7, x2=17/7 z(x)=-23/7. Informatikai Alkalmazások

25

x2

u2

x1

u1

1 0

0 -½ ½ 1 7/2 -½

b 2 3

0

0

- 3/2 ½

2

x2 u2

x1

u1

-½

½

7/2 -½

b 2 3

- 3/2 ½

2

Ha jól számolunk, akkor az egységmátrix mindig megjelenik a táblázatban. Ezeket nem kell kiszámítani, elhagyhatjuk a táblázatból. Helyezzük át ezeket a változókat a táblázat elsı oszlopába az egységvektoruknak megfelelı pozícióba. Az elemek transzformációja ennek megfelılen változik. Informatikai Alkalmazások

26

13

Az algoritmus:

x1 x2 u2

u1

½ 7/2 -½

b 2 3

- 3/2 ½

2

-½

x2 x1

u2

u1

b

1/7

3/7

17/7

2/7

-1/7

6/7

3/7

2/7

Probléma: A bázistranszformáció feltételeként beállított

23/7

A bázisba a generáló elem oszlopában lévı változó kerül be a g.e. sorában levı bázisváltozó helyére. Legyen a generáló elem akj. Ekkor a´kj=1/akj a´ij = – aij a´kj , ha i ≠ j,

érték csak akkor létezik, ha a generáló oszlopban van pozitív együttható. Tétel (Optimum nemlétezésének kritériuma): Ha lehetséges kanonikus alakú feladatban valamely n+1 ≤ j ≤ n+m indexre cj < 0, és az arj ( r = 1, 2, …, n) elemek egyike sem pozitív, akkor a feladat célfüggvénye alulról nem korlátos a lehetséges megoldások halmazán.

a´ki = aki a´kj , ha i ≠ j, a´it = ait – aij a´kt , ha i ≠ j és t ≠ k. Informatikai Alkalmazások

27


28

14

A standard feladat általános megoldása bonyolultabb, mivel a kiinduló bázismegoldás nem áll rendelkezésünkre.

Hozzárendelési feladat

Tovább bonyolódik a helyzet, ha nem folytonos feladatról, hanem egész értékő feladatról van szó:

Adott n számú dolgozó és n különbözı munka. A dolgozók a munkákat különbözı költségekkel végzik el. Osszuk szét a dolgozók között a munkákat úgy, hogy minden dolgozó pontosan egy munkát kapjon, és a munkavégzés költsége minimális legyen!

5

4

n

A dolgozók száma

cij

A j. munka elvégzésének költsége, ha azt az i. dolgozó hajtja végre. (1 ≤ i,j ≤ n)

3

2

1, ha az i. dolgozó végzi a j. munkát 1

xij 0, különben 1

2

3

4


29


30

15

Megoldható a feladat?

A matematikai modell

A megoldást mindig egy olyan nµn-es bináris mátrix szolgáltatja, amelynek minden sorában és minden oszlopában egy – és csak egy – 1-es van.

i = 1, 2, …, n

Példa: 4µ4-es esetben legyen a költségmátrix Egy lehetséges megoldás:

j = 1, 2, …, n 1 ≤ i ≤ n, 1 ≤ j ≤ n


31


32

16

Következmény-1: Egy hozzárendelési feladatnak (HF) mindig van lehetséges megoldása. Következmény-2: Egy HF lehetséges megoldásainak halmaza csak ntıl függ, a költségmátrix értékétıl a a lehetséges megoldások halmaza független. Következmény-3: Egy HF-nak n! különbözı lehetséges megoldása van. Következmény-4: Különbözı célfüggvényő (de azonos n-hez tartozó) HF-hoz tartozó lehetséges megoldások halmaza megegyezik. Ezért a HF-t meghatározza a C = {cij} költségmátrix. Jelölése: H(C).

A Cnµm és Dnµm mátrixokat ekvivalensnek mondunk, ha léteznek olyan α1, α2, …, αn, és β1, β2, …, β m konstansok, amelyekre cij = dij + αi + βj minden 1 ≤ i ≤ n, 1 ≤ j ≤ n értékre. Jelölése: C ~ D. Tétel (Mátrixok ekvivalenciája): Ha C és D nµn-es költségmátrixok, és C ~ D, akkor H(C) és H(D) optimális megoldásai megegyeznek. Biz. Legyen zC és zD a két célfüggvény, és legyen megoldás.

egy tetszıleges

Megmutatjuk, hogy létezik egy olyan γ konstans, amelyre

Következmény-5: Egy HF optimális megoldását mindig meghatározhatjuk, ha végigpróbáljuk az összes lehetséges megoldást, és kiválasztjuk azt, amelyhez a minimális célfüggvényérték tartozik. Informatikai Alkalmazások

33


34

17

Egy mátrix 0 elemeinek egy rendszerét független 0 rendszernek nevezzük, ha a mátrix minden sora és minden oszlopa legfeljebb egy elemet tartalmaz a rendszerbıl. (Elemeit 0*-gal jelöljük.) Tekintsük azt az eljárást, amely elıállít egy olyan C(0), C(1), …, C(k) mátrixsorozatot (k ≤ n), amelyre teljesül, hogy (1) C ~ C(0) (2) C(t) ~ C(t+1), t = 0, 1, 2, …, k-1 1

1

(3) C(t) ≥ 0, (4)

C(k)

t = 0, 1, 2, …, k

–ban ki van jelölve egy n elemő független 0 rendszer.

γ Informatikai Alkalmazások

35


36

18

Magyar módszer

Tétel: Tegyük fel, hogy van egy ilyen mátrixsorozatunk. Legyen egy olyan nµn-es mátrix, amelyre teljesül, hogy

Jelölje || 0* || a kijelölt független 0 rendszer elemeinek a számát. Elıkészítı rész (Egy független 0 rendszer elıállítása):

Ekkor

Vonjuk ki a sorminimumokat a sorokból

optimális megoldása H(C)-nek.

Vonjuk ki az oszlopminimumokat az oszlopokból.

Biz.

Így megkapunk egy C(0) mátrixot.

lehetséges megoldás (4) miatt. optimális megoldása H(C(k))-nak, mert zk( ) = 0, és (3) miatt, és bármely X lehetséges megoldásra zk(X ) ≥ 0. •

(1) és (2) valamint az ekvivalencia tranzitivitása miatt C ~ C(k).

Jelöljünk ki C(0)-ban egy független 0 rendszert. Egy mátrix egy elemét szabad elemnek nevezzük, ha nincs jellel ellátva, és sem a sora sem az oszlopa nincs lekötve.

optimális megoldása H(C)-nek is. Informatikai Alkalmazások

37


38

19

r=0

||0*|| = n

i

VÉGE

Példa: Oldjuk meg a következı hozzárendelési feladatot!

Kössük le a 0* oszlopait Van szabad 0 elem? Jelöljük meg '-vel a szabad 0-t 0' sora tartalmaz 0*-t? 0' sorát kössük le, 0* oszlopát oldjuk fel r=r+1

A szabad elemek minimumát levonjuk a szabad elemekbıl, és hozzáadjuk a kétszeresen kötött elemekhez. Láncképzés:0’oszlopában 0*, 0* sorában 0’. (Jel.: L) C(r+1) elemei: Jelölések nélküli C(r) megjelölése *-gal, ha -

és

-

és


39


40

20

Jelöljük ki a független 0 rendszert oszlopfolytonosan: *

Keressünk sorfolytonosan szabad 0-t! Ez a c35 elem lesz. Mivel a harmadik sor tartalmaz 0* elemet, ezért a c35 elemet ellátjuk '-vel, a sort lekötjük, a sorában levı 0* oszlopát pedig feloldjuk: + + + + * ' +

* * * Kössük le a 0*-k oszlopait!

* ' +

* '

+ + + + *

+

*

* Most a c41 lesz az elsı szabad 0, a negyedik sort lekötjük és a negyedik oszlopot kell feloldani. Keresve szabad 0-t azt kapjuk, hogy a c14 lesz az elsı szabad 0, az elsı sort le kell kötni és a harmadik oszlopot kell feloldani.

* * Informatikai Alkalmazások

41


42

21

Szabad 0-t keresve most azt látjuk, hogy nincs ilyen elem. Mivel a független 0 rendszerünk csak 4 elemet tartalmaz, ezért – az ekvivalencia tétel felhasználásával – „gyártani” kell szabad 0-t: A szabad elemek minimuma most 1. + + + + * '

'

+

*

+

*

* * '

Most már ismét kereshetünk szabad 0-t. Ez a c21 elem lesz. Ennek sora tartalmaz 0* elemet, ezért a c21 elemet ellátjuk '-vel, a sorát lekötjük, és a harmadik oszlopot feloldjuk: + * ' +

*

' + +

'

Vonjuk le az 1-t a szabad elemekbıl, és adjuk hozzá a kétszer kötött elemekhez: Informatikai Alkalmazások

43

*

' + +

Ismét szabad 0-t keresve, c51 lesz az elsı szabad 0, de a sora nem tartalmaz 0* elemet, ezért a láncképzés indul be: Informatikai Alkalmazások

44

22

C (0)

2  0 =  0*   0'  ' 0

4 0* 0' 1   0* 0 0 1  1 0 1 0' 3 0 0* 2   0 0 2 1

+ + +

C

+

Most törölve a jelöléseket, és ”*”-gal ellátva a láncon kívüli 0* elemeket, valamint ”*”-gal ellátva a láncon belüli 0' elemeket, megkapjuk a a C(1) mátrixot.


(1)

2  0 = 0  0  * 0

4 0* 0 1   0* 0 0 1  1 0 1 0* 3 0 0* 2   0 0 2 1

Mivel C(1)-ben 5 elemő a független 0 rendszer, ezért az eljárás véget ér. Most már csak az X megoldásmátrix elıállítása van hátra:

45


46

23

Szállítási feladat

Ez a k ép most nem jeleníthetı meg.

0  0 0 = X  0  1

0 1 0 0  1 0 0 0 0 0 0 1  0 0 1 0  0 0 0 0

Adottak feladóhelyek (raktárak), amelyekben azonos árú áll rendelkezésre különbözı mennyiségben. Adottak továbbá felvevıhelyek (igények), amelyekben elıírt mennyiségekben árúra van szükség. Szállítsuk el a raktárakban levı árút a felvevıhelyekre úgy, hogy a szállítási költségek összege minimális legyen.

Ezért a célfüggvény értéke:


47

n

A dolgozók száma

ai

Az i. raktárban lévı árumennyiség. (i = 1,2,…,n)

m

Az igények száma

cij

Egységnyi anyagmennyiség szállítási költsége az i. raktárból a j. felvevıhelyre. (1 ≤ i ≤ n, 1 ≤ j ≤ m)

xij

Az i. raktárból a j. felvevıhelyre szállítandó árumenynyiség. (1 ≤ i ≤ n, 1 ≤ j ≤ m) Informatikai Alkalmazások

48

24

Megoldható a feladat?

A matematikai modell

Tétel (Egyensúlyi feltétel): A szállítási feadatnak akkor és csak akkor létezik optimális megoldása, ha

i = 1, 2, …, n

és j = 1, 2, …, m A korábbiakból látható, hogy egy szállítási feladatot meghatározza az a és b vektor, valamint a C költségmátrix. Jelöljük az így meghatározott szállítási feladatot S(a, b, C)-vel.

1 ≤ i ≤ n, 1 ≤ j ≤ m

Tétel: Ha a C és D mátrixok ekvivalensek, akkor az S(a, b, C) és S(a, b, D) feladatok optimális megoldásai megegyeznek. A következıkben feltételezzük, hogy az a, b, C elemei egész számok. Informatikai Alkalmazások

49


50

25

Tétel: A bemutatott eljárás feltételeit kielégítı mátrixsorozat esetén X(k) optimális megoldása az S(a, b, C) szállítási feladatnak. Biz:

Tekintsük a következı eljárást (Ford-Fulkerson, 1956): Elıállítunk egy olyan mátrixsorozatot, amelyre

∆t definíciója miatt, és a (4), (5), (8) feltételek teljesülése miatt ahol Lk az S(a, b, C(k)) szállítási feladat lehetséges megoldásainak a halmaza.

(1) C ~ C(0) (2) C(t) ~ C(t+1), t = 0, 1, 2, …, k-1 (3) C(t) ≥ 0,

t = 0, 1, 2, …, k

Ha zk az S(a, b, C(k)) célfüggvénye, akkor (6) miatt

(4) X(t) ≥ 0, és X(t) egész, t = 0, 1, 2, …, k (5) Ha 0 ≤ t ≤ k, akkor (6) Bármely 1 ≤ i ≤ n, 1 ≤ j ≤ m, 1 ≤ t ≤ k indexháromasra következik, hogy (7) Ha

akkor

.

(3) miatt bármely lehetséges megoldásra zk(X) ≥ 0, ezért X(k) optimális megoldása S(a, b, C(k))-nak.

-ból

(1), (2) és az ekvivalencia tranzitivitása miatt C ~ C(k). Ezért X(k) optimális megoldása S(a, b, C)-nek is.

bármely 0 ≤ t < k.

(8) ∆k = 0. Informatikai Alkalmazások

51


52

26

Hogyan lehet az (1) – (8) feltételeket kielégítı mátrixpár-sorozatot elıállítani? Ford – Fulkerson (1956): A hozzárendelési feladatra kidolgozott gondolatmenet alapján megalkotta a magyar módszert a szállítási feladat megoldására.

r=0

Paraméterek kiszámítása ∆r = 0

i

VÉGE

Ekvivalencia lépés

Van szabad 0 elem? i. sorban

Elıkészítı rész: C(0)-ban 0 elemek elıállítása sorminimumok és oszlopminimumok segítségével. X(0) elıállítása (mohó algoritmus segítségével)


53

Jelöljük meg '-vel a szabad 0-t Láncképzés kössük le az i. sort. ha és és az s. oszlop le van kötve, akkor oldjuk fel az s. oszlopot, és jelöljük *-gal.Informatikai Alkalmazások

r=r+1

54

27

Paraméterek kiszámítása:

Példa: Oldjuk Meg a következı S(a,b, C) szállítási feladatot!

Ekvivalencia-lépés: A szabad elemek minimumát levonjuk a szabad elemekbıl, és hozzáadjuk a kétszeresen kötött elemekhez. Láncképzés: 0’ oszlopában 0*, 0* sorában 0’ választása.

Elıször az elıkészítı részben – a sorminimumok és az oszlopminimumok segítségével – kiszámítjuk C(0)-t: 0 3 0 0 0   X (0) =  0 0 2 0 2  2 1 0 0 0   Most C(0) alapján megkonstruáljuk az X(0) mátrixot:


55


56

28

Mivel az iterációs részben mindig mátrixpárral dolgozunk, ezért a továbbiakban ezeket adjuk meg. + + + + 0 3 0 0 0   (0) = X  0 0 2 0 2 2 1 0 0 0   Következik a paraméterek kiszámítása: Ezért az oszloplekötésekkel folytatódik az eljárás. Ehhez ki kell számolnunk a a szükségletek és a szállítandó mennyiségek eltéréseit a

Most – az algoritmus szerint – sorfolytonosan keresünk szabad 0-t. Az elsı szabad 0 elem . Megvizsgálva X(0) elsı sorára a készlet és a szállítandó mennyiségek eltérését, kapjuk, hogy azaz X(0) elsı sorára teljesül a szállítás. Ellátjuk vesszıvel a elemet, lekötjük a sorát, a sorában megvizsgáljuk az elemeket. Azt látjuk, hogy és C(0) második oszlopa le van kötve. Ezért ezt az oszlopot feloldjuk, és a elemet *-gal látjuk el: + + + *

'

+

+

képlet alapján. Kapjuk δ1 = δ2 = δ3 = δ5 = 0, ezért ezeket az oszlopokat lekötjük. Informatikai Alkalmazások

57

0 3 0 0 0   X (0) =  0 0 2 0 2  2 1 0 0 0  


58

29

Több ilyen elem nincs az elsı sorban. Ezért ismét szabad 0-t keresünk. Az elsı szabad elem lesz. Kiszámolva a különbséget kapjuk, hogy következik:

-t vesszıvel kell ellátni, és a láncképzési lépés

+ + + * '

'

Másrészt venni kell a lánc kezdı elemének sorindexét, és az X(0)-ban ehhez a sorhoz tartozó lehetséges növekményt: Ezután még venni kell a lánc befejezı elemének oszlopindexét (ez 4), és meg kell határozni az oszlopeltérést: Ezért Állítsuk elı a (C(1), X(1)) mátrix-párt:

+ +

+ + +

0 3 0 0 0   X ( 0) =  0 0 2 0 2  2 1 0 0 0  

+

0 2 0 1 0   X (1) =  0 0 2 0 2   2 2 0 0 0  

Most X(0) és a lánc alapján elkészítjük X(1)-t. Ehhez ki kell számítanunk Θ értékét. Ehhez elıször ρ értékét határozzuk meg, amely a láncba tartozó 0*-knak megfelelı x értékek minimuma. Most egyetlen ilyen elem van, ezért ρ = 3.

Mivel ∆1 = 1, ezért ismét oszloplekötésekkel folytatódik az eljárás. δ1= δ2= δ3= δ5= 0, ezért az indexeknek megfelelı oszlopokat lekötjük.



59

60

30

Sorfolytonosan az elsı szabad 0 elem. Mivel ezért -et ellátjuk vesszıvel, a sorát lekötjük, majd a C (1) második oszlopát feloldjuk, és -et ellátjuk *-gal. + + + *

'

+

+ X ( 1)

*

'

+

*

0 2 0 1 0   = 0 0 2 0 2 2 2 0 0 0  

Több elemet nem lehet ellátni *-gal ebben a sorban, ezért sorfolytonosan 0-t keresünk. Sorfolytonosan az elsı szabad elem. Mivel ezért -et ellátjuk vesszıvel, a sorát lekötjük, majd a C (1) elsı oszlopát feloldjuk, és -et ellátjuk *-gal. Mivel nincs szabad 0, ezért az ekvivalencia lépéssel folytatjuk az eljárást. Informatikai Alkalmazások

+ + + *

61

'

'

+

+ +

0 2 0 1 0   X (1) =  0 0 2 0 2  2 2 0 0 0  

Kössük le a sorokat és az oszlopokat. A szabad elemek minimuma 1, ezt kivonjuk a hozzáadjuk a kétszer kötött elemekhez: + + + + * ' 0 +  X ( 1) =  0 2 * ' + 

szabad elemekbıl és 2 0 1 0  0 2 0 2 2 0 0 0 


62

31

Ismét szabad 0-t keresve, lesz az elsı szabad 0. ezért az eljárás a láncképzéssel folytatódik. Lássuk el vel. + + + + * ' 0 2 0 +  (1) ' = X 0 0 2 2 2 0 * ' + 

Mivel -et vesszı1 0  0 2 0 0 

Képezzük most ∆2 –t. Azt kapjuk, hogy ∆2 = 0, ezért az eljárás véget ér. A feladat optimális megoldásához tartozó célfüggvényérték:

A C(1) negyedik oszlopában nincs 0*, ezért a lánc elfajuló, csak egyetlen elemet tartalmaz. Számoljuk ki most is elıször Θ-t. és ezért Θ = 1. Így a lánc alapján az X(1) mátrixnak csak a (2,4) indexő eleme változik meg.


0 2 0 1 0   X (2) =  0 0 2 1 2  2 2 0 0 0  

63

0 2 0 1 0   X (2) =  0 0 2 1 2   2 2 0 0 0  


64

32

A potenciálok módszere Tekintsük a következı szállítási feladatot: 5

K2

4

K3 Igény (b)

F3

F2

F1 K1

8

8 90

20

3

70

3

40

F4

4

10

3

6

20

4

7 40

Készlet (a) 40

80 70

8 30

50

40

200

Keressünk egy kiinduló megoldást a mohó algoritmussal!

v3 = 6

v4 = 5

v1 = 4

v2 = 3

u1 = -2

5

8

4

3

u2 = 0

4

3

6

4

80

u3 = 4

8

3

7

8

70

Igény (b)

Így az összes költség: 8·70 + 4 ·20 + 3 ·40 + 6 ·20 + 4 ·10 + 3 ·40 = 1040 Az összesen n + m -1 = 6 helyre allokáltunk szállítást. Informatikai Alkalmazások

Vezessük be segédváltozóként az ui és a vj potenciálokat, úgy, hogy a költségmátrixban szereplı a lekötött elemekre cij = ui+vj legyen. Írjuk ezeket a lekötött elemek oszlopa elé ill. sora fölé. A potenciálok közül egyet szabadon választhatunk meg. Legyen u2 = 0.

90

40

30

Készlet (a) 50

40

200

Számítsuk ki a nem lekötött relációkra a cij – (ui+vj) különbségeket: 65


66

33

c11 – (u1+v1) = 5 – (-2 + 4) = 3 c12 – (u1+v2) = 8 – (-2 + 3) = 7 c32 – (u3+v2) = 3 – (4 + 3) = -4 c33 – (u3+v3) = 7 – (4 + 6) = -3 c24 – (u2+v4) = 4 – (0 + 5) = -1 c34 – (u3+v4) = 8 – (4 + 5) = -1

elıjele elıjele elıjele elıjele elıjele elıjele

+ + – – – –

Miután több negatív különbséget is kaptunk, a program, vagyis a költség csökkenthetı, ha a negatív elıjelő relációk közül lekötünk. A legnegatívabb a T3→F2 viszonylat adódott, ennek lekötése csökkentené leginkább a költségeket.

Vizsgáljuk meg ezek után, hogy a nem lekötött relációk esetén hogyan alakul a cij – (ui+vj) különbség. Ha ez 0, ez azt jelenti, hogy annak relációnak a lekötése nem változtatna a költségeken. Ha ez a különbség pozitív, akkor ennek a relációnak a bevonása növelné a költségeket. Ha negatív, akkor ennek a relációnak a bevonása ncsökkentené a költségeket. Informatikai Alkalmazások

67

Ha ezt a viszonylatot lekötjük egy x mennyiséggel, akkor ez hiányozni fog az elıbbi lekötések közül. Vagyis át kell rendeznünk a korábbi elosztási rendet egy kör mentén. x értékét úgy kell megválasztani, hogy ezáltal egy addig kötött elemhez 0 mennyiség kerüljön, és így a kötöttsége megszőnjön. Pl. x = 40-t választva a T2→F2 reláció kötöttsége megszőnik.


68

34

v1 = 4

v2 = 3

u1 = -2

5

8

u2 = 0

4

2060+x

u3 = 4

8

30-x 70

Igény (b)

v3 = 6

v4 = 5

4

10

3

3 400-x

6

20

4

3

7

90

40 +x

Készlet (a)

40

50 80 70

8

40

200

40

30

Az új program költsége: 4 · 60 + 8 · 30 + 3 · 40 + 4 · 10 + 6 · 20 + 3 · 40 = 880. Tekintsük most az új helyzetet, és jelöljük be az új kötött relációkat.

Nézzük a további javítás lehetıségét: c11 – (u1 + v1) = 5 – (0 + 2) = 3 c12 – (u1 + v2) = 8 – (0 – 3) = 11 c23 – (u2 + v3) = 3 – (2 - 3) = 4 c33 – (u3 + v3) = 7 – (6 + 4) = -3 c24 – (u2 + v4) = 4 – (2 + 3) = -1 c34 – (u3 + v4) = 8 – (6 + 3) = -1

az elıjel az elıjel az elıjel az elıjel az elıjel az elıjel

+ + + – – –

A program ugyan jobb lett, mint korábban, a szállítási költség kevesebb, de mivel még vannak negatív különbségek, ezért tovább javítható. Most a legnagyobb javítást a T3→F3 reláció bevonása ígéri, ezért – a korábbi elvekhez hasonlóan – növeljük meg ezt a relációt egy x mennyiséggel.


69


70

35

v1 = 4 u1 = -2

5

u2 = 0

4

u3 = 4 Igény (b)

8

v2 = 3

v3 = 6

v4 = 5

Készlet (a)

8

4

10

3

50

u1 = -2

60+x

3

6

20-x

4

80

u2 = 0

30-x

3

8

70

u3 = 4

200

Igény (b)

90

40 40

+x

7 30

40

40

Most x = 20 a helyes választás ahhoz, hogy egy lekötött pozíción 0-t kaphassunk.

v1 = 4

v2 = 3

5 4 8

v3 = 6

8

4

80

3

6

10

3

90

40

10 20

7

40

30

v4 = 5 3

Készlet (a)

40

50

4

80

8

70 40

200

Az új program költsége: 4 · 80 + 8 · 10 + 3 · 40 + 4 · 10 + 7 · 20 + 3 · 40 = 820. Számítsuk ki ismét az új potenciálokat:


71


72

36

v3 = 7

v1 = 8

v2 = 3

u1 = -3

5

8

4

u2 = -4

4

80

3

6

u3 = 0

8

10

3

Igény (b)

90

40

20

7

40

c11 – (u1+v1) = 5 – (-3 + 8) = 0 c12 – (u1+v2) = 8 – (-3 + 3) = 8 c22 – (u2+v2) = 3 – (-4 + 3) = 1 c23 – (u2+v3) = 6 – (-4 + 7) = 3 c24 – (u2+v4) = 4 – (-4 + 6) = 2 c34 – (u3+v4) = 8 – (0 + 6) = 2

10

30 elıjele elıjele elıjele elıjele elıjele elıjele

v4 = 6 3

40

50

4

80

8

70 40

200

+ + + + + +

Legyen V elemeknek egy véges halmaza, és E a V elemeibıl képezett rendezett párok – esetleg üres – halmaza. Gráfnak nevezzük a V és E által meghatározott struktúrát. Jelölése: G(V,E)

1

v 3

e1 e5

e3

v 4

e4

e2

v

v

73

E(G) ≔ A G élhalmaza

V(G) ≔ A G csúcshalmaza

v

Mivel minden le nem kötött potenciál értéke pozitív, ezért a megoldásunk tovább nem javítható. Informatikai Alkalmazások

Gráfelmélet alapjai

Készlet (a)

• e1 = {v1,v4} összeköti a v1 és v4 csúcsokat • v3 és v2 szomszédos csúcsok, • e2 és e4 szomszédos élek, • e4 és v5 illeszkednek.

5

2

Idınként a v1v2 jelölést fogjuk használni a {v1,v2} helyett. Matematika I.

Informatikai Felsıfokú Alkalmazások Szakképzés

74

37

V(G) elemeinek a számát a gráf rendjének nevezzük. Jelölése: n(G). E(G) elemeinek a számát a gráf méretének nevezzük. Jelölése: m(G). Az n-ed rendő, m mérető gráfot G(n,m) vagy Gn,m jelöli.

{

Az illeszkedési mátrix B(G) = [bij]nxm ahol

Matematika I.

1 ha vi és ej illeszkedik 0 különben. Informatikai Felsıfokú Alkalmazások Szakképzés

v2 e4

e5

v3

v1 v2 v3 v4

A szomszédsági mátrix A(G) = [aij]nxn ahol 1 ha vivj ∊ E(G) aij = 0 ha vivj ∉ E(G)

{

e3

e2

Legyen a G gráf csúcshalmaz V(G) = {v1, v2, … , vn} és élhalmaza E(G) = {e1, e2, … , em}. A gráf leírható mátrixokkal.

bij =

e1

v1

v4

e1 e2 e3 e4 e5

v1 v2

v1 v2

v3 v4

v3 v4

Egy gráf, és a hozzá tatozó szomszédsági és illeszkedési mátrixok 75

Matematika I.


76

38

Csúcsok fokszáma Egy G gráf v csúcsának fokszámán a csúcshoz illeszkedı élek számát értjük. Jelölése: degG v vagy deg v.

2

Jelılje a v csúccsal szomszédos csúcsok halmazát Γ(v). degGv=|Γ(v)|.

3

v1

5

v2

v4

v3

degG v2 = 3

δ(G) = min degG v a G gráf minimális fokszáma.

δ(G) = degG v8 = 1

∆(G) = max degG v a G gráf maximális fokszáma.

1

v8

v9

degG v4 = 4

degG v9 = 2 ∆(G) = degG v6 = 5

Csúcsfokszámok egy gráfban

v∊ G


v7

2

4

Egy csúcsot izoláltnak nevezünk, ha deg v = 0, és vég-csúcsnak, ha deg v = 1.

Matematika I.

3

2 v5 2

Egy csúcsot párosnak vagy páratlannak nevezzük attól függıen, hogy a fokszáma páros vagy páratlan.

v∊ G

v6

77

Matematika I.


78

39

Tétel (“Kézfogási“ Lemma): Tekintsük a G(n,m) gráfot, ahol V(G) = {v1, v2, …, vn}. Ekkor n

∑degG vi = 2m

Biz.: Az állítás azonnal következik abból a ténybıl, hogy minden él két csúcsra illeszkedik. Következmény: Bármely gráfban a páratlan csúcsok száma mindig páros.


Azt a gráfot, amelynek nincsenek élei üres gráfnak nevezzük. A H gráf a G gráf részgráfja, ha V(H)⊆ V(G) és E(H)⊆ E(G).

i=1

Matematika I.

Részgráfok és indukált részgráfok

79

Legyen v∊V(G) és |V(G)| ≥ 2. A H = G – v gráf a v csúcs törlésével áll elı G-bıl, ha V(H) = V(G) – {v} és E(H) a G azon éleit tartalmazza, amelyek nem illeszkednek v-re. Ha e∊ E(G), akkor H = G – e (egy él kitörlése) G-nek egy olyan részgráfja, amelyre V(H) = V(G) és v E(H) = E(G) – {e}. Matematika I.


80

40

Ha u és v a G nem szomszédos csúcsai, akkor G + f, ahol f = uv, jelöli azt a gráfot, amelynek csúcshalmaza V(G) és élhalmaza E(G) ∪ { f }. Ezért G ⊆ G + f. v

Ha G egy H részgráfjának rendje megegyezik G rendjével, akkor Ht G feszítı részgráfjának nevezzük.

e

G

Matematika I.

G–v

Ha U a V(G) egy részhalmaz, akkor 〈U 〉 a G-nek egy olyan U által indukált gráfja, amely csúcshalmaza U ⊆ V(G) és élhalmaza minden olyan élet tartalmaz G-bıl, amely illeszkedik az U két elemére.

G–e


81

Matematika I.


82

41

Speciális gráfok Egy G gráfot r-reguláris gráfnak nevezünk, ha deg v = r a G gráf minden v csúcsára. Egy gráf teljes, ha bármely két csúcsa szomszédos.

Ha G = G(m,n), akkor G (n-1)-reguláris, és m = n(n-1)/2. Jelölése: Kn.

A Petersen gráf

4-reguláris gráfok. Matematika I.


83

Matematika I.


84

42

Egy G gráfot k-részesnek mondunk, k ≥ 1, ha a V(G) csúcspontjainak halmaza úgy particionálható k részhalmazra (V1,V2,…,Vk), hogy E(G) elemei Vi és Vj -beli csúcsokat kötnek össze, ahol i ≠ j.

Egy G gráf komplemens gráfján azt a gráfot értjük, amelyre V( )= V(G) u,v∊V(G), uv∊ E( ) akkor és csak akkor, ha uv ∉ E(G).

Ha k = 2, akkor a gráf kétrészes. Állítás-1: Ha G = G(m,n), akkor amelynek mérete:

egy olyan n-ed rendő gráf,

Tétel: Ha G egy r-reguláris kétrészes gráf, r ≥ 1, akkor |V1| = |V2| . Egy teljes kétrészes gráfot, ahol |V1| = r és |V2| = s K(r,s)-el vagy Kr,sel jelöljük . (A K1,s gráfot csillagnak nevezzük).

Állítás- 2: A Kn teljes gráf komplemens gráfja üres.

Matematika I.

az n-ed rendő


85

Matematika I.


86

43

v1

v4

v5

Mőveletek gáfokon

v7

Két gráf egyesítésén (unióján) azt a G = G1 U G2 gráfot értjük, amelyre V(G) = V(G1) U V(G2) és E(G) = E(G1) U E(G2). v2

v3

v6

v1

v3

v5

v2

v4

v6

v7

V1

Példa: 3K1 U 2K3 U K2,2.

V2

Egy kétrészes gráf két különbözı (izomorfikus) ábrázolása Matematika I.


87

Matematika I.


88

44

Két gráf összekapcsolásán azt a G = G1+G2 gráfot értjük, amelyre V(G) = V(G1) U V(G2) és E(G) = E(G1) U E(G2) U{uv | u∊V(G1) és v ∊ V(G2)}.

Két gráf direkt szorzatán azt a G = G1 × G2 gráfot értjük, amelyre V(G) = V(G1) × V(G2) és két csúcs: (u1,u2) és (v1,v2) akkor és csak akkor szomszédos, ha vagy u1 = v1 és u2v2∊E(G2) vagy u2= v2 és u1v1∊E(G1) Példa:

Példa:

u1

(u1,u2) u2

v2

v1 w1 G2

G1 Matematika I.

G1

G1+G2 Informatikai Felsıfokú Alkalmazások Szakképzés

89

Matematika I.

(u1,v2) (u1,w2)

(v1,u2) w2

(v1,v2) (v1,w2) G = G1×G2

G2 Informatikai Felsıfokú Alkalmazások Szakképzés

90

45

Gráfok bejárása Legyen u és v a G gráf – nem szükségképpen különbözı – két csúcsa. Egy W-vel jelölt u–v séta a G gráfban a csúcspontoknak és az éleknek egy olyan W: u = u0,e1,u1,e2,u2,….,uk-1,ek,uk = v véges, alternáló sorozata, amely az u csúcsponttal kezdıdik, a v csúccsal végzıdik, és ei = ui-1ui mindig egy él, i=1,2,…,k. A k számot a W séta hosszának nevezzük. u1

u4

e1

e2

u e6 Matematika I.

u6=v

e5 u2=u5

e4 e3

Egy u–v sétát zártnak vagy nyitottnak nevezünk attól függıen, hogy u = v vagy u ≠ v. A u-v ösvény az egy olyan u–v séta, amelyben él nem ismétlıdik, és egy u–v út az egy olyan u–v séta, amelyben csúcspont nem ismétlıdik. Következmény-1: minden út egyben ısvény is. Következmény-2: Minden út egyben séta is, de a megfordítottja általában nem igaz.

k=6 u3


91

Matematika I.


92

46

Tétel: Ha A a G szomszédsági mátrixa, és V(G) = {v1,v2,…,vn}, akkor az Ak hatványmátrix (i,j) eleme, k ≥ 1, megadja a k hosszúságú vi-vj sétákat a G gráfban.

Példa: v2

Példa: v4 v5

v3

v1

v2

v1

egy v1-v4 séta de nem ösvény. egy ösvény de nem út. egy út.

v3 v4

Matematika I.


93

Matematika I.


94

47

Egy nem triviális zárt ösvényt körútnak nevezünk, és azt a körutat, amelyben n különbözı csomópont szerepel, kırnek nevezzük.

Tétel: Egy G gráf csúcshalmazán értelmezett „összefüggı” reláció egy ekvivalancia reláció.

Egy aciklikus gráfban nincs kör.

Biz.: Házi feladat

Egy kör páros, ha hossza páros, egyébként a kör páratlan.

Azokat a részgráfokat, amelyek az ekvivalencia reláció eredményeként létrejött ekvivalencia osztályoknak felelnek meg, a G gráf összefüggı komponensének nevezzük. A G gráf komponenseinek számát k(G) jelöli.

Egy k hosszúságú kört k-körnek nevezünk. A 3-kör a háromszög. Azt az n-ed rendő gráfot, amely út, Pn jelöli, és Cn egy n csúcspontú kört jelöl. Egy u csúcsról azt mondjuk, hogy összeköthetı a v csúccsal, a gráfban létezik egy u–v út.

Egy összefüggı gráfban az u és v csúcsok d(u,v) távolságán a két csúcspont között megadható u−v utak minimális hosszát értjük.

Egy gráf összefüggı, ha bármely két csúcsa összeköthetı. Egyébként a gráf nem összefüggı. Matematika I.


95

Matematika I.


96

48

A feszítı fa probléma 0

v1

1

v6

2

v7

3

v8

Egy G gráf feszítı fáján azt a feszítı részgráfot értjük, amely fa.

2 v5 2

1 v2

2

3 v4

v3

v9 v1

v2

szint 0 szint 1

v6

v3

v9

v5

Tétel: Minden összefüggı fának van feszítı részgráfja Biz.: Konstrukcióval. Válasszunk egy tetszıleges x∊ V csúcspontot. Legyen Vi={ y ∊ G : d(x,y)= i, i=1,2,…,M }.

v4

v7

szint 2

v8

szint 3

Ha yi∊ Vi , i > 0 és x,z1,z2,…,zi-1,yi egy x – yi út, akkor d(x,zj)= j, 0 < j < i. Az világos, hogy Vj ≠ Ø, ha j < M, és bármely y ∊ Vi-hez, i ≤ M, létezik legalább egy y'∊ Vi-1, amely szomszédos y-nal. ({y',y} ∊ E(G)).

Távolsági szintek a v1 csúcsból kiindulva. Matematika I.


97

Matematika I.


98

49

x

Az optimalizáció-elmélet egyik ismert problémája az, hogy hogyan lehet megtalálni egy gráf valamilyen speciális tulajdonsággal rendelkezı feszítı fáját. Legyen adott a G=(V,E) gráf és egy pozitív értékő f függvény, amely + a gráf élein van definiálva: f: E→ℝ . Keressük azt a T=(V,E΄) összefüggı feszítı fát, amelyre

…

minimális. V0

V1

V2

VM-2

VM-1

Az ilyen tulajdonságú feszítı részfát gazdaságos feszítı fának nevezzük.

VM

Következmény-1: A G(n,m) feszítıfája: T(n,n-1). Matematika I.


99

Matematika I.


100

50

Egy valós probléma: Egy adott régióban falvakat akarunk összekötni vízvezetékkel. Ismerjük, hogy mennyibe kerül az egyes flvak közötti vezetékek felépítése. Keressük meg azt a hálózatot, mely a legkevesebb költséggel építhetı fel! Példa:

Kruskal Algoritmus (1956): Válasszuk ki a legolcsóbb élet G-bıl, azaz azt az élet, amelyre f(e) minimális. A következı élet a még ki nem választottak közül mindig úgy választjuk, hogy az a legolcsóbb legyen. A választásnál arra kell ügyelnünk, hogy nem képezhetünk körutat a kiválasztott élekbıl. Ha ilyen él már nincs, akkor véget ér az algoritmus. 1

1

3

3

2

4

3

3 3

2

4

5

3

3

2

4

5

f(T1)=15

1

1 2

4

Matematika I.

2

4

3


101

Matematika I.

4

2


102

51

2. Algoritmus: Az algoritmus lényege az, hogy drága élet csak akkor szabad választani, ha biztosítani akarjuk a gráf összefüggıségét. Töröljük tehát a legdrágább élet a gráfból mindaddig, amíg a gráf összefüggı marad. Ha ilyen él már nincs, akkor véget ér az algoritmus. 1 3 3 3

2

4

5

f(T2)=15

1 3

Matematika I.

4

Rendeljünk a G gráf minden (u,v )∊ E(G) éléhez egy w(u,v) függvényt, és nevezzük ezt súlynak. Azt a gráfot, amelynek élei súlyozva vannak, súlyozott gráfnak nevezzük. Legyen w: E(G)→ℝ+ egy függvény. Terjesszük ki a függvény definícióját egy gráf H ⊆ G részgráfjára:

2

4

A legrövidebb út problémája

Számos olyan optimalizációs probléma létezik, amely egy súlyozott gráfban keres egy olyan részgráfot, amely valamilyen tulajdonság szerint minimális (vagy maximális).

2


103

Matematika I.


104

52

A legrövidebb út problémája: adott egy súlyozott gráf, (vasút hálózat). Határozzuk meg a legrövidebb utat a gráf – elıre adott – két csúcspontja (városa) között. Ebben a környezetben az út hosszán a út által reprezentált részgráf súlyát fogjuk érteni.

Elıkészítı lépés:

Iterációs lépés:

The Dijkstra algorithm (1959)

Ha Si = V(G) akkor az algoritmus befejezıdik.

Tegyük fel, hogy az u0 és a v0 csúcsok közötti út hosszát akarjuk meghatározni: Az algoritmus egy fokozatosan növekvı Si halmazt készít, ahol 0 ≤ i ≤ n – 1, és {u0} ⊆ Si ⊆ V(G).

Ha Si ≠ V(G) akkor legyen ui+1 a W egy tetszıleges csúcspontja.

Minden lépésben egy cimkét rendelünk a csúcspontokhoz: l:(G)→ℝ∪{∞} úgy, hogy a v ∊ S csúcshoz tartozó l(v) címke a v csúcs távolságát adja meg az u0 csúcstól az 〈S 〉 indukált részgráfban. Matematika I.


105

és

Ha l(ui+1) = ∞ vagy ui+1 = v0 akkor az algoritmus megáll. Ha l (ui+1) < ∞ akkor Si+1 = Si U {ui+1}, és legyen

i=i+1. Matematika I.


106

53

Mi a Dijkstra's Algoritmus bonyolultsága?

Euler gráfok

n-ben polinomiális: O(n2). Példa: v2

2

4

2

1 u0

7

Step

v3

v1

l(u0) l(v1)l(v2)l(v3)l(v0)

Egy olyan körutat a G gráfban, amely tartalmazza a G összes élét Euler körnek mondjuk.

Si

Egy Euler ösvény tartalmazza az összes élet, de nem zárt.

0

0

7

1

2

∞ u0

1 1

1

0

7

1

2

2

3

2

0

5

1

2

2 u0 v2 v0

3

0

5

1

2

2 u0 v2 v0 v3

4

0

5

1

2

2 u0 v2 v0 v3 v1

v0

u0 v2

Egy gráf Euler gráf, ha benne létezik Euler-kör. Egy G gráfot párosnak (páratlannak) mondunk, ha minden csúcsa páros (páratlan). Tétel : Egy összefüggı gráfban akkor és csak akkor van Euler-körút, ha a gráf minden csúcsa páros.

Matematika I.


107

Matematika I.


108

54

Definiáljuk a következı sorozatot: a sorozatban egy bető azt a szárazföldet jelenti, amelyhez az út során elérkeztünk, és két egymás utáni elem azt a hidat jelenti, amelyen át kell kelni útban az egyik területrıl a másikra. Ha ilyen út létezne, akkor az leírható lenne 8 betővel, amelyek mindegyikét az A, B, C és D betőkbıl választjuk Mivel minden hídon pontosan egyszer szabad átmenni, ezért az A és B betők ebben a sorozatban kétszer fordulnak úgy elı, hogy ık egymást követik. Ugyanez a helyzet az A és C betőpárral is. Mivel öt híd vezet az A által jelölt területre, ezért A-nak a jó megoldásban háromszor kell megjelenni. (Két pár jelöl egy-egy belépést és kilépést az A területre, egy pedig vagy kilépést vagy belépést A-ra.) Hasonló megfontolásból, B, C és D kétszer jelenik meg a sorozatban. Ezért legalább 9 betőbıl kell állni a sorozatnak. Ez pedig lehetetlen. Matematika I.


109

Matematika I.


110

55

Hamilton utak Az utazó ügynök problémája: egy utazóügynök n várost akar meglátogatni úgy, hogy az út végén visszaérjen a központi irodába. Bármely két város közötti utazás költsége ismert. Keressünk egy hatékony algoritmust, amely megtalálja a legolcsóbb utat.

C

A

D

Mit jelent a „hatékony algoritmus”? A válasz meglepı: nem ismert az, hogy létezik-e hatékony algoritmus a probléma megoldására.

B

Variáns: Ha az úttól azt követeljük meg, hogy körút legyen, azaz nincs megengedve az, hogy az utazás alatt ugyanazt a várost kétszer is érintse.

The seven bridges on the Pregel in Königsberg Matematika I.


111

Matematika I.


112

56

Azt a körutat, amely tartalmazza a problémához tartozó gráf minden csúcspontját, Hamilton körnek nevezzük. Azt a gráfot, amelynek van Hamilton köre, Hamilton gráfnak nevezzük. Az elnevezés onnan ered, hogy Sir William Rowan Hamilton 1857ben konstruált egy játékot, amely során a feladat az volt, hogy miként lehet a dodekaéder csúcsaiba vert szögeken végigvezetni egy madzagot úgy, hogy minden csúcsot csak egyszer érintünk. Ez volt 19. század “Rubik kockája “. 1855-ben Thomas P. Kirkman következı kérdést tette fel: Legyen adott egy poliéderhez tartozó gráf. Lehet-e mindig konstruálni egy olyan körutat, amely minden csúcspontot egyszer és csak egyszer érint? Matematika I.


113

A dodekaéder gráfja Matematika I.


114

57

Hamilton köröket (és Hamilton utakat) már korábban is vizsgáltak. 1759-ben Euler tanulmányozta azt a problémát, hogy lehetséges-e a huszárral bejárni a sakktábla mind a 64 mezıjét úgy, hogy minden mezıt érintünk, egyikre sem lépünk kétszer, és a végén vissza jutunk a kiindulópontra.

A gazdaságos Hamilton kör meghatározásánál lényegesen egyszerőbb az a feladat, hogy létezik-e Hamilton kör a gráfban? Erre a kérdésre sincs jó válasz. Van-e olyan feltétel, amely alapján eldönthetı, hogy egy gráf Hamilton-gráf-e vagy sem? Tétel (Dirac): Ha G egy 2n-ed rendő gráf, és minden csúcspontja legalább n-ed fokú, akkor a gráf Hamilton-gráf. Tétel (O. Ore, 1960): Ha G egy n-ed rendő, n ≥ 3, és minden nem szomszédos u, v csúcspontjára deg u + deg v ≥ n, akkor G Hamilton-gráf.

Matematika I.


115

Matematika I.


116

58

Reguláris gráfok esetében a Dirac-tétel javítható: Jackson (1980) kimutatta, hogy minden olyan 2-összefüggı r-reguláris gráf, amelynek legalább 3r csúcspontja van, az Hamilton-gráf. A Petersen gráf mutatja, hogy a 3r feltétel nem helyettesíthetı 3r+1el.

Matematika I.


117

Gyakorlat: Bináris fák és alkalmazásaik: bináris fák ábrázolása rendezés fával tömörítés fával.

Matematika I.


118

59

VÉGE


119

60

Informatikai Alkalmazások Mőszaki menedzser szak. Galambos Gábor SZTE Az anyag elsajátításához szükséges ismeretek

Recommend Documents