Кіріспе
Топологиялық графтар теориясында, математикалық ғылымда, бағытталмаған графтың байланыссыз ендірілуі – графтың үш өлшемді евклид кеңістігіне оның екі циклы бір-бірімен байланыспайтындай етіп ендірілуі. Жазық ендіру – әрбір цикл графтан бөлінген ішкі топологиялық дискінің шекарасы болатын ендіру. Байланыссыз ендірілетін граф – байланыссыз немесе жазық ендірілуі бар граф; мұндай графтар жазық графтардың үш өлшемді аналогын құрайды. Керісінше, ішкі байланысты граф – байланыссыз ендірілуі жоқ граф. Жазық ендірулер автоматты түрде байланыссыз болады, бірақ керісінше дұрыс емес. Олар жазық графтар мен төбелік графтарды қамтиды. Проекция «туралы» болуы керек, яғни екі төбе бір нүктеге проекцияланбауы керек, төбе шеттің ішкі бөлігіне проекцияланбауы керек, және проекциядағы екі шеттің проекциялары қиылысатын әрбір нүктеде олар көлденең қиылысуы керек; осы шектеумен кез келген екі проекция бірдей байланыс нөміріне әкеледі. Байланыс ажыратудың байланыс нөмірі нөлге тең, сондықтан егер екі қисықтың байланыс нөмірі нөлден өзгеше болса, екі қисық байланысқан болуы керек. Дегенмен, байланысқан, бірақ байланыс нөмірі нөлге тең болатын қисықтардың мысалдары бар, мысалы, Уайтхед байланысы. Графты үш өлшемді кеңістікке ендіру – графтың төбелерін кеңістіктегі нүктелерге, ал графтың шеттерін кеңістіктегі қисықтарға бейнелеуден тұрады, сондықтан әр шеттің әрбір ұшы сәйкес қисықтың ұшына бейнеленеді және екі шеттің қисықтары шеттердің ортақ ұшынан басқа жерде қиылыспайды. Кез келген шекті графтың шекті (бірақ, мүмкін, экспоненциалды) саны ерекше қарапайым циклдері болады, және егер граф үш өлшемді кеңістікке ендірілсе, онда осы циклдердің әрқайсысы қарапайым жабық қисық құрайды. Осылайша қалыптасқан әрбір бірікпес қисық жұбының байланыс нөмірін есептеуге болады; егер циклдердің барлық жұптарының байланыс нөмірі нөл болса, ендіру байланыссыз деп аталады. Кейбір жағдайларда граф кеңістікте осылай орналасуы мүмкін, әрбір цикл үшін графиктегі басқа элементтермен қиылыспайтын, осы циклмен шектелген дискіні табуға болады. Бұл жағдайда цикл графиктегі басқа циклдардан ажыратылған болуы керек. Егер әрбір цикл дискіні осылай шектесе, онда ендіру жазық деп аталады. Жазық ендіру міндетті түрде байланыссыз, бірақ жазық емес байланыссыз ендірулер болуы мүмкін: мысалы, егер G екі ажыратылған циклдан құралған граф болса және ол Уайтхед байланысын құру үшін ендірілсе, онда ендіру байланыссыз, бірақ жазық емес. Граф, оның қалай ендірілгеніне қарамастан, ендіру әрқашан байланысқан болса, ішкі байланысты деп аталады. Байланыссыз және жазық ендірулер бірдей болмаса да, байланыссыз ендірулері бар графтар жазық ендірулері бар графтармен бірдей.
In topological graph theory, a mathematical discipline, a linkless embedding of an undirected graph is an embedding of the graph into three dimensional Euclidean space in such a way that no two cycles of the graph are linked. A flat embedding is an embedding with the property that every cycle is the boundary of a topological disk whose interior is disjoint from the graph. A linklessly embeddable graph is a graph that has a linkless or flat embedding; these graphs form a three dimensional analogue of the planar graphs. Complementarily, an intrinsically linked graph is a graph that does not have a linkless embedding. Flat embeddings are automatically linkless, but not vice versa. and include the planar graphs and apex graphs. The projection must be "regular", meaning that no two vertices project to the same point, no vertex projects to the interior of an edge, and at every point of the projection where the projections of two edges intersect, they cross transversally; with this restriction, any two projections lead to the same linking number. The linking number of the unlink is zero, and therefore, if a pair of curves has nonzero linking number, the two curves must be linked. However, there are examples of curves that are linked but that have zero linking number, such as the Whitehead link. An embedding of a graph into three dimensional space consists of a mapping from the vertices of the graph to points in space, and from the edges of the graph to curves in space, such that each endpoint of each edge is mapped to an endpoint of the corresponding curve, and such that the curves for two different edges do not intersect except at a common endpoint of the edges. Any finite graph has a finite (though perhaps exponential) number of distinct simple cycles, and if the graph is embedded into three dimensional space then each of these cycles forms a simple closed curve. One may compute the linking number of each disjoint pair of curves formed in this way; if all pairs of cycles have zero linking number, the embedding is said to be linkless. In some cases, a graph may be embedded in space in such a way that, for each cycle in the graph, one can find a disk bounded by that cycle that does not cross any other feature of the graph. In this case, the cycle must be unlinked from all the other cycles disjoint from it in the graph. The embedding is said to be flat if every cycle bounds a disk in this way. A flat embedding is necessarily linkless, but there may exist linkless embeddings that are not flat: for instance, if G is a graph formed by two disjoint cycles, and it is embedded to form the Whitehead link, then the embedding is linkless but not flat. A graph is said to be intrinsically linked if, no matter how it is embedded, the embedding is always linked. Although linkless and flat embeddings are not the same, the graphs that have linkless embeddings are the same as the graphs that have flat embeddings.
Мысалдар мен қарсы мысалдар
Көрсетілгендей, Петерсен отбасының жеті графигінің әрқайсысы өзіндік байланысқа ие: осы графиктің әрқайсысы кеңістікте қалай орналасқандығына қарамастан, олардың бір-бірімен байланысты екі циклы бар. Бұл графиктің ішіне толық K6 графигі, Петерсен графигі, толық екі бөлікті K4,4 графигінен бір қабырғасы алынып тасталған графигі және толық үш бөлікті K3,3,1 графигі кіреді. Кез келген жазық графтың жазық және байланысы жоқ орналасуы бар: графты жазықтыққа орналастырып, жазықтықты кеңістікке орналастырыңыз. Егер граф жазық болса, оны кеңістікте тегіс және байланысы жоқ етіп орналастырудың жалғыз жолы – әрбір жазық орналасуды үнемі тегіс жазықтықта орналасу үшін деформациялауға болады. Керісінше, кез келген жазық емес, байланысы жоқ графтың бірнеше байланысы жоқ орналасуы бар. Байланыссыз кіріктірілетін графтардың тыйым салынған кіші топтамасы анықталды: Петерсен отбасының жеті графигі – барлығы кіші, ең аз өзара байланысты графтар. Алайда, Сакс осылар ғана ең аз байланысты графтар екенін дәлелдей алмады, және бұл ақыры орындалды. Байланыссыз графтардың тыйым салынған кіші сипаттамасы оларды тану үшін полиномиалдық уақыт алгоритміне әкеледі, бірақ нақты кіріктіруді құру үшін емес. графиктің байланыссыз кіріктірілуге болатынын тексеріп, егер солай болса, графиктің жазық кіріктіруін құрастыратын сызықтық уақыт алгоритмін сипаттады. Олардың алгоритмі берілген графиктің ішіндегі үлкен жазық субграфтарды табады, егер байланыссыз кіріктіру болса, ол субграфтың жазық кіріктіруін сақтауы керек. Мұндай субграф табылған сайын графикті қайта-қайта оңайлату арқылы олар мәселені қалған графтың шектелген ағаш еніне дейін азайтады, сол кезде оны динамикалық бағдарламалау арқылы шешуге болады. Берілген кіріктірудің тегіс немесе байланысы жоқ екенін тиімді тексеру мәселесі қойылды. Ол әлі де шешілмеген күйде қалып отыр, және оның күрделілігі түйінсіздік мәселесімен тең – кеңістіктегі бір қисықтың түйінсіз екенін тексеру мәселесі. Түйінсіздікті тексеру (сонымен қатар, кіріктірудің байланыссыздығын тексеру) NP класында екені белгілі, бірақ NP-толық екені әлі белгісіз.
The forbidden minor characterization of linkless graphs leads to a polynomial time algorithm for their recognition, but not for actually constructing an embedding. described a linear time algorithm that tests whether a graph is linklessly embeddable and, if so, constructs a flat embedding of the graph. Their algorithm finds large planar subgraphs within the given graph such that, if a linkless embedding exists, it has to respect the planar embedding of the subgraph. By repeatedly simplifying the graph whenever such a subgraph is found, they reduce the problem to one in which the remaining graph has bounded treewidth, at which point it can be solved by dynamic programming. The problem of efficiently testing whether a given embedding is flat or linkless was posed by It remains unsolved, and is equivalent in complexity to unknotting problem, the problem of testing whether a single curve in space is unknotted. Testing unknottedness (and therefore, also, testing linklessness of an embedding) is known to be in NP but is not known to be NP complete.
Кіші Колин де Вердиер инварианты бар графиктер
Колин де Вердиердің граф инварианты – алгебралық граф теориясын қолдана отырып, кез келген граф үшін анықталатын бүтін сан. Кез келген тұрақты μ үшін, Колин де Вердиердің граф инварианты μ-дан аспайтын графтар кіші жабық отбасын құрайды, және олардың алғашқылары жақсы белгілі: μ ≤ 1 болғанда – сызықтық ормандар (жалғасқан жолдардың жиынтығы), μ ≤ 2 болғанда – сыртқы жазықтық графиктер, ал μ ≤ 3 болғанда – жазықтық графиктер. Бұрын болжанылған және дәлелденгендей, μ ≤ 4 болғанда – сілтемесіз ендірілетін графиктер болып табылады.
Апекс графиктері
Жазық графиктер және апекс графиктер сілтемесіз ендіріледі, сондай-ақ осы графиктерден YΔ және ΔY түрлендірулері арқылы алынған графиктер де сілтемесіз ендіріледі. Бірақ, YΔ және ΔY түрлендірулері, оқшауланған төбелерді және бірінші дәрежелі төбелерді жою, екінші дәрежелі төбелерді ығыстыру арқылы апекс графына түрлендірілмейтін сілтемесіз графиктер де бар: мысалы, он төбелі тәж графы сілтемесіз ендіріледі, бірақ оны осылайша апекс графына түрлендіру мүмкін емес. Дегенмен, түйінсіз ендіру үшін тыйым салынған минималды кіші графиктер де бар, олар (осы екі график сияқты) ішкі байланысты графикке бір төбе қосу арқылы жасалмайды, бірақ олардың тізімі белгісіз. Графтар отбасыларын олардың ендірілімдеріндегі күрделі түйіндер мен сілтемелердің болуымен немесе болмауымен, немесе Евклид кеңістігінен өзге үш өлшемді манифольдтарда сілтемесіз ендіру арқылы анықтауға болады. Егер үш цикл болса, олардың біреуі екінші екеуінен бөліне алмайтын болса, онда графты үш есе байланысқан деп анықтаймыз; олар K9 өзінен-өзі үш есе байланысқан емес екенін, бірақ K10 екенін көрсетеді. Жалпы алғанда, кез келген n үшін n-есе байланысқан ендіруді топологиялық сферамен екі бөлек бөлікке бөліне алмайтын n компоненттік сілтемесі бар ендіру деп анықтауға болады; n-есе байланысқан минималды кіші графиктер барлық n үшін белгілі.