zurück zu Grundbegriffe II

12. Stabile Mengen

• In einem Graphen X heißt eine Teilmenge W ⊂ V(X) innen stabil, wenn keine zwei ihrer Knoten adjazent sind.
• Eine Knotenmenge W heißt maximal innen stabilgenau dann, wenn eine der folgenden Bedingungen erfüllt ist:
  • Kein Knoten x ∈ V(X) kann zu W hinzugefügt werden, ohne die innere Stabilität aufzuheben.
  • Alle Knoten der Differenzenmenge V(X)W haben mindestens einen unmittelbaren Nachbarn in W.

Die größte Anzahl von Knoten aller maximal innen stabilen Mengen gibt den Koeffizienten der inneren Stabilität (innerer Stabilitätskoeffizient) α(X) an.

12.1 Bestimmung der inneren stabilen Mengen

1. Wir ordnen jeden Knoten x_i eine Boolesche Variable i zu.
2. Für alle Knoten x_i ∈ V(X) Bildung des Booleschen Ausdrucks i + j.k.l…(j, k und l sind die Boolschen Variablen aller Knoten die mit x_i adajazent sind)
   Beispiel: 1 + 2 * 4 * 5 ⇔ 1 ∨ 2 ∧ 4 ∧ 5 mit + … ∨ ist logische Summe und * … ∧ ist logisches Produkt
3. Bildung des logischen Produkts aller Ausdrücke von Punkt 2
   (1 + 2 * 4 * 5)(2 + 1 * 3 * 5)(3 + 2 * 5 * 6)(4 + 1 * 5)(5 + 1 * 2 * 4)
4. Äquivalenzumformung des so erhaltenen Ausdrucks mit Hilfe des Distributiv-, Absorptions- und Idempotenzgesetzes).
   Distributivgesetz:
   a ∨ (b ∧ c) ⇔ (a ∨ b) ∧ (a ∨ c)
   a ∧ (b ∨ c) ⇔ (a ∧ b) ∨ (a ∧ c)
   Verschmelzungs- oder Absorbtionsgesetz:
   a ∧ (a ∨ b) ⇔ a oder a ∨ (a ∧ b) ⇔ a
   Entsprechung: ∧ …. ∩ und ∨ ….. ∪
   Idempotenz: a ∨ a ⇔ a bzw. a ∨ a ⇔ a
5. Ist keine Vereinfachung mehr möglich, so besteht der Boolesche Ausdruck aus einer logischen Summe logischer Produkte (DNF = Disjunktive Normalform).
6. Jedes logische Produkt stellt eine Knotenmenge dar, deren Komplement in bezug auf die Knotenmenge des Graphen eine maximal innen stabile Knotenmenge ist.

Beispiel:

Nenne einige innen stabile Mengen.

{[2, 4, 6]}
{[1, 6]}, {[2,6]}, {[2, 4]}
{[3, 4]}, {[3, 1]}, {[4, 6]}
{1}, {2}, {3}, {4}, {5}, {6}

Algorithmus:
(1 + 2 * 4 * 5) (2 + 1 * 3 * 5) (3 + 2 * 5 * 6) (4 + 1 * 5) (5 + 1 * 2 * 3 * 4 * 6) (6 + 3 * 5)

(1 + 2 4 5) (2 + 1 3 5)

Damen auf Schachbrett –> dürfen sich nicht bedrohen

	X
			X
X
		X

hier α(x) = 4 aber 8 Damen → 64 Felder → 92 Lösungen; α(x)=8

Man muss eine Knotenmenge finden, in der die Knoten paarweise untereinander nicht adjazent sind; daraus muss man die größtmögliche heraussuchen –> stabilen Mengen

			X
X
				X
							X
					X
		X
						X
		X

{2,4} max {1}
{1,3} max {2}
{1,6} max {3}
{2,6} max {4}
{2,4,6} max {5} max
{3,4} max {6}
{4,6}

α(x) = 3

12.1.1 Genauere Vorgangsweise bei der Bestimmung der innenstabilen Menge

ad 1) Zuordnung: Knoten x_i ⇐ i Boolesche Variable
i+j*k*l*K
mit x_i adjazent

Idempotenz: a∧a⇔a und a∨a⇔a

(1+245)(2+135)(3+256)(4+15)(5+12346)(6+35)

+K∨ *;∧ (1∨2∧4∧5)∧(2∨1∧3∧5)K

(a+bx)(b+ay) ⇔ (a+bx)(b+y)
ab+ay+bx+abxy ⇔ ab+ay+bx+bxy
(der kürzere Ausdruck kommt im längeren vor → längere streichen)
aay ⇔ ay
a∧a∧y⇔a∧y

(1+245)(2+35)(3+56)(4+5)(5+6)

Adjazenzmatrix:
Adjazenzen für alle Verbindungen zw. den Knoten

Knoten-Knoten-(0,1)-Matrix

McCarthy-Schreibweise
a_ij([i,j]∈E(x) →1, sonst → 0)
symmetrische Matrix, weil der Graph ungerichtet ist.

	1	2	3	4	5	6
1	–	1	0	1	1	0
2		–	1	0	1	0
3			–	0	1	1
4				–	1	0
5					–	1
6						–

a∨(a∧b)⇔a
(3,4,5,6)∪(3,5)

(1+245)(2+35)(3+56)(4+5)(5+6)
(1+245)(23+256+35+356)(45+46+5+56)
12346 + 1256 + 135 + 23456 + 2456 + 2345

{5} {3,4} {2,4,6} {1,3} {1,6} ∀ (x)=3

