1
Matematika NYME KTK, Egyetemi kiegészít˝o alapképzés 2002/2003. tanév, I. évf. I.félév Budapest El˝oadó: Dr. Takách Géza NyME FMK Információ Technológia Tanszék 9400 Sopron, Bajcsy Zs. u. 9. GT fszt. 3. (30) 509 7361
[email protected] http://titanic.nyme.hu/˜takach
Számonkérés Írásbeli vizsga januárban • Feladatok • Elméleti kérdések • Bizonyítások
1. konzultáció Gráfelmélet • Alapfogalmak • Euler-vonal • Hamilton-kör • Legrövidebb út • Minimális feszít˝ofa • Hozzárendelési feladat • Folyamprobléma
Irodalom F. S. Hillier és G. J. Lieberman. Bevezetés az operációkutatásba.
Algoritmusok!
2
LSI Oktatóközpont, Budapest, 1994. Szükséges részek: 10. fejezet, azaz 237–247, 258–261 oldal.
A többi anyagrészhez: ld. tantárgy honlapja
A gráf definíciója 1.. DEFINÍCIÓ. Legyen V egy véges halmaz, E pedig V -beli rendezetlen elempárok véges rendszere. Ekkor a G=(V, E) párt gráfnak nevezzük. V elemei a gráf csúcsai, E elemei a gráf élei. Ha e = (v1 , v2 ) egy él, akkor azt mondjuk, hogy az e él a v1 és a v2 csúcsokat köti össze.
Egy labdarúgó tornán 6 csapat vesz részt. Ez a gráf azt írja le, hogy mely csapatok mérk˝oztek meg egymással az els˝o négy fordulóban. V = {A, B, C, D, E, F } E = {(A, B), (A, C), (A, D), (A, F ), (B, C), (B, E), (B, F ), (C, D), (C, E), (D, E), (D, F ), (E, F )}
Rendezetlen elempáron azt értjük, hogy nem teszünk különbséget a (v1 , v2 ) és a (v2 , v1 ) pár között, a rendszer pedig abban különbözik a halmaztól, hogy egy elem többször is szerepelhet benne.
Gráfelméleti alapfogalmak
2.. DEFINÍCIÓ. Egy gráf egy csúcsa izolált csúcs, ha nem indul ki bel˝ole él. (W ) Többszörös élr˝ol beszélünk, ha két pontot több él köt össze.((Y, V ) ) A hurokél önmagába visszatér˝o él, azaz két végpontja azonos.((X, X)) Az üres gráf csupa izolált pontokból álló gráf, azaz E = ∅. Az egyszer˝u gráfok nem tartalmaznak sem hurokélet, sem többszörös élet.
3
Gráfelméleti alapfogalmak
3.. DEFINÍCIÓ. A teljes gráfok olyan egyszer˝u gráfok, amelyekben bármely két különböz˝o csúcs között vezet él. Kn : n csúcsú teljes gráf. ¯ gráf, amely teljes gráffá egészíti ki; tehát Egy G egyszer˝u gráf komplementere az a G ¯ ¯ G és G csúcsai megegyeznek, továbbá két csúcs között pontosan akkor vezet él G-ben, ha G-ben nem vezet él. A G1 = (V, E 0 ) gráf a G = (V, E) gráf részgráfja, ha E 0 ⊆ E; tehát G1 -et G-b˝ol néhány él elhagyásával kapjuk. A G1 és G2 gráfok izomorfak, ha létezik a csúcsok között olyan bijekció, hogy két G1 -beli csúcs között pontosan akkor vezet él, ha a megfelel˝o két G2 -beli csúcs is össze van kötve.
Síkgráfok 4.. DEFINÍCIÓ. Egy gráf síkgráf, ha lerajzolható úgy a síkba, hogy élei csak a szögpontokban metszik egymást.
G síkgráf, mert a vele izomorf H a síkba van rajzolva. Ha egy gráf lerajzolható a síkba, akkor lerajzolható úgy is, hogy minden éle egyenes szakasz legyen. (K)
4
Síkgráfok
K5 és K3,3 nem rajzolhatók le a síkba. Az is belátható, hogy ha egy gráf nem rajzolható síkba, akkor K5 vagy K3,3 valahol "benne van" a gráfban.
Fokszámok 5.. DEFINÍCIÓ. Egy csúcs fokszáma a bel˝ole kiinduló élek száma. Megjegyzés. Egy n-pontú teljes gráfban minden csúcs fokszáma n − 1, és összesen élet tartalmaz.
n 2
6.. TÉTEL. Egy gráf páratlan fokú csúcsainak száma páros. Bizonyítás. Felhasználjuk az alábbi segédtételt. 7.. SEGÉDTÉTEL. Egy gráf csúcsai fokszámainak összege megegyezik az élek számának kétszeresével. Ezek után a tétel bizonyítása a következ˝o: Jelölje a gráf csúcsait A1 , . . . An , a megfelel˝o fokszámokat ρ(A1 ), . . . , ρ(An ). Tegyük fel, hogy ρ(A1 ), . . . , ρ(Ak ) páratlan számok, ρ(Ak+1 ), . . . , ρ(An ) párosak. A segédtétel szerint ρ(A1 ) + . . . + ρ(An ) páros, így páros számokat elhagyva ρ(A1 ) + . . . + ρ(Ak ) is páros lesz. Páratlan számok összege pedig csak akkor lehet páros, ha páros sok van bel˝olük. ♦
Fokszámok 8.. TÉTEL. Legyen G egy n-csúcsú egyszer˝u gráf, n ≥ 2. Ekkor van legalább két olyan csúcs, melyek fokszáma megegyezik. Bizonyítás. Minden egyes csúcs fokszáma 0, 1, . . . , n − 1 lehet, vagyis n-féle. Egy 0-fokú csúcs izolált csúcs, egy (n − 1)-fokú pedig minden másik csúccsal össze van kötve. Tehát nem lehet a gráfban egyszerre 0-fokú és (n−1)-fokú csúcs is, vagyis csak (n−1) féle lehet a fokszám. Ekkor a skatulya-elv szerint van két azonos fokszámú csúcs. ♦
5
Gráfok bejárása 9.. DEFINÍCIÓ. Sétán két csúcsot összeköt˝o élsorozatot értünk. Speciális séták: • vonal: olyan séta, melyben minden él legfeljebb egyszer szerepel (a csúcsok többször is szerepelhetnek). • zárt vonal: olyan vonal, melynek kezd˝o és végpontja azonos. • nyílt vonal: olyan vonal, melynek kezd˝o és végpontja különböz˝o. • út: minden csúcsot legfeljebb egyszer érint˝o séta. • kör: olyan séta, melynek a kezd˝o és végpontja azonos, a többi csúcsot legfeljebb egyszer érinti. 10.. DEFINÍCIÓ. Egy gráf összefügg˝o, ha bármely két csúcs között vezet út.
Königsbergi hidak Eulert˝ol megkérdezték Königsberg lakói, hogy miért nem tudnak átmenni a város hídjain úgy, hogy mindegyiken pontosan egyszer mentek át:
Euler-vonal Melyik ábra (gráf) rajzolható le egy vonallal a ceruza felemelése nélkül?
6
A kukásautónak egy körzet minden utcáján végig kell mennie, és be kell gy˝ujteni a szemetet. Meg tudja-e ezt tenni úgy, hogy minden utcán csak egyszer megy végig?
Euler-vonal 11.. DEFINÍCIÓ. Euler-vonal: olyan vonal (séta), melyben minden él pontosan egyszer szerepel. Szükséges feltétel Euler-vonal létezésére: zárt Euler-vonal esetén minden pontba pont ugyanannyiszor megyünk be mint ki ⇒ minden pont foka páros. Belátható, hogy ez elegend˝o is! 12.. TÉTEL. Egy összefügg˝o gráfban pontosan akkor létezik zárt Euler-vonal, ha minden csúcs fokszáma páros. Egy összefügg˝o gráfban pontosan akkor létezik nyitott Euler-vonal az A csúcsból a B csúcsba, ha csak A és B fokszáma páratlan. Ha egy összefügg˝o gráfban a páratlan fokszámú csúcsok száma 2k, akkor a gráf k darab diszjunkt vonal egyesítése. ⊗
Algoritmusok "Algoritmus" zárt Euler-vonal keresésére: Tetsz˝oleges csúcsból kiindulva rajzolom fel a gráfot, ügyelve arra, hogy a le nem rajzolt rész összefügg˝o maradjon. "Algoritmus" nyílt Euler-vonal keresésére: Ugyanaz, mint a zártra, de a kiindulópont szükségszer˝uen az egyik páratlan fokú csúcs.
Utazó ügynök probléma Egy ügynöknek meg kell látogatnia bizonyos városokat útja során (és végül haza kell térnie). Adott: • mely városokból mely másik városokba van járat(közvetlen út) • milyen költséggel tud eljutni egyik városból másikba (repül˝ojegy, autóút ára).
7
Cél: az utak összköltségét minimalizálni. Ez a feladat sok alkalmazás során felmerül, és csak bizonyos speciális esetekben ismeretesek jó algoritmusok a megoldására.
Ha bármely két város közt, melyek között van összeköttetés, az 1 költség˝u, és az ügynöknek minden várost meg kell látogatnia, akkor a feladat a Hamilton-kör létezésére vezet.
Hamilton-kör 13.. DEFINÍCIÓ. A Hamilton-kör olyan kör, amely minden csúcson átmegy (szükségszer˝uen pontosan egyszer). A Hamilton-kör létezésére nem ismert egyszer˝u szükséges és elégséges feltétel, s ugyancsak nincs gyors algoritmus sem Hamilton-kör keresésére. Elégséges, de nem szükséges feltétel Hamilton-kör létezésére: 14.. TÉTEL. Legyen G n-csúcsú egyszer˝u összefügg˝o gráf. Ha minden csúcs fokszáma legalább n/2, akkor a gráfban létezik Hamilton-kör. ⊗
Hamilton-kör Szükséges, de nem elégséges feltétel Hamilton-kör létezésére: 15.. TÉTEL. Ha egy G = (V, E) gráfban van Hamilton-kör, akkor bármely S ⊆ V ponthalmaz esetén S pontjait és a bel˝olük kiinduló csúcsokat elhagyva a maradék gráfnak legfeljebb annyi össefügg˝o komponense van, mint |S|. Másképpen: Ha egy G = (V, E) gráfban létezik olyan S ⊆ V ponthalmaz, hogy S pontjait és a bel˝olük kiinduló csúcsokat elhagyva a maradék gráfnak |S|-nál több össefügg˝o komponense van, akkor a gráfban nincs Hamilton-kör.
Legrövidebb út keresése Alapfeladat: Adott egy összefügg˝o gráf, egy kezd˝o- és egy végs˝o csúcs, valamint az élekhez rendelt távolságok. Keressük a legrövidebb utat a kezd˝o és a végs˝o csúcs között. Figyelem! Nem a felhasznált élek számát kell minimalizálni, hanem a hosszaik összegét. Átfogalmazások: Az elemekhez rendelt számok jelképezhetnek költségeket illetve id˝otartamokat is. Ilyenkor a minimális költség˝u illetve a legkevesebb id˝o alatt bejárható utat keressük.
Algoritmus. A gráf minden élére meghatározzuk a kezd˝oponttól oda vezet˝o legrövidebb utat. A kezd˝oponttól mért távolságok szerint növekv˝o sorrendben vesszük a pontokat. 1. iterációs lépés: Meghatározzuk a kezd˝oponthoz legközelebbi pontot.
8
n. iterációs lépés: Meghatározzuk a kezd˝oponthoz n. legközelebbi pontot. Bemenet: A legközelebbi n − 1 csúcs, beleértve a legrövidebb útvonalakat is. (Ezeket nevezzük megoldott pontoknak (beleértve a kezdeti pontot is), a többit megoldatlan pontnak mondjuk.) Jelöltek: minden megoldott ponthoz a legközelebbi megoldatlan pont (ha van ilyen). Döntés: minden jelöltre kiszámítjuk a jelöl˝o–kezd˝o távolság és a jelölt–jelöl˝o távolság összegét, és ezek közül a minimálisat választjuk. A jelöl˝o csúcsot is feljegyezzük. A legrövidebb út: Ha az iterációban elérek a végs˝o pontig, akkor készen vagyok. (Visszafejtés!)
n 1 2 4
5
6
Jelöl˝o O O A A B C A B E D E
Jelölt A C B D E E D D D T T
Távolság 2 4 2+2=4 2+7=9 4+3=7 4+4=8 2+7=9 4+4=8 7+1=8 8 + 5 = 13 7 + 7 = 14
Gy˝oztes A C B
Távolság 2 4 4
Összeköttetés OA OC AB
E
7
BE
D D T
8 8 13
BD ED DT
Visszafejtés Az összeköttetés oszlop tartalma: OA, OC, AB, BE, BD, ED, DT
9
Azaz OABEDT és OABDT a két legrövidebb út.
Fák 16.. DEFINÍCIÓ. Fának nevezzük az olyan összefügg˝o gráfokat, amikben nincs kör. A fák szükségszer˝uen egyszer˝u gráfok, hiszen a hurokél 1-hosszú kör, a többszörös él 2-hosszú kör.
Fák jellemzése 17.. TÉTEL. Legyen G egy n-csúcsú gráf. Ekkor a következ˝o állítások ekvivalensek 1. G fa; 2. G összefügg˝o és n − 1 éle van; 3. G összefügg˝o, de tetsz˝oleges élét elhegyva már nem lesz összefügg˝o. 4. G-ben nincs kör, de egy tetsz˝oleges új élet hozzávéve már lesz benne kör.
⊗
10
1.
Feszít˝o fák
18.. DEFINÍCIÓ. Legyen G egyszer˝u, összefügg˝o gráf. Az F fa a G gráf feszít˝o fája, ha F olyan részgráfja G-nek, mely a G minden csúcsát és bizonyos éleit tartalmazza.
Minimális kifeszít˝o fa keresése Feladat: Adott egy n csúcsú, egyszer˝u összefügg˝o gráf, valamint az élekhez rendelt valós számok, amelyek az élek hosszai. Keressük azt a kifeszít˝o fát, amelyben az élek összhossza minimális. 1. ALGORITMUS (K RUSKAL - FÉLE MOHÓ ALGORITMUS ): • Rendezzük hosszuk szerint növekv˝o sorrendbe az éleket. • Válasszunk ki sorban éleket, de olyan élet ne válasszunk ki, melynek kiválasztásával kör keletkezne. • Az el˝oz˝o pontot ismételjük n − 1-szer. 2. ALGORITMUS: ld. [HL], 10.4. Ez szintén mohó algoritmus, de végig összefügg˝o részgráfot alkotnak a kiválasztott élek.
Páros gráfok
19.. DEFINÍCIÓ. Egy G = (V, E) gráfot páros gráfnak nevezünk, ha van olyan V = B ∪ J felbontás, hogy B ∩ J = ∅, továbbá minden él egyik végpontja B-ben, a másik J-ben van. Jelölése: G = (B, J; E).
11
Vegyük észre, hogy ha B és J nem adott, akkor nem egyszer˝u feladat eldönteni, hogy a gráf páros-e.
Hozzárendelési feladat páros gráfokban
20..DEFINÍCIÓ. A G = (B, J; E) páros gráf éleinek egy M halmaza lefedést (matchinget, független élrendszert, párosítást) alkot, ha nincs két olyan M -beli él, amelyeknek van közös végpontja. Egy csúcs lefedetlen az M élrendszerben, ha nem végpontja egyetlen M -beli élnek sem. Egy lefedés teljes lefedés, ha a gráf minden csúcsát lefedi. (Teljes lefedés csak akkor létezhet, ha |B| = |J| teljesül.)
Javító útak 21.. DEFINÍCIÓ. Adott egy M párosítás egy páros gráfban. Ha egy út felváltva tartalmaz M -hez tartozó és M -hez nem tartozó éleket, akkor alternáló útnak nevezzük. Egy alternáló út javító út (b˝ovít˝o út), ha mindkét végpontja lefedetlen csúcs.
12
Javító útak Vegyük észre, hogy ha U egy b˝ovít˝o út az M párosításra nézve, akkor az U 4 M eggyel nagyobb elemszámú párosítás, mint M . Tehát az alternáló út M -hez tartozó éleit M -b˝ol elhagyva, az M -hez nem tartozó éleit M -hez hozzávéve eggyel nagyobb elemszámú párosítást nyerünk.
22.. TÉTEL. Egy páros gráf M lefedése akkor és csak akkor maximális elemszámú független élrendszer, ha nem létezik b˝ovít˝o út a gráfban M -re nézve.
Matching-algoritmus Adott egy G = (B, J; E) páros gráf, valamint egy M kiindulási párosítás (amely esetleg üres is lehet). M -b˝ol kiindulva keresünk egy maximális elemszámú párosítást G-ben. • Ha nincs lefedetlen csúcs B-ben, akkor M maximális párosítás, STOP. Ha van, akkor folytassuk a következ˝o lépéssel. • Keressünk egy b˝ovít˝o utat, • Ha találunk b˝ovít˝o utat, akkor ennek segítségével b˝ovítsük M -et, és folytassuk az els˝o lépéssel. Ha nem találtunk b˝ovít˝o utat, akkor M maximális elemszámú párosítás.
Javító út keresése
13
• Minden egyes i ∈ B csúcsra és (i, j) ∈ / M élre cimkézzük meg a (J-beli) j csúcsot i-vel. • Minden egyes lefedett j ∈ J csúcsra cimkézzük meg a (B-beli) i csúcsot j-vel, ahol (i, j) ∈ M . • Minden egyes J-beli lefedetlen csúcsra felírható egy alternáló út, amely a csúcsból indul ki, és mindig a cimkének megfelel˝oen folytatódik. Ha egy út 0 cimkéhez ért, akkor az b˝ovít˝o út.
Éllefogások Annak megállapítása, hogy egy párosítás maximális elemszámú-e, történhet az alábbi tétel segítségével is. 23.. DEFINÍCIÓ. A G = (V, E) gráf W ⊆ V pontjai éllefogó ponthalmazt alkotnak, ha minden él legalább egyik végpontja W -beli.
24.. TÉTEL. Egy páros gráfban tetsz˝oleges párosítás elemszáma kisebb vagy egyenl˝o tetsz˝oleges éllefogó ponthalmaz elemszámánál. Következésképpen ha |M | = |W | teljesül, akkor M maximális elemszámú párosítás, W pedig minimális elemszámú éllefogás.
Hálózatok Alapfeladat: Adott egy gráf, minden élének mindkét irányú kapacitása, valamint két kitüntetett csúcs: a forrás és a nyel˝o. Keresünk egy maximális érték˝u megengedett folyamot (áramlást).
14
Szemléltetésképpen feltehetjük, hogy a hálózattal egy olajvezetékrendszert ábrázolunk. A kapacitások a vezeték vastagságát jelentik, vagyis azt, hogy egységnyi id˝o alatt mennyi olaj folyhat át azon a vezetékdarabon. A kérdés az, hogy egy adott hálózaton mennyi olaj folyhat át s-b˝ol t-be. Szoktak beszélni úthálózatokról is, ahol a kapacitás az utak átereszt˝oképessége, és árukat kell eljuttatni a termel˝ot˝ol a fogyasztókhoz. De beszlélhetünk számítógéphálózatokról és adatátviteli sávszélességr˝ol is.
Folyamok 25.. DEFINÍCIÓ. Folyamon a hálózat minden egyes éléhez rendelt számot értünk, amely azt mutatja, hogy mekkora az élen átáramló anyag mennyisége. Meg kell adni az áramlás irányát is. (Irányított gráf!) Megengedett folyamnak nevezünk egy olyan folyamot, ahol a forrásból csak kifelé, a nyel˝obe csak befelé vezet áramlás, minden egyes egyéb csúcs esetén a kifolyó áramlások összege megegyezik a befolyók összegével, továbbá a egyik élen sem haladja meg az él kapacitását. 26.. DEFINÍCIÓ. Egy út kapacitásán a rajta lév˝o minimális élkapacitást értjük.
Algoritmus 1. Keresünk egy forrás→nyel˝o utat pozitív kapacitással (c). Ha nincs ilyen út, akkor a jelenlegi folyam maximális. STOP! 2. Növeljük a folyamot c-vel ezen az úton. 3. Csökkentsük ezen az úton c-vel a kapacitást minden élen. Növeljük az ellenkez˝o irányú úton a kapacitást c-vel minden élen. Folytassuk az 1. lépéssel.
15
Vágások Hogyan gy˝oz˝odhetünk meg egyszer˝uen arról, hogy egy folyam maximális, azaz hogy nem tudunk további áramlást indítani s-b˝ol t-be? 27..DEFINÍCIÓ. Egy vágás irányított élek olyan halmaza, amelyek minden forrás→nyel˝o útból tartalmaz egy élet. Egy vágás értéke a hozzá tartozó élek kapacitásainak összege. 28.. TÉTEL. Minden megengedett folyam értéke kisebb minden vágás értékénél. S˝ot, a maximális folyamok(ok) értéke egyenl˝o a minimális vágás értékével. A tétel megkönnyíti az algoritmus 1. lépésében a döntést: ha úgy t˝unik, hogy nincs már pozitív kapacitású forrás→nyel˝o út, akkor megpróbálok keresni egy 0-érték˝u vágást. Ha van nulal érték˝u vágás, akkor biztos hogy nincs pozitív kapacitású forrás→nyel˝o út. Ha úgy t˝unik, hogy nincs nulal érték˝u vágás, akkor valószín˝uleg van pozitív kapacitású forrás→nyel˝o út...
