WikiDer > Spitzenabdeckung

In dem Graphentheorie ist ein Spitzenbedeckung (auch Bogenabdeckung, Bogenabdeckung und Randabdeckung genannt) (Englisch: Randabdeckung) von a AnzahlG ein TeilmengeC der Seiten des Graphen, für die jeder Knoten von G der Start- oder Endpunkt ist von mindestens einer Seite der Menge C. Es heißt dann C die Knöpfe von Gbedeckt. Die folgende Abbildung zeigt zwei Beispiele für Spitzenbespannungen:

EIN minimale Kantenabdeckung ist eine Kantenabdeckung mit der kleinstmöglichen Anzahl von Kanten. Diese Nummer heißt Kantenabdeckungsnummer (Englisch: Kantenbedeckungsnummer) ${Anzeigestil ho (G)}$. Die folgende Abbildung zeigt zwei minimale Kantenabdeckungen:

Beachten Sie, dass die Abbildung rechts auch a Verknüpfung und ein perfektes Match ich, wobei jeder Knoten des Graphen der Start- oder Endpunkt von genau einer Seite von ist ich. Eine perfekte Kopplung ist immer eine minimale Kantenabdeckung.

Das Auffinden einer minimalen Kantenbedeckung und damit der Kantenbedeckungszahl ist ein Problem, das in Polynomzeit kann zuerst gelöst werden maximale Kopplung finde und füge Seiten zu den sogenannten ungesättigten Knoten hinzu (die nicht Teil des Links sind). Im Gegensatz dazu ist das damit verbundene Problem, ein Minimum zu findenKnopfabdeckung ein NP-hart Problem.

Beispiele

• Die Sammlung von allen Seiten von G ist eine Spitzenbespannung, sofern keine isolierten Knoten vorhanden sind (mit Grad Null).
• Das vollzweigeteilte Zählungk_{m, nein} hat als Randabdeckungsnummer max(m,n).

Siehe auch

• Tastenabdeckung