Minimum vs Minimal Scheitel bedeckt

Question

I für eine Prüfung am Studium und eine der Beispielfragen ist wie folgt:

Vertex Abdeckung: eine Scheitelabdeckung in einem Graph ist eine Menge von Knoten, so dass jeder Rand mindestens eine aufweist seiner zwei Endpunkte in diesem Satz.

Minimale Vertex-Abdeckung: Eine MINIMUM-Vertex-Abdeckung in einem Diagramm ist eine Vertex-Abdeckung, die die kleinste Anzahl von Vertices unter allen möglichen Vertex-Abdeckungen aufweist.

Minimal Knotenüberdeckung eine minimale Knotenüberdeckung in einem Diagramm eine Knotenüberdeckung ist, die nicht ein andere Knotenüberdeckung enthält (jeden Scheitelpunkt aus der Menge zu löschen würde eine Menge von Knoten erzeugen, die nicht eine Scheitelabdeckung)

Frage : Eine minimale Vertex-Abdeckung ist nicht immer eine minimale Vertex-Abdeckung. Zeigen Sie dies anhand eines einfachen Beispiels.

Kann jemand ihren Kopf herumkommen? Ich kann den Unterschied zwischen den beiden nicht erkennen. Noch wichtiger ist, dass es mir schwer fällt, es mir vorzustellen.

Ich hoffe ernsthaft, er wird nicht ungerade Fragen wie diese auf der Prüfung stellen!

Answer 1

Betrachten Sie die grafische Darstellung

A --- B --- C 

B die minimale Knotenüberdeckung ist.

A, C ist eine minimale Vertex-Abdeckung. Entfernen Sie entweder A oder C, Sie bleiben nicht mit einer Vertex-Abdeckung zurück.

Answer 2

folgendes ungerichteten Graphen Betrachten:

Der Satz von Scheitelpunkten {2,4,5} ein Minimum Knotenüberdeckung des Diagramms. Warum? weil es eine Vertex-Abdeckung ist (alle Kanten sind bedeckt) und es gibt keine andere Vertex-Abdeckung mit weniger Vertices.

Der Satz von Scheitelpunkten {2,3,5,6,7} eine minimal Vertex Abdeckung. Warum? weil es eine Eckenabdeckung ist und jede nicht-triviale Teilmenge von {2,3,5,6,7} keine Eckenabdeckung ist. Versuchen Sie, einen Eckpunkt von {2,3,5,6,7} zu entfernen und sehen Sie, dass Sie eine unbedeckte Kante übrig lassen. Was eine Vertex-Abdeckung minimal macht, ist eine Unfähigkeit, sie zu reduzieren. Sie können die Menge nicht kleiner machen, als sie bereits ist, und trotzdem eine Vertex-Abdeckung erhalten (ohne Scheitelpunkte einzufügen).

Offensichtlich ist die gegebene minimale Vertex-Abdeckung keine minimale Vertex-Abdeckung, da eine minimale Vertex-Abdeckung drei Vertices hat und unsere minimale Vertex-Abdeckung 5 Vertices hat. Daher ist nicht jede minimale Vertex-Abdeckung auch eine minimale Vertex-Abdeckung.

Jede minimale Vertex-Abdeckung ist auch eine minimale Vertex-Abdeckung, da das Entfernen von Vertices aus einer minimalen Vertex-Abdeckung zu einer Menge von Vertices führt, deren Größe kleiner als die minimale Abdeckung ist. Somit ist jede nicht-triviale Teilmenge einer minimalen Vertex-Abdeckung keine Vertex-Abdeckung, und daher ist auch eine minimale Vertex-Abdeckung minimal.