Linkittämätön kaavion upottaminen

Linkittämätön graafin upotus  on suuntaamattoman graafin upottaminen euklidiseen avaruuteen siten, että kahdella graafin jaksolla ei ole nollasta poikkeavaa linkityskerrointa . Tasainen upotus  on upotus, jossa mikä tahansa sykli on topologisen ympyrän raja, jonka sisäpuoli ei ole linkitetty kuvaajaan. Upotettava kaavio ilman linkkejä  on kaavio, jossa on linkittämätön tai tasainen upotus. Nämä kuvaajat muodostavat tasograafien kolmiulotteisen analogin [1] . Sitä vastoin olennaisesti linkitetty kaavio  on sellainen, jossa ei ole linkittämätöntä upotusta.

Litteissä upotuksissa ei ole automaattisesti linkkejä, mutta ei päinvastoin [2] . Täydellisellä graafilla , Petersenin graafilla ja muilla viidellä Petersenin graafiperheen graafilla ei ole linkittämättömiä upotuksia [1] . Linkittämättömät upotetut graafit suljetaan graafin alaväreillä [3] ja Y-Δ muunnoksilla [2] . Näissä kaavioissa on Petersenin perheen graafit kiellettyinä alaikäisinä [4] ja ne sisältävät tasograafit ja kärkigraafit [2] . Kuvaajat voidaan tunnistaa (ja tasainen upotus voidaan rakentaa) lineaarisessa ajassa [5] .

Määritelmät

Kahden ei-leikkaavan käyrän euklidisessa avaruudessa sanotaan olevan linkittämättömiä, jos käyrien jatkuva liike muuttaa ne kahdeksi ei-leikkaavaksi samantasoiseksi ympyräksi ilman, että toinen käyrä kulkee toisen tai itsensä läpi. Jos tällaista jatkuvaa liikettä ei ole, käyrien sanotaan olevan linkitetty . Hopf-linkki, joka muodostuu kahdesta ympyrästä, jotka kulkevat näiden ympyröiden ylittämän levyn läpi, on yksinkertaisin esimerkki linkitetystä käyräparista, mutta käyriä voidaan yhdistää paljon monimutkaisemmilla tavoilla. Jos käyriä ei ole linkitetty, voidaan löytää (topologinen) levy avaruudesta, jota rajoittaa ensimmäinen käyrä ja joka ei leikkaa toista. Käänteisesti, jos tällainen levy on olemassa, käyriä ei ole linkitetty.

Kahden suljetun käyrän linkityskerroin kolmiulotteisessa avaruudessa on käyrän topologinen invariantti - tämä on käyrille jollain vastaavalla tavalla määritelty luku, joka ei muutu, jos käyriä liikutetaan avaruudessa jatkuvasti risteämättä toisiaan. tai itseään. Kiinnityskerroin löydetään projisoimalla upotus tasolle ja laskemalla tietyllä tavalla ensimmäisen käyrän kulkujen määrä toisen yli (+1 tai −1 merkillä kulumissuunnasta riippuen). Projektion on oltava "oikea", mikä tarkoittaa, että kahta kärkeä ei projisoida samaan pisteeseen, mitään kärkeä ei projisoida reunan sisään ja missä tahansa projektion kohdassa, jossa reunat leikkaavat, ne leikkaavat poikittain . Tällaisissa rajoituksissa mikä tahansa projektio johtaa samaan linkityskertoimeen. Linkittämättömien käyrien linkityskerroin on nolla, ja siksi, jos käyräparilla on nollasta poikkeava linkityskerroin, nämä kaksi käyrää on linkitettävä. On kuitenkin esimerkkejä linkitetyistä käyristä, joiden linkitystekijä on nolla, kuten Whitehead-linkki .

Kuvaajan upottaminen kolmiulotteiseen avaruuteen koostuu graafin pisteiden yhdistämisestä avaruuden pisteisiin ja reunojen kartoittamisesta käyriin siten, että reunan jokainen päätepiste kartoitetaan vastaavan käyrän päätepisteeseen ja käyrät vastaavat kahta eri reunat eivät leikkaa (paitsi yhteisissä päätepisteissä). Missä tahansa äärellisessä graafissa on äärellinen (mahdollisesti eksponentiaalinen) määrä erilaisia ​​yksinkertaisia ​​syklejä , ja jos graafi on upotettu kolmiulotteiseen avaruuteen, jokainen tällainen sykli muodostaa yksinkertaisen suljetun käyrän. Jokaisen tällä tavalla muodostetun ei-leikkaavan käyräparin linkityskerroin on mahdollista laskea. Jos kaikilla jaksoparilla on nolla linkityskerroin, upotuksen sanotaan olevan linkittämätön [6] [1] [2] .

