Перестановка графика так, чтобы определенные узлы не были смежными?

Question

EDIT: Именно поэтому я пытаюсь найти два непересекающихся независимых набора известного размера в графе, виде треугольной сетки, которая может иметь отверстия и имеет переменную форму периметра.

Я не очень хорошо разбираюсь в теории графов, поэтому не уверен, существует ли эффективное решение этой проблемы. Рассмотрим следующие графы:

http://i.imgur.com/Wi5Rfbd.jpg

http://i.imgur.com/0GFzaDl.jpg

http://i.imgur.com/pezW4yk.jpg

Цвета любых двух узлов можно поменять местами. Цель состоит в том, чтобы не было двух соседних красных узлов, и два зеленых узла не смежны. Края, отмеченные восклицательными знаками, недействительны. В принципе, мне нужно написать два алгоритма:

• Определить, что узлы в данной графе могут быть расположены таким образом, что красные и зеленые узлы не смежны с узлами одного и того же цвета.

• На самом деле переупорядочить узлы.

Я немного потерял, как это реализовать. Не сложно отделить узлы одного цвета, но повторение процесса для второго цвета может испортить первый цвет. Без способа определить, действительно ли график может быть правильно настроен, этот процесс может зависеть навсегда.

Есть ли какой-то алгоритм, который я могу использовать для этого? Меня в основном интересует граф первого изображения (треугольная сетка), но общий алгоритм тоже будет работать.

Answer 1

Прежде всего, отметим, что проблема заключается в варианте graph coloring.

Теперь, если вы имеете дело только с 2 цветами (красный, зеленый) - раскраска графика с 2 цветами довольно проста, и в основном это делается, если выяснить, является ли график bipartite и раскрасить каждую «сторону» графа в одном цвете. Найти, если граф двудольный, достаточно прост.

Однако, если вы хотите более двух цветов, проблема становится NP-Complete и на самом деле является вариантом проблемы раскрашивания графа.

График раскраски Проблема:

Учитывая график G = (V, E), а также ряд k определить, есть ли является функцию c:V->{1,2.,,,.k} такой, что с (v) = V (и) -> (v, u) не является краем .

неформально, вы можете покрасить граф в k цветов, и вы должны определить, есть ли какой-то окраски таким образом, что вы никогда не окрашивают 2 узла, которые разделяют края с тем же цветом.

Обратите внимание, что, хотя кажется, что ваша проблема немного проще, поскольку вы уже знаете, каково количество узлов в каждом цвете, это не имеет особого значения.

Предположим, у вас есть алгоритм полиномиального времени A, который решает вашу проблему.
Теперь, учитывая экземпляр (G,k) раскраски графа - есть только O(n^3) возможности # color1, # color2, # color3 - поэтому, исследуя каждый из них и вызывая на нем A, вы можете найти решение полиномиального времени для Graph-Coloring , Это будет означать P=NP, что, скорее всего, (по мнению большинства исследователей CS) не так.

---

TL; др:

для 2-х цветов: выяснить, если граф является двудольным - и дают один цвет на каждой стороне графика.
Для 3 или более цветов: Неизвестного эффективного решения нет, и общее мнение не существует.

Answer 2

Я думал, что эта проблема будет проще для планарного графика, но, к сожалению, это не так. Лучшее совпадение для этой проблемы я смог найти minimum sum coloring и largest bipartite subgraph.

Для большого двудольного подграфа предположим, что количество красных + количество зелени точно соответствует размеру самого большого двудольного подграфа. Тогда эта проблема эквивалентна вашей. Бумага утверждает, что она по-прежнему NP-жесткая даже для планарных графиков.

Для окраски минимальной суммы предположим, что красный цвет имеет вес 1, зеленый цвет имеет цвет 2, и у нас есть бесконечно много синих цветов с некоторым весом> размера графа. Тогда, если ответ является точно минимальной красной суммой, для его нахождения нет полиномиального алгоритма (хотя бумага ссылается на такой алгоритм для хордовых графов).

В любом случае, кажется, что чем ближе ваш красный + зеленый отсчет к «оптимальному» в некотором смысле подграфу, тем сложнее проблема.

Если вы можете позволить себе неточное решение или расслабленное решение, то вы только стреляете, скажем, красными, у вас есть возможность. Как я сказал в комментарии, приближенное решение задачи максимального независимого множества для планарного графа. Затем окрасьте этот набор в красный и синий цвета, если он достаточно большой.

Если вы знаете, что красный + зеленый намного меньше общего числа вершин, может работать другое приближение. Посмотрите на главу введения this article. Она утверждает, что:

Для графов, которые обещают иметь небольшую хроматическую число, лучше гарантии известно: дается K-раскрашиваемым граф, алгоритм, в связи с Karger и соавт. [12] использует полуопределенное программирование (SDP), чтобы найти независимый набор размеров около Ω (n/Δ^(1-2/k)) .

Ваш график определен для 4-цветных, поэтому вы можете рассчитывать на достаточно большой независимый набор. В той же статье говорится, что жадное решение уже может найти достаточно большой независимый набор.