Вграждане на несвързана графика
Вграждане на несвързана графае вграждане на неориентирана графа в евклидовото пространство, така че нито два цикъла на графиката да нямат различен от нула коефициент на свързване.Плоското вгражданее вграждане, при което всеки цикъл е границата на топологична окръжност, чиято вътрешност не е свързана с графиката.Вграждаща се графика без връзкие графика, която има несвързано или плоско вграждане. Тези графики образуват триизмерен аналог на равнинните графи [1] . За разлика от това,по същество свързана графикае графика, която няма несвързано вграждане.
Плоските вграждания автоматично нямат връзки, но не и обратното [2] . Пълна графика K 6>gt; , графиката на Петерсен и пет други графики от фамилията графики на Петерсен нямат несвързани вграждания [1] . Несвързаните графи за вграждане се затварят от второстепенни графове [3] и Y-Δ трансформации [2] . Тези графи имат семейни графи на Петерсен като забранени второстепенни [4] и включват равнинни графи и върхови графи [2] . Графиките могат да бъдат разпознати (и може да бъде построено плоско вграждане) в линейно време [5] .
Съдържание
Две непресичащи се криви в евклидовото пространство се наричат несвързани, ако има непрекъснато движение на кривите, което ги трансформира в две непресичащи се копланарни окръжности, без една крива да минава през другата или през себе си. Ако няма такова непрекъснато движение, се казва, че кривите са свързани. Връзката на Hopf, образувана от две окръжности, които минават през диск, обхванат от тези окръжности, предоставя най-простия пример за двойка свързани криви, но кривите могат да бъдат свързани по много по-сложни начини. Ако кривите не са свързани, може да се намери (топологичен) диск в пространството, ограничено от първата криваи не се пресича с втората. Обратно, ако такъв диск съществува, кривите не са свързани.
Коефициентът на свързване на две затворени криви в тримерното пространство е топологичен инвариант на кривата - това е число, определено за кривите по един от еквивалентните начини, което не се променя, ако кривите се преместват в пространството непрекъснато, без да пресичат една друга или самите себе си. Коефициентът на зацепване се намира чрез проектиране на вграждане върху равнина и преброяване по определен начин на броя на преминаванията на първата крива през втората (със знак +1 или −1 в зависимост от посоката на преминаване). Проекцията трябва да бъде "правилна", което означава, че няма два върха, проектирани в една и съща точка, нито един връх не се проектира вътре в ребро и във всяка точка от проекцията, където ръбовете се пресичат, те се пресичат напречно. При такива ограничения всяка проекция води до същия коефициент на свързване. Коефициентът на свързване на несвързаните криви е нула и следователно, ако двойка криви има ненулев коефициент на свързване, двете криви трябва да бъдат свързани. Има обаче примери за свързани криви, които имат коефициент на връзка нула, като връзката на Уайтхед.
Вграждането на графика в триизмерното пространство се състои от картографиране на върховете на графиката към точки в пространството и картографиране на ръбове към криви, така че всяка крайна точка на ребро се картографира към крайна точка на съответната крива и кривите, съответстващи на два различни ръба, не се пресичат (освен в общи крайни точки). Всяка крайна графика има краен (вероятно експоненциален) брой различни прости цикли и ако графиката е вградена в триизмерно пространство, всеки такъв цикъл образува проста затворена крива. Може да се изчисли коефициентът на свързване на всяка непресичаща се двойка криви, образувана отПо този начин. Ако всички двойки цикли имат нулев коефициент на свързване, се казва, че вграждането е несвързано [6] [1] [2] .
В някои случаи графът може да бъде вграден в пространството по такъв начин, че за всеки цикъл в графиката може да се намери диск, ограничен от този цикъл, който не пресича други елементи на графиката. В този случай цикълът не трябва да бъде свързан с други цикли на графиката, които не го пресичат. Едно вграждане се нарича плоско, ако някакъв цикъл ограничава диска по описания начин [7] . Едно плоско вграждане е задължително несвързано, но може да има несвързани вграждания, които не са плоски. Например, акоGе графика, образувана от два отделни цикъла и вграждането води до връзка на Уайтхед, вграждането не е свързано, но не е планарно.
Казва се, че една графика е по същество свързана, ако всяко вграждане води до винаги свързано вграждане. Въпреки че несвързаните и плоските вграждания не са едно и също, графиките с несвързани вграждания се оказват същите графики като графиките с плоски вграждания [8] .
Както показа Сакс [1], всичките седем графа на семейство Петерсен са по същество свързани и няма значение как тези графики са вградени в пространството, за всяко вграждане те имат два свързани цикъла. Тези графики включват пълната графика K6>gt; , графиката на Петерсен, графиката, образувана чрез премахване на ребро от пълна двустранна графа K 4 , 4>gt; и пълна тристранна графа K3, 3, 1>gt; .
Всяка равнинна графика има плоско и несвързано вграждане - просто вградете графиката в равнина, разположена в (триизмерно) пространство. Ако графиката е плоска, това е единственият начин да вградите графиката плоска и несвързана – всяко плоско вграждане може непрекъснато да се деформира във вграждане в равнината. Обратно, всякаквинеравнинна несвързана графа има множество несвързани вграждания [2] .
Граф на върхове, образуван чрез добавяне на един връх към планарен граф, също има плоско и неверижно вграждане - ние вграждаме равнинната част на графиката в равнината, поставяме горната част на графиката (върхът, който нарушава планарността) над равнината и след това изчертаваме ръбове от върха към съседните му върхове като сегменти. Всяка затворена крива на равнината ограничава диск, който не минава през друг елемент на графиката, а всяка затворена крива през върха ограничава диск над равнината, който не минава през никой друг елемент на графиката [2] .
Ако графиката има несвързано или плоско вграждане, тогава модифицирането на графиката чрез разделяне или сливане на нейните ръбове, добавяне или премахване на множество ръбове между двойка върхове или извършване на Y-Δ трансформации, в които връх от трета степен се заменя с триъгълник, свързващ три съседни, или обратното, води до запазване на съществуването на плоско или несвързано вграждане [2] . По-специално, в кубичен планарен график (в който всички върхове имат точно три съседа, като куб), човек може да направи копия на всеки независим набор от върхове, като направи Y-Δ трансформация, добави множество копия на ръбовете в получените триъгълници и след това направи обратна Δ-Y трансформация.
Наборът от забранени второстепенни за графи, допускащи несвързани вграждания, беше открит от Sacks [1] - седем графа от семейство Петерсен са второстепенни минимални по същество свързани графи. Въпреки това, Сакс не успя да докаже, че само тези графики са малки-минимални свързани графи и това беше направено от Робъртсън, Сиймор и Томас [4] .
Характеризирането чрез забранени непълнолетни на графики, допускащи несвързани вграждания, води доалгоритъм с полиномиално време на изпълнение за тяхното разпознаване, но този алгоритъм не изгражда истинско вграждане. Каравабаиши, Кройцер и Мохар [5] описаха алгоритъм за линейно време, който проверява дали графиката може да бъде вградена без връзка и, ако може да се вгради, конструира плоско вграждане на графиката. Техният алгоритъм намира големи равнинни подграфи в рамките на даден график, така че ако има несвързано вграждане, те представляват равнинно вграждане на подграфа. Чрез повторно опростяване на графиката, когато се намери такъв подграф, те намаляват проблема до такъв, при който оставащата графика е ограничена от ширината на дървото, в който момент проблемът може да бъде решен с помощта на динамично програмиране.
Проблемът за ефективната проверка дали дадено вграждане е плоско или несвързано беше поставен от Робъртсън, Сиймор и Томас [2] . Проблемът остава нерешен и е еквивалентен по сложност на проблема с разплитането на възел [en] , проблемът за проверка дали една крива в пространството е без възли [5] . Известно е, че проверката за разплитане (а следователно и за разплитане) принадлежи към класа NP, но не е известно дали принадлежи към класа на NP-пълните задачи [9] .
Инвариантът на Colin de Verdière е число, дефинирано за всяка графика, базирана на алгебричната теория на графите. График с инвариант на Колин дьо Вердиер, който не превишава μ за всяка фиксирана константа μ, образува второстепенно затворено семейство и първите няколко такива семейства са добре познати – графики с μ ≤ 1 са линейни гори (несвързано обединение на пътеки), графики с μ ≤ 2 са извънравнинни графики, а графики с μ ≤ 3 са равнинни графи. Както беше предложено от Robertson, Seymour и Thomas [2] и доказано от Lovasz и Schreiver [10], графиките с μ ≤ 4 са точно графики с несвързани вграждания.
Планарните графи и върховите графи позволяват несвързано вграждане, както и графите, получени чрез Y-Δ трансформации от тях [2] .YΔY сводимите графиса графики, които могат да бъдат редуцирани до един връх чрез трансформация Y-Δ, премахване на изолирани върхове и висящи върхове (върхове от степен 1) и замяна на дъги във връх със степен две с единична дъга. Тези графики също са затворени в минори. Съществуват обаче несвързани YΔY-нередуцируеми графики, като графиката на върхове, образувана чрез свързване на връх (връх, нарушаващ равнинността) към всички върхове от трета степен на ромбичен додекаедър [11] . Има и несвързани графи, които не могат да бъдат трансформирани чрез Y-Δ трансформации, премахване на изолирани и висящи върхове и замяна на дъги във връх със степен две с една дъга в граф на върхове. Например, корона с десет върха има несвързано вграждане, но не може да бъде преобразувана в граф на върха по начина, описан по-горе [2] .
Свързано с понятието за несвързано вграждане е понятието за несвързано вграждане. Това е такова вграждане на граф, че никой прост цикъл не образува нетривиален възел. Графиките, които нямат незавързано вграждане, включватK7 иK3,3,1,1 [6] [12] . Въпреки това, има минимални забранени второстепенни за невъзлести вграждания, които не се формират (за разлика от горните две графики) чрез добавяне на един връх към по същество свързан граф [13] .
Човек може да дефинира семейства от графи чрез наличието или отсъствието на по-сложни възли и връзки в тяхното вграждане [3] [14] или чрез несвързано вграждане в триизмерно многообразие [en], различно от евклидовото пространство [15] . Flapan, Naimi и Pommersheim [16] дефинират вграждане на графика като тройно свързан, ако има три цикъла, нито един от които не еможе да се отдели от другите две. Те показаха, чеK9 не са трикратно свързани по същество, докатоK10 е свързан [17] . По-общо, може да се дефинира вграждане наn-връзка за всяко n като вграждане, съдържащо n-компонентна връзка, която не може да бъде разделена от топологична сфера на две отделни части. Малките минимални по същество n-свързани графи са известни за всички n [18] .
Въпросът е дали K 6 > заплетено или плоско вграждане, поставено в топологичната изследователска общност в началото на 1970-те години от Боте [19] . Несвързаното вграждане привлече вниманието на теоретиците на графите Sacks [1], които предложиха няколко свързани проблема, включително проблема за намиране на характеристика чрез забранени графи на графи с несвързани или плоски вграждания. Сакс показа, че седем графики от семейство Петерсен (включително K 6> ) нямат такива вграждания. Както отбелязват Nexetril и Thomas [3], несвързаните вградени графи са затворени в минорите на графиката, което предполага, според теоремата на Robertson-Seymour, че съществува характеризиране чрез забранени графи. Доказателството за съществуването на краен брой обструктивни графи не води до изрично описание на този набор от забранени непълнолетни, но от резултатите на Сакс следва, че седем графика на семейство Петерсен принадлежат към набора. Тези проблеми най-накрая бяха решени от Робъртсън, Сиймор и Томас [4] [8], които показаха, че тези седем графики на семейство Петерсен са единствените минимални забранени второстепенни за такива графики. По този начин несвързаните вградени графи и плоските вградени графи са един и същ набор от графики и двете семейства могат да бъдат дефинирани като графики, които не съдържат елементи от семейството Петерсен като второстепенни.
Изследването на вграждания без връзки започна сизследване на алгоритмите в края на 80-те години [22] [23] . Алгоритмично, проблемът с разпознаването на безлинкови вграждащи се и плоски вграждащи се графи беше решен, когато беше доказано характеризиране чрез забранени непълнолетни - алгоритъмът на Робъртсън и Сиймор [24] може да се използва за проверка в полиномиално време дали дадена графа съдържа някой от седемте забранени непълнолетни [25] . Този метод не изгражда несвързано или плоско вграждане, ако съществува, а алгоритъм, който изгражда вграждане [26] , а по-късно е намерен по-ефективен алгоритъм, който работи в линейно време [5] .
Последният въпрос на Сакс [1] относно възможността за аналогия на теоремата на Фари за несвързани графи все още не е получил отговор. Въпросът се поставя по следния начин: кога съществуването на несвързано или плоско вграждане с извити или частично линейни ръбове предполага съществуването на несвързано или плоско вграждане, в което ръбовете са сегменти?