Joissakin tapauksissa graafi voidaan upottaa avaruuteen siten, että jokaiselle kaavion jaksolle löytyy tämän syklin rajoittama levy, joka ei leikkaa muita graafin elementtejä. Tässä tapauksessa sykliä ei saa linkittää muihin kaavion sykleihin, jotka eivät leikkaa sitä. Upotuksen sanotaan olevan litteä, jos mikä tahansa sykli rajoittaa levyä kuvatulla tavalla [2] . Samoin "hyvän sijoituksen" määritelmä on annettu julkaisussa Motwani, Raghunathan, Saran, 1988 . Katso myös Saran (1989 ) ja Böhme (1990 ). Tasainen upotus on välttämättä linkittämätön, mutta voi olla linkittämättömiä upotuksia, jotka eivät ole tasaisia. Jos G on esimerkiksi kahdesta erillisestä jaksosta muodostettu graafi ja upottaminen johtaa Whitehead-linkkiin, upottaminen on linkittämätön, mutta ei tasomainen.

Kaavion sanotaan olevan olennaisesti linkitetty, jos mikä tahansa upottaminen johtaa aina linkitettyyn upotukseen. Vaikka linkittämättömät ja litteät upotukset eivät ole samoja, linkittämättömiä upotuksia sisältävät kaaviot ovat samoja kaavioita kuin litteät upotukset [7] .

Esimerkkejä ja vastaesimerkkejä

Kuten Sacks [1] osoitti , kaikki Petersen-perheen seitsemän kuvaajaa ovat oleellisesti linkitettyinä, eikä sillä ole väliä, kuinka nämä graafit on upotettu avaruuteen, jokaisessa upotuksessa niillä on kaksi linkitettyä sykliä. Nämä kaaviot sisältävät koko graafin , Petersenin graafin, graafin, joka on muodostettu poistamalla reuna täydellisestä kaksiosaisesta graafista , ja täydellisen kolmiosaisen graafin .

Jokaisessa tasograafissa on litteä ja linkittämätön upotus - upota kuvaaja tasoon, joka sijaitsee (kolmiulotteisessa) avaruudessa. Jos kuvaaja on tasomainen, tämä on ainoa tapa upottaa kaavio litteäksi ja linkittämättömäksi – mikä tahansa litteä upottaminen voidaan jatkuvasti muuttaa muotoaan upotukseksi tasossa. Sitä vastoin missä tahansa ei-tasoisessa linkittämättömässä graafissa on useita linkittämättömiä upotuksia [2] .

Vertex graph , joka muodostetaan lisäämällä yksi kärki tasograafiin, sisältää myös litteän ja ketjuttamattoman upotuksen - upotamme graafin tasomaisen osan tasoon, sijoitamme graafin kärkipisteen (tasoisuutta rikkova kärki) tason yläpuolelle ja piirrä sitten reunat kärjestä vierekkäisiin huippuihin segmenttien muodossa. Mikä tahansa tasossa oleva suljettu käyrä rajoittaa kiekkoa, joka ei kulje graafin toisen elementin läpi, ja mikä tahansa suljettu käyrä huipun läpi rajoittaa levyä sen tason yläpuolella, joka ei kulje minkään muun graafin elementin läpi [2] .

Jos graafissa on linkittämätön tai litteä upotus, muokkaa graafia jakamalla tai yhdistämällä sen reunat, lisäämällä tai poistamalla useita reunoja pisteparin väliin tai suorittamalla Y-Δ muunnoksia , joissa kolmannen asteen kärki korvataan kolme naapuria yhdistävä kolmio tai päinvastoin johtaa tasaisen tai linkittämättömän upotuksen olemassaolon säilymiseen [2] . Erityisesti kuutiossa tasograafissa (jossa kaikilla pisteillä on täsmälleen kolme naapuria, kuten kuutiolla) voidaan tehdä kopioita mistä tahansa riippumattomasta pistejoukosta suorittamalla Y-Δ-muunnos, lisäämällä useita kopioita tuloksena olevan pisteen reunoista. kolmiot ja tee sitten käänteiset Δ -Y-muunnokset.

