Я учусь для экзамена, и один из демонстрационных вопросов следующие:
Покрытие вершины: покрытие вершины в графике является рядом вершин, таким образом, что каждый край имеет по крайней мере одну из своих двух конечных точек в этом наборе.
Минимальное покрытие вершины: МИНИМАЛЬНОЕ покрытие вершины в графике является покрытием вершины, которое имеет самое маленькое количество вершин среди всех возможных покрытий вершины.
Минимальное покрытие вершины МИНИМАЛЬНОЕ покрытие вершины в графике является покрытием вершины, которое не содержит другое покрытие вершины (удаляющий любую вершину из набора создал бы ряд вершин, который не является покрытием вершины),
Вопрос: минимальное покрытие вершины является не всегда минимальным покрытием вершины. Продемонстрируйте это с простым примером.
Кто-либо может получить их голову вокруг этого? Мне не удается видеть различие между двумя. Что еще более важно, мне нелегко визуализировать его.
Я серьезно надеюсь, что он не собирается задавать нечетные вопросы как этот на экзамене!
Рассмотрим граф
A --- B --- C
B - минимальное покрытие вершин.
A, C - минимальное вершинное покрытие. Удалите либо A, либо C, у вас не останется вершинной крышки.