Восстановление графа по вершинным покрытиям

[analitik777]

Здравствуйте! Предположим есть полный неориентированный граф из трёх вершин. Тогда минимальные вершинные покрытия имеют вид: {1,2}, {1,3},{2,3}. Рассмотрим задачу. Пусть задано множество, состоящее из множеств вершин. Нужно определить, является ли данное множество множеством минимальных вершинных покрытий графа. По сути надо найти граф. Есть ли алгоритм для решения такой задачи?

[mihaild]

Уточните формулировку: есть множество из всех минимальных покрытий (и минимальных по размеру, или таких что никакое их подмножество уже не будет покрытием?), или какое-то его подмножество? Нужно проверить, существует ли граф, для которого данные множества - это минимальные покрытия, или что?

[analitik777]

mihaild в сообщении #1371207 писал(а):

Уточните формулировку: есть множество из всех минимальных покрытий (и минимальных по размеру, или таких что никакое их подмножество уже не будет покрытием?), или какое-то его подмножество? Нужно проверить, существует ли граф, для которого данные множества - это минимальные покрытия, или что?

Будем называть множество $S=\{v_1,v_2,...,v_k\}$ минимальным вершинным покрытием, если любое подмножество множества $S$ не является вершинным покрытием.
Теперь поподробней о задаче. Пусть $V=\{1,2,...,n\}$. Дано множество $M=\{S_1,S_2,...S_m\}$, где $S_i\subseteq V,\forall i\in \{1,2,...,m\}$. Вопрос: существует ли граф, для которого $M$ будет множеством минимальных вершинных покрытий?

[Lia]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- отсутствуют собственные содержательные попытки решения задач(и).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.