Проблема покрытия отношений эквивалентности (в теории графов)

Отношение эквивалентности на конечном множестве вершин может быть представлено неориентированным графом, который является дизъюнктным объединением клик. Набор вершин представляет элементы, а ребро представляет, что два элемента эквивалентны.

Если у меня есть граф и графы , мы говорим, что покрывается если множество ребер равно объединению множеств ребер . Наборы ребер не должны быть непересекающимися. Обратите внимание, что любой неориентированный граф $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G$ $G_1,\dots,G_k$ $G_1,\dots,G_k$ $G$ может быть покрыто конечным числом отношений эквивалентности (т. е. непересекающимся объединением графов клик).

У меня есть несколько вопросов:

Что можно сказать о минимальном количестве отношений эквивалентности, необходимых для покрытия графа ? $G$
Как мы можем вычислить это минимальное число?
Как мы можем вычислить явное минимальное покрытие , т. Е. Набор отношений эквивалентности, размер которых минимален и которые покрывают ? $G$ $G$
Есть ли у этой проблемы какие-либо приложения помимо логики разбиения ( двойственной логики подмножеств )?
У этой проблемы есть хорошо установленное имя?

Учитывая различные недоразумения, указанные в комментариях, вот несколько рисунков, иллюстрирующих эти концепции. Если у вас есть идея для более понятной терминологии (вместо «покрытия», «отношения эквивалентности», «непересекающегося объединения клик» и «не обязательно непересекающегося» объединения ребер), не стесняйтесь, дайте мне знать.

Вот изображение графика и одного отношения эквивалентности, покрывающего его: граф и одно отношение эквивалентности, покрывающие его

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

Вот изображение графика и трех отношений эквивалентности, покрывающих его: граф и три отношения эквивалентности, покрывающие его
Менее очевидно, что требуются как минимум три отношения эквивалентности. Лемма 1.9 из Dual из логики подмножеств может быть использована, чтобы показать, что это правда. Обобщение этой леммы для операций nand с более чем двумя входами послужило мотивацией для этого вопроса.

algorithms graph-theory clique Томас Климпел
источник

Это хорошо известная проблема NP-Complete . en.wikipedia.org/wiki/Clique_cover_problem

садовник

@StephenBly Возможно, это хорошо известная проблема, но ссылка на википедию, которую вы дали, мне не очень помогает. В статье говорится о проблеме покрытия вершин, но здесь речь идет о проблеме покрытия краев. Также отметим, что отношение эквивалентности - это не клика, а непересекающийся союз клик.

Томас Климпел

Что вы подразумеваете под отношением эквивалентности? Набор вершин представляет элементы, а ребро представляет, что два элемента эквивалентны. Если это не то представление, которое вы используете, вам следует прояснить это.

садовник

n - 1

$n-1$

n

$n$

n - 1

$n-1$

@YuvalFilmus В вопросе задается вопрос о наименьшем числе отношений эквивалентности, объединение которых точно является отношением ребер данного графа, а не объединение которого просто включает данный граф.

Дэвид Ричерби

Ответы:

$\text{eq}(G)$ $\text{cc}(G)$

Существуют специальные классы графов, в которых известно точное значение или хорошая верхняя граница для любого числа. В общем, насколько мне известно, лучшие оценки дает Алон [1]:

\log_{2} n - \log_{2} d \leq eq (G) \leq cc (G) \leq 2 e^{2} (Δ + 1)^{2} \ln n,

$\log_2 n - \log_2 d \leq \text{eq}(G) \leq \text{cc}(G) \leq 2e^2 (\Delta+1)^2 \ln n,$

$\Delta$ $G$ $\lceil n^2/4 \rceil$

$\sf NP$ $\text{eq}(G)$ $\sf NP$

[1] Алон, Нога. «Покрытие графов минимальным числом отношений эквивалентности». Combinatorica 6.3 (1986): 201-206.

[2] Блохуис, Аарт и Тон Клокс. «Об эквивалентности, покрывающей число сплитграфов». Обработка информации письма 54,5 (1995): 301-304.

[3] Кучера, Людек, Ярослав Нешетржил и Алеш Пултр. «Сложность размерности три и некоторые связанные граничные характеристики графов». Теоретическая информатика 11.1 (1980): 93-106.

Юхо
источник

Следствие 1.3 из [1] именно то, что мне нужно (в версии, которая применяется к дополнениям пути). Теперь у меня больше нет оправданий для того, чтобы не писать статью об общем подтексте «(A, B, C, ...) подразумевать (Z, Y, X, ...)» (секвенция из секвенциального исчисления) в разделе логика и аналогичные неклассические логики. Но я думаю, я не буду писать это по крайней мере еще полгода. И, может быть, я даже сейчас найду новое оправдание.

Томас Климпел

@ThomasKlimpel Это здорово! (Не факт, что вы могли бы найти новое оправдание, но это было полезно :-))

Juho

Хотя я не знаю названия для такой проблемы, я могу показать, что эта проблема NP-трудная.

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

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

Чао Сюй
источник