Matematika | Felsőoktatás » Ujváry-Menyhárt Zoltán - Síkgráfok és konvex poliéderek

Diplomamunka Skgrfok s konvex poliderek Ujvry-Menyhrt Zoltn Tmavezet: Szab Lszl ELTE TTK 1997. Tartalomjegyzk 1. Bevezets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 2 2. Poliderek grfjai : : : : : : : : : : : : : : : : : : : : : : : : : : : : 4 2.1 Koebe reprezentcis ttele 4 2.2 Whitney ttele 11 2.3 Steinitz-ttel 13 3. lrint poliderek : : : : : : : : : : : : : : : : : : : : : : : : : : : 23 3.1 3- sszef gg s kgrfok reprezentcija 23 3.2 G mb t lben rint poliderek 34 4. G mbbe rhat poliderek : : : : : : : : : : : : : : : : : : : : : : : 36 4.1 G mbbe s g mb k r rhatsg IE3-ben 36 4.2 IH3-beli konvex idelis cscs poliderek 40 Irodalom : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44 1 1. Bevezets A szakdolgozat clja, hogy sszefoglalja a 3

dimenzis, konvex poliderek kombinatorikus struktrja s geometriai tulajdonsgai k z tti sszef ggsekkel kapcsolatos ismereteket. Ebben a tmban egy igen alapvet ttel Steinitz ttele, melyhez sz ksg van a k vetkez den cikra: 1.1 Den ci Egy P polider G(P) grfja olyan grf, melynek cscsai a P polider cscsainak feleltethetk meg, kt cscs k z tt pedig akkor fut l, ha a poliderben a megfelel kt cscs k z tt van l (azaz mindkt cscs rajta van egy 1-dimenzi s lapon). Ismert, hogy a konvex poliderek grfja s kgrf. Ez egyszeren belthat, pldul gy, hogy az leit a polider egy bels pontjbl felvet tj k a pontot tartalmaz g mbre. A grf lapjai megfeleltethet k a polider lapjainak 1.2 Den ci Kt konvex polider kombinatorikusan ekvivalens, ha a grfjaik izomorfak, valamint ez az izomorzmus kiterjeszthet a lapokra is. (Vagyis egy lapot hatrol k rnek a msik grfban is egy lapot hatrol k r felel meg.) Steinitz ttele szerint egy (legalbb 4 pont) grf akkor s

csak akkor lehet egy konvex polider grfja, ha s kbarajzolhat s 3- sszef gg . Whitney ttele azt mondja ki, hogy egy 3- sszef gg s kgrf begyazsa a g mbfelsz nbe homeomorzmus erejig egyrtelm. Ebb l a kt ttelb l az is k vetkezik, hogy a 12 Den ciban nem kellene foglalkozni a lapokkal, vagyis kt polider pontosan akkor kombinatorikusan ekvivalens, ha a grfjaik izomorfak. A Steinitz-ttel bizony tshoz fel fogom hasznlni Koebe s kgrfokra vonatkoz reprezentcis ttelt Koebe 1935. vb l szrmaz ttele szerint, egy s kbarajzolhat grf reprezentlhat pronknt k z s bels pont nlk li k rlemezek olyan rendszervel, hogy a grf cscsainak felelnek meg a k r k, kt k r (k v lr l) rinti egymst, ha a megfelel cscsok k z tt a grfban vezet l, egybknt pedig a k r k diszjunktak. Ennek egy k vetkezmnye az az ismert grfelmleti ttel, mely szerint ha egy grf s kbarajzolhat, akkor egyenes vonalakkal is s kbarajzolhat. Koebe ttelnek a tmval kapcsolatos er s tse

szerint (mely 1990-ben ksz lt), ha a s kgrf 3- sszef gg , akkor a grf s a dulisa egyszerre reprezentlhat egy-egy k rrendszerrel, melyeknek a grfok az rintkezsi grfjai s a lapokhoz tartoz k r k a megfelel lap cscsaihoz tartoz k r ket mer legesen metszik. Ebb l sztereograkus projekci seg tsgvel addik, hogy minden (legalbb 4 pont) 3- sszef gg G s kgrfhoz van olyan polider, amelynek G a grfja s az lei rintenek egy adott g mb t. Ennek a ttelnek k vetkezmnyeknt a Steinitz ttel is addik A ttel g mb helyett tetsz leges konvex halmazra igaz, vagyis brmely konvex halmazhoz brmely polidernek van lrint kombinatorikus ekvivalense. A ttel nem ltalnos that magasabb dimenzij poliderekre, mivel ott a k r l rs mindenfle t pusra1 van ellenplda. 1 akrhny dimenzis lapokra kvetelhetjk, hogy rintsk a gmbt 2 A tma egy msik rdekes krdse Jakob Steiner 1832-ben rt k nyvb l szrmazik. Ebben Steiner szmos rdekes krdst vetett fel, melyek k z

l mr csak kett maradt megoldatlan 150 vvel ks bb. Az egyik krds az volt, hogy mely esetben van egy konvex polidernek olyan kombinatorikus ekvivalense, amely g mbbe rhat. 1928-ig nem ismertek olyan konvex polidert, amelynek nincs kombinatorikus ekvivalense, amely g mbbe rhat. Emellett a konvex poliderek kombinatorikus karakterizcija is megoldatlan volt. Mindkt problmt Ernst Steinitz oldotta meg, a mr fent eml tett ttellel karakterizlta a konvex poliderek grfjait s ugyanabban a cikkben mutatott polidereknek vgtelen sok kombinatorikus t pust, amelyek nem rhatk g mbbe. Steiner krdsre a vlaszt vg l Igor Rivin 1991. s 1993 k z tti cikkeiben adta meg Ez a hiperbolikus tr idelis cscspont2 polidereinek karakterizcijbl addik a Cayley-Klein modell seg tsgvel. Csak a felttelek sz ksgessgvel foglalkozunk A felttelek elgsgessgt az Alekszandrov ltal kifejlesztett dierencilgeometriai mdszerek tovbbfejlesztsvel oldotta meg Rivin. Ez lnyegesen

k l nb zik a dolgozatban szerepl mdszerekt l, ezrt ezeket itt nem trgyaljuk. 2 vgtelen sugar gmbbe rt 3 2. Poliderek grfjai 2.1 Koebe reprezentcis ttele 2.1 Ttel (Koebe,1936) Legyen G tetszleges skbarajzolhat grf, cscsa- inak a halmaza V(G)={v1, : : : ,vn}, leinek a halmaza E(G). Ekkor van olyan k relhelyezs3 a skon, mely n k rlemezbl ll: C ={c1, : : : ,cn} s kt k r (ci s cj ) akkor rinti egymst, ha a megfelel cscsok szomszdosak (vivj 2 E (G)), egybknt pedig diszjunktak a k r k. Megjegyzs. Ha egy ilyen k relhelyezs adott, inverzi illetve brmilyen ha- sonlsgi transzformci seg tsgvel nyilvn jabb megfelel k relhelyezsekhez jutunk (termszetesen k r k n k v li pontbl kell invertlni). Thurston bebizony totta, hogy ha a s kgrf maximlis (vagyis hromsz glapokbl ll), akkor ett l a transzformcitl eltekintve egyrtelm a reprezentci. Bizony ts. (Colin de Verdiere 1989, Marden, Rodin 1990) A ttelt elg maximlis s kgrfokra

bizony tani. Ha G-ben lenne els fok cscs, azt elhagyhatjuk, s ha az gy kapott G szintn s kgrf lesz, tovbb ha ez reprezentlhat k rrendszerrel, akkor ott a megfelel k rh z tudunk elg kicsi rint k rt hzni, amely a t bbi lemezt l diszjunkt. A k l nb z sszef gg komponenseket elg k l n reprezentlni, a reprezentcik elhelyezhet k a s kon gy, hogy ne metszk egymst (elegend en tvol egymstl). Az egy pontbl ll grf esete nyilvnval, gy feltehetj k, hogy a G grf sszef gg , s minden pont foka legalbb 2. Ha G-ben van egy lap, amely nem hromsz g, akkor ennek a lapnak a belsejben vegy nk fel egy j cscsot, s ezt k ss k ssze a lap cscsaival. Ez az eljrs 2- sszef gg grfokra minden lapot hromsz gekre bont. Ha a grf nem 2- sszef gg , akkor az elvg pontok bizonyos tartomnyokat t bbsz r sen hatrolnak, de a hromsz gelsnl csak egyszer lehet ket sszek tni az j csccsal, hogy a grf egyszer maradjon. Emiatt, mg a hromsz gels el tt, egy j cscsot vesz nk hozz

