Минимальных против минимальной вершины охватывает

Question

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

Vertex Крышка: вершина крышка в графе есть множество вершин, что каждое ребро имеет по меньшей мере один его двух конечных точек в этом множестве.

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

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

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

Можете ли вы об этом подумать? Я не вижу различия между ними. Что еще более важно, мне трудно его визуализировать.

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

Answer 1

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

A --- B --- C 

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

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

Answer 2

Рассмотрим следующий неориентированный граф:

множество вершин {2,4,5} является минимальная вершина крышки графа. Зачем? потому что это крышка вершины (все края покрыты), и нет другого вершинного покрытия с меньшим количеством вершин.

Множество вершин {2,3,5,6,7} является минимальным вершина крышки. Зачем? потому что это крышка вершины, и любое нетривиальное подмножество {2,3,5,6,7} не является вершинным накрытием. Попробуйте удалить любую вершину из {2,3,5,6,7} и убедитесь, что вы оставили непокрытый край. То, что делает вершинную оболочку минимальной, - это неспособность ее уменьшить. Вы не можете сделать набор меньше, чем он есть, и по-прежнему получить вершинную обложку (без вставки вершин в нее).

Очевидно, что данное минимальное покрытие вершин не является минимальным вершинным накрытием, так как минимальное покрытие вершин имеет три вершины, а наше минимальное вершинное покрытие имеет 5 вершин. Следовательно, не каждое минимальное покрытие вершин также является минимальным вершинным накрытием.

Каждое минимальное покрытие вершин также является минимальным вершинным покрытием, так как удаление вершин из минимального вершинного покрытия приведет к тому, что множество вершин размером меньше минимального покрытия. Таким образом, любое нетривиальное подмножество минимального вершинного покрытия не является вершинным накрытием, поэтому минимальное покрытие вершин также минимально.