Минимум по сравнению с Минимальными покрытиями вершины

Я учусь для экзамена, и один из демонстрационных вопросов следующие:

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

Минимальное покрытие вершины: МИНИМАЛЬНОЕ покрытие вершины в графике является покрытием вершины, которое имеет самое маленькое количество вершин среди всех возможных покрытий вершины.

Минимальное покрытие вершины МИНИМАЛЬНОЕ покрытие вершины в графике является покрытием вершины, которое не содержит другое покрытие вершины (удаляющий любую вершину из набора создал бы ряд вершин, который не является покрытием вершины),

Вопрос: минимальное покрытие вершины является не всегда минимальным покрытием вершины. Продемонстрируйте это с простым примером.

Кто-либо может получить их голову вокруг этого? Мне не удается видеть различие между двумя. Что еще более важно, мне нелегко визуализировать его.

Я серьезно надеюсь, что он не собирается задавать нечетные вопросы как этот на экзамене!

9
задан Jk1 6 July 2014 в 09:47
поделиться

1 ответ

Рассмотрим граф

A --- B --- C

B - минимальное покрытие вершин.

A, C - минимальное вершинное покрытие. Удалите либо A, либо C, у вас не останется вершинной крышки.

19
ответ дан 4 December 2019 в 06:11
поделиться
Другие вопросы по тегам:

Похожие вопросы: