Maximalkantenabdeckung

Maximalkantenabdeckung ist ein Begriff aus der Graphentheorie, der sich auf eine Kantenmenge bezieht, die eine Knotenmenge vollständig abdeckt. Gegeben sei ein Graph G = (V,E). Eine Kantenabdeckung (edge cover) C ⊆ E ist eine Menge von Kanten, so dass jeder Knoten v ∈ V von mindestens einer Kante in C berührt wird. Eine Maximalkantenabdeckung ist eine solche Kantenabdeckung, die nicht durch Hinzufügen weiterer Kanten aus E erweitert werden kann, ohne ihre Abdeckungs-Eigenschaft zu verlieren. Da das Hinzufügen von Kanten zu einer Abdeckung deren Abdeckungs-Eigenschaft nicht verletzt, ist in der Praxis die einzige inklusionsmaximale Kantenabdeckung normalerweise der Gesamtkantenstamm E; damit ist der Begriff in dieser Form eher uninformativ. Daher wird der Ausdruck Maximalkantenabdeckung selten verwendet.

In der Praxis konzentriert man sich eher auf minimale oder minimale Kantenabdeckungen und deren Zusammenhang mit Maximum-Matching. Ein Graph ohne isolierte Knoten besitzt eine minimale Kantenabdeckung, deren Größe durch das Maximum-Matching bestimmt werden kann. Sei M ein maximales Matching mit Größe |M| = μ(G). Dann erhält man eine minimale Kantenabdeckung, indem man zusätzlich zu M für jeden ungeraden oder unverbundenen Knoten v eine Kante wählt, die v berührt. Die Größe dieser minimalen Kantenabdeckung ist |V| − μ(G). Folgt man dieser Construction, erhält man eine Kantenabdeckung mit minimaler Anzahl von Kanten.

Algorithmisch lässt sich eine minimale Kantenabdeckung effizient erreichen: Zunächst wird ein Maximum-Matching M berechnet (z. B. in bipartiten Graphen in O(E√V); für Allgemeingraphen mit Blosson-Algorithmus). Anschließend werden für alle unbesetzten Knoten neue Kanten hinzugefügt, bis jeder Knoten gedeckt ist. Die resultierende Menge ist eine minimale Kantenabdeckung. Voraussetzungen: Es gibt keine isolierten Knoten; sonst existiert keine Kantenabdeckung, die alle Knoten abdeckt.

Siehe auch: Kantenabdeckung, Maximum-Matching, Minimale Abdeckung.