diese 5 Mengen sind alle maximal innen stabile Mengen.

Beispiel: Seminarorganisation

Es ist ein Seminar zu organisieren, dass aus 8 eintägigen Einzelveranstaltungen besteht.

Das Organisationskomitee möchte jeden Teilnehmer die Möglichkeit geben an allen Veranstaltungen teilzunehmen, zu denen er sich anmeldet.
Nach Ende der Anmeldefrist ergibt sich folgende Situation:

Anmeldungen
Teilnehmer	Veranstaltungen
A	4,6,8
B	1,5
C	3,5
D	6,7
E	3
F	2,6
G	4,5,6
H	1,7
I	2,3
J	5,6
K	1,2
L	2,4,6
M	4,5

	1	2	3	4	5	6	7	8
1	–	1	0	0	1	0	1	0
2		–	1	1	0	1	0	0
3			–	0	1	0	0	0
4				–	1	1	0	1
5					–	1	0	0
6						–	1	1
7							–	0
8								–

(1+257)(2+346)(3+5)(4+568)(5+6)(6+78)
(12+1346+257)(35+36+5)(46+478+568)
(12+1346+257)(346+34678+3568+456+4578+568)
12346 + 12456 + 124578 + 12568 + 1346 + 13456 + 1345678 + 134568
234567 + 24567 + 24578 + 25678
{3,7,8} {1,3,8}
{3,4,7} {1,3,6} für alle Möglichkeiten; man kann beliebige Auswahl treffen
{2,5,7,8} {1,3,4}
in 2 Tagen geht- nicht! min. 3 Tage:
{2,5,7,8}
{1,3,6}
{3,4,7}

12.2 Euler’she Linie

Typische Problemstellung:
Die Müllabfuhr muss bei jedem Haus vorbeifahren (Häuser stehen an den Kanten). Für alle gilt man muß alle Kanten befahren

Definition: geschlossene Euler’sche Linie = geschlossener Kantenzug, der jede Kante des Graphen genau 1 x enthält.

Ein Graph mit einer Euler’schen Linie heißt Euler’scher Graph

Ein zusammenhängender Graph hat genau dann eine Euler’sche Linie, wenn jeder Knoten geraden Grad hat.

Offene Euler’sche Linie:
offener Kantenzug, der jede Kante genau 1 x enthält, wenn es genau 2 Knoten ungeraden Grades gibt

einer davon ist der Startknoten, der andere der Endknoten
(Euler’scher Graph, nur bei geschl Euler’scher Linie)

12.3 Hamilton’sche Linie

Typische Problemstellung:
Das “Vertreterproblem”:
Zentrallager – an verschiedene Filialen ausliefern, auf kürzestem Weg alle Knoten abfahren.

Das führt zu einem Kreis, der jeden Knoten genau 1 x enthält.

Knoten stehen für Filialen und
Kanten für Straßen

Hamilton’scher Graph ist gegeben, wenn eine Hamilton’sche Linie existiert

d(x) muß 2 sein
∀ dæ(X)< 2 hätten wir eine offene Hamilton’sche Linie = Weg, der jeden Knoten genau 1 x enthält

Algorithmus:
(1 + 2 * 4 * 5) (2 + 1 * 3 * 5) (3 + 2 * 5 * 6) (4 + 1 * 5) (5 + 1 * 2 * 3 * 4 * 6) (6 + 3 * 5)
(1 + 2 4 5), (2 + 1 3 5)
1 → a, 2 → b, 4 und 5 → x, 2 →b, 1 → a, 3 und 5 → y
(a+ b x) (b + a y)

(a + bx)(b +ay) ⇔ (a + bx)(b+y) → nach dem Distributivgesetz: a∧a∧y
Frage: ab+ a a y + b b x + abxy ⇔ ab + ay + bbx + bxy
Antwort: JA, weil:
ab + aax + bbx + abxy ⇔ ab + ay + bbx + bxy

Streichung von aa und xy sowie bbx
p∨ (p∧q) = p (Streichung p∧q
p∧(p∨q) = p (streichen von (p∨q)

Betrachtungsweise mittels Mengen:

A ∪ (A ∩ B)
(1 + 2 4 5)(2 + 1 3 5)(3 + 2 5 6)(4 + 1 5)(5 + 1 2 3 4 6)(6 + 3 5)

Adajazenzmatrix:

	1	2	3	4	5	6
1		1		1	1
2	1		1		1
3		1			1	1
4	1				1
5	1	1	1	1		1
6			1		1

(1 + 2 4 5) (2 + 3 5) (3 + 5 6) (4 + 5) (5 + 6)

weiter distribuieren:

(1 2 + 1 3 5 + 2 4 5) (3 + 5 6) (4 5 + 4 6 + 5 + 5 6)
(1 2 + 1 3 5 + 2 4 5) (3 4 6 + 3 5 + 4 5 6 + 5 6)
1 2 3 4 6 + 1 2 3 5 + 1 2 5 6 + 1 3 4 5 6 + 1 3 5 + 1 3 5 6 + 2 3 4 5 6 + 2 3 4 5 + 2 4 5 6

DNF: (1 2 3 4 5) ∨ (1 2 5 6) ∨ (1 3 5) ∨ (2 3 4 5) ∨ (2 4 5 6)

Komplement:

W = { 5 }
W = {[3,5]}
W = {[2,4,6]}
W = {[1,6]}
W = {[1,3]}
alle innen stabile Mengen des Graphen (Anzahl der stabilen Mengen)

Innerer Stabilitätskoeffizient: α(X) = 3 wegen W={[2,4,6]}

nach oben