Körcsomagolási tétel

A körcsomagolás tétele (más néven Koebe-Andreev-Thurston tétel ) leírja, hogyan lehet megérinteni a köröket, ha nincs közös belső pontjuk. A körcsomagolás metszésponti gráfja (néha érintőgráfnak is nevezik ) olyan gráf , amelynek csúcsai köröknek, élei pedig érintőpontoknak felelnek meg. Ha a körök síkra (vagy ennek megfelelő módon gömbre) vannak csomagolva, akkor metszésponti gráfjukat érmegráfnak nevezzük . Az érmegrafikonok mindig összefüggőek, egyszerűek és síkbeliek . A körcsomagolás tétele kimondja, hogy ennek fordítva is igaz:

Körcsomagolási tétel : Bármely összefüggő egyszerű G síkgráfhoz van egy olyan körcsomagolás a síkban, amelynek metszésponti gráfja izomorf G - vel.

Egyediség

Egy G gráfot háromszögelt síkbelinek (vagy maximális síkbelinek) nevezünk , ha sík, és G gömbbe ágyazásának komplementerének bármely összefüggő komponensének pontosan három éle van a határon, vagy más szóval, ha G egy -egy gömbre homeomorf, egyszerű komplex dimenziós átfeszítő fája . Bármely G háromszögelt síkgráf összefüggő és egyszerű, így a körcsomagolási tétel garantálja egy olyan csomagolás létezését, amelynek érintőgráfja izomorf G -vel . Egy ilyen G gráfnak végesnek kell lennie, hogy a megfelelő tömörítésnek véges számú köre legyen. Ahogy a következő tétel is kimondja, bármely maximális síkgráf legfeljebb egy pakolásnak felelhet meg.

Koebe–Andreev–Thurston tétel : Ha G egy véges háromszögű síkgráf, akkor az a körcsomagolás, amelynek érintőgráfja (izomorf) G -vel , egyedülálló a Möbius-transzformációkig és az egyenesekre való visszaverődésekig.

Thurston [1] megjegyezte, hogy ez az egyediség Mostow merevségi tételének következménye . A sík, amelybe a körök be vannak csomagolva , a Poincaré-modell határának tekinthető egy féltérben . Ebből a szempontból bármely kör a hiperbolikus térben lévő sík határa. Minden egyes körcsomag hozzárendelhető nem metsző síkok halmazához, valamint nem metsző síkok egy második halmazához, amelyeket a három tömörítő kör közötti háromszögterületek határoznak meg. A különböző halmazokból származó síkok derékszögben metszik egymást, és megfelelnek az reflexiós csoport generátorainak , amelyek alaptartománya hiperbolikus sokaságnak tekinthető . Mostow merevségi tétele szerint ennek a tartománynak a hiperbolikus szerkezete a hiperbolikus tér izometriáiig egyedileg meghatározott. Ezek az izometriák, ha a Poincaré-modell határán történő cselekvés szempontjából vizsgáljuk, Möbius-transzformációkká alakulnak.

Létezik egy elemi bizonyítás is, amely a maximum elvén alapul, és azon a megfigyelésen, hogy három, egymást kölcsönösen érintő kör középpontját összekötő háromszögben az egyik kör középpontjában lévő csúcsban bezárt szög a sugarának növekedésével és növekedésével monoton módon csökken. monoton a másik két kör bármelyikének növekedésével. Ha ugyanarra a G gráfra két pakolást kapunk, akkor a reflexiók és Möbius-transzformációk segítségével a két töltetben a külső körök egymásnak felelnek meg és azonos sugarúak. Ezután legyen v egy G  belső csúcsa, amelyre a kettős körök mérete a lehető legtávolabb van egymástól. Ez azt jelenti, hogy v úgy van megválasztva , hogy maximalizálja a két csomag körének sugarainak r 1 / r 2 arányát. Ebből következik, hogy G minden v -t tartalmazó háromszöglapja esetén az első töltetben lévő v -nek megfelelő kör középpontjának csúcsával bezárt szög kisebb vagy egyenlő, mint a második töltet szöge, és csak akkor egyenlő, ha a másik kettő körök háromszöget alkotnak a második töltet r 1 / r 2 sugarainak arányával. De a háromszög középpontját körülvevő összes háromszög szögeinek összege mindkét töltetben 2π kell, hogy legyen, így a v -vel szomszédos összes csúcsnak ugyanolyan arányúnak kell lennie, mint magának v -nek . Ugyanezt az érvelést más körökre is alkalmazva kiderül, hogy mindkét csomagban minden körnek azonos a kapcsolata. De a külső köröket 1-es arányra alakítjuk át, így r 1 / r 2 = 1, és mindkét csomagnak egyenlő sugara van minden körre.

A körcsomagolási tétel általánosításai

