Graphentheorie - Bedeckungen
Ein Abdeckungsgraph ist ein Untergraph, der entweder alle Eckpunkte oder alle Kanten enthält, die einem anderen Graphen entsprechen. Ein Untergraph, der alle Eckpunkte enthält, heißt aline/edge covering. Ein Untergraph, der alle Kanten enthält, heißt avertex covering.
Linienabdeckung
Sei G = (V, E) ein Graph. Eine Teilmenge C (E) wird als Linienbedeckung von G bezeichnet, wenn jeder Scheitelpunkt von G mit mindestens einer Kante in C einfällt, d. H.
Grad (V) ≥ 1 ≤ V ≤ G.
weil jeder Scheitelpunkt durch eine Kante mit einem anderen Scheitelpunkt verbunden ist. Daher hat es einen Mindestgrad von 1.
Example
Schauen Sie sich die folgende Grafik an -
Seine Untergraphen mit Linienbedeckung sind wie folgt:
C 1 = {{a, b}, {c, d}}
C 2 = {{a, d}, {b, c}}
C 3 = {{a, b}, {b, c}, {b, d}}
C 4 = {{a, b}, {b, c}, {c, d}}
Die Linienbedeckung von 'G' existiert nicht genau dann, wenn 'G' einen isolierten Scheitelpunkt hat. Die Linienbedeckung eines Graphen mit 'n' Eckpunkten hat mindestens [n / 2] Kanten.
Minimale Linienbedeckung
Eine Linie, die C eines Graphen G abdeckt, soll minimal sein if no edge can be deleted from C.
Example
In der obigen Grafik sind die Untergraphen mit Linienbedeckung wie folgt:
C 1 = {{a, b}, {c, d}}
C 2 = {{a, d}, {b, c}}
C 3 = {{a, b}, {b, c}, {b, d}}
C 4 = {{a, b}, {b, c}, {c, d}}
Hier sind C 1 , C 2 , C 3 minimale Linienbedeckungen, während C 4 nicht daran liegt, dass wir {b, c} löschen können.
Minimale Leitungsabdeckung
Es ist auch bekannt als Smallest Minimal Line Covering. Eine minimale Linienbedeckung mit einer minimalen Anzahl von Kanten wird als minimale Linienbedeckung von 'G' bezeichnet. Die Anzahl der Kanten in einer minimalen Linienabdeckung in 'G' wird als bezeichnetline covering numbervon 'G' (α 1 ).
Example
Im obigen Beispiel sind C 1 und C 2 die minimale Linienbedeckung von G und α 1 = 2.
Jede Linienbedeckung enthält eine minimale Linienbedeckung.
Jede Linienbedeckung enthält keine minimale Linienbedeckung (C 3 enthält keine minimale Linienbedeckung.
Keine minimale Linienbedeckung enthält einen Zyklus.
Wenn eine Linie, die 'C' abdeckt, keine Pfade mit einer Länge von 3 oder mehr enthält, ist 'C' eine minimale Linienabdeckung, da alle Komponenten von 'C' Sterngraphen sind und aus einem Sterngraphen keine Kante gelöscht werden kann.
Scheitelpunktabdeckung
Sei 'G' = (V, E) ein Graph. Eine Teilmenge K von V wird als Scheitelpunktabdeckung von 'G' bezeichnet, wenn jede Kante von 'G' mit einem Scheitelpunkt in 'K' zusammenfällt oder von diesem abgedeckt wird.
Example
Schauen Sie sich die folgende Grafik an -
Die Untergraphen, die aus dem obigen Diagramm abgeleitet werden können, sind wie folgt:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
K 4 = {a, d}
Hier haben K 1 , K 2 und K 3 eine Scheitelpunktbedeckung, während K 4 keine Scheitelpunktbedeckung hat, da es die Kante {bc} nicht bedeckt.
Minimale Scheitelpunktabdeckung
Ein Scheitelpunkt 'K' des Graphen 'G' wird als minimale Scheitelpunktabdeckung bezeichnet, wenn kein Scheitelpunkt aus 'K' gelöscht werden kann.
Example
In der obigen Grafik sind die Untergraphen mit Scheitelpunktbedeckung wie folgt:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Hier sind K 1 und K 2 minimale Scheitelpunktbedeckungen, während in K 3 der Scheitelpunkt 'd' gelöscht werden kann.
Minimale Scheitelpunktabdeckung
Es ist auch als kleinste minimale Scheitelpunktbedeckung bekannt. Eine minimale Scheitelpunktabdeckung des Graphen 'G' mit einer minimalen Anzahl von Scheitelpunkten wird als minimale Scheitelpunktabdeckung bezeichnet.
Die Anzahl der Scheitelpunkte in einer minimalen Scheitelpunktabdeckung von 'G' wird als Scheitelpunktabdeckungszahl von G (α 2 ) bezeichnet.
Example
In der folgenden Grafik sind die Untergraphen mit Scheitelpunktabdeckung wie folgt:
K 1 = {b, c}
K 2 = {a, b, c}
K 3 = {b, c, d}
Hier ist K 1 eine minimale Scheitelpunktabdeckung von G, da es nur zwei Scheitelpunkte hat. α 2 = 2.