TDK dolgozat Korlátosság vizsgálata irány-hossz vegyes gráfok esetén
Szabó Botond Alkalmazott matematikus szak Eötvös Loránd Tudományegyetem Természettudományi Kar 2009
Témavezet®:
Jordán Tibor, egyetemi tanár ELTE TTK Matematikai Intézet Operációkutatási Tanszék
Contents 1
Bevezetés
3
1.1 Általános bevezetés . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Jelölések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 7
2
Tételek az algoritmushoz
10
3
Az algoritmus
15
3.1 Az algoritmus megadása . . . . . . . . . . . . . . . . . . . . . . 15 3.2 Generikusan nem korlátos gráf tetsz®legesen nagy realizációja . 18 4
Következmények, kapcsolatok
22
4.1 A kétféle modell ekvivalenciája . . . . . . . . . . . . . . . . . . 22 4.2 Gráfelméleti karakterizáció a korlátosságra . . . . . . . . . . . . 23
1
Absztrakt
Irány-hossz rendszernek nevezzük azon (G, p) rendezett párokat, ahol a G = (V ; D, L) vegyes gráf, melyben V jelöli a csúcsok, D az "irány élek", L a "hossz élek" halmazát és p egy leképezés V -b®l a d dimenziós Euklideszi térbe. Egy uv él címkéje egy hossz vagy irány korlátozást fog adni p(u) és p(v) között. A hossz korlátozás lehet fels® határ vagy pontos távolság megadás és az így megadott két fajta de níció alapján lehet kötél illetve rúd modellr®l beszélni. A dolgozat során a kötél modell korlátosságával foglalkoztam majd végül beláttam, hogy a kapott állítások rúd modellre is alkalmazhatóak. Els®ként egy algoritmust adtam meg, mely eldönti, hogy egy (G, p) rendszer korlátos-e, majd nem korlátos esetben tetsz®leges nagyságú gráf elkészítésére adtam egy eljárást. Az algoritmus felhasználásával beláttam, hogy a kötél és rúd modell korlátosságának feltétele megegyezik, azaz az algoritmus mindkét modellre alkalmazható. Végül igazoltam, hogy az algoritmus pontosan azon gráfokat adja korlátosnak, melyek Bill Jackson és Peter Keevash (2009a) cikkében szerepl® korlátosság feltételeket is teljesítik, azaz az eljárásnak és a cikknek a (G, p) rendezett pár korlátosságára adott feltételrendszere megegyezik. A dolgozat során az általánosan használt rúd modell helyett bevezetett kötél modell segítségével egyszer¶síteni tudtam a problémát és a matroid elméletet kikerülve elemi operációkutatási módszereket alkalmazva sikerült a gráf korlátosságával ekvivalens feltételt megadni. A két modell korlátosságának ekvivalenciája miatt a kapott módszer segítséget nyújthat összetettebb problémák vizsgálatánál.
2
1
1.1
Bevezetés
Általános bevezetés
A geometriai megkötésekkel megadott szerkezeteket gyakorlati problémák széles skálájának modellezésére alkalmazzák, mint például szenzor rendszereknél, molekulák rugalmasságánál és számítógépes formatervezésnél. A G gráf bizonyos éleire irány (D, irány-élek ) illetve hossz (hossz-élek ) megkötéseket tehetünk és az így keletkezett rendszerrel kapcsolatban számos érdekes kérdés merül fel. Vizsgálhatunk olyan rendszereket, melyekben csak az élek hosszára (Laman (1970)) vagy irányára van megkötés (Whiteley (1996)), illetve a vegyes gráfok esetét, melyben mindkett® fajta megkötés el®fordulhat (Servatius and Whiteley (1999)). A hossz-éleket kétféleképpen de niálhatjuk. Az általánosan bevett gyakorlat szerint rúdnak (L) nevezzük azon hossz-éleket, melyekben az él hossza x, míg a dolgozatban bevezetett de níció szerint kötélnek (K ) nevezzük azon hossz-éleket, melyekben az él hosszára fels® korlát van megadva. A dolgozat során belátjuk, hogy az általunk vizsgált tulajdonságok egybeesnek a különböz® de nícióval megadott modellekben. Az él korlátozásokkal megadott gráfok esetén természetesnek t¶nik annak a kérdése, hogy az adataink tartalmaznak-e ellentmondást vagy létezik a feltételeket kielégít® realizációja a gráfnak. Létezés esetén továbbá felmerül az egyértelm¶ség kérdése. Jelentse a (G, p) rendezett pár a G = (V, E) gráf egy realizációját a d dimenziós Euklideszi térben, ahol p : V 7→ Rd függvény a csúcsok helyét jelöli. A kizárólag csak élek hosszára vonatkozó megkötéseket tartalmazó G = (V ; L) rúd-gráf két (G, p) és (G, q) realizációját rúd-ekvivalensnek nevezzük, ha minden élük egyenl® hosszú illetve rúd-kongruensnek nevezzük ®ket, ha tetsz®leges u, v ∈ V csúcsra teljesül, hogy kp(u) − p(v)k = kq(u) − q(v)k. Ezek segítségével de niálhatjuk a realizáció unicitásának különböz® szintjeit. Egy (G, p) realizációt globálisan rúd-merevnek hívunk, ha bármely vele rúdekvivalens (G, q) realizáció egyúttal rúd-kongruens is lesz vele. Továbbá rúdmerevnek nevezzük (G, p)-t, ha létezik olyan > 0 környezet, hogy bármely vele rúd-ekvivalens (G, q) realizációra, melyre teljesül, hogy kq(u) − p(u)k < minden u ∈ V csúcsra, a két realizáció egyúttal rúd-kongruens is lesz. Saxe (1979) bebizonyította, hogy a csak hossz megkötéseket tartalmazó gráfok esetén mind a létezés, mind a globális egyértelm¶ség eldöntése NP-nehéz feladat. Ennek oka, hogy bizonyos speciális esetek megnehezítik a probléma eldön3
tését. Ebb®l kifolyólag a gráfnak csak a generikus (G, p) realizációit vizsgáljuk, melynek pontos de nícióját a 1.2 alfejezetben adjuk meg. Egy G = (V ; L) rúdgráfot rúd-merevnek, illetve globálisan rúd-merevnek hívunk, ha minden generikus (G, p) realizációja rúd-merev, illetve globálisan rúd-merev. A speciális kétdimenziós esetben a G gráf rúd-merevségre (Laman (1970)) és a globális rúd-merevségére (Jackson és Jordán (2005)) adott kombinatorikus karakterizációt. Magasabb dimenzióban nem ismert kombinatorikai karakterizáció az unicitás kérdésére. A csak irány-élekkel de niált G = (V ; D) irány-gráfra egy (G, p) és egy (G, q) realizációt irány-ekvivalensnek mondunk, ha bármely e = uv ∈ D élhez tartozó p(u) − p(v) és q(u) − q(v) egymás konstansszorosai, valamint iránykongruensnek nevezzük ®ket, ha a fenti állítás tetsz®leges u, v ∈ V csúcspárra teljesül. A (G, p) szerkezet irány-merev, ha tetsz®leges vele irány-ekvivalens (G, q) szerkezet egyúttal irány-kongruens is lesz vele. A G irány-gráf iránymerev, ha tetsz®leges generikus (G, p) realizációja irány-merev lesz. A generikusan merev G irány-gráfokra d-dimenzióban Whiteley (1996) adott kombinatorikus karakterizációt. A speciális kétdimenziós esetre az alábbi kapcsolat áll fent a rúd-merevséggel:
Kétdimenzióban a G = (V ; L) rúd-gráf pontosan akkor rúd-merev, ha a G = (V ; D) irány-gráf irány-merev. (A két gráfban a rúd illetve az irány-élek halmaza megegyezik). Tétel 1.1.
0
Laman (1970) speciális kétdimenziós esetre adott karakterizációja a merevségre:
Egy |D| = 2n − 3 él¶ csak irány-élekb®l álló gráf akkor és csak akkor irány-merev, ha |D0 | ≤ 2|V (D0 )| − 3 minden nemüres D0 részhalmazára D-nek. Tétel 1.2.
Ezzel ekvivalens leírást ad Lovász és Yemini (1982) tétele:
Egy G = (V, E), 2n − 3 irány-élb®l álló gráf akkor és csak akkor irány-merev, ha minden e ∈ E él esetén a G gráfból az e él megduplázásával készített új gráf élhalmaza felbomlik két éldiszjunkt feszít®fa uniójára. Tétel 1.3.
Az irány-éleket és rudakat is tartalmazó G = (V ; D, L) vegyes gráf (G, p) és (G, q) realizációját irány-rúd ekvivalensnek nevezzük, ha bármely uv ∈ D irány-élre a p(u) − p(v) és q(u) − q(v) vektorok egymás konstansszorosai 4
valamint bármely zw ∈ L rúdra kp(z) − p(w)k = kq(z) − q(w)k. A két szerkezetet továbbá irány-rúd kongruensnek hívjuk, ha (G, p)-b®l csak eltolás és ±1-szeres nagyítás segítségével megkaphatjuk (G, q)-t, azaz G bármely két csúcsának távolsága megegyezik a két realizációban, illetve a csúcsok különbség vektorai egymás ±1-szeresei. Az irány-rúd merevség és globális irány-rúd merevségség de niálása a (G, p) rúd-szerkezet esetéhez hasonlóan történik. A következ® ábrán egy olyan (G, p) szerkezetet láthatunk, mely irány-rúd merev, de nem globálisan irány-rúd merev (hiszen létezik olyan (G, q) vele irány-rúd ekvivalens realizáció, amely nem irány-rúd kongruens vele). Az ábrákon szaggatott piros szakaszok jelölik a rudakat és fekete folytonos szakaszok jelölik az irány-éleket.
Figure 1: (G, p) realizációja Gnek
Figure 2: (G, q) realizációja G-nek
A G = (V ; D, L) gráfot irány-rúd merevnek, illetve globálisan irány-rúd merevnek nevezzük, ha tetsz®leges generikus (G, p) realizációja irány-rúd merev illetve globálisan irány-rúd merev. Fontos és sokat vizsgált tulajdonsága a gráfnak a redundáns irány-rúd merevség. Egy G = (V ; D, L) vegyes gráfot redundánsan irány-rúd merevnek nevezünk, ha tetsz®leges él elvétele után irányrúd merev marad a gráf. A G vegyes gráf kétdimenziós irány-rúd merevségére Servatius és Whiteley (1999) adott kombinatorikus karakterizációt. A globális irány-rúd merevség kérdése a mai napig nyitott. Egy (G, p) szerkezetet korlátosnak mondunk, ha létezik olyan K > 0 konstans, hogy bármely vele ekvivalens (G, q) szerkezet esetén tetsz®leges u, v ∈ V csúcspárra kq(u) − q(v)k ≤ K teljesül. Egy G = (V ; E) (ahol E -ben lehetnek irány- és/vagy hossz-élek) gráfot generikusan korlátosnak nevezünk, ha bármely generikus (G, p) realizációja korlátos. A szakirodalomban el®forduló fontos kérdés a globális irány-rúd merevség és redundáns irány-rúd merevség kapcsolata, miután a kapcsolat leírása elvezethet a globális irány-rúd merevség jellemzéséhez. A fenti kérdés többek között felvet®dött már Jackson és Jordán (2005)-ös cikkében is. Jackson és Keevash 5
(2009b) cikke a korlátosság segítségével ad kapcsolatot a két fogalomra a két dimenziós esetben. Az els® tétel rúd, a második tétel irány-él elhagyása utáni irány-rúd merevséget vizsgálja.
Tegyük fel, hogy G = (V ; D, L) globálisan irány-rúd merev és |L| ≥ d, ekkor G\{e} irány-rúd merev lesz minden e ∈ L esetében.
Tétel 1.4.
Legyen G = (V ; D, L) globálisan irány-rúd merev gráf és tekintsük a d = 2 dimenziós esetet. Tegyük fel, hogy az e ∈ D élre G\{e}-nek van nem egy csúcsot tartalmazó irány-rúd merev részgráfja. Ekkor a G\{e} irány-rúd merev vagy generikusan nem korlátos. Tétel 1.5.
Mindkét tétel bizonyításához szükséges a generikus korlátosság jellemzése. Ez motiválta a dolgozatunkat, illetve Bill Jackson and Peter Keevash (2009a) cikkét is, melyek egymástól függetlenül, egyid®ben, különböz® technikák felhasználásával készültek. A dolgozat célja tehát egy algoritmus és ezáltal kombinatorikus karakterizáció megadása tetsz®leges vegyes gráf generikus korlátosságának eldöntésére. Fontos, hogy generikus (G, p) realizációk korlátosságát vizsgáljuk csak, máskülönben nem tudnánk a G gráf korlátosságára kombinatorikus karakterizációt adni. Ezt egy rövid példán keresztül szemléltetjük:
Figure 3: Nem korlátos (G, p) Figure 4: Korlátos (G, p) realizációja realizációja G-nek G-nek A G generikusan korlátos gráf 3. ábrán látható (G, p) realizációja nem generikus, mert az AB és DC élek párhuzamosak. Ebben az esetben a realizáció korlátos sem lesz az el®bb említett élek párhuzamossága miatt. Ezzel ellentétben a 4. ábrán szerepl® generikus (G, p) szerkezet már korlátos. A dolgozat a következ®képpen épül fel. A bevezet® második felében a dolgozat során felhasznált de níciókat és jelöléseket adjuk meg, majd a második fejezetben az algoritmus helyes m¶ködésének igazolásához szükséges állításokat látjuk be. A harmadik fejezet els® részében megadjuk az algorimusunkat és felhasználva az el®z® fejezet eredényeit belátjuk helyességét. A fejezet második 6
részében megadunk egy eljárást, mely segítségével nem korlátos (G, p) realizáció esetén tetsz®leges nagyságú, vele ekvivalens (G, q) realizációt tudunk készíteni. A harmadik fejezet els® felében a tetsz®leges nagyságú realizációt készít® eljárás segítségével bebizonyítjuk, hogy a két különböz® hossz-él de nícióra felírt korlátossági probléma ekvivalens. A fejezet második felében belátjuk, hogy a kapott algoritmus ugyanazt a szükséges és elégséges feltételt generálja, mint ami Bill Jackson és Peter Keevash (2009a) cikkében is szerepel. 1.2
Jelölések
A következ®kben G = (V ; D, K) vegyes gráfokkal foglalkozunk, melyek olyan élcímkézett irányítatlan gráfok, ahol az élek irány-élek (D) és kötelek (K és számuk legyen m) lehetnek. A csak irány-éleket tartalmazó gráfot irány-gráfnak, míg a csak köteleket tartalmazó gráfot kötél-gráfnak nevezzük. Egy (G, p) szerkezetet triviális realizációnak hívunk, ha minden u, v ∈ V -re p(u) = p(v). Általában triviális realizáció alatt a (0,0,..,0)-ba eltolt változatot szoktuk érteni. A (G, p) szerkezetet generikusnak nevezzük, ha a realizáció tetsz®leges csúcsát (0,0,...,0)- ba eltolva a többi csúcs koordinátáinak halmaza a racionális számtest fölött algebrailag független, azaz nem létezik olyan egész együtthatós, többváltozós, nem azonosan nulla polinom, melynek van a koordináták halmazából kikerül® gyöke. A (G, p) és (G, q ) szerkezetek irány-kötél ekvivalensek, ha minden uv ∈ D irány-élre teljesül q(u) − q(v) = λ(p(u) − p(v)) valamilyen λ skalárral és minden uv ∈ K kötélre fennáll kp(u) − p(v)k ≤ cuv és kq(u) − q(v)k ≤ cuv valamilyen el®re megadott cuv konstanssal. A korlátosság vizsgálata szempontjából ez a feltétel lényegében egyenérték¶ azzal, hogyha a kötél csúcsainál koordinátánként követeljük meg a korlátos távolságot, azaz −cuv ≤ pi (u) − pi (v) ≤ cuv minden uv ∈ K -ra és i ∈ {1, ..., d}-re. Ennek oka, hogy ha kp(u)−p(v)k2 ≤ c2uv , akkor |pi (u)−pi (v)| ≤ cuv , valamint ha |pi (u)−pi (v)| ≤ cuv minden i ∈ {1, ..., d}-re, akkor kp(u) − p(v)k2 ≤ dc2uv . Tehát megválaszthatóak a konstansok úgy, hogy az egyik féleképpen megadott kötél feltételt teljesít® realizációk automatikusan teljesítsék a másik módon megadott kötél feltételt. Miután a korlátosság kérdése nem függ a konstansok pontos értékét®l, ezért a kétfajta megadása a feltételnek ugyanazt a korlátossági kérdést adja. Vegyük a G = (V ; D) irány-gráf egy olyan (G, p) realizációját, melyben 7
p(1) = (0, 0, ..., 0), azaz az 1-essel jelölt csúcs helye a d-dimenziós térben a
(0,0,...,0) koordinátájú pont. Tekintsünk egy olyan (d − 1)|D| × (d|V | − d)-es mátrixot, melyben minden egyes D-beli élhez d−1 sor és minden u ∈ V (u 6= 1) csúcshoz d darab egymás melletti oszlop tartozik (az i + 1-edik (i>0) sorszámú csúcshoz a d(i − 1) + 1,...,di-edik oszlop tartozik). Ezután vegyük minden e = uv ∈ D élhez tartozó hp(u) − p(v)i⊥ tér egy Be = (p1 (e)T , p2 (e)T , ..., pd−1 (e)T )T bázisát (ahol Be (d − 1) × d-es mátrix), és az e élhez tartozó sor u csúcscsal címkézett d darab oszlopába írjuk be Be -t, míg a v csúccsal címkézett d oszlopába −Be -t. Az u = 1 esetben Be , míg v = 1 esetén −Be nem kerül bele a mátrixba. A maradék részét a mátrixnak töltsük fel 0-kal. Az így kapott mátrixot nevezzük a (G, p) realizáció irány-mátrixának és jelöljük D(G, p)-vel. Könnyen észrevehet®, hogy a (G, p) realizáció csúcsaiból képzett T x = p(2), p(3), ..., p(|V |) oszlopvektor kielégíti a D(G, p)x = 0 egyenletrendszert. Továbbá elmondható, hogy egy (G, q) szerkezet, melynek egyes sorszámú csúcsa a (0, 0, ..., 0)-ba van eltolva, pontosan akkor irány-ekvivalens (G, p)-vel, ha a (G, q) realizációból képzett y vektor kielégíti a D(G, p)y = 0 egyenletrendszert. Ezután vezessük be a váz de nícióját. A (H, f ) rendezett párt váznak nevezzük, ahol H = (V, E) gráf és f : E → Rd leképezés. A váz F (H, f ) incidencia mátrixa egy |E|×d(|V |−1) mátrix, ahol a sorokat a H gráf éleinek segítségével indexeljük, míg oszlopainak d méret¶ csoportjait a csúcsok szerint (az egyes sorszámú csúcshoz tartozó oszlopokat kihagyjuk a mátrixból). Hasonlóan az irány-mátrixhoz, az e = uv ∈ E élhez tartozó sor u csúcshoz tartozó szakaszába f (e)-t, míg v -hez tartozó szakaszába −f (e)-t írunk, végül a mátrixot 0-kal töltjük fel. Legyen H = (d − 1)G = (V, (d − 1)D) a G = (V, D) irány-gráf éleinek d − 1-szerezésével gráf. Megjegyezzük, hogy a (G, p) szerkezet D(G, p) irány-mátrixa egyben a (H, f ) váz (H = (d − 1)G) egy F (H, f ) incidencia mátrixa is, ahol az f : (d − 1)D → Rd függvény értékeit a hp(u) − p(v)i⊥ altér egy tetsz®leges bázisa adja. A bázis megadható úgy, hogy minden bázisvektor koordinátája a p(u) − p(v) vektor koordinátáinak ±1-szeresei és a 0 érték közül kerüljenek ki. Az F (H, f ) mátrix sorai nem feltétlenül függetlenek, azaz tartalmazhatnak fölösleges információt. A Bill Jackson (2007) 1.4. tételéb®l következ®en független sorokból álló incidencia mátrixot hozhatunk létre, amelynek rangja megegyezik az irány-mátrix rangjával. Ezt a mátrixot nevezzük minimális incidencia mátrixnak. Jelöljük iE (X)-szel a G = (V, D) irány-gráf E ⊆ D élhalmazából azon 8
irány-élek számát, melyek mindkét végpontja az X ⊆ V csúcshalmazból kerül ki. Legyen H = (V, E) egy tetsz®leges gráf és I(H) = {D ⊆ E : iD (X) ≤ d|X| − (d + 1) ∀X ⊆ V,
ahol
|X| ≥ 2}
(1.1) élek egy halmazarendszere. Legyen B = arg max |D| D∈I(H)
(1.2)
és jelöljük H 0 = (V, B)-vel az ezen élek által meghatározott gráfot. Ezentúl a (H 0 , f 0 ) váz alatt a (H, f ) váz B-beli élek által meghatározott részét értjük. Tétel 1.6.
A fenti jelöléseket használva teljesülni fog, hogy r D(G, p) = r F (H 0 , f 0 ) ,
(1.3)
ahol r(A) az A mátrix rangját jelöli. A fent megadott H 0 gráf azért is érdekes, mert teljesíti Nash-Williams tételében (Nash-Williams (1964)) szerepl® feltételt, azaz:
Egy G = (V, E) gráf, melyben |E| = d|V | − d akkor és csak akkor bomlik fel d darab éldiszjunkt feszít®fa uniójára, ha iE (X) ≤ d|X| − d.
Tétel 1.7.
Legyen G = (V, D) irány-gráf és (G, p) egy generikus realizációja. Azt mondjuk, hogy a (G, p) realizáció teljesíti a (H, f ) vázban meghatározott feltételeket, ha a realizáció csúcsaiból készített d(|V |−1) dimenziós p(2), p(3), .. T .., p(|V |) oszlopvektor megoldása az F (H, f )x = 0 egyenletrendszernek. Végül de niáljuk az összehúzás m¶veletét. Rendezzük tetszés szerint csoportokba a G = (V, D) gráf csúcsait, majd húzzuk össze a csoportok tagjait egy-egy új csúcsba. Az így kapott G+ = (V + , D+ ) gráf élei az eredeti G gráf azon élei lesznek, melyek a csoportok között vezettek. Ezt a m¶veletet nevezzük a G gráf összehúzásának. A (H, f ) váz összehúzása is hasonlóan történik, annyi különbséggel, hogy itt egy új f + : D+ → Rd függvényünk lesz, mely az eredeti f függvényünk D+ ⊂ D élhalmazra vett megszorítása.
9
2
Tételek az algoritmushoz
Ebben a fejezetben el®készületeket teszünk egy tetsz®leges G = (V ; D, K) vegyes gráf generikus korlátosságát eldönt® algoritmus megadására.
Legyen G = (V, D) tetsz®leges irány-gráf és jelöljük H = (V, D0 )vel a (d−1)G gráfot. Legyen B ⊆ D0 a maximális nagyságú élhalmaz I(H)-ban és H 0 = (V, B). Ekkor tetsz®leges (H 0 , f ) vázhoz van olyan nemtriviális (G, p) realizációja a G gráfnak mely teljesíti a vázban foglalt feltételeket.
Lemma 2.1.
Bizonyítás: A G irány-gráfhoz tartozó váz incidencia mátrixának d|V | − d oszlopa és |D| ≤ d|V | − d − 1 sora van. Miután az F (H 0 , f )x = 0 egyenletrendszer homogén ez maga után vonja, hogy végtelen sok megoldása lesz az egyenletrendszernek. Tetsz®leges nem azonosan nulla megoldása pedig meghatározza egy nemtriviális, a (H 0 , f ) vázban szerepl® megkötéseket teljesít® (G, p) realizációját a G gráfnak. Legyen (G, p) a G = (V, D) irány-gráf generikus realizációja, továbbá jelöljük (H, f )-fel a (G, p) által meghatározott minimális vázat és F (H, f )fel a minimális incidencia mátrixot. Tekintsük a G gráf egy G∗ = (V ∗ , D∗ ) összehúzottját, amely egyben meghatározza a (H, f ) váz egy (H ∗ , f ∗ ) összehúzását is, és tegyük fel, hogy a H ∗ = (V ∗ , E ∗ ) gráfra teljesül a következ® két összefüggés: Állítás 2.2.
|E ∗ | ≥ d|V ∗ | − d , iE ∗ (X) ≤ d|X| − d ∀X ⊂ V ∗ .
(2.1) (2.2)
Ekkor a G∗ gráfnak csak a triviális lesz az egyetlen olyan realizációja, mely teljesíti a (H ∗ , f ∗ ) vázban foglalt feltételeket. Bizonyítás: Tegyük fel indirekten, hogy létezik olyan nem triviális (G∗ , p∗ ) T szerkezet, melyb®l készült x = p∗1 (2), ..., p∗d (2), ..., p∗1 (|V ∗ |), ..., p∗d (|V ∗ |) oszlopvektor kielégíti az F (H ∗ , f ∗ )x = 0 egyenletrendszert. Els® lépésként belátjuk, hogy a H ∗ gráf tetsz®leges összehúzottjára is teljesülni fog a (2.1) feltétel. Az 1.7. tételb®l következ®en H ∗ -ban van d éldiszjunkt feszít® fa. Tetsz®leges összehúzását véve a gráfnak, az összehúzott gráfban is lesz d éldiszjunkt feszít® fa, így teljesülni fog rá a (2.1) feltétel. Csoportosítsuk ezután a G∗ gráf csúcsait aszerint, hogy a (G∗ , p∗ ) realizációban egy pontba esnek-e. A H ∗ gráf csúcshalmaza megegyezik a G∗ gráf 10
csúcshalmazával, így a H ∗ gráfban az el®bb kapott csúcscsoportokat összehúzva a (2.1) feltételt teljesít® gráfot kapunk. Ezentúl a G∗ és H ∗ gráfokból a fenti csoportok összehúzásával kapott gráfokkal fogunk tovább dolgozni és az egyszer¶ség kedvéért ezen gráfokat fogjuk G∗ -gal és H ∗ -gal jelölni. Tehát összefoglalva a G∗ gráf olyan (G∗ , p∗ ) realizációjával dolgozunk ezentúl, melyre tetsz®leges u∗ , v ∗ ∈ V ∗ csúcspárra p∗ (u∗ ) 6= p∗ (v ∗ ) teljesül és a G∗ -hoz tartozó H ∗ = (V ∗ , E ∗ ) gráfra teljesülni fog a (2.1) feltétel. A (2.1) feltételb®l következik, hogy az F (H ∗ , f ∗ ) mátrix sorainak száma legalább akkora, mint oszlopainak száma. Az indirekt feltevés szerint az F (H ∗ , f ∗ )x = 0 egyenletrendszernek létezik nem triviális megoldása, így létezik olyan e∗ = u∗ v ∗ ∈ E ∗ éle a H ∗ gráfnak, melyhez tartozó F (H ∗ , f ∗ ) mátrixbeli sor benne van a többi sor által generált altérben. Jelöljük A ⊂ V -val az u∗ illetve B ⊂ V -vel a v ∗ csúcshoz tartozó, G gráfbeli csúcshalmazokat. Különböztessünk meg két esetet az A és B csúcshalmazok között vezet® irány-élek száma szerint. Az els® esetben tegyük fel, hogy két vagy több irány-él vezet A és B között G-ben. A (G, p) realizáció generikuságából következik, hogy ezek páronként nem párhuzamosak. Minden ilyen élhez (H, f ) egy d − 1-dimenziós normálalteret határoz meg, amelyek így páronként különböznek. Összehúzás hatására az élekhez tartozó normálalterek nem változnak meg, így e∗ élhez egy d dimenziós normálalteret fog a (H ∗ , f ∗ ) váz meghatározni, ami ellentmond a p∗ (u) 6= p∗ (v) feltevésünknek. Második esetben tegyük fel, hogy az A és B csúcshalmazok között csak egy ˆ ∗ -gal a H ∗ gráfból irány-él vezet a G gráfban és legyen ez uv ∈ D. Jelöljük H az e∗ él elhagyásával kapott gráfot, e ∈ E -vel az e∗ él H gráfbeli megfelel®jét ˆ -pal a H gráfból az e él elhagyásával nyert gráfot. A jelöléseket alkalés H ˆ f ) váz összehúzásával kapjuk a (H ˆ ∗ , f ∗ ) vázat, mazva elmondható, hogy a (H, ˆ ∗ , f ∗ ) incidencia mátrix sorai meghatározzák az egész amelyhez tartozó F (H F (H ∗ , f ∗ ) mátrixot. A (H, f ) minimális váz de níció szerint a G gráf minden g ∈ D irány-éléhez egy d − 1 dimenziós normálalteret határoz meg, így a (H ∗ , f ∗ ) összehúzott váz is a G∗ gráf minden g ∗ ∈ D∗ éléhez egy d − 1 dimenziós normálalteret határoz meg. A p∗ (u∗ ) 6= p∗ (v ∗ ) feltevésb®l következik, hogy a (H ∗ , f ∗ ) váz az u∗ v ∗ ∈ D∗ élnek egy pontosan d − 1 dimenziós alterét fogja meghatározni. A vázak összehúzása során az irányfeltételek nem változhatnak meg, így elmondhatjuk, hogy az uv ∈ D élnek a (H, f ) váz által meghatározott d − 1 dimenziós normálaltere megegyezik u∗ v ∗ ∈ D∗ él (H ∗ , f ∗ ) váz által 11
meghatározott pontosan d − 1 dimenziós normálalterével. Összefoglalva az edˆ f ) váz egyértem¶en meghatározza az u∗ v ∗ ∈ D∗ élhez tartozó digieket a (H, d − 1 dimenziós normálalteret, ami megegyezik az uv ∈ D élhez tartozó d − 1 ˆ f ) váz meghatározza az uv ∈ D élhez dimenziós normálaltérrel, tehát a (H, tartozó d − 1 dimenziós normálalteret. ˆ f) Különböztessünk meg két alesetet. Amennyiben f (e) benne van a (H, váz által meghatározott d − 1 dimenziós alterében az uv ∈ D élnek, úgy ellentmondásra jutottunk azzal, hogy a (H, f ) minimális váz F (H, f ) minimális incidencia mátrixának sorai lineárisan függetlenek. A második esetben tegyük fel, hogy az f (e) vektor nincs benne a d − 1 dimenziós normálaltérben. Ekkor azonban a (H ∗ , f ∗ ) váz az u∗ v ∗ élre egy d dimenziós normálalteret határoz meg, ami azt jelenti, hogy az u∗ és v ∗ csúcs minden realizációban egybe kell essen. Ez viszont ellentmond a (G∗ , p∗ ) realizációra tett feltevésünknek. Tehát csak triviális megoldása van a F (H ∗ , f ∗ )x = 0 egyenletrendszernek, azaz csak a triviális (G∗ , p∗ ) realizáció elégíti ki a (H ∗ , f ∗ ) vázban foglalt irány feltételeket. Frank András (2008)-as jegyzetének 3.5.10 tétele kimondja, hogy: Tétel 2.3.
Egy R = {x : Qx ≤ b} nemüres poliéderre a következ®k ekvi-
valensek: (1) Q oszlopai lineárisan függetlenek. (2) R egyenes-mentes. A fenti tétel segítségével lássuk be a f®tételünket.
A (G, p) irány-kötél szerkezet pontosan akkor nem korlátos, ha a G gráfnak van olyan G+ összehúzottja, amelyben már csak irány-élek szerepelnek és létezik olyan (G+ , q) nem triviális realizációja, amely teljesíti a (G, p) szerkezet által meghatározott (H, f ) minimális váz összehúzásával kapott (H + , f + ) vázban meghatározott feltételeket, azaz a realizáció csúcsaiból képzett T q(2), ..., q(|V + |) d(|V + |−1) dimenziós oszlopvektor megoldása az F (H + , f + )x = 0 egyenletrendszernek. Tétel 2.4.
Bizonyítás: Könnyen látható, hogy egy (G, p) szerkezet pontosan akkor nem korlátos, ha tetsz®leges w ∈ V csúcsot kiválasztva teljesül, hogy minden M természetes számhoz létezik olyan vele irány-kötél ekvivalens (G, q) realizáció, melyben van legalább egy z ∈ V csúcs és annak legalább egy i ∈ {1, ..., d} koordinátája, melyre |qi (w) − qi (z)| > M teljesül. Válasszuk ki így az egyes sorszámú csúcsot és legyen q(1) = (0, 0, ..., 0) minden (G, p)-vel ekvivalens 12
realizáció esetén. Tehát a (G, p) szerkezet pontosan akkor nem korlátos, ha minden M természetes számhoz létezik olyan vele ekvivalens (G, q) szerkezet és a G vegyes gráfban olyan u ∈ V csúcs, hogy |qi (u)| > M teljesül valamely i ∈ {1, ..., d} koordinátára. Készítsük el a (G, p) irány-kötél szerkezet által meghatározott irány-kötél mátrixot, mely az összes szükséges információt tartalmazza a (G, p) szerkezetr®l. Els® lépésben tekintsük az irány-élek által meghatározott részgráfot. A G0 = (V, D) ⊆ G irány-élek alkotta részgráfnak egy (G0 , p) realizációja meghatároz egy F (H, f ) minimális incidencia mátrixot. Legyen k a (H, f ) minimális vázban az élek száma. Ez a mátrix alkotja az irány-kötél mátrix fels® részét. Ezután a következ® 2dm sorba a kötél feltételek szerepelnek, miszerint −cuv ≤ pj (u) − pj (v) ≤ cuv , ha uv ∈ K valamely el®re adott cuv > 0 konstanssal. Így az irány-kötél mátrixunk az alábbi alakú lesz: A=
f1 (e1 ) .... fd (e1 )
0
0
...
−f1 (e1 ) ... −fd (e1 )
... 0
...
0
−f1 (ek )
...
−fd (ek )
0
...
0
1
0
...
0
−1
0
0
...
0
−1
0
...
0
1
0
0
...
0
0
1
0
...
0
−1
0
...
0
0
−1
0
...
0
1
0
...
0
...
0
0
1
... 0
...
0
−1
0
Legyenek továbbá x = (q(2), q(3), ..., q(n))T ,
(2.3)
0 = (0, 0, ..., 0)T
(2.4)
d(|V | − 1) dimenziós oszlopvektorok, és b = (0, 0, ..., 0, c1 , ..., c1 , c2 , ..., c2 , ..., cm , ..., cm )T k + 2dm dimenziós oszlopvektorok.
A G gráf (G, p)-vel ekvivalens (G, q) realizációiból képzett (2.3) alakú vektorok alkotják az Ax ≤ b egyenletrendszer megoldásainak halmazát, ahol az els® k darab egyenl®tlenség helyett egyenl®ség áll fenn. A (G, q) realizációk
13
els® csúcsát (0,0,...,0)-ba lerögzítettük, így pontosan akkor korlátos a (G, p) realizáció, ha a fenti Ax ≤ b egyenletrendszerrel meghatározott poliéder nem tartalmaz félegyenest. Az irány-kötél mátrix egy szimmetrikus poliédert határoz meg, így a (G, p) szerkezet korlátossága ekvivalens az {x : Ax ≤ b} poliéder egyenesmentességével. A 2.3 Tételb®l következ®en az egyenesmentesség ekvivalens az irány-kötél mátrix oszlopainak függetlenségével, azaz hogy az Ax = 0 egyenletrendszernek csak a triviális a jó megoldása. Próbáljuk gráfok segítségével megoldani az átfogalmazott problémát, azaz nézzük meg, hogy milyen esetben lesz végtelen sok megoldása az egyenletrendszernek. Tekintsük a z oszlopvektort (2.3) alakban, azaz mintha |V | − 1 darab d dimenziós csúcsot egy vektorba tárolnánk egymás után. Az A mátrix els® k sora a (G, p) realizáció irány-éleire vonatkozó megkötéseket tartalmazza, azaz olyan (G, q) realizációt keresünk, melyre az irány feltételek teljesülnek. Itt fontos megjegyeznünk, hogy két csúcs közötti irány-él feltétel nem sérül, ha a két csúcs a realizációban egy pontba esik. A következ® dm sor pedig azt fejezi ki az Ax = 0 egyenletrendszerben, hogy a kötelek végpontjai egybeesnek. Azaz átfogalmazva a problémát olyan összehúzását keressük a gráfnak, melyben csak irány-élek szerepelnek (tehát a kötelek csúcsai össze vannak húzva) és van nem triviális realizációja az összehúzásnak. Amennyiben találunk ilyent, a (G, p) realizációnk nem korlátos, ellenkez® esetben pedig korlátos.
14
3
3.1
Az algoritmus
Az algoritmus megadása
Ebben a részfejezetben megadunk egy algoritmust, mely eldönti egy G vegyes gráfról, hogy generikusan korlátos-e. Az eljárás helyességének belátásához az el®z® fejezetben belátott állításokat fogjuk felhasználni. Az algoritmusunk célja, hogy találjon egy megfelel® G+ összehúzását a G gráfnak. Induljunk ki egy tetsz®leges (G, p) generikus szerkezetb®l és vegyük az irány-élei által meghatározott (H, f ) minimális váz összehúzása után kapott (H 0 , f 0 ) vázat. Olyan G+ összehúzott gráfot keresünk, melyhez létezik olyan nem triviális (G+ , p+ ) realizáció, amely teljesíti a (H 0 , f 0 ) vázban foglalt megkötéseket, azaz a (p+ (2), ..., p+ (|V + |))T oszlopvektor nem triviális megoldása az F (H 0 , f 0 )x = 0 egyenletrendszernek. Amennyiben az algoritmusunk nem talál ilyen G+ összehúzást, úgy a G gráfunk generikusan korlátos. Els® lépésben a G gráf irány-élei helyett a (1.2)-ban meghatározott élhalmazt írjuk be, így megkapjuk a H gráfunkat. Ezután húzzuk össze a H ˆ gráfban az élek gráfban a kötelek csúcsait egy-egy pontba. Az így kapott H ezentúl az összehúzás után kapott új csúcsok között vezetnek majd. Azon ˆ gráfból, miután semmiéleket, melyek csúcsait összehúztuk, elhagyhatjuk a H ˆ gráf egy lyen plusz megkötést nem tartalmaznak. Ezután keressük meg a H olyan H ∗ = (V ∗ , E ∗ ) részgráfját, melyre teljesül |E ∗ | ≥ d|V ∗ | − d , iE ∗ (X) ≤ d|X| − d ∀X ⊂ V ∗ ,
és amint találunk egyet, húzzuk össze egy pontba. (Nevezzük ezentúl ezen részgráfokat túlhatározottaknak.) Folytassuk az eljárásunkat, amíg már nem találunk több ilyen részgráfot. Amennyiben az eljárás végén egy pontot kapunk, úgy az algoritmus a G gráfot generikusan korlátosnak adja, míg ellenkez® esetben a gráfot generikusan nem korlátosnak mondja. Az algoritmust röviden összefoglalva az alábbi diagrammot kapjuk: 1. Gráfban a kötelek által meghatározott részgráfok összehúzása 2. Ciklus kezd®dik Amíg van túlhatározott részgráf tedd - Húzd össze egy pontba a csúcsait - A túlhatározott részgráfból kiinduló
15
élek ebb®l a pontból indulnak ezentúl Ciklus vége 3. Ha az eredmény egy pont kiír: Korlátos Különben kiír: Nem korlátos. Tétel 3.1.
A fent megadott algoritmusunk helyesen m¶ködik.
Bizonyítás: Az algoritmus kétféle eredménnyel állhat le. Els® esetben az algoritmus nem egy pontot ad vissza eredményként, hanem egy olyan H + = (V + , E + ) gráfot, melyre iE + (X) ≤ d|X| − (d + 1) ∀X ⊆ V + .
(3.1)
Tetsz®legesen megválasztva az f + : E + → Rd függvényt a 2.1 Lemmából következ®en létezik olyan (G+ , p+ ) nem triviális realizáció, mely a (H + , f + ) generikus vázban meghatározott feltételeket teljesíti, azaz a (p+ (2), ..., p+ (|V + |))T oszlopvektor megoldása lesz az F (H + , f + )x = 0 egyenletrendszernek. Így a 2.4. tételb®l következ®en tetsz®leges generikus (G, p) szerkezet nem korlátos lesz, tehát a G gráfunk generikusan nem korlátos. A másik irányhoz be kell látnunk, hogy amennyiben az algoritmus egy pontban áll le, nem lesz olyan nem triviális realizációja az összehúzott G+ gráfnak, mely teljesíti tetsz®leges generikus (G, p) szerkezet által meghatározott (H + , f + ) vázban foglalt megkötéseket. Az algoritmus során csak olyan részgráfokat húzunk össze, amelyeknek a 2.2 Állításból következ®en csak a triviális az egyetlen jó realizációja. Amennyiben ezen eljárás során egy pontot kapunk végeredményül, úgy elmondhatjuk, hogy nem létezik nem triviális realizációjú G+ összehúzottja a G gráfnak, tehát a 2.4 Tételb®l következ®en a G+ gráf generikusan korlátos lesz. A következ®kben az algoritmus m¶ködését szemléltetjük egy rövid példán keresztül kétdimenzióban, generikusan nem korlátos G gráf esetén. Induljunk ki az 5. ábrán látható G vegyes gráfból (piros szaggatott élek a köteleket, a fekete élek az irány-éleket jelölik) és húzzuk össze els® lépésként a kötelek alkotta részgráfokat. Így megkapjuk a 6. ábrán szerepl® gráfot, melyben az {A, C}, {D, F } és {J, H} csúcsok túlhatározott részgráfokat határoznak meg. Ezen részgráfok összehúzása után megkapjuk a 7. ábrát, melyben {D, E} csúcsok által meghatározott részgráf túlhatározott lesz. Ezt összehúzva kapjuk 16
a 8. ábrát, mely nem egy pontból áll és nincs benne túlhatározott részgráf, így az eredeti G vegyes gráfunk generikusan nem korlátos volt.
Figure 5: G gráf (fekete irányél, piros szaggatott kötél)
Figure 6: Kötelek összehúzása utáni állapot
Figure 7: Túlhatározott részgráfok Figure 8: Túlhatározott részgráfok összehúzása után összehúzása után 2 Ezután a d = 3 dimenziós esetben generikusan korlátos G gráfon is szemléltessük az algoritmus m¶ködését. A 9. ábrán láthatjuk a G vegyes gráfot, melyben a korábbiakhoz hasonlóan a piros szín¶ szaggatott vonalak a köteleket, míg a fekete szín¶ vonalak az irány-éleket jelölik. Els® lépésben minden irányélet d − 1 = 2 éllel helyettesítünk (10. ábra), majd elhagyjuk a felesleges információt tartalmazó éleket, azaz olyan H 0 = (V, M ) gráfot veszünk, ahol M a maximális elemszámú halmaza az I (d − 1)G halmazrendszernek (a 11. ábrán egy ilyen megoldás látható). Ezután összehúzzuk a köteleket (az AC kötél összehúzása), melynek eredménye a 12. ábrán látható. Az {A, B} részgráf három élet tartalmaz, tehát túlhatározott részgráf d = 3 dimenzióban, összehúzva a 13. ábrát kapjuk. Az így kapott gráfunk túlhatározott lesz, így összehúzva egyetlen pontot kapunk eredményül, amit a 14. ábrán láthatunk. Tehát megállapíthatjuk, hogy a G gráfunk valóban generikusan korlátos volt.
17
Figure 9: G gráf (fekete irány-él, piros Figure 10: irány-éleket két új élre kiszaggatott kötél) cserélve
Figure 11: Plusz éleket elhagyva
Figure 12: Kötelek összehúzása utáni állapot
Figure 13: Túlhatározott részgráf össze- Figure 14: Algoritmus eredménye: egy pontba összehúzva húzása után 3.2
Generikusan nem korlátos gráf tetsz®legesen nagy realizációja
Egy generikusan nem korlátos G = (V ; D, K) gráf tetsz®leges generikus (G, p) realizációjához el® tudunk állítani az algoritmusunk segítségével tetsz®legesen nagy, vele irány-kötél ekvivalens (G, q) realizációt. Továbbá belátható, hogy a két szerkezet irány-hossz ekvivalens is lesz egymással. Állítás 3.1.
Bizonyítás: G vegyes gráf generikusan nem korlátos, ezért az algoritmusunk nem egy pontot ad eredményül, hanem egy olyan új gráfot, mely teljesíti (3.1)t. Nevezzük ezt a gráfot vég-gráfnak és jelöljük H + = (V + , E + )-szal. Vegyük sorba a vég-gráf csúcsait és tekintsük az ezekhez a csúcsokhoz tartozó (összehúzás el®tti) G gráfbeli részgráfok (G, p) szerkezet által meghatározott realizációit és hivatkozzunk rájuk ezentúl G-komponensekként. Egy olyan (G, q) realizációt fogunk megadni, melyben az egyes G-komponensek eltoltjai szerepelnek úgy, hogy a szerkezet egyúttal (G, p)-vel is ekvivalens legyen. A Gkomponenseken belül a csúcsok helyzete nem változik az eltolás hatására, így 18
a G-komponensek csúcsaira vonatkozó (G, p) szerkezet által megadott irány és kötél megkötések teljesülni fognak a (G, q) szerkezetben is. Miután az összes kötél megkötés a G-komponenseken belül vezet, ezért a G-komponensek között csak irány megkötések vannak. Vezessük be az alábbi jelöléseket: y = (p(t2 ), p(t3 ), ..., p(t|V + | ))T , x = (q(t2 ), q(t3 ), ..., q(t|V + | ))T , 0 = (0, 0, ..., 0)T d(|V + | − 1) dimenziós oszlopvektorok, és jelölje k az élek számát a H + vég-
gráfban. A (G, p) szerkezet által meghatározott, összehúzott (H + , f + ) váz incidencia mátrixa:
C = F (H + , f + ) = 0 0 ...
−f1+ (e1 ) ... −fd+ (e1 )
+ f1 (e2 ) .... fd+ (e2 ) 0 0 ... −f1+ (e2 ) ... −fd+ (e2 ) ... 0 ... 0 −f1+ (ek ) ... −fd+ (ek ) 0 ... 0
.
f1+ (e1 ) .... fd+ (e1 )
Válasszunk ki minden egyes G-komponensb®l egy-egy csúcsot és fejezzük ki a komponens többi csúcsát ennek segítségével. Legyen p(ti ) az i-edik (mi darab csúcsot tartalmazó) G-komponensb®l kiválasztott ti csúcs (G, p) realizációbeli helye. Az i-edik G-komponens többi csúcsának a (G, p) realizációban elfoglalt helyét jelölje p(ti )+wi,1 , p(ti )+wi,2 ,..., p(ti )+wi,mi −1 , ahol a wi,j -k d dimenziós vektorokat jelölnek. Feltehetjük, hogy a (0,0,...,0) koordinátájú pont az els® G-komponensben volt és hogy az a csúcs lett kiválasztva. Nevezzük ezentúl az egyes G-komponensekb®l kiválasztott ti csúcsokat együttesen kiválasztott csúcsoknak. Írjuk fel az eredeti (G, p) realizációban a G-komponensek között vezet® irány-él feltételeket a kiválasztott csúcsokra megszorítva. Fejezzük ki minden rs ∈ D irány-élre a p(r) és p(s) csúcsok között vezet® él irányát a p(ti ) (i = 1, ..., |V + |) csúcsok és wi,j (i = 1, ..., |V + |; j = 1, ..., mi −1) vektorok segítségével. Legyen az s-edik - G-komponensek között vezet® - irány-él egy tet sz®leges normálvektora n1 (s), ..., nd (s) és vezessen a p(ti )+wi,j és p(tk )+wk,l csúcsok között. Így teljesülni fog rá, hogy d X
i,j k,l (pm (ti ) + wm − pm (tk ) − wm nm (s) = 0,
m=1
19
melyet átrendezve a d X
d X i,j k,l pm (ti ) − pm (tk ) nm (s) = wm − wm nm (s)
m=1
(3.2)
m=1
egyenletet kapjuk. A (3.2) alakú egyenletek jobb oldalán lév® értékekb®l alkotott b vektor segítségével az alábbi alakban fejezhet®ek ki a G-komponensek között vezet®, a (G, p) szerkezet által meghatározott minimális vázban lév® megkötések: Cy = b.
(3.3)
A minimális vázat úgy választottuk, hogy az összes szükséges információt tartalmazza, azaz egy (G, q) szerkezet pontosan akkor teljesíti a minimális vázban foglalt feltételeket, ha teljesíti a (G, p) szerkezet D(G, p) irány-mátrixában foglalt feltételeket. Így a (G, q) szerkezetre is pontosan akkor fognak teljesülni a (G, p) realizáció által meghatározott G-komponensek között vezet® irány-él megkötések, ha a (G, q) realizáció kiválasztott csúcsaiból alkotott T x = q(t2 ), ..., q(t|V + | ) vektorra teljesül Cx = b.
(3.4)
A vég-gráf de níciójából következik, hogy tetsz®leges generikus (G, p) szerkezet által meghatározott C = F (H + , f + ) incidencia mátrixra létezik nem triviális (G+ , p+ ) realizációja a G+ összehúzott gráfnak. Ebb®l a (G+ , p+ ) szerkezetb®l nagyítás hatására el®állítható olyan megfelel®en nagy (G+ , p∗ ) realizáció, mely szintén teljesíti az irány-gráfban megkövetelteket. Eltolás hatására az élek irányai nem változnak, így feltehet®, hogy p∗ (1) = (0, 0, ..., 0). Tehát az így megadott (G+ , p∗ ) szerkezet csúcsaiból alkotott z = (p∗ (2), ..., p∗ (|V + |))T vektorra teljesül a Cz = 0
(3.5)
egyenletrendszer. Legyen x = y + z , melyre (3.3)-b®l és (3.5)-b®l következ®en teljesül (3.4). Tehát az egyes G-komponenseket a z vektorban megadott értékek szerint eltolva megfelel®en nagy, (G, p) szerkezettel ekvivalens (G, q) realizációt kapunk. Egy rövid példán fogjuk bemutatni az algoritmus m¶ködését. Induljunk ki a 15. ábrán látható (G, p) realizációjából a G vegyes gráfnak. Az {A, B, C}, 20
{D, E, F, G} és {I, J, H} G-komponensek legyenek rögzítettek az algoritmus-
ban leírtak szerint. A komponenseket a köztük lév® irány-él megkötéseknek megfelel®en egymáshoz képest eltolva tetsz®legesen nagy (G, q) realizáció nyerhet®, melyre egy példát is bemutatunk a 16. ábrán.
Figure 15: Kiindulási (G, p) re- Figure 16: Felnagyított (G, q) alizáció realizáció
21
4
4.1
Következmények, kapcsolatok
A kétféle modell ekvivalenciája
Az els® fejezetben két de níciót adtunk a hossz-élre, attól függ®en, hogy fels® korlátunk (kötél) vagy pontos értékünk (rúd) volt-e a csúcsok távolságára. A következ®kben belátjuk, hogy a különböz® megközelítésekb®l adódó különböz® modellekben a korlátosság problémája megegyezik.
A kötél de nícióval megadott G = (V ; D, K) vegyes gráf pontosan akkor generikusan korlátos, ha rúd de nícióval megadott G0 = (V ; D, L) vegyes gráf is generikusan korlátos.
Tétel 4.1.
Bizonyítás: De níció szerint egy G = (V ; D, K) gráf és egy G0 = (V ; D, L) gráf generikusan korlátos, ha tetsz®leges generikus (G, p) illetve (G0 , p0 ) realizációja korlátos. Tegyük fel, hogy a G gráfunk generikusan nem korlátos és lássuk be, hogy a G0 gráfunk sem az. Vegyük tetsz®leges generikus (G0 , p) realizációját G0 -nek, amit tekinthetünk a G gráf generikus realizációjának is. A 3.2 alfejezetb®l tudjuk, hogy létezik olyan tetsz®legesen nagy, (G0 , p)-vel irány-kötél ekvivalens (G0 , q) realizációja G-nek, melyben a kötelek hossza megegyezik a (G0 , p) szerkezetben megadott kötél hosszakkal. Így a (G0 , q) realizáció egyúttal irány-rúd ekvivalens is lesz (G0 , p)-vel, tehát tetsz®legesen nagy, a (G0 , p)-vel irány-rúd ekvivalens (G0 , q) realizációját el® tudtuk állítani a G0 -nek, így a G0 irány-rúd gráf generikusan nem korlátos. A másik irányhoz tegyük fel, hogy a G0 irány-rúd gráfunk generikusan nem korlátos. Induljunk ki a G gráf egy tetsz®leges generikus (G, p) realizációjából, amely tekinthet® a G0 generikus realizációjának is egyben. Feltevésünkb®l adódóan létezik tetsz®leges nagyságú (G, p)-vel irány-rúd ekvivalens (G, q) realizációja G0 -nek. Az irány-rúd ekvivalencia szigorúbb, mint az irány-kötél ekvivalencia, így a (G, q) irány-kötél ekvivalens is lesz (G, p)-vel, amib®l következik a G irány-kötél gráfunk generikus nem korlátossága. A kötél és rúd modellek különböz® gyakorlati problémák megoldására szolgálnak és viselkedésük is eltér, így kifejezetten hasznos, hogy minél több közös tulajdonságot találjunk bennük.
22
4.2
Gráfelméleti karakterizáció a korlátosságra
A következ®kben megmutatjuk, hogy a Bill Jackson és Peter Keevash (2009a) cikkében szerepl® korlátossági feltétel egybeesik az algoritmus által megadottal. Els® lépésben adjuk meg a tétel kimondásához szükséges H ∗ = (V ∗ , E ∗ ) gráfot. Induljunk ki tetsz®leges G vegyes gráfból, melynek az irány-élei helyére a (1.2)ben meghatározott élhalmazt írjuk. Ezután húzzuk össze a hossz-élek által meghatározott részgráfokat egy-egy csúcsba. Az így kapott gráfot nevezzük H ∗ gráfnak a tétel kimondásában. A feltétel a cikk 4.3 Állításának és 5.1 Tételének kombinációjaként áll el®.
Egy G = (V ; D, L) vegyes gráf akkor és csak akkor generikusan korlátos Rd -ben, ha a G gráf rúd éleinek összehúzásával és irány-éleinek d-1 éllel való helyettesítésével kapott H ∗ gráfban van d darab éldiszjunkt feszít® fa.
Tétel 4.2.
Az algoritmus els® felében mi is a H ∗ gráfot állítjuk el®, tehát elég az algoritmus m¶ködését ett®l a lépést®l vizsgálni. Az algoritmus kétféle eredménnyel állhat le. Az els® esetben az algoritmus eredményeként egy olyan H + = (V + ; E + ) vég-gráfot kapunk, melyre teljesül (3.1). Ekkor azonban nincsen d éldiszjunkt feszít® fa H + -ban, hiszen ahhoz legalább d|V + |−d él kellene. A H + vég-gráf élei a H ∗ gráf diszjunkt részgráfjait kötik össze és ha ezeket a részgráfokat nem lehet d éldiszjunkt feszít® fával összekötni, akkor a H ∗ gráfban sincs d éldiszjunkt feszít® fa. A második esetben az algoritmus úgy áll le, hogy az összes csúcsot összehúztuk egy pontba. Az 1.7 Tételb®l következik, hogy tetsz®leges túlhatározott részgráfban van d éldiszjunkt feszít® fa. Tegyük fel, hogy a túlhatározott részgráf összehúzása után kapott gráfban van d éldiszjunkt feszít® fa. Ekkor az összehúzás el®tti gráfban is van d éldiszjunkt feszít® fa, amelyeket az összehúzott részbeli éldiszjunkt feszít®fák hozzáadásával tudunk megkapni az összehúzás utáni éldiszjunkt feszít® fákból. Ezzel beláttuk, hogy a két különböz® megközelítés ugyanazt a kombinatorikus karakterizációt adja a G irány-rúd gráf generikus korlátosságára. A dolgozatban bemutatott eljárás el®nye, hogy elemibb matematikai módszereket használ fel a bizonyítás során és egy olyan új modellrendszert vezet be (kötél modell), mely lényegesen megkönnyítheti nehezebb problémák vizsgálatát is lineáris viselkedése miatt.
23
References
[1] Frank András, Operációkutatás jegyzet, Frank András honlapja legutolsó frissítés (2008) [2] B. Jackson, Parallel Drawings of Graphs, unpublished (2007) [3] B. Jackson and T. Jordán, Connected rigidity matroids and unique realizations of graphs, J. Combin. Theory Ser. B 94 (2005), 1-29. [4] B. Jackson and P. Keevash, Bounded direction-length frameworks,Bill Jackson's homepage (2009a), submitted. [5] B. Jackson and P. Keevash, Necessary Conditions for the Global Rigidity of Direction-Length Frameworks (2009b),Bill Jackson's homepage submitted [6] G. Laman, On graphs and rigidity of plane skeletal structures, J. Engrg. Math 4 (1970), 331-340. [7] L. Lovász, Y. Yemini: On generic rigidity in the plane, SIAM J. Alg. Discr. Methods 1 (1982), 91-98. [8] C.St.J.A. Nash-Williams, Decomposition of nite graphhs into forests, J. London Math. Soc. 39 (1964), 12. [9] J.B. Saxe, Embeddability of weighted graphs in k -space is strongly NP hard, in: Proc. 17th Allerton Conference in Communications, Control and Computing, 1979, 480-489. [10] B. Servatius and W. Whiteley, Constraining plane con gurations in CAD: Combinatorics of directions and lengths, SIAM J. Disc. Math. 12 (1999), 136-153. [11] W. Whiteley, Some matroids from discrete applied geometry, in: Matroid theory, AMS Contemporary Mathematics, vol. 197, (1996),171-313.
24