A körtömörítés általánosítható olyan grafikonokra, amelyek nem síkbeliek.

Ha G egy gráf, amely beágyazható egy S orientálható felületbe , akkor létezik egy állandó görbületű d Riemann-metrika S -en és egy ( S , d ) -be csomagoló kör , amelynek érintőgráfja izomorf G -vel. Ha S zárt ( kompakt és nincs határa ), és G az S  háromszögelése , akkor ( S , d ) és a csomagolás a konform ekvivalenciáig egyedi. Ha S  egy gömb, akkor a konformális ekvivalencia ekvivalencia Möbius-transzformációkig; ha tórusz, akkor konstanssal és izometriákkal való szorzásig; ha a felület nemzetsége legalább 2, akkor az izometriáig.

A körcsomagolás tételének egy másik általánosítása magában foglalja az érintési feltételt a szomszédos csúcsoknak megfelelő körök metszésszögének megadásával. Ennek a tételnek a következő elegáns változata van. Tegyük fel , hogy G egy véges 3-összefüggésű síkgráf (más szóval poliéder gráf ), akkor van olyan körcsomagoláspár, hogy az egyik csomag metszésponti gráfja izomorf G -vel, a másik metszésponti gráfja pedig izomorf G síkbeli duális gráfjához . Ezen túlmenően a G -ben lévő bármely csúcs és a vele szomszédos lap esetén az első tömítés csúcsának megfelelő kör derékszögben metszi a második töltetben lévő lapnak megfelelő kört [2] . Például, ha ezt az eredményt egy tetraéder gráfjára alkalmazzuk, tetszőleges négy páronkénti érintőkörhöz egy második négy egymást érintő érintő kört kapunk, amelyek mindegyike merőleges az első halmaz háromra [3] . További általánosítást kaphatunk, ha a metszésszöget inverz távolságra cseréljük [4] .

Egy másik általánosítás lehetővé teszi a köröktől eltérő alakzatok használatát. Tételezzük fel, hogy G = ( V , E ) egy véges síkgráf, és G minden v csúcsa egy olyan alaknak felel meg , amely homeomorf a zárt egységkoronggal, és amelynek határa sima. Ezután a síkon van egy olyan pakolás , hogy akkor és csak akkor és mindegyikhez a halmazt mozgatással és skálázással kapjuk meg. (Megjegyzendő, hogy az eredeti körtömörítési tételnek három csúcsparamétere van, amelyek közül kettő a megfelelő kör középpontját, egy pedig a sugarat adja meg, és minden élhez tartozik egy egyenlet. Ez érvényes erre az általánosításra is.) Egy bizonyíték ezt az általánosítást Koebe [5] eredeti bizonyításának, valamint Brandt [6] és Harrington [7] tételének felhasználásával kapjuk meg, amely szerint bármely véges összefüggő tartomány konforman ekvivalens egy olyan lapos tartományral, amelynek komponenshatárai egészen a fordításig, ill. méretezés.

Kapcsolat a konform leképezések elméletével

Egy nagyobb dimenziójú sík vagy tér két nyitott részhalmaza közötti konformális leképezés folytonos , és megőrzi bármely két görbe közötti szögeket . A Riemann leképezési tétel , amelyet Riemann 1851-ben fogalmazott meg , kimondja, hogy a síkban lévő bármely két nyitott topológiai lemezre létezik konform leképezés az egyik lemezről a másikra.

A konformális leképezéseket számítási rácsok , térképi vetületek és más területek felépítésében lehet alkalmazni. Azonban nem mindig könnyű konformális leképezést létrehozni két adott régió között kifejezetten [8] .

Egy 1985-ös konferencián William Thurston azt javasolta, hogy a körtömítést fel lehetne használni a konformális leképezések közelítésére. Pontosabban, Thurston körtömítéseket használt egy tetszőleges nyitott (topológiai) A lemez konform leképezésére a kör belsejébe. Egy topológiai lemezről egy másik B lemezre való leképezést ezután úgy találhatjuk meg, hogy egy A -ból egy körre leképezést, és egy leképezést inverz a B -nek egy körre való leképezésével [9] .

Thurston ötlete az volt, hogy az A tartományon belüli síkon valamilyen kis r sugarú körökből egy hatszögletű burkolóanyagot [10] hozzon létre, egy keskeny csíkot hagyva az A határa közelében , amelyben még egy ilyen sugarú kör. nem helyezhető el. Ezután a körmetszés gráfból megszerkesztjük a G maximális síkgráfot , és hozzáadunk egy további csúcsot a tömörítési határon lévő összes körhöz. A körtömítés tételével ez a sík gráf egy C körtömörítéssel ábrázolható , amelyben az összes él (beleértve a határcsúcsokra eső éleket is) a körök érintőjével van ábrázolva. Az A töltetből származó körök egy az egyben megfelelnek a C köröknek , kivéve a C határkört , amely megfelel A határának . Ez a megfeleltetés használható folyamatos leképezés készítésére A - tól C - ig , amelyben minden kört és minden három kör közötti hézagot egy Möbius - transzformáció segítségével leképeznek egyik tömítésről a másikra . Thurston azt javasolta, hogy mivel az r sugár nullára hajlik, az így megszerkesztett A -ból C -be való leképezés egy konform függvényre hajlamos, amit Riemann [9] tétele ad meg .