Karakterisointi ja tunnistaminen

Jos graafissa on linkittämätön tai litteä upotus, niin kaikilla graafin sivuilla (reunojen kutistumisesta ja reunojen ja kärkien poistamisesta muodostuvassa graafissa) on myös linkittämätön tai litteä upotus. Poistaminen ei voi katkaista linkittämättömän tai tasaisen sisäkkäisyyden mahdollisuutta, ja supistuminen voidaan tehdä jättämällä yksi reunan päätepiste supistumaan paikoilleen ja vaihtamalla kaikki vastakkaiseen kärkeen tulevat reunat. Siten Robertson-Seymour-lauseen mukaan graafit, joissa on linkittämätön upotus, luonnehditaan kiellettyjen graafien avulla graafiksi, jotka eivät sisällä mitään äärellisestä joukosta ala-arvoja [3] .

 Kiellettyjen alaikäisten joukon kaavioita, jotka sallivat linkittämättömiä upotuksia, löysi Sacks [1] – seitsemän Petersen-perheen kaaviota ovat pieniä minimaalisia olennaisesti linkitettyjä kaavioita. Sachs ei kuitenkaan pystynyt todistamaan, että vain nämä graafit ovat minimaalisia linkitettyjä kaavioita, ja tämän tekivät Robertson, Seymour ja Thomas [4] .

Linkittämättömän upotuksen sallivien graafien karakterisointi kiellettyjen alaikäisten avulla johtaa algoritmiin, jonka tunnistusaika on polynomi , mutta tämä algoritmi ei rakenna todellista upotusta. Karavabaishi, Kreutzer ja Mohar [5] kuvasivat lineaariaikaisen algoritmin, joka tarkistaa, onko graafi upotettava ilman linkkiä, ja jos se on upotettava, muodostaa graafin tasaisen upotuksen. Heidän algoritminsa löytää suuret tasomaiset osagraafit annetusta graafista siten, että jos on linkittämätön upottaminen, ne edustavat aligraafin tasomaista upotusta. Yksinkertaistamalla kuvaajaa uudelleen, kun tällainen osagraafi löytyy, ne vähentävät ongelman sellaiseksi, jossa jäljellä olevaa kuvaajaa rajoittaa puun leveys , jolloin ongelma voidaan ratkaista dynaamisen ohjelmoinnin avulla .

Robertson, Seymour ja Thomas esittivät ongelman tehokkaasti tarkistaa, onko tietty upotus litteä vai linkittämätön [2] . Ongelma jää ratkaisematta ja vastaa monimutkaisuudeltaan solmun purkamisongelmaa , ongelmaa, joka koskee sen tarkistamista, onko avaruudessa oleva käyrä leimaamaton [5] . Tiedetään, että merkintöjen poistamisen (ja siten myös linkittämättömän sisäkkäisyyden) tarkistus kuuluu NP -luokkaan , mutta ei tiedetä kuuluuko se NP-täydellisten ongelmien luokkaan [8] .

Liittyvät kaavioperheet

Colin de Verdièren invariantti  on luku, joka on määritelty mille tahansa graafille algebrallisen graafiteorian perusteella . Graafi, jonka Colin de Verdièren invariantti ei ylitä μ:tä millekään kiinteälle vakiolle μ, muodostaa pienemmän suljetun perheen, ja muutamat ensimmäiset tällaiset perheet ovat hyvin tunnettuja – graafit, joissa μ ≤ 1 ovat lineaarisia metsiä (polkujen hajaliitto), graafit joissa μ ≤ 2 ovat ulompia kaavioita , ja graafit , joissa μ ≤ 3 ovat tasokaavioita . Kuten Robertson, Seymour ja Thomas [2] ehdottivat ja Lowash ja Schreiver [9] ovat osoittaneet , graafit, joiden μ ≤ 4, ovat täsmälleen kaavioita, joissa on linkittämättömiä upotuksia.

