View
9
Download
0
Category
Preview:
Citation preview
Approximation unabhangiger Mengen inGraphen mit dem Greedy Algorithmus
(Teil 2)
Matthias Baumgart
matthias.baumgart@informatik.tu-chemnitz.de
Chemnitz, 9. Dezember 2003
1
Gliederung
1. Der MIN-Greedy Algorithmus
1
Gliederung
1. Der MIN-Greedy Algorithmus
2. Die Gute des MIN-Greedy
1
Gliederung
1. Der MIN-Greedy Algorithmus
2. Die Gute des MIN-Greedy
1.1. Obere Schranken
1
Gliederung
1. Der MIN-Greedy Algorithmus
2. Die Gute des MIN-Greedy
1.1. Obere Schranken
bezuglich des maximalen Knotengrades ∆
1
Gliederung
1. Der MIN-Greedy Algorithmus
2. Die Gute des MIN-Greedy
1.1. Obere Schranken
bezuglich des maximalen Knotengrades ∆bezuglich des durchschnittlichen Knotengrades d
1
Gliederung
1. Der MIN-Greedy Algorithmus
2. Die Gute des MIN-Greedy
1.1. Obere Schranken
bezuglich des maximalen Knotengrades ∆bezuglich des durchschnittlichen Knotengrades d
1.2. Untere Schranken
1
Gliederung
1. Der MIN-Greedy Algorithmus
2. Die Gute des MIN-Greedy
1.1. Obere Schranken
bezuglich des maximalen Knotengrades ∆bezuglich des durchschnittlichen Knotengrades d
1.2. Untere Schranken
3. Demonstration einer Implementierung des MIN-Greedy in Java
2
Der MIN-Greedy Algorithmus
MIN-Greedy(G = (V,E))1 IGr ← ∅
2
Der MIN-Greedy Algorithmus
MIN-Greedy(G = (V,E))1 IGr ← ∅2 while V 6= ∅ do3 wahle v ∈ V mit d(v) = minw∈V {d(w)}
2
Der MIN-Greedy Algorithmus
MIN-Greedy(G = (V,E))1 IGr ← ∅2 while V 6= ∅ do3 wahle v ∈ V mit d(v) = minw∈V {d(w)}4 IGr ← IGr ∪ {v}
2
Der MIN-Greedy Algorithmus
MIN-Greedy(G = (V,E))1 IGr ← ∅2 while V 6= ∅ do3 wahle v ∈ V mit d(v) = minw∈V {d(w)}4 IGr ← IGr ∪ {v}5 V ← V \ ({v} ∪N(v))
2
Der MIN-Greedy Algorithmus
MIN-Greedy(G = (V,E))1 IGr ← ∅2 while V 6= ∅ do3 wahle v ∈ V mit d(v) = minw∈V {d(w)}4 IGr ← IGr ∪ {v}5 V ← V \ ({v} ∪N(v))6 E ← E \ {e : e ∈ E und e ∩ ({v} ∪N(v)) 6= ∅}
2
Der MIN-Greedy Algorithmus
MIN-Greedy(G = (V,E))1 IGr ← ∅2 while V 6= ∅ do3 wahle v ∈ V mit d(v) = minw∈V {d(w)}4 IGr ← IGr ∪ {v}5 V ← V \ ({v} ∪N(v))6 E ← E \ {e : e ∈ E und e ∩ ({v} ∪N(v)) 6= ∅}7 return IGr
3
Obere Schranke der Gute bezuglich ∆
Satz 1 Sei ∆ der maximale Grad des Graphen G = (V,E). Danngilt fur die Gute des MIN-Greedy
RGr(G) ≤ ∆ + 23
.
3
Obere Schranke der Gute bezuglich ∆
Satz 1 Sei ∆ der maximale Grad des Graphen G = (V,E). Danngilt fur die Gute des MIN-Greedy
RGr(G) ≤ ∆ + 23
.
Beweis: Teil 1. 2
4
Obere Schranke der Gute bezuglich d
Satz 2 Sei d der Durchschnittsgrad eines Graphen G = (V,E).Dann gilt fur die Gute des MIN-Greedy
RGr(G) ≤ d + 22
.
4
Obere Schranke der Gute bezuglich d
Satz 2 Sei d der Durchschnittsgrad eines Graphen G = (V,E).Dann gilt fur die Gute des MIN-Greedy
RGr(G) ≤ d + 22
.
Beweis: In Teil 1 des Vortrages wurde bewiesen, dass
|IGr| ≥(1 + τ2) · nd + 1 + τ
gilt.
5
Eine maximale unabhangige Menge hat die Kardinalitat α = τ ·n.
5
Eine maximale unabhangige Menge hat die Kardinalitat α = τ ·n.Fur die Gute gilt also:
RGr(G) ≤ (τ · n) · (d + 1 + τ)(1 + τ2) · n
5
Eine maximale unabhangige Menge hat die Kardinalitat α = τ ·n.Fur die Gute gilt also:
RGr(G) ≤ (τ · n) · (d + 1 + τ)(1 + τ2) · n
=d · τ + τ + τ2
1 + τ2
5
Eine maximale unabhangige Menge hat die Kardinalitat α = τ ·n.Fur die Gute gilt also:
RGr(G) ≤ (τ · n) · (d + 1 + τ)(1 + τ2) · n
=d · τ + τ + τ2
1 + τ2
= f(τ) .
5
Eine maximale unabhangige Menge hat die Kardinalitat α = τ ·n.Fur die Gute gilt also:
RGr(G) ≤ (τ · n) · (d + 1 + τ)(1 + τ2) · n
=d · τ + τ + τ2
1 + τ2
= f(τ) .
Die Funktion f(τ) ist im Intervall (0, 1] monoton steigend undnimmt ihr Maximum fur τ = 1 an.
5
Eine maximale unabhangige Menge hat die Kardinalitat α = τ ·n.Fur die Gute gilt also:
RGr(G) ≤ (τ · n) · (d + 1 + τ)(1 + τ2) · n
=d · τ + τ + τ2
1 + τ2
= f(τ) .
Die Funktion f(τ) ist im Intervall (0, 1] monoton steigend undnimmt ihr Maximum fur τ = 1 an.
Damit gilt
RGr(G) ≤ d + 22
.2
6
Untere Schranken der Gute
Die vorgestellten oberen Schranken der Gute des MIN-Greedy
Algorithmus konnen nicht wesentlich verbessert werden.
6
Untere Schranken der Gute
Die vorgestellten oberen Schranken der Gute des MIN-Greedy
Algorithmus konnen nicht wesentlich verbessert werden.
Satz 3 Es gibt Graphen G = (V,E) mit maximalem Knotengrad∆ ≥ 3, so dass fur die Gute des MIN-Greedy Algorithmus
RGr(G) ≥ ∆ + 23−O(∆2/n)
gilt.
6
Untere Schranken der Gute
Die vorgestellten oberen Schranken der Gute des MIN-Greedy
Algorithmus konnen nicht wesentlich verbessert werden.
Satz 3 Es gibt Graphen G = (V,E) mit maximalem Knotengrad∆ ≥ 3, so dass fur die Gute des MIN-Greedy Algorithmus
RGr(G) ≥ ∆ + 23−O(∆2/n)
gilt.
Beweis: Wir konstruieren in Abhangigkeit von ∆ mod 3 Graphen,so dass keine bessere Gute erreichen kann.
7
Fall 1: Es sei ∆ ≡ 1 mod 3.
7
Fall 1: Es sei ∆ ≡ 1 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj — Kj
besteht.
7
Fall 1: Es sei ∆ ≡ 1 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj — Kj
besteht.
Jede Clique ist vollstandig mit der nachsten unabhangigen Mengeverbunden.
7
Fall 1: Es sei ∆ ≡ 1 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj — Kj
besteht.
Jede Clique ist vollstandig mit der nachsten unabhangigen Mengeverbunden.
Die Knoten der unabhangigen Menge eines Teilgraphen werden –bis auf ein perfektes Matching – vollstandig mit der Clique desnachsten Teilgraphen verbunden.
8
Den Abschluss bildet eine Clique Kj, die vollstandig mit der letztenunabhangigen Menge verbunden ist.
8
Den Abschluss bildet eine Clique Kj, die vollstandig mit der letztenunabhangigen Menge verbunden ist.
Ein vollstandiger Graph aus 2 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
8
Den Abschluss bildet eine Clique Kj, die vollstandig mit der letztenunabhangigen Menge verbunden ist.
Ein vollstandiger Graph aus 2 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
9
Tabelle der Knotengrade:
9
Tabelle der Knotengrade:
KnotengradKnoten der ersten Clique 2j − 1Knoten der abschließenden Clique 2j − 1Knoten aller anderen Cliquen 3j − 2Knoten der letzten unabhangigen Menge 2j
Knoten aller anderen unabhangigen Mengen 2j − 1
10
10
|IGr| =n− j
2j+ 1
10
|IGr| =n− j
2j+ 1
|Imax| =n− j
2
11
Fur die Gute gilt also
RGr(G) ≥ (n− j)/2(n− j)/(2j) + 1
11
Fur die Gute gilt also
RGr(G) ≥ (n− j)/2(n− j)/(2j) + 1
= j − 2j2
n + j.
11
Fur die Gute gilt also
RGr(G) ≥ (n− j)/2(n− j)/(2j) + 1
= j − 2j2
n + j.
Der Maximalgrad ist ∆ = 3j − 2.
11
Fur die Gute gilt also
RGr(G) ≥ (n− j)/2(n− j)/(2j) + 1
= j − 2j2
n + j.
Der Maximalgrad ist ∆ = 3j − 2. Also gilt
RGr(G) ≥ j − 2j2
n + j
11
Fur die Gute gilt also
RGr(G) ≥ (n− j)/2(n− j)/(2j) + 1
= j − 2j2
n + j.
Der Maximalgrad ist ∆ = 3j − 2. Also gilt
RGr(G) ≥ j − 2j2
n + j
=∆ + 2
3− 2 · ((∆ + 2)/3)2
n + (∆ + 2)/3
11
Fur die Gute gilt also
RGr(G) ≥ (n− j)/2(n− j)/(2j) + 1
= j − 2j2
n + j.
Der Maximalgrad ist ∆ = 3j − 2. Also gilt
RGr(G) ≥ j − 2j2
n + j
=∆ + 2
3− 2 · ((∆ + 2)/3)2
n + (∆ + 2)/3
=∆ + 2
3−O(∆2/n) .
12
Fall 2: Es sei ∆ ≡ 0 mod 3.
12
Fall 2: Es sei ∆ ≡ 0 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj−1 — Kj — Kj−1 — Kj — Kj — Kj−1
besteht.
12
Fall 2: Es sei ∆ ≡ 0 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj−1 — Kj — Kj−1 — Kj — Kj — Kj−1
besteht.
Jede Clique ist vollstandig mit der nachsten unabhangigen Mengeverbunden.
12
Fall 2: Es sei ∆ ≡ 0 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj−1 — Kj — Kj−1 — Kj — Kj — Kj−1
besteht.
Jede Clique ist vollstandig mit der nachsten unabhangigen Mengeverbunden.
Die Verbindung einer unabhangigen Menge mit der nachsten Cli-que ist – bis auf ein einzelnes maximales Matching – vollstandig.
12
Fall 2: Es sei ∆ ≡ 0 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj−1 — Kj — Kj−1 — Kj — Kj — Kj−1
besteht.
Jede Clique ist vollstandig mit der nachsten unabhangigen Mengeverbunden.
Die Verbindung einer unabhangigen Menge mit der nachsten Cli-que ist – bis auf ein einzelnes maximales Matching – vollstandig.
In dieser Weise erfolgt auch die Verbindung zweier Teilgraphen.
13
Die Kette wird mit einer Clique Kj−1 abgeschlossen.
13
Die Kette wird mit einer Clique Kj−1 abgeschlossen.
Ein vollstandiger Graph aus 2 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
13
Die Kette wird mit einer Clique Kj−1 abgeschlossen.
Ein vollstandiger Graph aus 2 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
14
Tabelle der Knotengrade:
14
Tabelle der Knotengrade:
KnotengradKnoten der ersten Clique 2j − 2Knoten der abschließenden Clique 2j − 2Knoten aller anderen Cliquen 3j − 3Knoten der letzten unabhangigen Menge 2j − 1Knoten aller anderen unabhangigen Mengen 2j − 2
15
15
|IGr| = 3 · n− j + 16j − 3
+ 1
15
|IGr| = 3 · n− j + 16j − 3
+ 1
|Imax| = (3j − 1) · n− j + 16j − 3
16
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j − 1) · (n− j + 1)/(6j − 3)3(n− j + 1)/(6j − 3) + 1
16
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j − 1) · (n− j + 1)/(6j − 3)3(n− j + 1)/(6j − 3) + 1
=3j − 1
3− 6j2 − 5j + 1
3n + 3j.
16
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j − 1) · (n− j + 1)/(6j − 3)3(n− j + 1)/(6j − 3) + 1
=3j − 1
3− 6j2 − 5j + 1
3n + 3j.
Der Maximalgrad ist ∆ = 3j − 3.
16
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j − 1) · (n− j + 1)/(6j − 3)3(n− j + 1)/(6j − 3) + 1
=3j − 1
3− 6j2 − 5j + 1
3n + 3j.
Der Maximalgrad ist ∆ = 3j − 3.
Also gilt
RGr(G) ≥ ∆ + 23− 2∆2/3 + 8∆/3− 3
3n + ∆ + 3
16
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j − 1) · (n− j + 1)/(6j − 3)3(n− j + 1)/(6j − 3) + 1
=3j − 1
3− 6j2 − 5j + 1
3n + 3j.
Der Maximalgrad ist ∆ = 3j − 3.
Also gilt
RGr(G) ≥ ∆ + 23− 2∆2/3 + 8∆/3− 3
3n + ∆ + 3
=∆ + 2
3−O(∆2/n) .
17
Fall 3: Es sei ∆ ≡ 2 mod 3.
17
Fall 3: Es sei ∆ ≡ 2 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj−1 — Kj+1 — Kj — Kj — Kj — Kj .
besteht.
17
Fall 3: Es sei ∆ ≡ 2 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj−1 — Kj+1 — Kj — Kj — Kj — Kj .
besteht.
Jede Clique wird vollstandig mit der nachsten unabhangigen Men-ge verbunden.
17
Fall 3: Es sei ∆ ≡ 2 mod 3.
Konstruiere fur einen Parameter j ≥ 2 einen Graphen, der auseiner Kette von Teilgraphen der Form
Kj−1 — Kj+1 — Kj — Kj — Kj — Kj .
besteht.
Jede Clique wird vollstandig mit der nachsten unabhangigen Men-ge verbunden.
Die unabhangigen Mengen sind – bis auf ein einzelnes maximalesMatching – vollstandig mit der nachsten Clique verbunden.
18
Zwei Teilgraphen werden verbunden, indem die letzte unabhangigeMenge eines Teilgraphen vollstandig mit der ersten Clique desnachsten Teilgraphens verbunden wird.
18
Zwei Teilgraphen werden verbunden, indem die letzte unabhangigeMenge eines Teilgraphen vollstandig mit der ersten Clique desnachsten Teilgraphens verbunden wird.
Die Kette wird mit einer Clique Kj abgeschlossen.
18
Zwei Teilgraphen werden verbunden, indem die letzte unabhangigeMenge eines Teilgraphen vollstandig mit der ersten Clique desnachsten Teilgraphens verbunden wird.
Die Kette wird mit einer Clique Kj abgeschlossen.
Ein vollstandiger Graph aus 2 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
18
Zwei Teilgraphen werden verbunden, indem die letzte unabhangigeMenge eines Teilgraphen vollstandig mit der ersten Clique desnachsten Teilgraphens verbunden wird.
Die Kette wird mit einer Clique Kj abgeschlossen.
Ein vollstandiger Graph aus 2 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
19
Tabelle der Knotengrade:
19
Tabelle der Knotengrade:
KnotengradKnoten der ersten Clique 2j − 1Knoten der abschließenden Clique 2j − 1Knoten aller anderen Cliquen 3j − 1Knoten der letzten unabhangigen Menge 2j
Knoten aller anderen unabhangigen Mengen 2j − 1
20
20
|IGr| = 3 · n− j
6j+ 1
20
|IGr| = 3 · n− j
6j+ 1
|Imax| = (3j + 1) · n− j
6j
21
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j + 1) · (n− j)/(6j)3(n− j)/(6j) + 1
21
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j + 1) · (n− j)/(6j)3(n− j)/(6j) + 1
=3j + 1
3− 6j2 + 2j
3n + 3j.
21
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j + 1) · (n− j)/(6j)3(n− j)/(6j) + 1
=3j + 1
3− 6j2 + 2j
3n + 3j.
Der Maximalgrad ist ∆ = 3j − 1.
21
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j + 1) · (n− j)/(6j)3(n− j)/(6j) + 1
=3j + 1
3− 6j2 + 2j
3n + 3j.
Der Maximalgrad ist ∆ = 3j − 1.
Also gilt
RGr(G) ≥ ∆ + 23− 2∆2/3 + 2∆ + 4/3
3n + ∆ + 1
21
Damit erhalten wir fur die Gute
RGr(G) ≥ (3j + 1) · (n− j)/(6j)3(n− j)/(6j) + 1
=3j + 1
3− 6j2 + 2j
3n + 3j.
Der Maximalgrad ist ∆ = 3j − 1.
Also gilt
RGr(G) ≥ ∆ + 23− 2∆2/3 + 2∆ + 4/3
3n + ∆ + 1
=∆ + 2
3−O(∆2/n) . 2
22
Satz 4 Es gibt Graphen G = (V,E) mit durchschnittlichem Kno-tengrad d, so dass fur die Gute des MIN-Greedy Algorithmus
RGr(G) ≥ d + 22−O(1/d)
gilt.
22
Satz 4 Es gibt Graphen G = (V,E) mit durchschnittlichem Kno-tengrad d, so dass fur die Gute des MIN-Greedy Algorithmus
RGr(G) ≥ d + 22−O(1/d)
gilt.
Beweis: Konstruiere fur einen Parameter j ≥ 2 einen Graphen,der aus einer Kette von Teilgraphen der Form
K1 — Kj
besteht.
22
Satz 4 Es gibt Graphen G = (V,E) mit durchschnittlichem Kno-tengrad d, so dass fur die Gute des MIN-Greedy Algorithmus
RGr(G) ≥ d + 22−O(1/d)
gilt.
Beweis: Konstruiere fur einen Parameter j ≥ 2 einen Graphen,der aus einer Kette von Teilgraphen der Form
K1 — Kj
besteht.
Die Anzahl h der Teilgraphen soll dabei wesentlich großer als derParameter j sein.
23
Die Kette wird mit einer Clique Kj abgeschlossen.
23
Die Kette wird mit einer Clique Kj abgeschlossen.
Die Verbindung der einzelnen Teilgraphen geschieht nun so:
23
Die Kette wird mit einer Clique Kj abgeschlossen.
Die Verbindung der einzelnen Teilgraphen geschieht nun so:
1. Fur die ersten h− j + 1 Teilgraphen gilt:
23
Die Kette wird mit einer Clique Kj abgeschlossen.
Die Verbindung der einzelnen Teilgraphen geschieht nun so:
1. Fur die ersten h− j + 1 Teilgraphen gilt:
Jeder Knoten der j-elementigen unabhangigen Menge eines Teil-graphens wird mit den einzelnen (Cliquen)-Knoten der j−1 nach-folgenden Teilgraphen verbunden.
23
Die Kette wird mit einer Clique Kj abgeschlossen.
Die Verbindung der einzelnen Teilgraphen geschieht nun so:
1. Fur die ersten h− j + 1 Teilgraphen gilt:
Jeder Knoten der j-elementigen unabhangigen Menge eines Teil-graphens wird mit den einzelnen (Cliquen)-Knoten der j−1 nach-folgenden Teilgraphen verbunden.
2. Fur die letzten j − 1 Teilgraphen gilt:
23
Die Kette wird mit einer Clique Kj abgeschlossen.
Die Verbindung der einzelnen Teilgraphen geschieht nun so:
1. Fur die ersten h− j + 1 Teilgraphen gilt:
Jeder Knoten der j-elementigen unabhangigen Menge eines Teil-graphens wird mit den einzelnen (Cliquen)-Knoten der j−1 nach-folgenden Teilgraphen verbunden.
2. Fur die letzten j − 1 Teilgraphen gilt:
Verbinde so weit wie moglich analog zu Punkt 1.
23
Die Kette wird mit einer Clique Kj abgeschlossen.
Die Verbindung der einzelnen Teilgraphen geschieht nun so:
1. Fur die ersten h− j + 1 Teilgraphen gilt:
Jeder Knoten der j-elementigen unabhangigen Menge eines Teil-graphens wird mit den einzelnen (Cliquen)-Knoten der j−1 nach-folgenden Teilgraphen verbunden.
2. Fur die letzten j − 1 Teilgraphen gilt:
Verbinde so weit wie moglich analog zu Punkt 1.
Verbinde die j unabhangigen Knoten des i’ten letzten Teilgraphensdurch j − i paarweise verschiedene Matchings mit den j Knotender letzten Clique.
24
Ein vollstandiger Graph aus 7 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
24
Ein vollstandiger Graph aus 7 Teilgraphen fur den Parameter j = 3hat folgende Gestalt:
25
Tabelle der Knotengrade:
25
Tabelle der Knotengrade:
KnotengradKnoten der ersten Clique K1 j
Knoten aller unabhangigen Mengen Kj j
Knoten der abschließenden Clique Kj (j − 1) +∑j−1
i=1 i
Knoten der i’ten Clique K1 fur i = 2, . . . , j − 1 i · jKnoten aller anderen Cliquen K1 j2
26
26
|IGr| = h + 1
26
|IGr| = h + 1
|Imax| = j · h
27
Die Gute ist also
RGr(G) ≥ h · jh + 1
= j − o(1) .
27
Die Gute ist also
RGr(G) ≥ h · jh + 1
= j − o(1) .
Berechnung des Durchschnittsknotengrades d:
d · n = j · j · h + j ·
((j − 1) +
j−1∑i=1
i
)+
j−1∑i=1
i · j + (h− j + 1) · j2
27
Die Gute ist also
RGr(G) ≥ h · jh + 1
= j − o(1) .
Berechnung des Durchschnittsknotengrades d:
d · n = j · j · h + j ·
((j − 1) +
j−1∑i=1
i
)+
j−1∑i=1
i · j + (h− j + 1) · j2
= h · j2 + j · (j − 1) + j · j · (j − 1) + j2 · (h− j + 1)
27
Die Gute ist also
RGr(G) ≥ h · jh + 1
= j − o(1) .
Berechnung des Durchschnittsknotengrades d:
d · n = j · j · h + j ·
((j − 1) +
j−1∑i=1
i
)+
j−1∑i=1
i · j + (h− j + 1) · j2
= h · j2 + j · (j − 1) + j · j · (j − 1) + j2 · (h− j + 1)
⇐⇒ d =2h · j2 + j2 − j
h · (j + 1) + j
27
Die Gute ist also
RGr(G) ≥ h · jh + 1
= j − o(1) .
Berechnung des Durchschnittsknotengrades d:
d · n = j · j · h + j ·
((j − 1) +
j−1∑i=1
i
)+
j−1∑i=1
i · j + (h− j + 1) · j2
= h · j2 + j · (j − 1) + j · j · (j − 1) + j2 · (h− j + 1)
⇐⇒ d =2h · j2 + j2 − j
h · (j + 1) + j
= 2j − 2 +2
j + 1− o(1) .
28
Nach j umstellen:
28
Nach j umstellen:
j ≥ d + 22− 1
j + 1
28
Nach j umstellen:
j ≥ d + 22− 1
j + 1
≥ d + 22− 2
d + 2
28
Nach j umstellen:
j ≥ d + 22− 1
j + 1
≥ d + 22− 2
d + 2
=d + 2
2−O(1/d) .
28
Nach j umstellen:
j ≥ d + 22− 1
j + 1
≥ d + 22− 2
d + 2
=d + 2
2−O(1/d) .
Damit gilt
RGr(G) ≥ d + 22−O(1/d) .
2
29
Literatur
[1] M. M. Halldorsson und J. Radhakrishnan, Greed is Good: Appro-
ximating Independent Sets in Sparse and Bounded-degree Graphs,
Proc. Twenty-Sixth Annual ACM Symp. on the Theory of Com-
puting, Canada, 439-448, 1994.
[2] M. M. Halldorsson und J. Radhakrishnan, Greed is Good: Appro-
ximating Independent Sets in Sparse and Bounded-degree Graphs,
Algorithmica, Springer Verlag, New York, 145-163, 1997.
Recommended