Thurston sejtését Rodin és Sullivan igazolta [11] . Pontosabban azt mutatták ki, hogy mivel n a végtelenbe hajlik, a Thurston-módszerrel kapott f n függvény egyenletesen konvergál az A kompakt részhalmazokon az 1/ n sugarú körökkel való pakolástól az A -tól C -ig terjedő konformális leképezésig [9] .

Thurston sejtésének beigazolódása ellenére ennek a módszernek a gyakorlati alkalmazását nehezíti a körtömítések felépítésének bonyolultsága és a viszonylag lassú konvergencia. Ez a módszer azonban sikeresen alkalmazható nem egyszerűen összefüggő tartományok esetén, valamint a Schwartz-Christoffel leképezéseket számító numerikus módszerek kezdeti közelítéseinek megválasztásában  – ez egy némileg eltérő módszer a sokszögű tartományok konformális leképezéseinek megalkotására [9] .

A körcsomagolási tétel alkalmazásai

A körcsomagolási tétel hasznos eszköz a planimetria, a konformális leképezések és a síkgráfok különböző problémáinak tanulmányozására. Az eredetileg Lipton és Tarjan [12] által bizonyított síkgráf-particionálási tétel elegáns bizonyítását a körcsomagolási tétel [13] segítségével kapjuk . A körcsomagolás tételének másik alkalmazása annak az állításnak a bizonyítása, hogy a korlátos fokos síkgráfok torzítatlan határai szinte mindig rekurzívak [14] .

További alkalmazások egy gráf véletlenszerű bejárásának idejére vonatkozó származtatások [15] és a korlátos nemzetség gráfjainak maximális sajátértékének becslése [16] .

A gráfvizualizációban a körcsomagolást egy korlátozott felbontású [17] és korlátozott számú meredekségű síkgráf reprezentációjának megkeresésére használják [18] .

A tétel bizonyítása

A körcsomagolás tételének számos jól ismert bizonyítása létezik. Paul Koebe eredeti bizonyítása a konform paraméterezési tételén alapul, amely szerint egy véges összefüggő tartomány konforman egyenértékű egy körrel. Számos különböző topológiai bizonyítás ismert. Thurston bizonyítása Brouwer fixpont tételén alapul .

A Dirichlet-probléma megoldásának megalkotására a Perron-módszer diszkrét változatát használó bizonyíték is létezik . Yves Colin de Verdière bebizonyította [19] , hogy létezik egy körtömörítés a konvex függvény minimalizálásaként bizonyos konfigurációs tereken.

Következmények

Faree tétele , amely kimondja, hogy bármely gráf, amely görbe élekkel a síkban metszéspontok nélkül ábrázolható , és metszéspontok nélkül is megrajzolható szakaszokkal, a körcsomagolás tételének egyszerű következménye - a csúcsok a körök középpontjába helyezve. és az érintkező köröket összekötő vonalszakaszokat rajzolva szegmensek formájában élekkel rendelkező ábrázolást kapunk.

A tömörítési tétel szigorú változata kimondja, hogy bármely poliéder gráf és duális gráfja ábrázolható két körcsomaggal úgy, hogy a két érintőkör az alapgráf élét, a másik két érintőkör pedig a duális élét reprezentálja. a gráf derékszögben metszi egymást. Ez a fajta tömítés használható konvex poliéder megalkotására , amelyet egy adott gráf reprezentál, és amelynek félig beírt gömbje van , amely a poliéder minden élét érintő gömb . Ezzel szemben, ha egy poliédernek félig beírt gömbje van, akkor a gömbnek a poliéder lapjaival való metszéséből és a gömb horizontjai által alkotott, a poliéder csúcsaiból látható körökből alakulnak ki. kettős csomagolás.

Algoritmikus szempontok

