Вложение графа в трехмерное пространство без сцепленных циклов.

Введение

Встраивание графа в 3D пространство без переплетенных циклов

В топологической теории графов, математической дисциплине, вложение без сцеплений ненаправленного графа — это вложение графа в трехмерное евклидово пространство таким образом, что никакие два цикла графа не сцеплены. Плоское вложение — это вложение, обладающее свойством, что каждый цикл является границей топологического диска, внутренность которого не пересекается с графом. Граф, допускающий вложение без сцеплений, — это граф, имеющий вложение без сцеплений или плоское вложение; такие графы образуют трехмерный аналог планарных графов. Соответственно, внутренне сцепленный граф — это граф, не имеющий вложения без сцеплений. Плоские вложения автоматически являются вложениями без сцеплений, но не наоборот, и включают в себя планарные графы и апексные графы. Проекция должна быть «регулярной», то есть никакие две вершины не проецируются в одну и ту же точку, никакая вершина не проецируется во внутреннюю часть ребра, и в каждой точке проекции, где проекции двух ребер пересекаются, они пересекаются трансверсально; при этом ограничении любые две проекции приводят к одному и тому же числу сцеплений. Число сцеплений развязки равно нулю, и поэтому, если пара кривых имеет ненулевое число сцеплений, то эти две кривые должны быть сцеплены. Однако существуют примеры кривых, которые сцеплены, но имеют нулевое число сцеплений, например, связь Уайтхеда. Вложение графа в трехмерное пространство состоит из отображения вершин графа в точки пространства и ребер графа в кривые в пространстве, так что каждая конечная точка каждого ребра отображается в конечную точку соответствующей кривой и так, что кривые для двух различных ребер не пересекаются, кроме как в общей конечной точке ребер. Любой конечный граф имеет конечное (хотя, возможно, экспоненциальное) число различных простых циклов, и если граф вложен в трехмерное пространство, то каждый из этих циклов образует простую замкнутую кривую. Можно вычислить число сцеплений каждой непересекающейся пары кривых, образованных таким образом; если все пары циклов имеют нулевое число сцеплений, то вложение считается вложением без сцеплений. В некоторых случаях граф может быть вложен в пространство таким образом, что для каждого цикла в графе можно найти диск, ограниченный этим циклом, который не пересекает никакие другие элементы графа. В этом случае цикл должен быть несцеплен со всеми другими циклами, не связанными с ним в графе. Вложение считается плоским, если каждый цикл ограничивает диск таким образом. Плоское вложение обязательно является вложением без сцеплений, но могут существовать вложения без сцеплений, которые не являются плоскими: например, если 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. Каждый планарный граф имеет плоскую и не сцеплённую (linkless) вложенность: достаточно вложить граф в плоскость и затем плоскость — в пространство. Если граф планарный, это единственный способ вложить его плоско и без сцеплений в пространство: любое плоское вложение можно непрерывно деформировать так, чтобы оно лежало на плоскости. И наоборот, каждый непланарный не сцеплённый граф имеет несколько не сцеплённых вложений. Набор запрещённых миноров для не сцеплённо встраиваемых графов был определён : семь графов семейства Петерсена являются всеми минимальными внутренне связанными графами по минорам. Однако Саксу не удалось доказать, что это единственные минимальные связанные графы, и это было окончательно установлено . Характеризация не сцеплённых графов через запрещённые миноры приводит к алгоритму полиномиального времени для их распознавания, но не для фактического построения вложения. описал алгоритм линейного времени, который проверяет, является ли граф не сцеплённо встраиваемым, и, если да, строит плоское вложение графа. Их алгоритм находит большие планарные подграфы в заданном графе таким образом, что, если существует не сцеплённое вложение, оно должно соответствовать планарному вложению подграфа. Повторно упрощая граф при обнаружении такого подграфа, они сводят задачу к той, в которой оставшийся граф имеет ограниченную древовидную ширину, после чего её можно решить с помощью динамического программирования. Проблема эффективной проверки, является ли заданное вложение плоским или не сцеплённым, была поставлена . Она остаётся нерешённой и по сложности эквивалентна проблеме развязки узла, проблеме проверки, является ли одна кривая в пространстве незавязанной. Известно, что проверка развязки узла (и, следовательно, также проверка не сцеплённости вложения) находится в классе NP, но неизвестно, является ли она NP-полной.

As showed, each of the seven graphs of the Petersen family is intrinsically linked: no matter how each of these graphs is embedded in space, they have two cycles that are linked to each other. These graphs include the complete graph K6, the Petersen graph, the graph formed by removing an edge from the complete bipartite graph K4,4, and the complete tripartite graph K3,3,1. Every planar graph has a flat and linkless embedding: simply embed the graph into a plane and embed the plane into space. If a graph is planar, this is the only way to embed it flatly and linklessly into space: every flat embedding can be continuously deformed to lie on a flat plane. And conversely, every nonplanar linkless graph has multiple linkless embeddings. The set of forbidden minors for the linklessly embeddable graphs was identified by : the seven graphs of the Petersen family are all minor minimal intrinsically linked graphs. However, Sachs was unable to prove that these were the only minimal linked graphs, and this was finally accomplished by
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.