2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Восстановление графа по вершинным покрытиям
Сообщение23.01.2019, 22:12 
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$ будет множеством минимальных вершинных покрытий?

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

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

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group