Collins és Stephenson [20] William Thurston ötletei alapján egy numerikus relaxációs algoritmust írt le körpakolások megtalálására . A körtömörítési probléma általuk megoldott változata bemenetként egy síkgráfot vesz fel, amelyben minden belső oldal háromszög, és minden külső csúcs pozitív számokkal van jelölve. Az algoritmus olyan körök csomagját adja, amelyek érintőpontjai az adott gráfot reprezentálják, és amelyeknél a külső csúcsokat reprezentáló körök a bemenetben megadott sugarúak. Amint azt javasolták, a probléma kulcsa a tömítőkörök sugarának kezdeti kiszámításában rejlik. Ha a sugarak ismertek, a körök geometriai helyzetét nem nehéz kiszámítani. Olyan próbasugárral kezdődnek, amely nem egyezik a valódi csomagokkal, majd a következő lépéseket hajtják végre:

  1. Válasszunk egy belső csúcsot a bemeneti gráfnak, ez a csúcs megfelel valamilyen körnek, amit v -vel fogunk jelölni . A szomszédos csúcsok lebenyeknek , azaz a kiválasztott kört érintő köröknek felelnek meg. Legyen k  a szirmok száma.
  2. Számítsuk ki azt a teljes θ szöget, amelyet a v kör körül k db szomszédos kör fed át , ha ezek egymáshoz közel helyezkednek el, és érintik a középső kört.
  3. Számítsuk ki a szirmok átlagos r s sugarát úgy, hogy k r s sugarú kör fedje be a v szomszédok által megadott θ szöget .
  4. Állítson be egy új r n sugarat v -re úgy, hogy k átlagos sugarú kör pontosan 2π-t fedjen át.

Ezen lépések mindegyike elvégezhető egyszerű trigonometrikus számításokkal, és amint arra Collins és Stephenson rámutatott, a sugarak rendszere egyetlen fix ponthoz konvergál, amelynek minden lefedési szöge 2π. Ha a sugarak rendszere összeállt, a köröket egyenként elhelyezhetjük, minden lépésben a két szomszédos kör helyzetének és sugarainak felhasználásával, hogy kiszámítsuk minden sikeres kör középpontját.

Mohar [21] egy hasonló iteratív technikát ír le egy poliéder gráf és duális töltésének megtalálására, amelyben a duális ciklusok derékszögben metszik egymást az alatta lévő körökkel. Bebizonyította, hogy a módszer polinomiális időben működik a körök számában és log 1/ε-ban, ahol ε a középpontoktól való távolságok határa, valamint a számított és az optimális pakolás sugarai közötti különbség.

Történelem

A körcsomagolás tételét először Paul Koebe bizonyította [5] .

William Thurston [1] újra felfedezte a körcsomagolás tételét, és megjegyezte, hogy az E. M. Andreev munkájából következik. Thurston egy sémát is javasolt a körcsomagolási tétel felhasználására, hogy megkapjuk egy összefüggő halmaz homeomorfizmusát a síkban az egységkör belsejéhez. Thurston körtömörítő sejtése az a feltevés, hogy a homeomorfizmus egy Riemann-térképhez  konvergál, mivel a sugarak nullára hajlanak. Thurston sejtését később Burton Rodin és Dennis Sullivan is bebizonyította [11] . Ez számos tanulmányhoz vezetett a körcsomagolási tétel általánosításairól, valamint a konformális leképezésekkel való összefüggésekről és a tétel alkalmazásairól.

Lásd még

Jegyzetek

  1. ↑ 1 2 Thurston, 1978-1981 .
  2. ↑ Brightwell, Scheinerman, 1993 , p. 214-229.
  3. ↑ Coxeter, 2006 , p. 109-114.
  4. ↑ Bowers, Stephenson, 2004 , p. 78-82.
  5. ↑ 1 2 Koebe, 1936 , p. 141-164.
  6. ↑ Brandt, 1980 .
  7. ↑ Harrington, 1982 , p. 39-53.
  8. ↑ Stephenson, 1999 , p. 551-582.
  9. ↑ 1 2 3 4 Stephenson, 1999 .
  10. ↑ Ha a körök középpontjai téglalap alakú rácsot alkotnak, akkor a töltetet négyzetnek nevezzük. Ha a körök középpontjai háromszögrácsot alkotnak, akkor a töltetet hatszögletűnek nevezzük.
  11. ↑ 1 2 Rodin és Sullivan 1987 , p. 349-360.
  12. ↑ Lipton, Tarján, 1979 .
  13. ↑ Miller, Teng, Thurston, Vavasis, 1997 , p. 1-29.
  14. ↑ Benjamini, Schramm, 2001 .
  15. ↑ Jonnason, Schramm, 2000 .
  16. ↑ Kelner, 2006 , p. 882-902.
  17. ↑ Malitz és Papakostas 1994 , p. 172-183.
  18. ↑ Keszegh, Pach, Pálvölgyi, 2011 , p. 293-304.
  19. ↑ Verdière, 1991 , p. 655-669.
  20. ↑ Collins, Stephenson, 2003 , p. 233-256.
  21. ↑ Mohar, 1993 , p. 257-263.

Irodalom

Linkek

 Csomagolási feladatok
Csomagolási körök
Léggömb csomagolás
Egyéb csomagok
Kirakós játék