Выпуклое вложение - Convex embedding

В геометрическая теория графов, а выпуклое вложение графа - это вложение графа в Евклидово пространство, вершины которого представлены в виде точек, а края - в виде отрезки линии, так что все вершины вне указанного подмножества принадлежат выпуклый корпус своих соседей. Точнее, если ${ displaystyle X}$ - подмножество вершин графа, то выпуклый ${ displaystyle X}$-вложение вкладывает граф таким образом, что каждая вершина либо принадлежит ${ displaystyle X}$ или помещается внутри выпуклой оболочки своих соседей. Выпуклое вложение в ${ displaystyle d}$-мерное евклидово пространство называется общая позиция если каждое подмножество ${ displaystyle S}$ его вершин охватывает подпространство размерности ${ Displaystyle мин (д, | S | -1)}$.^[1]

Выпуклые вложения были введены В. Т. Тутте в 1963 году. Тутте показал, что если внешняя грань ${ displaystyle F}$ из планарный граф фиксируется к форме данного выпуклого многоугольника на плоскости, а остальные вершины размещаются путем решения система линейных уравнений описывая поведение идеальных пружин на ребрах графа, результатом будет выпуклый ${ displaystyle F}$-встраивание. Более того, каждая грань вложения, построенного таким образом, будет выпуклым многоугольником, в результате чего получится выпуклый рисунок графа.^[2]

Помимо планарности, выпуклые вложения вызвали интерес в результате исследования 1988 г. Нати Линиал, Ласло Ловас, и Ави Вигдерсон что график k-вершинно-связанный тогда и только тогда, когда у него есть ${ Displaystyle (к-1)}$-мерная выпуклая ${ displaystyle S}$-встраивание в общее положение, для некоторых ${ displaystyle S}$ из ${ displaystyle k}$ его вершин, и что если он k-вершинносвязно, то такое вложение можно построить в полиномиальное время выбирая ${ displaystyle S}$ быть любым подмножеством ${ displaystyle k}$ вершин и решение системы линейных уравнений Тутта.^[1]

Одномерные выпуклые вложения (в общем положении) для заданного набора из двух вершин эквивалентны биполярные ориентации данного графа.^[1]

Рекомендации