az elvg ponthoz a megfelel lap belsejben, ezt sszek tj k az elvg ponttal, valamint az elvg pontbl kiindul, a lapot szomszdosan hatrol kt l msik vgpontjval. Ennek eredmnyekppen kapunk egy egyszer s kbarajzolhat grfot, ahol az adott elvg pont a megfelel lap hatrn mr eggyel kevesebbszer fordul el , s nem keletkezett j elvg pont. Ezt az eljrst vges sokszor alkalmazva 2- sszef gg grfot kapunk, amelynek a lapjait mr hromsz gekre bonthatjuk a korbban le rt mdon. (Lsd az 1 brt!) gy minden tatomnyt hromsz glapokra bontottunk. Ha az gy kapott G s kgrf reprezentlhat k rrendszerrel, akkor a reprezentcibl elhagyva az j cscsoknak megfelel k rt, G-nek egy j reprezentcijt kapjuk. 0 0 3 nem felttlenl kongruens krkb l ll 4 1. bra Egy grf lapjainak felbontsa hromszglapokra. Legyen G egy x, hromsz glapokbl ll, s kbarajzolhat grf, cscsai V (G) = fv1 : : :  vng, leinek halmaza E  lapjainak halmaza (belertve a k ls

vgtelen tartomnynak megfelel lapot is) pedig F . Az Euler-ttelb l: jV j ; jE j + jF j = 2 : Mivel minden lap hromsz g: 3jF j = 2jE j, amelyekb l: jF j = 2jV j ; 4 = 2n ; 4  jE j = 3n ; 6 : n X Legyen r=(r1, : : : ,rn) tetsz leges vektor melyre ri = 1. A G i=1 grf minden lapjhoz rendelj nk egy hromsz get a k vetkez mdon: a vivj vk laphoz rendelj nk egy ri,rj ,rk sugar, egymst pronknt k v lr l rint k r k k zppontjai ltal alkotott hromsz get (vagyis (ri + rj ) (ri + rk ) (rj + rk ) oldal hromsz get). A hromsz g cscsainak megfelelnek a grf vi vj  vk cscsai Minden vi cscshoz legyen r (vi) a vi-vel szomszdos lapokhoz rendelt hromsz gekben a vi-nek megfelel cscsoknl lv sz gek sszege. Ha r(vi) = 2 teljes l a G minden cscsra a k ls tartomny cscsain k v l, akkor ezek a hromsz gek egymshoz ragaszthatk a megfelel lek mentn a s kbarajzolsnak megfelel en, s gy a cscsokba ri sugar k r ket rva, G-nek egy megfelel reprezentcijt kapjuk (a k ls

tartomny a hozz rendelt hromsz g komplementere lesz). A k ls tartomnnyal nem kell k l n foglalkozni, mert a t bbi hromsz g sszeragasztsa utn kapott hromsz glap egybevg az ehhez a tartomnyhoz rendelt hromsz glappal. IRn -ben, 5 2.2 ll ts: Ha r (vi) = 2 teljesl G minden cscsra a kls tartomny cscsain kvl, akkor ezek a hromsz gek egymshoz ragaszthat k az leik mentn a skbarajzolsnak megfelelen. Bizony ts. Hogy ez a ragaszts megtehet , azt a cscsok szmra vonatkoz teljes indukcival bizony tom.  n=3 esetn nyilvnval. (Ez a legkisebb, nem res, hromsz gekb l ll grf, egyetlen hromsz g van, nincs semmi felttel, s ragasztani sem kell.)  Ha n  4, akkor vlasszunk ki a G-ben egy cscsot, amely nem tartozik a k ls laphoz. Az ehhez tartoz hromsz gek a felttel miatt sszeragaszthatk, ha a cscs k-adfok volt, akkor gy egy k-sz get kapunk (k  3) Ez a k-sz g tlival k ; 2 darab hromsz gre bonthat (csak olyan tlkkal, amelyek a soksz g n

bel l haladnak). G-b l hagyjuk el a kivlasztott cscsot, az ezzel szomszdos cscsokat k ss k ssze a hromsz gelsnek megfelel mdon, s az j hromsz glapokhoz rendelj k a k-sz g megfelel hromsz geit (az j lekhez a megfelel tlk hosszt rendelj k). Az indukci sorn csak a grf leihez rendelt hosszsgok, s a lapokhoz ennek megfelel en rendelt sugarak vannak, nem foglalkozunk a cscsokhoz kezdetben rendelt sugarakkal, azokrl r gt n ttr nk az lekhez rendelt hosszsgra. Az gy kapott G -ben nyilvn teljes l az indukcis felttel s 1-gyel kevesebb cscsa van, teht a lapjainak megfelel hromsz gek jl ragaszthatl az lek mentn. Ekkor az j hromsz gek a fenti k-sz get adjk ki s gy lecserlve ket a rgi k darab hromsz gre a G-hez tartoz megfelel ragasztst kapunk. 0 2 Teht azt kell elrni, hogy a r (vi)-kre a felttel teljes lj n. Mivel a hromsz g sz geinek sszege : n X i=1 r(vi) = jF j = (2n ; 4) : Legyen S  IRn az az (n ; 1) dimenzis szimplex, amelyre: S=

 ) n X r = (r1 : : :  rn)  (ri > 0) 8i;re valamint ri = 1 i=1 ( s legyen H  IRn az a halmaz, melyre: H=  X ) n  x = (x1 : : :  xn)  xi = (2n ; 4) : i=1 ( 6 Legyen f : S 7! IRn a k vetkez f ggvny: f (r) = (r (v1) : : :  r (vn)) : Ez nyilvn folytonos lekpezs. Feltehetj k, hogy v1 v2 v3 a k ls hromsz cscsai. Elg beltni,  2glap  hogy az f f ggvny kphalmaza tartalmazza a  2 2 2 2 : : : 2 pontot. 3 3 3 2.3 ll ts: f : S 7! H injektv Bizony ts. Legyen r r 2 S kt k l nb z pont, legyen I azon i indexek 0 halmaza, amelyekre ri < ri. Nyilvn I 6= s I 6= f1 2 : : : ng Legyenek vi,vj s vk hrom olyan, egymst pronknt k v lr l rint k r k k zppontjai, melyek sugarai rendre ri,rj s rk . Ha ri n rj s rk pedig nem n (cs kken vagy ugyanaz marad), akkor a vi-nl lev sz g cs kken. Ha ri s rj n , rk pedig nem n , akkor vk -nl lev sz g n , gy a vi-nl s vj -nl lev sz gek sszege cs kken. Emiatt: 0 X i2I r (vi) > X i2I r

(vi)  0 amelyb l f (r) 6= f (r ) addik. 0 2 Legyen s = (s1 : : :  sn ) 2 bd(S ) (azaz s az S szimplex hatrpontja), s legyen I azon i indexek halmaza, amelyekre si = 0. Ha r 2 S ponttal tartunk s-hez, akkor minden hromsz gben, amelynek van I -beli indexhez tartoz cscsa, az I -beli indexekhez tartoz cscsoknl lev sz gek sszege -hez tart. gy: lim r s ! X i2I r (vi) = jF (I )j   ahol F (I ) azon hromsz gek halmaza a G-beli lapokbl, amelyeknek van olyan cscsa, amely I -beli indexhez tartozik. Legyen r 2 S tetsz leges, s I valdi rszhalmaza az f1 2 : : : ng halmaznak. Nyilvn van olyan s 2 bd(S ), hogy minden I -beli i indexre si = 0 s ha i 62 I , akkor X si > ri. Ha r-et mozgatjuk s fel az ket sszek t egyenes mentn, akkor r (vi) n ni fog, s jF (I )j -hez i2I 7 tart, gy X i2I r(vi) < jF (I )j  : Vagyis f (S ) rsze annak az (n ; 1) dimenzis P polidernek, melynek minden x = (x1 : : :  xn) pontjra teljes lnek az albbiak: n X (i) i=1 xi

= (2n ; 4) : (ii) Az f1 2 : : : ng halmaznak minden valdi I rszhalmazra: X i2I xi < jF (I )j  : Teht f : S 7! P injekt v, folytonos f ggvny. Ha r 2 S ponttal tartunk bd(S )-hez, akkor f (r) minden torldsi pontja bd(P )-ben kell legyen (az el bbiek alapjn). Ebb l k vetkezik, hogy f : S7! P sz rjekt v  2  2  2  Ezek utn elg azt beltni, hogy a 3 3 3 2 2 : : : 2 pont P -ben van, mert ekkor az skpe megfelel vektort ad. Legyen:  2 2 2  (x1 x2 : : :  xn) = 3 3 3 2 2 : : : 2 :    Nyilvn n X i=1 xi = (2n ; 4) :  Legyen I nem res, valdi rsze az f1 2 : : : ng halmaznak. Ha jI j = (n ; 1) vagy jI j = (n ; 2), akkor G minden lapjnak legalbb egy cscsa I -ben van, gy ez esetben: jF (I )j = 2n ; 4. n X i=1 xi  2(n ; 3) + 23 2 < (2n ; 4) : 8 Ha jI j (n ; 3), akkor felhasznljuk az albbi ll tst: 2.4 ll ts: Ha I  f1 2 : : : ng  1 jI j n ; 2, akkor G-nek legalbb 2jI j lapja tartalmaz I-beli index cscsot. Bizony ts. Ezt

n-re vonatkoz indukcival bizony tom  Ha |I|=1, akkor mivel a cscs legalbb harmadfok, kszen vagyunk. Ezzel n = 3-ra belttuk az ll tst.  Ha n  4, akkor tegy k fel, hogy (n ; 1)-re igaz az ll ts. Az indukcis lps sorn 3 esetet k l nb ztet nk meg: (a) Ha jI j = n;2, akkor minden lapnak van I -beli index cscsa, amelyb l jF (I )j = 2n ; 4, teht az ll ts trivilis. (b) Ha van kt k l nb z index: i s j gy, hogy vivj 2 E (G), de i 62 I s j 62 I , akkor a vivj l pontra hzsval keletkezett grf legyen G . Feltehetj k, hogy jI j n ; 3, gy a G -ben az indukcis feltevs alapjn4 van legalbb 2jI j megfelel lap s ezek skpei G-ben megfelel k lesznek, mivel i 62 I s j 62 I . (c) Ha nincs kt k l nb z index a fenti feltteleknek megfelel en, akkor jF (I )j = 2n ; 4  2jI j, mivel minden hromsz gben van legalbb kt I -beli index cscs. 0 0 Egyenl sg csak jI j = n ; 2 esetn van. Ha n  4 s jI j n ; 3, akkor az indukci szerint egyenl sg csak gy lehet, ha pontra

hztuk az egyik megfelel let, s ott is egyenl sg volt5. De ott az jI j = (n ; 1) ; 2 = n ; 3 eset kellet el forduljon az indukci miatt, s ekkor a pontra hzott l valamelyik oldaln van egy hromsz g, amelyet eddig nem szmoltunk, mivel szakassz hzodott ssze. gy szigor egyenl tlensg lesz ez esetben Teht ha 1 jI j n ; 3, akkor jF (I )j > 2jI j. 2 A 2.4 !ll ts alapjn: X i2I 4 5 xi  2jI j < jF (I )j  : V (G ) = n ; 1 ekkor a (c) esetben nincs egyenl sg, az (a) eset pedig el sem fordul 0 9 Teht (x1 : : :  xn) 2 P , amivel a 2.1 Ttelt belttuk   2 Most trj nk r a 2.1 Ttelben szerepl reprezentci egyrtelmsgre maximlis s kgrfok esetn Whitney ttele szerint egy 3- sszef gg s kgrf begyazsa a g mbfelsz nbe "egyrtelm#, vagyis nem f gg a grf s kbarajzolstl, hogy mely lek hatrolnak egy tt egy lapot, s melyek nem. Ezt a ttelt ks bb bizony tjuk A maximlis s kgrfok 3- sszef gg grfok, mivel sszef gg k, s ha lenne 1 vagy 2

elvg pontunk egy ilyen grfban, akkor azok a k ls tartomnynak is cscsai lennnek, gy viszont a k ls tartomny nem lehetne hromsz g. Legyen G egy maximlis s kbarajzolhat grf, egy hromsz ge pedig v1v2v3. Megfelel inverzival elrhet , hogy G-hez tartoz reprezentciban v1,v2 s v3 cscsokhoz tartoz k r k egyenl sugarak legyenek s az ltaluk k zbezrt tartomnyban legyen a t bbi k rlemez. Ekkor a bizony tsbl k vetkezik, mivel f : S 7! P injekt v, hogy az gy kapott reprezentci hasonlsg erejig egyrtelm kell legyen. 10 2.2 Whitney ttele 2.5 Den ci Legyen adott egy G grf s ennek egy G1 rszgrfja A G egy H rszgrfjt a G1 hdjnak nevezzk, ha a H lei diszjunktak a G1 leitl s vagy egyetlen olyan lbl ll H , amely lnek mindkt vgpontja G1 -ben van, vagy pedig H tartalmazza a G ; G1 egy sszefgg komponenst s a komponenst G1-gyel sszek t sszes let. Megjegyzs. A hidak az E (G) ; E (G1 ) leket part cionljk, gy denilhattuk volna ket egy

ekvivalencia relci ltal meghatrozott ekvivalencia osztlyokknt is, ahol a relcink: e1  e2 pontosan akkor, ha e1 = e2 vagy ha van egy G1t l diszjunkt t, amely sszek ti e1-t s e2-t. Nyilvnval, hogy egy h d mindig sszef gg . Az is ltszik, hogy ha G1 fesz tett rszgrf, akkor a h djainak a szma G ; G1 sszef gg komponenseinek a szmval egyezik meg. 2.6 Lemma Legyen G egyszer 3- sszefgg skgrf, C pedig a G egy k re Pontosan akkor van egyetlen hdja C -nek, ha C a G egy lapjt hatrolja. Bizony ts. Feltehetj k, hogy G legalbb 4 cscs grf, ellenkez esetben az ll ts trivilis. R gz ts k G egy s kbarajzolst Legyen C a G egy F lapjnak hatrn s legyen H a C egy h dja. Ekkor azt akarjuk megmutatni, hogy H tartalmazza a C sszes pontjt. Ezt indirekt ton mutatjuk meg, tegy k fel, hogy van olyan x cscsa a G grfnak, melyre x 2 V (C ) s x 62 V (H ). Nyilvnval, hogy H C csak cscsokbl ll, ezek a C k rt vekre osztjk, legyenek y s z azok a cscsok, amelyek k z

tti ven nyugszik az x cscs. (Vagyis az y s z k z tti egyik vn a C k rnek fekszik az x cscs s ennek az vnek a bels pontjai diszjunktak H -tl.) Az y s z cscsok nem lehetnek szomszdosak a k rben ha H egyetlen l, akkor ez trivilis, ha pedig H nem egyetlen lb l ll, akkor k vetkezik abbl, hogy a 3- sszef gg sg miatt a k r n legalbb 3 pontja kell legyen H -nak. Mivel G 3- sszef gg , G ; fx yg sszef gg , gy kell legyen egy t a G ; fx yg grfban, amely sszek ti C -nek a kt (x y) vt legyen P egy ilyen t. Legyen Q az x s y cscsokat H -ban sszek t t. P s Q nem futhatnak az F lap belsejben, gy metszik egymst, ami ellentmond a s kbarajzolsnak. (Lsd a 2 brt) Teht belttuk, hogy egy h dnak tartalmaznia kell C sszes pontjt, ebb l az is k vetkezik, hogy H nem llhat egyetlen lb l. Mivel a hidak s kbarajzolsa diszjunkt az F laptl, s minden h d tartalmazza C sszes pontjt, csak egy h d lehet, k l nben a grf nem lenne s kbarajzolhat. 11 P y C F Q z x 2.

bra Ha C nem egy lapja G-nek, akkor vagy vannak cscsok, amelyeket elvlaszt egymstl a s kbarajzolsnl, vagy pedig van olyan h dja C -nek, amely egyetlen lb l ll. Az els esetben a G ; C grfnak van legalbb 2 sszef gg komponense s gy legalbb 2 h dja is. A msodik esetben legyen egy hidat alkot l kt vgpontja x s y. A G ; fx yg grf sszef gg kell legyen, x s y pedig a C k rt kt vre bontja, (nem lehetnek szomszdosak a k rben is, mivel a grf egyszer) vagyis kell legyen a kt vet sszek t t a grfban. Vegy nk egy minimlis ilyen utat, ennek nyilvn csak az els s utols cscsa van a h don, vagyis nem tartalmaz lt C -b l, s gy van egy h d, amely tartalmazza ezt az utat. Teht ez esetben is legalbb 2 h dja van C -nek. A 2.6 Lemma k vetkezmnye a korbban mr eml tett Whitney-ttel: 2 2.7 Ttel (Whitney) Egy egyszer 3- sszefgg skgrf begyazsa a g mbfelsznbe homeomorzmus erejig egyrtelm Bizony ts. A 26 Lemma szerint ha vesz nk kt begyazst, akkor abban

ugyanazok a k r k hatroljk a lapokat, mivel a hidak szma a h d den cija szerint f ggetlen a s kbarajzolstl. A kt g mbbegyazst kt cellakomplexusnak tekintj k, az egy dimenzis vzuk a kt grf. A kt egy dimenzis vz homeomorf (mivel a grfok izomorfak), s a 2 dimenzis vz ragaszt lekpezsei is ugyanazok, mivel ugyanazok az lek hatroljk a lapokat, gy a kt komplexus homeomorf. 2 12 2.3 Steinitz-ttel A Steinitz-ttel bizony tshoz sz ksg nk lesz a Y s az Y -transzformcik fogalmra. 2.8 Den ci Legyen G egy skbarajzolhat grf Egy Y -transzformci a G egy hromsz glapjt cserli le egy 3-g csillagra gy, hogy a lap hatrol leit elt rli, s hozzvesz egy j cscsot a grfhoz, amelyet a lap 3 cscsval k t ssze. Egy Y -transzformci ennek a transzformci nak az inverze, egy harmadfok cscsot elhagy a grfb l s a szomszdait sszek ti egymssal. f g e g e f 3. bra Az brn jellt mdon ltezik egy termszetes megfeleltets a hromszg s a

3-g csillag lei kztt. Megjegyzs. Whitney ttele miatt a 3- sszef gg grfban nem f gg a s kbaraj- zolstl, hogy a grf mely hromsz geire lehet alkalmazni a transzformcit. Ha a grf nem 3- sszef gg , akkor egy r gz tett s kbarajzols utn fogjuk alkalmazni a transzformcikat. Nyilvnval, hogy a kt transzformci a s kbarajzolhatsgot nem befolysolja. Az is ltszik, hogy a kt transzformci egyms "dulisa#, vagyis ha egy grfban vgrehajtjuk az egyiket, akkor a dulis grfban ppen a msik transzformcit hajtottuk vgre. Ezeket a transzformcikat s kbarajzolhat, 2- sszef gg , egyszer grfokra fogjuk alkalmazni. Egy Y -transzformci sorn keletkezhetnek t bbsz r s lek, ezek k z l az egyiket a transzformci utn t r lni kell, hogy a grf egyszer maradjon. Egy Y -transzformci sorn pedig keletkezhetnek msodfok cscsok, ami a dulis grfban jelentene t bbsz r s leket. Amikor 3- sszef gg grfokkal dolgozunk, az ilyen cscsokat is t r lni kell s a

szomszdait sszek tni. A msodfok cscsbl indul kt let prhuzamos leknek nevezz k, az el bbi mvelet pedig a prhuzamos lek egyszers tse. 2.9 Den ci Az elz kt fajta transzformci k elvgzst, vagyis a t bb- sz r s lek egyszeresre cserlst a grfban, illetve a dulisban, SP-redukci nak6 nevezzk. 6 serial-parallel reduction 13 Egyszer Y -transzformci alatt egy Y -transzformci t s az utna elvgzett SP-redukci t rtjk. Ugyangy denilhatjuk az egyszer Y -transzformci t is A k vetkez lemma a Y s Y -transzformcik alkalmazhatsgt biztos tja azt mondja meg, hogy az sszef gg sg milyen felttelekkel marad meg a grfban: 2.10 Lemma (i) Legyen G egy 2- sszefgg grf, s legyenek egy harmadfok v cscsb l indul lei a grfnak fe f gg. Ha ezek az lek nem prhuzamosak7, akkor a grf egy v cscsot lecserl Y -transzformci utn ismt 2- sszefgg lesz. (ii) Legyen G egy 3- sszefgg egyszer grf,8 s legyenek egy harmadfok v cscsb l indul lei

a grfnak fe f gg. Ha vgrahajtunk egy Y -transzformci t erre a 3-g csillagra, s ezutn egy SP-redukci t a kapott grfra, akkor a kapott grf egyszer 3- sszefgg lesz. Bizony ts. A den cikbl addan igen egyszer Vegy nk egy Y - transzformcit G 7! G . Ha van egy elvlaszt, 1 vagy 2 pont halmaz G -ben, akkor ugyanez a halmaz elvlaszt G-ben is. Az egyetlen problma, hogy egy Y -transzformci ltrehozhat t bbsz r s leket, de az SP-redukci ezeket is megsz nteti. 0 0 2 A dualits seg tsgvel ebb l r gt n addik a Y -transzformcik hatsa az sszef gg sgre. Az albbi prok feleltethet k meg egymsnak a dualits seg tsgvel: s kbarajzolhat grf G prhuzamos lek egyszers tse k- sszef gg grf hromsz glap Y -transzformci ! ! ! ! ! dulis grf G t bbsz r s lek egyszers tse k- sszef gg grf 3-g csillag Y -transzformci  A poliderek szempontjbl is fontos szerepe van a dualitsnak, mivel egy polider grfjnak dulisa megegyezik a polris

polider grfjval: G(P ) = G(P  ) :  7 8 v-nek 3 klnbz szomszdja van vagyis nincsenek prhuzamos lek, s minden pont foka legalbb 3 14 Megjegyzs. A legfeljebb 4 cscs 3- sszef gg grfok a K1,K2,K3 s K4 teljes grfok. 2.11 Ttel (Steinitz) G egy 3-dimenzi s konvex polider grfja akkor s csak akkor, ha G egyszer, skbarajzolhat , 3- sszefgg grf (s legalbb 4 cscsa van). Bizony ts. Ha G egy konvex P polider grfja, akkor G legalbb 4 cscs s a s kbarajzolhatsg is k nnyen lthat a bevezetsben eml tettek szerint. Emiatt csak a G grf 3- sszef gg sgt bizony tjuk. Az nyilvnval, hogy G sszef gg Indirekt ton bizony tunk, tegy k fel, hogy G nem 3- sszef gg grf. gy van G-ben 1 vagy 2 pont elvg H halmaz.9 Legyenek a polidernek a H halmaz elemeihez tartoz cscsai C s D, ha H kt pontbl ll, s C , ha H 1 pont halmaz Van a polidernek olyan A s B cscsa, hogy a hozzjuk tartoz cscsai G-nek a G ; H grf k l nb z sszef gg komponensbe esnek.

Projekt v transzformcival elrhetj k, hogy ezekben a cscsokban hzott olyan tmaszhipers kok k z essen a polider, amelyek egymssal prhuzamosak, s a polidert csak az A illetve B pontokban metszik. Legyenek az el bbi A- s B -beli tmaszs kok S1 s S2 az ezekkel prhuzamos, C ponton tmen s k pedig legyen S3. Az S3 P -nek van olyan relat v bels E pontja, amelyre a CE egyenes nem prhuzamos a polider egyetlen lapjval sem. (Nincs S3 s kkal prhuzamos lap mivel S1 s S2 ezzel prhuzamos rint .) Vet ts k le mer legesen a P polidert egy CE egyenesre mer leges S4 s kra. Ekkor a vet let egy konvex soksz g lesz, amelynek relat v bels pontja a C pont kpe. Az A s B pontok nyilvn a soksz g relat v hatrn vannak. A S1 S4 E A| S3 C C| = E| D S2 B D| B| 9 4. bra Ha van elvg cs cs G-ben, akkor mindenkppen 1 elem H halmazt vlasszunk. 15 Az A s B pontok10 k z tt van kt diszjunkt t a soksz g hatrn, amelyek k z l legfeljebb egyet vghat el a H halmaz kpe, mivel C

bels pont. Az el nem vgott t skpe pedig a P polider leinek egy lnca az A s B k z tt, amely nem tartalmazza C s D pontokat. Ez ellentmonds, mivel H elvlasztotta az A s B pontokhoz tartoz cscsait G-nek. Az A s B pontok k z tti tnak azrt ltezik megfelel skpe, mert a vet ts kpnek hatrn minden pont skpe egyrtelm kell legyen, k l nben EC egyenes prhozamos lenne a polider valamely lapjval. Ezzel a 2.11 Ttel feltteleinek sz ksgessgt belttuk Megjegyzs. A bizony ts k nnyen mdos that gy, hogy n-dimenzis politpok grfjnak n- sszef gg sge addjon A 2.11 Ttel msik felnek bizony tsnl a lpsek a k vetkez k lesznek: 0 0 0 0 0  A Y s Y -transzformcik meg rzik a "realizlhatsgot#.  Minden egyszer, s kbarajzolhat s 3- sszef gg grf reduklhat K4 -re egyszer Y s Y -transzformcikkal. Egy egyszer Y -transzformci a 2.10 Lemma alapjn meg rzi a 3- sszef gg sget 4 fle k l nb z egyszer Y -transzformci van aszerint, hogy a

lecserlend hromsz gben hny harmadfok cscs van: 5. bra A transzformci szempontjbl nem szm t, hogy az brn a szaggatott vonallal rajzoltak a grfban lek vagy sem. Hasonlan, 4 fajta egyszer Y -transzformci van, vessz k a harmadfok cscsot, s megnzz k, hogy a grfban a szomszdai k z tt hny l megy. gy ugyanazt az osztlyozst kapjuk, mint ha a 4 fle egyszer Y -transzformci hatst vizsglnnk a dulis grfban. 10 Egy M pont kpt a vet ts sorn M -vel jellm. 0 16 6. bra 2.12 Lemma Legyen G egy 3- sszefgg skgrf s legyen G a G-bl egyszer 0 Y vagy Y -transzformci val keletkez grf. Ha G egy konvex polider grfja, akkor G is az. 0 Bizony ts. A dualits/polarits seg tsgvel elg csak a Y -transzformcikat vizsglni. Ezekre pedig egyszer az ll ts Legyen P a G grfhoz tartoz polider Ha SP-redukcival t r lt nk egy msodfok cscsot, akkor P -ben a neki megfelel l felez pontja legyen ez a cscs. Ezutn vegy k a P politp sszes

cscst a 3-g csillag k zephez tartoz cscs kivtelvel s vegy k mg hozz az el bb denilt j cscsokat (ha vannak ilyenek). Az gy kapott ponthalmaz konvex burka megfelel P polidert alkot, vagyis P polider grfja G lesz. Lnyegben a fenti eljrs a P polidernek a csillag k zppontjhoz tartoz cscst levgta egy megfelel s kkal. A 3- sszef gg sgb l k vetkezik, hogy a transzformci utn csak a "csillag# vgpontjaiban lehettek msodfok cscsok, gy ezekhez a P polidernek k l nb z lei fognak tartozni. 0 0 0 0 0 0 2 Ezentl legalbb 2- sszef gg grfokkal fogunk foglalkozni, s csak akkor enged nk meg egy Y vagy Y -transzformcit alkalmazni, ha a kapott grf is legalbb 2- sszef gg lesz. 2.13 Den ci Egy G skgrf Y -reduklhat G -re, ha a G a G-bl elrhet 0 0 Y s Y -transzformci k, valamint SP-redukci segtsgvel. 2.14 Den ci G grf minorja a G grf, ha megkaphat G a G-bl a k vet0 kez mveletek (akrhny egyms utni) alkalmazsval: (i) T r

lhetnk egy let. (ii) Szomszdos cscsokat pontra hzhatunk. 17 0 Megjegyzs. Nyilvnval, hogy az el bbi kt fajta mvelet egymssal felcserlhet (Mivel most a t bbsz r s leket nem egyszers tj k) Ezutn azt fogjuk megmutatni, hogy minden 3- sszef gg legalbb 4 cscs s kgrf Y -reduklhat K4-re, ebb l az el z 2.12 Lemma alapjn k vetkezik a ttel. 2.15 Lemma Ha a G skgrf Y -reduklhat K2-re, akkor brmely 2- sszefgg, legalbb 2 cscs H minorja is az Megjegyzs. Ha legalbb 3 cscs grfokon hajtjuk vgre a redukcis lpseket, akkor (mivel a 3 cscs 2- sszef gg grfok csak a K3 s a bel le t bbsz r s lek ksz tsvel kaphat grfok) a grfunk Y -reduklhat lesz K3-ra is. Ha legalbb 4 cscs, 3- sszef gg grfokra hajtjuk vgre, akkor pedig ugyan gy a grfunk Y -reduklhat lesz K4-re is. Bizony ts. Ezt a G-beli redukcis lpsek szmra vonatkoz indukcival bizony tjuk A kezd lps trivilis, ha nincs redukcis lps, akkor G  K2, gy H  K2. F ltehetj k,

hogy H -ban nincsenek t bbsz r s, vagy prhuzamos lek k l nben ezeket egyszers thetj k, ny lvn gy is G-nek egy 2- sszef gg , legalbb 2 cscs minorjt kapjuk. Ha a G-beli redukci els lpse SP-redukci, akkor H az els lps utn kapott grfnak is a minorja lesz az el bbi feltevs szerint, gy az indukcis lps mk dik. Egybknt a dualits seg tsgvel feltehetj k, hogy az els lps egy Y -transzformci: G ! G Legyenek e, f s g az a hrom le G-nek, amelyek a lecserlend hromsz get alkotjk. Ha mindhrom l H -ban is benne van, akkor hajtsuk vgre ugyanezt a transzformcit H -ban is: H ! H . Ezutn H Y -reduklhat K2-re az indukci szerint s gy H is az. Ha van olyan l, amely nincs benne H -ban, akkor nzz k meg, mi t rtnhetett vele. Mivel H egyszer, nem lehetsges, hogy csak egy vagy kt l pontra hzsa t rtnt, vagy mindhrmat pontra kellett hzni, vagy valamelyiket t r lni kellett. Ha mindhrmat pontra hztuk, akkor is feltehetj k, hogy az egyiket t r lt k s utna

a msik kett t pontra hztuk. Mivel ezek a mveletek felcserlhet k, mindkt esetben feltehetj k, hogy egy let t r lt nk el sz r ezek k z l, legyen ez az l e. De ekkor ugyanazt a H minort kapjuk G -ben, ha abban az e-hez tartoz lt11 pontra hzzuk s a t bbi G-ben sz ksges lpst elvgezz k, mivel: 0 0 0 0 G ; feg = G = e : 0 gy ismt alkalmazhat az indukcis lps. 11 a den cinl az brn jellt termszetes megfeleltetssel 18 2 2.16 Den ci Legyen G(m,n) az nxm-es ngyzetrcsnak megfelel grf, vagyis az a grf, melyre: jV (G(n m))j = nm, s a cscsait (i,j) szmprokkal indexelve (ahol 1 i n s 1 j m egszek) kt cscs pontosan akkor van sszek tve, ha a nekik megfelel (i1 j1) s (i2 j2) szmprokra teljesl, hogy ji1 ; i2j + jj1 ; j2 j = 1. 2.17 Lemma Ha G skgrf, akkor a minorja valamely G(m n) grfnak Megjegyzs. Nyilvnval, hogy ha m > m s n > n, akkor a G(m n) grf 0 0 minorja a G(m  n ) grfnak. Bizony ts. Vegy k G egy s kbarajzolst

Ha van egy v cscs, amelynek a foka 3-nl t bb, akkor ezt osszuk kett, egy kis k rnyezetben vegy nk fel mg egy j u cscsot valamelyik tartomny belsejben, majd t r lj k azt a kt let, ami az el bbi tartomnyt hatrolja s v az egyik vgpontja, vg l ennek a kt lnek a msik vgpontjval s v-vel k ss k ssze az j u cscsot. Trivilis, hogy a kapott grf s kbarajzolhat, s G a minorja. Ennek a mveletnek az ismtlsvel elrhet , hogy a grf legfeljebb harmadfok cscsokbl lljon. 0 0 7. bra Elg mutatni egy begyazst a G grfnak egy vges ngyzetrcsba oly mdon, hogy a grf cscsai a ngyzetrcs cscsaiba menjenek, mert ekkor a begyazs kpeknt el ll G grfnak nyilvnvalan minorja lesz a G grf (csak lek pontra hzsval el ll that), s a G grf minorja lesz a megfelel G(m n) grfnak. Ha van egy ilyen G grf, akkor a k vetkez algoritmus el ll tja a G -t a G(m n) grf minorjaknt: Kezdetben legyen G0 = G(m n). A mr megkonstrult Gi grfunk olyan, amelynek

rsze a G grf, s amelynek nincs olyan izollt pontja, amely nem cscsa a G grfnak. Ha Gi 6 G , akkor van olyan l Gi -ben, amely nem le G -nek, vegy nk egy ilyen let. Ha ennek valamelyik vgpontja els fok, akkor hzzuk pontra, ha pedig egyik sem, akkor t r lj k ezt az let a kapott grf legyen Gi+1 . Ennek az algoritmusnak vges sok lpsben vge lesz, mivel az lek szma minden lpsben cs kken 1-gyel, a vgn kapott grf G kell legyen. Egy ilyen begyazst k nny csinlni, el sz r egy fesz t erd t kell begyazni, majd pedig az leket egyms utn, a s kbarajzolsnak megfelel en. Ha valamely 0 00 0 00 00 00 00 00 00 00 00 19 lre ezt mr nem tudjuk megcsinlni, akkor pedig a rcs sr tsvel (a rcs leinek felre cs kkentsvel) mr ismt folytathat az eljrs. A fesz t erd begyazsa pedig trivilis. Koebe reprezentcis ttelvel is egyszeren mutathat a G grfnak (a korbbi feltteleknek megfelel ) begyazsa egy ngyzetrcsba. A grfot reprezentljuk k

rrendszerrel, a cscsok a k r k k zppontjai legyenek Elg az leket lecserlni a megfelel cscsok k z tt fut, "v zszintes# s "f gg leges# szakaszokbl ll t r ttvonalakra, ekkor az sszes t r ttvonal, s az sszes cscson thalad "v zszintes# s "f gg leges# egyenesek egy tt egy vges tglalaphlt hatroznak meg, amelybe a fentieknek megfelel en van begyazva a grfunk. Elg a k r k n bel l sszek tni az rintsi pontokat a k r k k zppontjval az el bbieknek megfelel mdon. Egy k r n bel l pedig trivilisan sszek thet a legfeljebb 3 rintsi pont a k zpponttal az el bbieknek megfelel t r ttvonalakkal. 0 2 2.18 Lemma Ha m s n legalbb 3, akkor a G(m n) grf Y -reduklhat K4-re. Bizony ts. A k vetkez kt alapmveletet fogjuk alkalmazni: (1) Ha van egy l, amely egy harmadfok cscs kt vgpontjt k ti ssze, akkor azt az let t r lhetj k egy Y -transzformci s egy SP-redukci egyms utn alkalmazsval. 8. bra (2) Ha van egy l amely sszek ti egy

negyedfok cscs kt szomszdjt, akkor ez kicserlhet a negyedfok cscs kt msik szomszdjt sszek t lre egy Y majd egy Y -transzformci seg tsgvel. 9. bra 20 Ezen transzformcik alapjn a k vetkez mdon redukljuk a G(m n)-grfot:  El sz r a "jobb-fels # sarokban alkalmazunk egy SP-redukcit.  Ezutn, ha m  4, akkor t rl nk egy sort a k vetkez k szerint. A bal als sarokban vrgehajtunk egy SP-redukcit, majd a kapott tls let a (2) mvelet seg tsgvel mozgatjuk, am g "elri a f ls , vagy a jobb szlt# a hlnak. 10. bra Ekkor az l vagy prhuzamos a "jobb-fels tls# llel s egy SP-redukcival t r lhet , vagy egy harmadfok cscs kt vgpontjt k ti ssze s gy az (1) mvelettel t r lhetj k. 11. bra Ezzel a mdszerrel az "als sorban lev ngyzeteket# egyms utn t r lhetj k. A legutols ngyzetnl csak kt SP-redukcit kell vgrehajtani 12. bra  Hasonlan t r lhetj k az oszlopokat, am g n  4. 21  Vg l a kapott grfbl a

k vetkez bra szerint kaphatjuk meg K4 -et: 13. bra Ezzel az eljrssal teht minden G(m n) grf K4-re reduklhat. 2 Az el z hrom lemmbl a 2.15 Lemmhoz rt megjegyzssel k vetkezik, hogy minden 3- sszef gg s kgrf Y -reduklhat K4-re, mivel a transzformciink "meg rzik# a 3- sszef gg sget. Ezzel a Steinitz-ttel bizony tst befejezt k. 2 A mveleteket gy is elvgezhetj k, hogy a poliderek cscsai mind racionlis koordintjak legyenek, a bizony ts mdos tsval az albbi ttel is belthat: 2.19 Ttel Minden P  IR3 konvex polider tetszlegesen k zelthet racio- nlis cscs konvex poliderekkel, amelyek kombinatorikusan ekvivalensek P -vel. 2 A k zel tst itt gy rtj k, hogy a megfelel cscsok tvolsga tetsz leges pozit v konstansnl kisebb. Vgezet l megeml tennk kt ttelt, amelyek a 2.11 Ttelhez hasonlan bizony thatk s azt mutatjk meg, hogy milyen kombinatorikus felttelek sz ksgesek ahhoz, hogy a polider szimmetrikus legyen 2.20 Ttel Egy

G grfhoz pontosan akkor ltezik k zppontosan szimmetrikus konvex polider, amelynek G a grfja, ha G legalbb 4 pont 3- sszefgg skgrf s van olyan  msodrend automorzmusa, amely minden v 2 V (G) cscsra teljesti, hogy v s (v) elvlaszthat k egy k rrel G-ben.12 2 2.21 Ttel Egy G grfhoz pontosan akkor ltezik egy skra szimmetrikus kon- vex polider, amelynek G a grfja, ha G legalbb 4 pont 3- sszefgg skgrf s van olyan  msodrend automorzmusa, amely a lapok irnytst megfordtja. 2 12 Az elvlaszts 3-sszefgg s kgrfokra egyrtelm, nem fgg a s kbarajzolstl. 22 3. lrint poliderek 3.1 3- sszef gg s kgrfok reprezentcija 3.1 Ttel Legyen G egy (legalbb 4 pont) 3- sszefgg skgrf, egy elre meghatrozott lapja legyen a kls (vgtelen) tartomny. Ekkor van olyan k rrendszer a skon, hogy a grf cscsainak s lapjainak a k rrendszer egy-egy eleme felel meg, s teljeslnek az albbiak: (1) Kl nb z cscsokhoz tartoz k r k nem metszik

egymst, s kl nb z lapokhoz tartoz k r k sem metszik egymst. (2) G-nek minden e lhez tartozik a sk egy pontja, amelyen a k rrendszer 4 eleme halad t, az l kt vgpontjhoz tartoz , s az l kt oldaln lev lapokhoz tartoz k r k. Ezt a pontot l-pont-nak fogjuk hvni (3) Egy laphoz s egy cscshoz tartoz k r csak akkor metszi egymst, ha a cscs a lap hatrn van. (4) A kls laphoz tartoz k r ltal hatrolt k rlemez tartalmazza az sszes t bbi laphoz tartoz k rt, s ezen a k r n kvl semelyik k r nem tartalmaz a belsejben egy msik k rt. (5) Minden l-pontban a kt cscshoz tartoz k r derksz gben metszi a kt laphoz tartoz k rt. Ez a reprezentci inverzi t l s a sk hasonl sgi transzformci it l eltekintve egyrtelm. Megjegyzs. Vegy k a grfnak s a dulisnak olyan s kbarajzolst, ahol a grf leit metszik a dulis grf megfelel lei. A metszspontoknak az l-pontok feleltethet k meg. Ksz ts nk egy j grfot, amelynek cscsai a grf s a dulis grf cscsai

valamint az l-pontok, az lei pedig az l-pontokat k tik ssze a nekik megfelel ngy csccsal. Az gy kapott grfnak egy s kbarajzolst mutattuk meg az el bb. A s kbarajzolsnl a grf lapjai ngysz glapok lesznek, egy ilyen lapnak 2 l-pont, valamint egy eredeti s egy dulis grfbeli cscs lesz a cscsa. Ha a ttel szerinti reprezentcit ksz tett k el, akkor ezek a lapok a k ls tartomnyhoz tartoz lapokon k v l nyilvn deltoidok lesznek, kt-kt oldaluk a megfelel cscshoz s laphoz tartoz k r k sugaraival egyezik meg. A bizony ts sorn ilyen deltoidokat konstrulunk s ragasztunk ssze gy, hogy a vgn a kapott hlzat az el bbi grfot adja ki (a vgtelen tartomnynl lev lapok kivtelvel). A megfelel cscsokba a hlzat ltal mr denilt sugar k r ket rva megkapjuk a sz ksges reprezentcit. A ttel bizony tsa nmi el ksz letet ignyel 23 14. bra Az brn K4 reprezentcija lthat a ttelnek megfelel krrendszerrel. A lapokhoz tartoz krk a szaggatott vonallal

rajzoltak. 15. bra A bal oldali brn egy s kbarajzolhat grf (K4 ), s a dulisnak egy egyttes s kbarajzolst lthatjuk az l pontokat res krkkel jelltem. A jobb oldali brn a reprezentcibl add egyttes s kbarajzols lthat, ahol a grf lei a dulis grf megfelel leire mer legesek. Lthat, hogy minden vges tartomny deltoid. 3.2 Den ci Legyen G egy 3- sszefgg legalbb 4 pont skgrf Ennek a cscs-lap illeszkedsi grfja az a G^ grf, amelynek cscsai G cscsai s lapjai (belertve a kls lapot is), s k ssnk ssze kt cscsot, ha az egyik G egy cscsnak, a msik G egy lapjnak felel meg, s a megfelel cscs a megfelel lap hatrn van. Nyilvnval, hogy G^ egy s kbarajzolhat pros grf s minden ngysz glapja G egy lnek feleltethet meg. Az is ltszik, hogy G cscsainak megfelel cscsok foka G^ -ben ugyanakkora, mint az eredeti cscs foka G-ben. 24 3.3 Lemma Legyen G egy 3- sszefgg skbarajzolhat grf s legyen G^ a cscs-lap illeszkedsi grf.

(1) Ha G^ -nak v darab cscsa van, akkor az leinek szma 2v ; 4. gy van harmadfok cscsa, legyen egy ilyen cscs x. (2) Legyen S  V (G^ ) nem res halmaz, amely nem tartalmazza x-et s annak egyetlen szomszdjt sem. Ekkor S legfeljebb 2jS j ; 2 lt feszti ki G^ -nak, s legalbb 2jS j + 1 lre illeszkedik. Bizony ts. Az (1) bizony tsa egyszeren k vetkezik az Euler-formulbl. A (2) els felnek bizony tshoz legyen G^ (S ) az S ltal G-ben kifesz tett rszgrf. G^ (S ) is s kgrf, vegy k ennek egy begyazst a s kba Nyilvnval, hogy G^ (S ) pros grf is, gy ha legalbb 2 le van, akkor minden lapja legalbb 4 llel rintkezik,13 amelyb l ismt az Euler-formula seg tsgvel addik, hogy G^ (S )-nek legfeljebb 2jS j ; 2 le van. Ha G^ (S )-nek legfeljebb 1 le van, akkor az ll tsnak ez a fele trivilis. A (2) msodik felnek bizony tshoz legyen S = V (G^ ) ; S . Ha S -beli cscsokkal legfeljebb 2jS j l rintkezik, akkor az (1) miatt G^ (S)-nak legalbb 2jSj; 4 le

van. Az el bbiekhez mg nem hasznltuk ki a (2) k l nleges feltteleit, gy mindkt esetben egyenl sg kell legyen. Vagyis S -beli cscsokkal pontosan 2jS j l rintkezik s G^ (S)-nak 2jSj; 4 le van. A felttelek szerint S legalbb 4 elem, gy G^ (S)-nak legalbb 2 le van, ami azt jelenti, hogy G^ (S) minden lapja ngysz g. Valamelyik ilyen lap tartalmazza S -nek egy elemt, gy ennek a lapnak a cscsai elvlaszt halmazt alkotnak G^ -ban, mivel nem lehet S sszes eleme ezen a lapon. Ezek az lek G kt szomszdos cscshoz s kt szomszdos lapjhoz tartoznak, de gy nem szeparlhatjk G^ -ot, mivel G hromszorosan sszef gg . 2 Megjegyzs. Ha jS j > 2, akkor a fels korlt (2)-ben cs kkethet 2jS j ; 4-re Most mr elkezdhetj k a 3.1 Ttel bizony tst Bizony ts. Feltehetj k a 33 Lemma (1) ll tsa alapjn, hogy G k ls lapja hromsz g, mivel vagy G-ben vagy G -ban van harmadfok cscs, ennek megfelel en a msikuk tartalmaz egy hromsz glapot. Ha kell ttrhet nk a grf

dulisra s feltehetj k, hogy a hromsz glap a k ls tartomnyt hatrolja, mivel ha ez esetben tudunk a ttelnek megfelel reprezentns rendszert mutatni, akkor az a k rrendszer inverzival az eredeti s kbarajzolsnak megfelel reprezentns rendszerr tehet . Trj nk r a bizony ts el tt le rt deltoidokra s vizsgljuk meg, hogy milyen felttelekkel ragaszthatk megfelel en egymshoz.  13 ktszer szmoljuk, ha egy lap egy lnek mindkt oldalval rintkezik 25 Legyen v = jV (G^ )j, s G^ minden cscshoz a k ls F0 tartomnyhoz tartoz cscs kivtelvel rendelj nk egy r vltozt, amelynek rtke majd az -hoz tartoz k r sugara lesz. A k ls tartomny hrom, a, b s c cscshoz hozzrendelt ra, rb s rc vltozk rtke majd a vgn 1 lesz, minden ms r rtke ezek ltal egyrtelmen meg lesz hatrozva. Legyen r az (r) G^ F0 vektor. ;  ;  + v 1 + v 4 Deniljuk a : IR 7! IR f ggvnyt a k vetkez kppen: 2 ; ahol (r) = ( (r)) 2 (r) az sszegzs ; ; = G^ ;fF0 abcg

  r  X Arctg r    ? sszes G^ -beli szomszdjra fut vgig. r r β α r r α β 16. bra A K  deltoid. Legyen K az r s r oldal deltoid. Ha hzunk kt r s r sugar, egymst mer legesen metsz k rt, akkor a kt k r k zppontja s a kt metszspont ltal alkotott ngysz g ppen a K lesz. Ebben a kt r hosszsg oldalak ltal bezrt sz g: r  2 Arctg r :  gy (r) az sszes olyan deltoidok -hoz tartoz cscsnl lev sz gei sszegnek a fele, amelyeknek van ilyen cscsuk. Ebben a pontban a deltoidok jl ragaszthatk, ha az ehhez a cscshoz tartoz sz g sszeg 2, gy sz ksges, hogy (r) =  teljes lj n, ahol  az a vektor, amelynek minden koordintja . Ez a felttel elgsges is, vagyis ha teljes l, akkor a deltoidok jl ragaszthatk a 2.2 !ll ts 26 felhasznlsval14. gy a grfnak s a dulisnak egy egy ttes s kbarajzolst fogjuk megkapni, ezek utn el kell ksz teni az (1)%(5) feltteleknek ;megfelel  k rrendszert. El bb azonban azt mutatjuk

meg, hogy van olyan r 2 IR+ v 1, melyre (r) = . Egy itercis eljrs seg tsgvel el fogunk ll tani egy; megfelel  r vektort. Az eljrs 2 lpcs b l fog llni, az (i) lpsben egy ri = ri  ri  : : : vektorsorozatot kpez nk gy, hogy ha brmely (ri ) koordinta kisebb mint , akkor ri rtkt megfelel en cs kkentve kapjuk ri+1 rtkt. Ennek a sorozatnak a hatrrtkeknt el ll r rtke olyan lesz, hogy minden koordintja pozit v, s minden lehetsges esetn (r)  . Az (ii) lpsben, ha valamely (r) > , akkor r n velsvel elrj k, hogy egyenl sg teljes lj n. Ekkor be kell ltni, hogy r rtke korltos marad az eljrs utn, s a feltteleknek megfelel lesz. A bizony ts vgn az is addik, hogy az (ii) lpsben a konvergencia ellen rzse f l sleges. El sz r nzz k meg hogyan vltozik a f ggvny, amikor r-nek egyetlen koordintjt vltoztatjuk. Ha n velj k r rtkt m g minden ms vltoz rtke xen marad, akkor (r) rtke cs kken, ugyanakkor  (r) rtke n

minden olyan -ra, amely szomszdja G^ -ban. ; (i) lps: Kezdetben legyen r0 = (1 1 : : :  1). Ha valamikor minden (r) koordinta legalbb , akkor vge az els lpsnek Tegy k fel, hogy van egy ri vektorunk, amelynek nhny (ri ) koordintja kisebb mint . Ekkor a k vetkez k szerint deniljuk ri+1 vektort. Ha (ri )  , akkor legyen ri+1 = ri. Ha (ri) < , akkor ri+1 legyen a k vetkez egyenlet egyrtelm megoldsa: ! X ri Arctg ri+1 = :   ? Nyilvnval, hogy ilyen mdon nem lehet egyetlen ri+1 koordinta sem 0. Az eljrsunk vagy vget; r egyszer, vagy vgtelen sokig folytatjuk, ez utbbi esetben minden rj j=0 sorozat pozit v szmoknak egy monoton cs kken 15 sorozata, gy ltezik egy nem negat v r hatrrtke. Meg kell mutatni, hogy r 6= 0, a f ggvny folytonossgbl k vetkezik, hogy (r )   s gy folytathatjuk az eljrst az (ii) lpsnl. Tegy k fel, hogy nhny (rj ) sorozat tart a 0-hoz, ahogy j ! 1, s legyen S az a nem res halmaz, melyre 1 1 1 1

14 15 Ks bb szerepel, hogy hogyan kell ezt a ragasztst elvgezni. nem felttlenl szigor an monoton cskken 27  jlim rj = 0 : S= !1 Minden 2 S esetn valamilyen j -re (rj ) < , k l nben r nem cs kkent volna az eljrs sorn, gy a hatrrtke 1 lenne. Ha pedig valamikor j , akkor ez megmarad az eljrs sorn, mivel r rtkt csak (r ) annyira cs kkentj k, hogy (ri+1) rtke  lehessen s ms r cs kkentse nem n velheti (r) rtkt. Teht minden elg nagy j -re X 2S  (r jS j  j) azonban X 2S  (r j) = XX ! rj Arctg j : r  2S  ? G^ minden lre, amelynek mindkt vgpontja S -ben van, a fenti sszeg vgpontokhoz tartoz tagjainak sszege minden j -re 2 , mivel Arctg  r   r   r + Arctg r = 2 : rj Ha az l vgpontja S -beli, vgpontja pedig nem, akkor j tart a vgr telenhez, ahogy j tart a vgtelenhez s gy lim Arctg j !1 rj  = : rj 2 A 3.3 Lemma (2) ll tsa szerint legalbb 2jS j + 1 olyan l van, amelynek valamelyik

vgpontja S -beli, gy a fenti sszeg legalbb jS j + 2 , ez pedig ellentmonds lenne. Teht feltevs nk nem igaz, S = Az eljrs vgn teht kaptunk egy pozit v koordintj s0 vektort, melyre (s0)  . (ii) lps: Most egy si = (si si  : : : ) vektorsorozatot denilunk. A kezd rtket az (i) lps szolgltatja. Ha (si) = , akkor legyen si+1 = si, ha pe28 dig (si) > , akkor si+1 rtke az albbi egyenlet egyrtelm megoldsa legyen: ! X si Arctg si+1 =  :   ? j Nyilvnval,; hogy  (s ) rtke nem cs kken  al. Ezt a mveletet iterlva  kapjuk az sj j=0 monoton n vekv sorozatot. Ha minden sorozat korltos marad, akkor a vektorok egy s rtkhez tartanak, a hatrrtkekb l sszell tott vektorra, ismt folytonossgbl addik, hogy (s ) = , amelyre sz ksg nk volt. ;  Tegy k fel, hogy nhny sj j=0 sorozat nem korltos. Legyen S azon a X2 G^ jindexek halmaza amelyre ez a sorozat vgtelenhez tart. Most ^  (s ) sszeget fogjuk vizsglni, az el z ekhez

hasonlan. Ha G egy  S lnek mindkt vgpontja S -ben van, akkor az sszegben a hozzjuk tartoz kt tag sszege 2 , ha pedig csak az vgpont S -beli a pedig nem, akkor ahogy j tart a vgtelenhez az sj is tart a vgtelenhez, m g sj korltos marad, vagyis 1 1 1 1 2 lim Arctg j !1 sj = 0: sj Legyen az S elemei ltal G^ -ban kifesz tett rszgrf G^ (S ), leinek halmaza E . Az el bbiek szerint: lim j !1 X 2S (s j) = jE j 2 : Mivel az sszeg minden tagja legalbb , az sszeg rtke legalbb jS j, amelyekb l jE j  2jS j addik, amely ellentmond a 3.3 Lemma (2) ll tsnak Teht S = , vagyis s megfelel vektor 1 Most vizsgljuk meg az egyrtelmsg krdst. Legyen kt megoldsa a (r) =  egyenletnek r s r , ahol a k ls lap minden a cscsra ra = ra. Legyen S = f j r > rg. Ha r s r nem egyenl k, akkor feltehetj k, hogy S nem res, gy:  r  X XX jS j = Arctg r = (r) =   S  S  0 0 0 0 2 2 29 ? 1 0 B X C C B + C B 2 A @  S  S   1 0 B X C C

B + C B 2 A @  S  S     r  X XX  0 B X =B B @   S   0 B X <B B @   S 2 2 62 ? ? 2 2 ? 62 1  r C Arctg r C C<  A 1  r C Arctg r C C=  A 0 0 ? 0 Arctg r =    2S  ? 0 S (r ) 0 = jS j : 2 Ez pedig ellentmonds. Teht pontosan egy olyan r vektor van, amelyre teljes l, hogy a k ls lap minden a cscsra ra = 1, tovbb (r) = . Ekkor elksz thet k a K deltoidok. Ksz ts k el azt a G~ grfot, amelynek cscsai a G cscsainak, leinek valamint lapjainak feleltethet k meg, s kt cscsa k z tt akkor fut l, ha az egyik cscsnak a G egyik le, a msik cscsnak pedig vagy az l egyik vgpontja vagy pedig az l ltal hatrolt egyik lap felel meg. Ez a G~ grf nem ms mint a grfnak s a dulisnak egy ttes s kbarajzolsa, ahol a grf s a dulis grf megfelel lei (egy pontban) metszik egymst. Ezek a metszspontok minden let 2 rszre osztanak, ezekhez rendelt nk j cscsokat, az leket pedig a kapott s kbarajzols alapjn hatroztuk

meg. G~ lapjai ngysz glapok, minden lapot 2 l-pont, egy G-beli s egy G -beli cscs hatrol, ppen az ilyen lapokhoz ksz tett k el a K deltoidokat16. A G~ grfot gy is megkaphatnnk, hogy G^ grfban minden laphoz hozzvesz nk egy j cscsot, amelyet a lap cscsaival k t nk ssze, majd a kapott grfbl t r lj k G^ leit17. Teht a G~ ;fF0g grf s kbarajzolsnak megfelel en szeretnnk a deltoidokat ragasztani. A 22 !ll ts seg tsgvel bizony tjuk, hogy ez megtehet Minden deltoidot vgjunk fel a f tljval kt rszre, a G~ ;fF0g grfban pedig hzzuk be a G^ leinek megfelel leket. gy a grf minden lapjt kt hromsz glapra osztottuk gy, hogy sszek t tt k a rajta lv G illetve G grf cscsnak megfelel kt cscsot. A laphoz rendelt deltoidot is kt rszre vgtuk az ennek az lnek megfelel tl seg tsgvel. A kapott grf lapjaihoz rendelt hromsz glapokra ellen rizni kell a 2.2 !ll ts hasznlathoz sz ksges feltteleket A grfnak a k ls tartomnnyal nem szomszdos cscsainl,

a csccsal szomszdos lapokhoz rendelt hromsz gek megfelel sz geinek sszege 2 kell legyen. Ha ez a cscs G egy lhez tartozik, akkor 4 hromsz glappal szomszdos, amelyek mindegyikben derksz g a neki megfelel sz g. Ha G egy lhez vagy lapjhoz tartoz   16 17 a vgtelen tartomnyhoz tartoz lapok kivtelvel Csak az leket trljk, a vgpontjaikat nem! 30 cscsrl van sz, akkor az itt tallkoz lapok sz geinek sszege 2 (r) = 2. gy alkalmazhatjuk a 2.2 !ll tst, a hromsz glapok a s kbarajzolsnak megfelel en egymshoz ragaszthatk A kapott hlzat hatrn 6 cscs van, 3 a G grf k ls tartomnnyval szomszdos cscsainak felel meg, 3 pedig az ezeket sszek t lekhez tartoz l-pontoknak. Az l-pontoknak megfelel cscsokban kt hromsz g derksz gt ragasztottuk ssze, gy a hlzat egy hromsz get alkot. Az l-pontoknak megfelel pontok s a hromsz g cscsai k z tti megfelel szakaszok egyenl sgb l k vetkezik, hogy az l-pontoknak megfelel pontok a hromsz g be rt k

rnek rintsi pontjai. A G F C B E 17. bra Ismert, hogy ha egy ABC 4 hrom oldaln adott egy-egy pont, E 2 BC F 2 AB G 2 AC ezek akkor s csak akkor lesznek a be rt kr rintsi pontjai, ha jFAj = jGAj, jFB j = jEB j s jEC j = jGC j. Ezzel a mdszerrel lnyegben a deltoidokat ragasztottuk ssze. Az sszes 2 (G^ ; fF0g) elemnek megfelel cscsokba rjunk r sugar k r ket, s a kapott elhelyezst egsz ts k ki a k ls tartomnynak megfelel k rrel, ami az egsz hlzat ltal alkotott hromsz glap be rt k re legyen. Mr csak azt kell beltni, hogy az gy kapott k relhelyezs az (1)%(5) feltteleket kielg ti. A G egy lapjhoz (a k ls tartomny kivtelvel) tartoz deltoidok egy ttesen egy konvex soksz get hatroznak meg, amelynek annyi oldala van, ahny le az adott lapnak. Ennek a soksz gnek a be rt k re lesz az -hoz tartoz k r, az rintsi pontok pedig a megfelel l-pontok lesznek, ahol a szomszdos deltoidok derksz geit ragasztottuk ssze. Ezek a soksz gek k l nb z lapok esetn

diszjunktak, gy nincs kt laphoz tartoz k r, amelyek metszenk egymst A k ls tartomnnyal majd ks bb foglalkozunk. Ehhez hasonlan belthat, hogy nincs kt k l nb z cscshoz tartoz k r, amelyek metszenk egymst, ez a k ls tartomny cscsaira is mk dik. Ezzel az (1) felttelt a k ls tartomnyhoz tartoz k r kivtelvel belttuk. A hlzat konstrukcijbl addan minden laphoz illetve cscshoz tartoz k r tmegy a vele szomszdos lekhez tartoz l-pontokon, vagyis a (2) felttel is teljes l. Ha egy cscs s egy lap nem szomszdosak (G^ -ban), akkor a hozzjuk tartoz deltoidok diszjunktak, gy nem metszhetik egymst a megfelel k r k. A k ls tartomnyhoz tartoz k rvonal a vele szomszdos cscsokhoz tartoz deltoidok 31 egyes tsn bel l halad, gy erre is teljes lnek az el bbiek. Ha a cscs a lap hatrn van, akkor pedig van egy hozzjuk tartoz deltoid, amely f tljnak a kt vgpontjban van a megfelel k r k k zppontja, s a deltoid konstrukcija miatt a k r k derksz gben

metszik egymst. A k ls lap is nyilvnvalan derksz gben metszi a 3 megfelel cscshoz tartoz vektort Ezekb l (3) s az (5) felttel is addik. Az is nyilvnval, hogy a k ls tartomnyhoz tartoz k r kivtelvel semelyik k r nem tartalmazhat a belsejben egy msikat. Most mr csak azt kell megmutatni, hogy a k ls tartomny a belsejben tartalmazza az sszes vele nem szomszdos laphoz tartoz k rt, ezzel az (1) felttel hinyz rszt is beltjuk a (4) felttel mellett. A k ls tartomnyhoz tartoz k rvonal a vele szomszdos cscsokhoz tartoz deltoidok egyes tsn bel l halad, gy nyilvn a belsejben tartalmaz minden olyan k rlapot, amelyhez tartoz lap nem szomszdos ezekkel a cscsokkal, a k ls tartomnnyal szomszdos lapokhoz tartoz k r k pedig bel lr l rintik a k ls tartomnyhoz tartoz k rt. A t bbi laphoz tartoz k r mer legesen metszi valamelyik k ls cscshoz tartoz k rt, a kt metszspontjuk pedig a k ls laphoz tartoz k r belsejben van18, s a k ls laphoz tartoz k r is mer

legesen metszi a szomszdos cscsokhoz tartoz k r ket, gy a maradk lapokhoz tartoz k r k is a belsejben kell legyenek. Az elhelyezsb l addik, hogy nincs k r, amelynek a sugara nagyobb lenne, mint 1, gy az (ii) lpsben a konvergencia ellen rzse f l sleges volt, minden n vekv sorozatunk 1 alatt maradt. Ha a k ls lap nem hromsz g, akkor inverzi s a dulis grfra val ttrs seg tsgvel visszavezetj k a problmt erre az esetre. Az egyrtelmsg k vetkezik abbl, hogy a le rt transzformcikkal elrhetj k, hogy a k ls tartomny hromsz g legyen s a cscsaihoz tartoz k r k 1 sugarak. Ekkor pedig a reprezentci egyrtelm kell legyen a megfelel r vektor egyrtelmsge miatt, ugyanis k l nb z megfelel k rrendszerhez k l nb z megfelel r vektor tartozik. Ezzel a ttel bizony tst befejezt k. 2 Vgezet l vizsgljuk meg a ttelben szerepl felttelek sz ksgessgt! Az, hogy a grf legalbb 4 pont, a lapok reprezentlhatsga miatt kellett. G s kbarajzolhatsga is

nyilvnvalan sz ksges, mivel egy ilyen reprezentci seg tsgvel megadhat G egy s kbarajzolsa (egyenes vonalakkal) Mr csak a 3- sszef gg sget kell megvizsglni. Legyen G egy s kgrf, amely nem 3- sszef gg , s tegy k fel, hogy ltezik a ttelnek megfelel reprezentcija. K nnyen lthat, hogy ilyen nem ltezhet, ha G nem sszef gg , vagy pedig ha van benne elvg cscs. Ha pedig G legalbb 2- sszef gg , akkor van egy S  V (G^ ) halmaz, amely nem tartalmazza a k ls tartomnyhoz tartoz cscsot s G^ -nak legfeljebb 2jS j lvel szomszdos. Min18 mivel ezek az el bb le rt deltoidok valamelyiknek a derkszg cs csai 32 den 2 G^ esetn legyen r a reprezentciban hozz tartoz k r sugara s a bizony tsban szerepeltek szerint deniljuk a  rtkt. Ebb l 0 B X B X jS j = (r) = B @   S  S 2 2 ? 1 0 B X C C B + C B 2 A @  S  2 62 ? S 1  r C Arctg r C C:  A Itt a jobb oldalon ll sszeg legalbb ( 2 )(2jS j) = jS j, s egyenl sg csak akkor

lehetne, ha r = 0 teljes lne minden 2 S esetn. Ez pedig lehetetlen, teht a 3- sszef gg sg is sz ksges felttel a reprezentcihoz. 33 3.2 G mb t lben rint poliderek A 3.1 Ttel seg tsgvel k nnyen belthat az albbi, poliderekre vonatkoz meglep eredmny. 3.4 Ttel Minden G legalbb 4 cscs 3- sszefgg skgrfhoz tallhat olyan P polider, amelynek a grfja G, s P sszes le rint egy adott g mb t. Bizony ts. Meg fogjuk konstrulni a P polidert Mivel G grfjra teljes lnek a 3.1 Ttel felttelei, G reprezentlhat egy megfelel k rrendszerrel Ksz ts k el a ttelben szerepl reprezentcijt a grfnak. A k rrendszert egy specilis sztereograkus projekcival vet ts k fel egy g mbre. A G lapjainak megfelel k r k s kjai ltal meghatrozott polider lesz P . A k rrendszert gy vet ts k fel sztereograkus projekcival a g mbre, hogy a lapokhoz tartoz k rvonalak konvex burka a belsejben tartalmazza a g mb k zppontjt. Emellett mg arra is sz ksg lesz, hogy a

cscsokhoz rendelt k rlapok mindegyiknek a kpe rsze egy flg mbnek Ezeket k nnyen elrhetj k Vlasszunk a s kon egy olyan k rt, amely benne van a k ls laphoz tartoz k rben, s a k zppontja egy msik laphoz tartoz olyan k rben van, amelyet tartalmaz a k r nk. Ilyet a k ls tartomnytl k l nb z laphoz tartoz k rnek egy megfelel pontjbl val igen kis arny felfjsval kaphatunk A sztereograkus projekcit ezek utn gy hajtsuk vgre, hogy az el bb kivlasztott k r menjen az egyenl t be. Ekkor nyilvn a feltteleknek megfelel lesz a vet ts, mivel az szaki s a dli plus is benne lesz az szaki illetve dli flg mbben lev g mbi k rlapban, amelyb l k vetkezik az egyik sz ksges felttel nk. A msik felttel trivilisan teljes l, mivel egyetlen cscshoz tartoz k rlap sem tartalmazza az szaki s a dli plust. A dli plust azrt nem tartalmazzk, mert a kivlasztott k r nk k zppontjt nem tartalmazhattk, mivel vagy diszjunktak a megfelel laphoz tartoz k rt l, vagy mer

legesen metszik azt. A kapott g mbi k rreprezentciban vegy k a lapokhoz tartoz k r k s kjai ltal hatrolt, a g mb k zppontjt tartalmaz fltereket ezek egy konvex polidert hatroznak meg, legyen ez P . A vet ts specilis tulajdonsgai miatt a flterek metszete korltos kell legyen. A kapott P polider kt szomszdos lapja a G szomszdos lapjaihoz tartoz, egymst rint k r k s kjai lesznek. Ez k nnyen lthat Vegy k a G-nek egy f lapjhoz tartoz k r s kjt, legyen ez Sf . Metssz k el az Sf s kot az f lappal szomszdos lapokhoz tartoz flterekkel, gy kapunk egy Kf soksz get. Azt ll tom, hogy Kf soksz get az sszes laphoz tartoz fltr tartalmazza Az f -fel szomszdos lapokra ez trivilis. G lapjaihoz (a k ls tartomny kivtelvel) rendelj k hozz a nekik megfelel k rlemez sztereograkus projekci utn kapott kpt. A k ls tartomnyhoz nem a k rlap kpt, hanem az szaki plust tartalmaz lemezt rendelj k, hogy a g mbi k rrendszer megfelel legyen. gy a lapokhoz tartoz k

rlemezek belseje is diszjunktak lesznek. 34 Ha egy fltr nem tartalmazn a Kf soksz get, akkor vagy a hatrol s kja metszi a soksz g belsejt, vagy a fltr komplementernek a lezrtjban van a Kf . Ez utbbi eset nem fordulhat el , mivel a G lapjaihoz tartoz g mbi k rlemezek belsejei diszjunktak. Megmutatjuk, hogy az els eset sem fordulhat el , ehhez sz ksg nk lesz a cscsokhoz tartoz k rlemezekre. Egy cscshoz tartoz k rt a vele szomszdos lapokhoz tartoz k r k mer legesen metszenek a g mb n is, mivel a sztereograkus projekci sz gtart. Legyen v a G grf egy cscsa, a vele szomszdos lapok pedig a s kbarajzolsnl egy adott k r ljrs szerint f1 f2 : : :  fn (fn+1 = f1). Az fi s fi+1 lapokhoz rendelt k r k rintik egymst, az rintsi pontjuk a v-hez rendelt k r n van. Emiatt a kt laphoz tartoz s k metszsvonala a g mb t rinti, az rintsi pont a v-hez tartoz k r n kell legyen. Mivel a kt laphoz tartoz k r mer legesen metszi a v-hez tartoz k rt, a kt laphoz

tartoz k r metszsvonala egy alkotja lesz annak a g mbh z hzott rint kpnak, amely a v-hez tartoz k rben rinti a g mb t. Ennek a kpnak a cscsa legyen Mv . gy minden v csccsal szomszdos laphoz tartoz s k tmegy Mv ponton, s az ezek ltal hatrolt flterek metszete egy Mv vgtelen cscs gla. Trj nk vissza a Kf soksz gre. Legyenek G grfnak az f lap a hatrn lev cscsai v1 v2 : : :  vk . Az el bb lttuk, hogy a vi cscsokkal szomszdos lapok nem metszhetik a Kf soksz g belsejt. Ha egy soksz glaphoz tartoz s k metszi a Kf soksz get, akkor annak metszenie kell valamely vi-hez tartoz k rt is. Ekkor pedig ezzel a vi csccsal szomszdos lapnak a s kjrl van sz, ami nem metszi a Kf soksz g belsejt. gy P polider kt lapjnak pontosan akkor van k z s le, ha a nekik megfelel G-beli lapok szomszdosak, s pontosan akkor van k z s cscsuk, ha a nekik megfelel G-beli lapoknak van k z s cscsa. Teht G grf a P polider grfja P kt szomszdos lapjnak metszsvonala rinti

a g mb t, mert a s kok metszete a g mbbel 2 egymst rint k r. Az rintsi pont az l belsejben kell legyen, mivel k l nben az l egyik vgpontjhoz tartoz k rlemez tartalmazna egy flg mb t. Ezzel az ll tst bebizony tottuk 2 Megjegyzs. A 34 Ttelb l k vetkezik a 211 Ttel egyik fele, hogy minden legalbb 4 cscs 3- sszef gg G s kgrfokhoz ltezik olyan konvex polider, amelynek G a grfja.19 A 211 Ttel msik felnek felhasznlsval a 34 Ttel tfogalmazhat az albbiak szerint: 3.5 Ttel Minden konvex polidernek van olyan kombinatorikus ekvivalense, amely lben rint egy adott g mb t. 19 2 A 3.4 Ttelnek teht kvetkezmnye a Steinitz-ttel 35 4. G mbbe rhat poliderek 4.1 G mbbe s g mb k r rhatsg IE -ben 3 4.1 Den ci Tekintsk a Cayley-Klein modellt, ami a IH3 hiperbolikus tr egy modellje az Euklideszi trben. IH3 pontjait egy g mb B 3 bels pontjai reprezentljk Ennek a g mbnek a hatrt nevezzk vgtelen sugar g mbnek, s S2 -nel jel ljk. (S 2 =

@B 3) Megjegyzs. Lnyegben a hiperbolikus teret kib v tett k egy idelis s k pontjaival 4.2 Den ci Egy IH3-ben idelis cscs polidernek neveznk vges sok zrt fltr metszett, ha a Cayley-Klein modellben S2 nhny pontjnak hozzvtelvel a modellt alkot B 3 g mbbe bert polidert kapunk.20 Mint mr a bevezet ben eml tettem Steiner vettete fel a mlt szzadban azt a problmt, hogy karakterizljuk a g mbbe s g mb k r rhat21 polidereket. Ebben a tmban is Steinitzt l szrmaznak az els fontos eredmnyek, mutatott el sz r olyan polidert pusokat amelyek nem rhatk g mbbe. T le szrmazik az albbi ttel is, mely a g mbbe s g mb k r rhatsg k z tti sszef ggst mutatja meg: 4.3 Ttel Egy G grfhoz akkor s csak akkor ltezik olyan g mbbe rhat polider, amelynek G a grfja, ha G skgrf, s a G dulishoz ltezik olyan g mb k r rhat polider, amelynek a grfja G . Bizony ts. Mivel mr lttuk, hogy a poliderek grfjai s kgrfok, gy ezzel a felttellel nem foglalkozunk, ez

csak ahhoz kellett a ttelben, hogy beszlhess nk dulis grfrl. Igen egyszer a bizony ts Ha a P polider g mb k r rhat, akkor az rintsi pontok konvex burka P polrisa lesz, amely gy g mbbe rhat s a grfja G . Ha P g mbbe rhat s belsejben tartalmazza a g mb k zppontjt, akkor a polrisa g mb k r rhat. Ha P nem tartalmazza a g mb k zppontjt, akkor el bb vgrehajtunk egy transzformcit. Vegy nk fel egy olyan derksz g koordintarendszert, amelynek origja a g mb k zppontja, az 1. tengelye thalad a polider belsejn s a g mb sugara egysg Tekints k az albbi projekt v transzformcit. p Legyen j j < 1 ks bb megvlasztand konstans s = 1 ; 2. A T transzformcit az albbi kplettel deniljuk: 1 1 1     x;  T (x y z) = 1 ; x  1 ;y x  1 ;z x : 20A polider minden cs csa S2 -en helyezkedik el, az egy cs csba fut lek emiatt prhuzamos egyenesek. 21Gmb kr rhat a polider, ha a ltezik olyan gmb, amelyet minden lapja rint. 1 36 Ez a

transzformci az egysgg mb t nmagra kpezi s T (  0 0) = (0 0 0), vagyis rtkt gy kell megvlasztani, hogy az (  0 0) pont a polider belsejben legyen. Ily mdon P polider kpe a korbbi feltteleknek megfelel lesz (s nyilvn kombinatorikusan ekvivalens P -vel), vagyis az el z esetben le rtak alkalmazhatk. 2 Lthat, hogy elg karakterizlni a IH -beli idelis cscs polidereket, mivel a Cayley-Klein modellben ezek ppen a g mbbe rhat poliderek. A 43 Ttel alapjn pedig a g mb k r rhat polidereket is tudjuk gy karakterizlni. A k vetkez rszben szerepl 4.11 Ttelb l az el bbiek alapjn a k vetkez ttelt mondhatjuk ki: 3 4.4 Ttel Egy P poliderhez akkor s csak akkor ltezik vele kombinatorikusan ekvivalens g mb k r rhat polider, ha a P polider G grfjban ltezik olyan W slyozsa az leknek, amelyre az albbi hrom felttel teljesl: (1) Minden e 2 E (G) lre 0 < W (e) < 12 . (2) G minden lapjra teljesl, hogy a rajta lev lekre sszegezve a

slyokat 1 lesz az eredmny. (3) Ha egy olyan k rben szerepl lekre adjuk ssze a slyokat, amely k r nem hatrol lapot, akkor az eredmny nagyobb lesz 1-nl. Hasonl an egy P poliderhez akkor s csak akkor ltezik vele kombinatorikusan ekvivalens g mbbe rhat polider, ha a P polider G grfjnak G dulishoz ltezik olyan W slyozsa az leknek, amelyekre a fenti hrom felttel teljesl.  2 Warren D. Smith bebizony totta, hogy ltezik a cscsok szmban polinomilis algoritmus, amely eld nti, hogy egy grfban ltezik-e a feltteleknek megfelel slyozs. Azta mr Rivin tallt egy lineris algoritmust a krds eld ntsre Megeml tennk mg (bizony ts nlk l) az albbi, M. Dillencourt-tl s W. D Smith-t l szrmaz ttelt: 4.5 Ttel Minden 4- sszefgg, legalbb 4 cscs G skgrfhoz van olyan g mbbe rhat polider, amelynek a grfja G. 2 A 4.4 Ttel bizony tsa el tt megmutatjuk, hogy az ottani felttelek nem minden poliderre (pontosabban azok grfjaira) teljes lnek, azaz

mutatunk vgtelen sok polidert pust, amelyek nem rhatk g mbbe. Ehhez el sz r deniljuk a k vetkez mveletet: 37 4.6 Den ci Adott egy skgrf Minden lapjhoz vegynk hozz egy j cs- csot, s minden ilyen cscsot k ssnk ssze annak a lapnak a cscsaival, amelyhez hozzvettk. Ezt a mveletet nevezzk csillagostsnak Egy P polider a P polider csillagja, ha P grfja izomorf a P grfjb l csillagostssal kaphat gral Megjegyzs. A csillagos ts utn nyilvn ismt s kgrfot kapunk Ha egy konvex P polider grfjt csillagos tjuk, akkor a kapott grf is el ll egy polider grfjaknt, pldul gy, hogy a P polider lapjaihoz elg k zel felvesz nk j cscsokat, s vessz k ezeknek a pontoknak s P -nek a konvex burkt. gy minden polider csillagos that. Nyilvnval, hogy egy P polider csillagjai kombinatorikusan ekvivalensek, s a vel k kombinatorikusan ekvivalens poliderek is a csillagjai P -nek. Az egyszersg kedvrt a tovbbiakban egy P polider cscsainak halmazt V (P

)-vel, leinek halmazt E (P )-vel s a lapjainak halmazt F (P )-vel fogom jel lni. 4.7 Ttel Ha a P poliderre teljesl, hogy jV (P )j jF (P )j, ahol V (P ) a polider cscsainak, F (P ) pedig a lapjainak a halmaza, akkor P csillagjai nem rhat k g mbbe. Bizony ts. Azt kell beltni, hogy nem ltezik a 44 Ttelnek megfelel slyozsa a dulis grf leinek Azt mutatjuk meg, hogy a megfelel poliderekben nem ltezik mr a ttel (1) s (2) felttelnek megfelel slyozs sem. Ez nyilvn azzal ekvivalens, hogy a polider grfjnak leit nem tudjuk gy slyozni 0 s 21 k z tti slyokkal, hogy minden cscsnl az oda befut lek slyainak sszege 1 legyen. Legyen P a P polider egy csillagja Indirekt ton bizony tunk tegy k fel, hogy mgis ltezik az el bbieknek megfelel slyozsa a P polider grfjnak. P grfjnak cscsai kt osztlyba sorolhatk, legyen VP azoknak a cscsoknak a halmaza, amelyek P grfjnak is cscsai, s legyen VS azon cscsok halmaza, amelyet P grfjnak a csillagos tsa

sorn vett nk hozz a grfhoz. Mostantl P grfjval fogunk foglalkozni, legyen ez G. Nyilvnval, hogy ha egy l egyik vgpontja VS -beli, akkor a msik vgpontja VP -beli s ez nem megford that, vagyis vannak VP -beli cscsok, amelyek k z tt megy l. Adjuk ssze a VS -beli cscsokba fut lek slyait. Mivel egy cscsba fut leken a slyok sszege 1, s kt VS -beli cscs k z tt nem megy l, az eredmny jVS j = jF (P )j lesz. Ez nyilvn kisebb, mint az sszes lre sszegezve a slyokat, ami fel lr l becs lhet a jVP j = jV (P )j rtkkel, mivel minden lnek legalbb az egyik vgpontja VP -beli. Teht jF (P )j < jV (P )j kne legyen, ami ellentmond a ttel felttelnek. Teht P nem lehet g mbbe rhat. 0 0 0 0 0 0 0 2 Ennek a ttelnek egy k vetkezmnye az albbi ll ts. 4.8 ll ts: Ha egy polider minden lapja hromsz g, akkor a csillagjai nem rhat k g mbbe. 38 Bizony ts. Legyen P egy csupa hromsz glapbl ll polider Legyenek a cscsainak, leinek s lapjainak

halmazai rendre V , E s F . Ekkor 3jF j = 2jE j, amelyb l az Euler-fle poliderttel seg tsgvel: jF j + jV j ; 3 jF j = 2 2 addik, vagyis 1 2 jV j = jF j + 2 : Tudjuk, hogy jF j  4, gy a fenti kpletb l jV j jF j. Teht a P polider teljes ti a 4.7 Ttel felttelt, gy P csillagjai nem lehetnek g mbbe rhatk 2 Mutatunk olyan nem g mbbe rhat pldt is, amelynek a bizony tshoz a 4.4 Ttel minden felttelre sz ksg van 4.9 ll ts: Ha egy kocknak levgjuk az egyik cscst, mondjuk a belle kiindul 3 l felezpontjn tmen skkal, akkor a kapott polider tpusa nem g mbbe rhat . Bizony ts. Indirekt ton bizony tunk, tegy k fel, hogy ltezik a 44 Ttel feltteleinek megfelel slyozs a kapott polider grfjban. A polider grfja a k vetkez : E B F C H I J G D A 18. bra Ha sszeadjuk az A E F s G cscsokba fut lek slyait s kivonjuk bel le a B C s D cscsokba fut lek slyainak az sszegt, akkor az eredmny a (2) felttel alapjn 1 lesz. Ugyanaz az

eredmny addik, ha az EH IF s JG leken lev slyokat sszegezz k, m ez a (3) felttel miatt nagyobb, mint 1, ami ellentmonds. 2 39 4.2 IH -beli konvex idelis cscs poliderek 3 4.10 Den ci Egy P idelis polider grfja a Cayley-Klein modellben P - nek megfelel polider grfja legyen. Minden konvex polider G grfjnak a G dulist elltjuk egy slyozssal. A G grf minden e lhez egy W (e ) slyt rendelnk, ahol W (e ) rtke a P poliderben e -hoz tartoz e lnl lev lapok kls sz ge.       Ebben a rszben az albbi ttel bizony tsval fogunk foglalkozni: 4.11 Ttel Egy P polider idelis cscs akkor s csak akkor, ha a grfjnak a G dulisra teljeslnek az albbi felttelek: (1) Minden e 2 E (G ) lre 0 < W (e ) < . (2) G minden lapjra teljesl, hogy a rajta lev lekre sszegezve a slyokat 2-t kapunk eredmnyl. (3) Ha a G grfnak olyan e1 e2 : : :  ek leire adjuk ssze a slyokat, amely lek egy olyan k rt alkotnak, amely k r nem

hatrol lapot, akkor az eredmny nagyobb lesz, mint 2.          Bizony ts. Csak a felttelek sz ksgessgt fogjuk beltni Az (1) felttel trivilis, mivel P konvex. A (2) felttel nyilvn ekvivalens azzal, hogy P polider brmely v cscsra a bel le kiindul lekre sszegezve a k ls sz geket, 2 sz get kapunk eredmny l. Hzzunk egy elg kicsi v cscshoz tartoz Hv paraszfrt22. Ismert, hogy Hv paraszfrn bel l az Euklideszi geometria aximi teljes lnek. Hv -t a v-n tmen s kok paraciklusban metszik, kt ilyen s k sz ge megegyezik a hozzjuk tartoz paraciklusok sz gvel. Ennek alapjn Hv a P polidert egy pv soksz gben metszi, amelynek a k ls sz gei megegyeznek a P polider megfelel leinl lv k ls sz geivel. gy kszen vagyunk, hiszen az Euklideszi geometriban egy soksz g k ls sz geinek sszege 2. A (3) felttel sz ksgessgnek beltshoz nhny lemmra van sz ksg nk. 4.12 Den ci Legyen egy zrt t r ttvonal IH3-ben, cscsai sorrendben legyenek p1 p2

 : : :  pk , ahol p1 = pk . Legyen elfordulsa pi cscsban a pi 1 pipi+1 hromsz g pi cscsnl lev kls sz ge, ezt jel ljk i( )-val. A t r ttvonal ; teljes elfordulsa a  ( ) = k 1 X ; i=1 i( ) sszeg. 4.13 Lemma IH3-ben egy zrt t r ttvonalnak a teljes elfordulsa nagyobb, mint 2, kivve azt az esetet, amikor minden cscs egy egyenesen van. 22 Hv egy olyan paraszfra legyen, amely P minden v-b l indul lt metszi 40 Bizonyj ts. Ksz ts k el a Ti = p1pipi+1 hromsz geket, ahol 2 < i < k ; 2 Le- gyen i a Ti hromsz g pj cscsnl lev bels sz ge, ha pedig nincs ilyen, akkor legyen 0. Vegy nk egy kis g mb t pj k r l s ennek a metszett a Ti hromsz gekkel s a pi 1 pi pi+1 hromsz ggel A g mbi hromsz gegyenl tlensgb l23 ; X i j i   ; j ( ) addik. Ezt sszegezve minden megfelel j-re a k 2 X ; i=2 (Ti sz geinek sszege)  (k ; 1) ;  ( ) egyenl tlensget kapjuk. Minden hromsz gben a sz g sszeg legfeljebb 2 s mivel nem minden hromsz g elfajul,

van olyan, ahol ez kisebb 2-nl, gy a k vetkez szigor egyenl tlensg addik (k ; 3) > (k ; 1) ;  ( ) : Ebb l pedig k vetkezik a  ( ) > 2 egyenl tlensg. 2 4.14 Lemma Legyen ABC 4 egy g mbhromsz g, amelyben jAB j + jBC j = =  s amelynek B cscsnl lev sz ge < . Ekkor jAC j  s egyenlsg pontosan akkor van, ha jAB j = jBC j = 2 . Bizony ts. Ha jAB j = jBC j = 2 , akkor nyilvnval, hogy jAC j = Egyb- knt a szimmetria miatt feltehetj k, hogy jAB j > jBC j. Azt is feltehetj k, hogy jAC j <  , k l nben az ll ts trivilis. Legyen az AB vnek A1 az a pontja, melyre A1B = 2 , s legyen C1 az a pont, melyre BC1 = 2 s C 2 BC1. (Lsd a 19. brt!) Legyen F pont az AC oldal s a kisebbik A1C1 v metszete Ekkor AA1F 4  = CC1F 4, mivel F-nl lev sz geik egyenl k, A1%nl s C1-nl derksz g van, jAA1j = jCC1j s jAF j+jFC j = jAC j kisebb, mint . Ebb l k vetkezik, hogy F felez pontja az AC oldalnak s az A1C1 vnek is. gy az AA1F 4-nek az AA1 s az A1F

oldalai kisebbek, mint 2 , tovbb A1-nl van a derksz g. 23 alkalmazhatjuk a hromszgegyenl tlensget, mivel minden v nyilvnvalan kisebb -nl 41 B β C A1 F C1 A 19. bra Emiatt jAF j > jA1F j s az el bbi egybevgsg miatt ebb l az is addik, hogy jCF j > jC1 F j. Ezekb l jAC j = jAF j + jCF j > jA1F j + jC1 F j = jA1C1j = k vetkezik, amit bizony tani akartunk. 2 4.15 Lemma Legyen H1 s H2 kt flsk, amelyeknek k z s a hatrol egyenese (jel lje e ezt az egyenest) s a kt sk ltal bezrt sz g . Legyen P1 2 H1 s P2 2 H2, tovbb a kt pontot sszek t, a H1  H2 fellet bels metrikja szerinti geodetikus legyen , ennek az e egyenesre es pontja pedig P = H1 H2. Ekkor a P ( ) elforduls legfeljebb  ; Bizony ts. Vilgos, hogy a PP1 s a PP2 szakaszok unija, s ha  az e egyenes egyik P -b l indul flegyenese, valamint ha az 1 s 2 sz gek rendre a PP1 s a PP2 szakaszok  -val bezrt sz gei, akkor 1 + 2 = . Vegy nk egy P k zppont elg kis

sugar g mb t, ennek metszspontjai a PP1, a PP2 szakaszokkal s  -val rendre legyenek az A, C , s B pontok. Ekkor a g mb n jAB j = 1 , jBC j = 2 , az ABC 4-nek a B cscsnl lev sz ge = s jAC j = =  ; P ( ). Alkalmazva az el bbi 414 Lemmt azt kapjuk, hogy:  ; P ( )  amelyb l  ;  P ( ) addik, amit bizony tani akartunk. 42 2 Most visszatrhet nk a 4.11 Ttel bizony tshoz A (3) felttel sz ksgessgt akarjuk beltni Legyenek a G grfnak e1 e2 : : :  ek lei olyanok, amelyek egy k rt alkotnak, de nem egy lapot hatrolnak. Vegy k P poliderben azoknak az f1 f2 : : :  fk lapoknak a lnct, amelyekre fi fi+1 = ei (vagyis a G grfban lev k r cscsainak megfelel lapokat). Az sszes ei lnek nem lehet k z s az egyik idelis cscsa, mivel e1 e2 : : :  ek lek nincsenek egy lapon. Legyen f~i az ei s ei+1 egyenesek s kjban a kt egyenes k z tti sv. Nyilvnval, hogy fi  f~i k ~ ~ ~ Legyen F = fi. F topolgikusan ekvivalens egy vgtelen henger palstjval,  

      i=1 mivel megkaphat az f~i svok megfelel egyenesek mentn val sszeragasztsval. Azt akarjuk beltni, hogy ltezik egy geodetikus az F~ fel leten, amely homotp a meridinnal24. (Ez a geodetikus egyrtelm lesz, de ezt most nem bizony tjuk be, mivel nincs sz ksg nk r) A svok egyenesek diszjunkt unijra bonthatk, ezltal az F~ fel let is, s ezen egyenesek k z tt kell legyen kett , amelyek egymssal egyik irnyban sem prhuzamosak, ellenkez esetben minden egyenes ugyanabban az irnyban lenne prhuzamos egymssal, vagyis az sszes ei lnek k z s lenne az egyik idelis cscsa, ami persze nem lehet. Vegy nk kt ilyen nem prhuzamos egyenest. Az egyik egyenesen vgtelenhez tartva (akrmelyik irnyban), az egyenes pontjainak a tvolsga a msik egyenest l vgtelenhez tart. Vegy nk az F~ fel leten egy meridinnal homotp g rbt, ennek a hossza legyen h. Vegy k a kt egyenesen azt a kt szakaszt, amelyek pontjaira igaz, hogy a msik egyenest l vett tvolsguk

legfeljebb h. Vegy k azokat a meridinnal homotp g rbket, amelyek hossza h-nl kisebb, ezek biztosan metszik az el bbi kt szakaszt. gy a g rbknek egy kompakt tert kapjuk, ahol nyilvnval, hogy alulrl is korltos a g rbk hossza, s itt a hossz egy folytonos f ggvny, gy ltezik minimlis hosszsg g rbe ezek k z tt. Ez a g rbe geodetikus kell legyen, mivel ha nem lenne az, akkor valamelyik kt pontja k z tti rszt lecserlhetnnk a kt pontot sszek t geodetikusra gy, hogy r videbb hosszsg, a meridinnal homotp g rbt kapnnk, vagyis nem lenne minimlis hosszsg. Ez a geodetikus be van gyazva IH3-be, mint egy zrt t r ttvonal, amelynek a cscsai az ei egyeneseken vannak. a 415 Lemma szerint elfordulsa ezekben a cscsokban legfeljebb akkora, mint a megfelel kt lap k ls sz ge. A 4.13 Lemma szerint teljes elfordulsa nagyobb, mint 2, gy az ei leknl lev k ls lapsz gek sszege nagyobb, mint 2. Ezzel a (3) felttel sz ksgessgt is bebizony tottuk. A felttelek

elgsgessghez az Alekszandrov ltal kifejlesztett dierencilgeometriai mdszerekre van sz ksg. Ez lnyegesen k l nb zik a dolgozatban szerepl mdszerekt l, ezrt a felttelek elgsgessgt itt nem bizony tjuk. 2 24 egyszer kerli meg a felletet 43 Irodalom &1] P. Koebe: Kontaktprobleme der konformen Abbildung, Berichte ber die Verhandlungen der Schsischen Akad. d Wiss Math - Physische Klasse 88 (1936), 141-164. old &2] J. Steiner: Systematische Entwicklung der Abh(ngigkeit geometrischer Gestalten voneinander, Fincke, Berlin (1832) &3] E. Steinitz: )ber isoperimetrische Probleme bei konvexen Polyedern, J reine angew Math 159 (1928), 133-143 old &4] E. Steinitz: Polyeder und Raumeinteilungen, Enzykl math Wiss 3 (1922), 1-139. old &5] Hassler Whitney: Non-separable and planar graphs, Trans. American Math. Society 34 (1932), 339-362 old &6] Branko Gr nbaum: Convex polytopes, (1967) &7] Graham R. Brightwell - Edward R Scheinerman: Reprezentations

of planar graphs, SIAM J. Disc Math 6(2) (1993), 214-229 old &8] Craig D. Hodgson - Igor Rivin - Warren D Smith: A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere, Bulletin of the American Math. Society 27(2) (1992), 246-251 old &9] Igor Rivin: On geometry of convex ideal polyhedra in hyperbolic 3-space, Topology 32(1) (1993), 87-92. old &10] Craig D. Hodgson - Igor Rivin: A characterization of compact convex polyhedra in hyperbolic 3-space, Invent Math 111 (1993), 77-111 old &11] Igor Rivin : A characterization of ideal polyhedra in hyperbolic 3-space, Annals of Math. 143 (1996), 51-70 old 44