Tasograafit ja kärkigraafit mahdollistavat linkittämättömän upotuksen, samoin kuin niistä Y-Δ-muunnoksilla saadut graafit [2] . YΔY pelkistettävät graafit  ovat kaavioita, jotka voidaan pelkistää yhdeksi pisteeksi Y-Δ-muunnolla, poistamalla eristetyt kärjet ja riippuvat kärjet (asteen 1 kärjet) ja korvaamalla kaaret kakkospisteen kärjessä yhdellä kaarella. Nämä kaaviot ovat myös suljettuja alaikäisillä. On kuitenkin olemassa linkittämättömiä YΔY-pelkistymättömiä graafia, kuten kärkigraafi, joka on muodostettu yhdistämällä kärki (tasoisuutta rikkova kärki) rombisen dodekaedrin kaikkiin kolmannen asteen kärkiin [10] . On myös linkittämättömiä graafeja, joita ei voida muuntaa Y-Δ-muunnoksilla, poistamalla eristettyjä ja riippuvia kärkipisteitä ja korvaamalla kaareja asteella kaksi yhdellä kaarella kärkigraafiksi. Esimerkiksi kruunussa , jossa on kymmenen kärkeä, on linkittämätön upotus, mutta sitä ei voi muuntaa kärkigraafiksi yllä kuvatulla tavalla [2] .

Linkittämättömän upotuksen käsitteeseen liittyy myös linkittämättömän upotuksen käsite. Se on sellainen graafin upottaminen, ettei mikään yksinkertainen sykli muodosta ei-triviaalista solmua . Kaaviot, joissa ei ole huomautuksetonta upotusta, sisältävät K 7 ja K 3,3,1,1 [6] [11] . Huomauttamattomille upotuksille, joita ei muodosteta (toisin kuin yllä olevat kaksi graafia) ei kuitenkaan muodosteta lisäämällä yksi kärki olennaisesti linkitettyyn graafiin [12] , on kuitenkin olemassa minimaalisesti kiellettyjä molempia .

Graafiperheitä voidaan määritellä monimutkaisempien solmujen ja linkkien läsnäolon tai puuttumisen perusteella niiden upotuksessa [3] [13] tai yhdistämättömällä upotuksella kolmiulotteiseen monimuotoiseen muuhun kuin euklidiseen avaruuteen [14] . Flapan, Naimi ja Pommersheim [15] määrittelivät graafin upotuksen kolminkertaiseksi linkitetyksi, jos sykliä on kolme, joista yhtäkään ei voida erottaa kahdesta muusta. He osoittivat, että K 9 ei ole olennaisesti kolminkertainen, kun taas K 10 on linkitetty [16] . Yleisemmin voidaan määritellä n - linkitetty upotus mille tahansa upotukseksi, joka sisältää -komponenttilinkin, jota ei voida jakaa topologisella pallolla kahteen erilliseen osaan. Pieni-minimaaliset olennaiset linkitetyt graafit tunnetaan kaikille [17] .

Historia

Kysymys siitä, onko upotuksella linkki vai taso, nosti esiin topologisessa tutkimusyhteisössä 1970-luvun alussa Bothe [18] . Linkittämätön upottaminen herätti graafiteoreetikot Sacksin [1] huomion , joka ehdotti useita asiaan liittyviä ongelmia, mukaan lukien ongelman löytää karakterisointi kiellettyjen graafien avulla linkittämättömillä tai litteillä upotuksilla. Sachs osoitti, että seitsemässä Petersen-perheen kaaviossa (mukaan lukien ) ei ole tällaisia ​​upotuksia. Kuten Nexetril ja Thomas [3] huomauttivat , linkittämättömät upotettavat graafit suljetaan graafin molleihin , mikä Robertson-Seymour-lauseen mukaan tarkoittaa , että on olemassa karakterisointi kiellettyjen graafien avulla. Todistaminen rajallisen määrän estäviä kaavioita olemassaolosta ei johda tämän kiellettyjen alaikäisten joukon selkeään kuvaukseen, mutta Sacksin tuloksista seuraa, että ryhmään kuuluu seitsemän Petersen-perheen graafia. Nämä ongelmat ratkaisivat lopulta Robertson, Seymour ja Thomas [4] [7] , jotka osoittivat, että nämä seitsemän Petersen-perheen kuvaajaa ovat ainoat vähimmäiskielletyt alaikäiset sellaisille kaavioille. Siten linkittämättömät upotettavat graafit ja taso upotettavat graafit ovat sama kaaviojoukko, ja molemmat perheet voidaan määritellä graafiksi, jotka eivät sisällä Petersen-perheen elementtejä alaikäisinä.

