Объединение двух глобально жестких графов

Question

Это вопрос об алгоритме для решения задачи теории графов.

Допустим, нам даны два глобально жестких графа F1 и F2.У нас также есть список E ребер, которые соединяют пары вершин (i, j), где i всегда является вершиной в F1, а j всегда является вершиной в F2.Эрен и соавт.(см. цитату ниже) доказали, что в двух измерениях граф F, созданный путем слияния F1, F2 и E, также является глобально жестким, если выполняются следующие два условия:

1. E содержит по крайней мере триотдельные вершины в F1 и, по крайней мере, три разные вершины в F2.
2. В E. есть по крайней мере четыре ребрадля любых заданных F1, F2 и E. Меня интересует предоставление исправления для случая, когда вышеуказанные условия не выполняются.В частности, я ищу алгоритм, чтобы найти наименьший набор новых ребер E ', которые при слиянии с E удовлетворяют вышеуказанным условиям.У кого-нибудь есть идея, как мне поступить?

   Я поставил задачу, и знаю, как проверить, соответствуют ли F1 и F2 Условию (1).Затем я могу произвольно выбирать новые вершины из каждого графа для использования в E + E '.Я застрял в том, как определить связь между новой и старой вершинами.

   Цитирование (Эрен и др.) http://www.cs.columbia.edu/techreports/cucs-022-05.pdf

Answer 1

Я думаю, что вы просто должны быть в состоянии

• Выбрать несколько произвольных наборов вершин V1 и V2 (конечно, не инцидентных ни одному ребру в E), пока у нас не будет достаточно, чтобы удовлетворить (1)
• Соедините элементы V1 и V2, чтобы сформировать ребра в E ', пока не исчерпан один набор
• Соедините остаток с произвольными вершинами в противоположном наборе
• Добавьте еще одинпроизвольное ребро между F1 и F2, если E + E 'все еще не удовлетворяет (2)