Sacks [1] kysyi myös reunojen lukumäärän rajoista ja ilman linkkiä upotettavien graafien kromaattisesta lukumäärästä . Reunojen määrä upotettavassa kärkigraafissa ilman linkkiä ei ylitä  — maksimipistegrafeissa c on täsmälleen tämä määrä reunoja [1] , ja Mader [19] osoitti ylärajan yleisemmälle K 6 -vapaalle graafille . alaikäiset. Vuonna 1985 osoitettiin, että Sachsin kysymys kromaattisesta luvusta ratkeaisi, jos Hadwigerin olettamus todistettaisiin, että millä tahansa -kromaattisella graafilla on täydellinen graafi, jonka kärjet ovat sivuarvoja [3] . Robertsonin, Seymourin ja Thomasin [20] todiste Hadwigerin arvelun tapauksesta riittää ratkaisemaan Sachsin kysymyksen – linkittomat graafit voidaan värjätä enintään viidellä värillä, koska mikä tahansa 6-kromaattinen graafi sisältää mollivärin eikä ole linkittämätön . , ja on linkittämättömiä kaavioita, kuten , jotka vaativat viisi väriä. Snark- lauseesta seuraa, että mikä tahansa kuutiomainen upotettava graafi ilman linkkiä on 3-reunaväritettävä .

Linkittömien upotusten tutkimus alkoi algoritmien tutkimuksessa 1980-luvun lopulla [21] [22] . Algoritmisesti linkittömien upotettavien ja litteiden upotettavien graafien tunnistamisen ongelma ratkesi, kun kiellettyjen alaikäisten karakterisointi todistettiin - Robertsonin ja Seymourin [23] algoritmilla voidaan tarkistaa polynomiajassa , sisältääkö annettu graafi jotakin seitsemästä kielletystä alaikäisestä. [24] . Tämä menetelmä ei rakenna linkittämätöntä tai litteää upotusta, jos sellainen on olemassa, vaan algoritmia, joka rakentaa upotuksen [25] ja löysi myöhemmin tehokkaamman algoritmin, joka toimii lineaarisessa ajassa [5] .

Sachsin [1] viimeiseen kysymykseen Fari-lauseen analogian mahdollisuudesta linkittämättömille graafeille ei ole vielä vastattu. Kysymys esitetään seuraavasti: milloin linkittämättömän tai litteän upotuksen olemassaolo kaarevilla tai paloittain lineaarisilla reunoilla tarkoittaa linkittämättömän tai litteän upotuksen olemassaoloa, jossa reunat ovat segmenttejä ?

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 7 8 9 Sachs, 1983 .
  2. ↑ 1 2 3 4 5 6 7 8 9 10 11 12 Robertson, Seymour, Thomas, 1993a .
  3. ↑ 1 2 3 4 5 Nešetřil, Thomas, 1985 .
  4. ↑ 1 2 3 Robertson, Seymour, Thomas, 1995 .
  5. ↑ 1 2 3 4 Kawarabayashi, Kreutzer, Mohar, 2010 .
  6. ↑ 1 2 Conway, Gordon, 1983 .
  7. ↑ 12 Robertson, Seymour, Thomas, 1993b .
  8. ↑ Hass, Lagarias, Pippenger, 1999 .
  9. ↑ Lovász, Schrijver, 1998 .
  10. ↑ Truemper, 1992 .
  11. ↑ Foisy, 2002 .
  12. ↑ Foisy, 2003 .
  13. ↑ Fleming, Diesl, 2005 .
  14. ↑ Flapan, Howards, Lawrence, Mellor, 2006 .
  15. ↑ Flapan, Naimi, Pommersheim, 2001 .
  16. ↑ Muita esimerkkejä ei-kolmesti linkitetyistä kaavioista, katso Bowlin ja Foisy 2004 .
  17. ↑ Flapan, Pommersheim, Foisy, Naimi, 2001 .
  18. ↑ Bothe, 1973 .
  19. ↑ Mader, 1968 .
  20. ↑ Robertson, Seymour, Thomas, 1993c .
  21. ↑ Fellows, Langston, 1988 .
  22. ↑ Motwani, Raghunathan, Saran, 1988 .
  23. ↑ Robertson, Seymour, 1995 .
  24. ↑ Robertson-Seymour-algoritmin soveltuvuuden tähän ongelmaan huomasivat Fellows ja Langston ( Fellows, Langston, 1988 ).
  25. ↑ van der Holst, 2009 .

Kirjallisuus