Testbeispiele

zurück zu Allgemeines

Testbeispiele

1 a) Wie ist die Isomorphie zwischen zwei Graphen definiert?

A: Eine bijektive Abbildung von V1 auf V2 heißt Isomorphismus von X1 auf X2, wenn gilt:

[x,y] ⇔ [ρ(x), ρ(y)] ∈ E2

Untersuchen sie folgenden Graphen paarweise auf Isomorphie.

Existiert zwischen zwei Graphen ein Isomorphismus, so geben Sie diesen an, andernfalls formulieren Sie eine Begründung, warum kein Isomorph ismus existiert.

A: Der Knoten 3 weist Grad 5 auf, weshalb der 1. und der zweite bzw. der 1. und der 3. Graph nicht isomorph sind.

Der 3. und 4. Graph kann auch nicht isomorph sein da die Anzahl der Knoten gleichen Grades unterschiedlich ist.

2) Gegeben sind die beiden Graphen X und Y:

X: V(X) = {1,2,3,4,5,6,7,8}          E(X) = {[x,y]| y teilt x}

X: V(Y) = 1,3,4,5}                      E(Y) = {[x,y] y größer x}

a)     Zeichnen sie die beiden Graphen und bilden Sie deren Vereinigung und Durchschnitt.

b)     Das Komplement Zc eines Graphen ist wie folgt definiert:

V(Zc) = V(Z)

E(Zc) = {[x,y] | x ¹ y, [x,y] Î E(Z)}

Stelle das Komplement des Graphen X dar.

 

3) Bestimmen Sie (algorithmisch) alle Blöcke, Artikulationen und Brücken des Graphen X.

Bestimmen Sie den durchmesser der von K(4) aufgespannten Komponente von X und skizzieren Sie außerdem alle Teilgraphen von X – {5,6,7,8,9,10,11,12,13,14}.

nach oben

(429)

Graphentheoretische Algorithmen

zurück zu Allgemeines

1      Graphentheoretische Algorithmen

1.1  Algorithmus zur Konstruktion eines maximalen Matchings

Matching maximal Û es existiert kein erweiterter alternierender Weg.

Initialisierung:

Step1: Aufnahme von paarweise disjunkten Kanten in einer Menge M (soviele wie möglich).

i=0, Mo = M;

Iteration:

Step2: Gibt es einen erweiterten alternierenden Weg W des Matchings Mi, dan ist Mi+1 =

(Mi-W) È (W-Mi) (= Mi D  W).

goto Step 3

Gibt es keinen alternierenden Weg, so gogo Step 4.

Step3:  i=i+1, goto Step2

Abschluß:

Step4: Mi ist das maximale matching.

 

1.2  Algorithmus zur Untersuchung eines gerichteten Graphen auf Azyklizität

G azyklisch -> $ x mit d+(x) = 0

Algorithmus:

Step1: Wir markieren alle Punkte x mit d+(x) =0 mit der Marke +.

Step2: jeder Punkt mit der Eigenschaft, daß alle seine Nachfolger mit + markiert sind, wird auch mit + markiert. Step 2 wird so oft wiederholt, als neue Punkte markiert werden.

Step3. Tritt keine neue Marke auf:

Sind alle Punkte markiert, so ist der Graph G azyklisch.

Gibt es nicht markierte Punkte, so enthält der Graph G einen Zyklus.

Beispiel:

 

 

 

 

 

 

 

 

Azyklisch da alle Punkte markiert sind: 5+ 4+ 3+ 2+ 1+

 

 

 

 

 

 

 

 

 

nicht azyklixh, da nicht alle Punkte markiert sind: 4+

 

Weiterer Algorithmus für dieses Problem:

Streichen von Kanten, die in keinem Zyklus liegen. Kanten <x,y> mit d+(y) =0.

Step1: Kante <x,y> mit d+(y) = 0 wird gestrichen, solange noch Kanten gestrichen werden können.

Step 2: Es kann keine Kante mehr gestrichen werden:

a) keine Kante mehr vorhanden -> G ist azyklisch

b) es gibt noch Kanten -> G ist nicht azyklisch

 

Beispiel:

 

 

5

 

 

 

 

 

 

 

 

 

 

azyklisch, da alle Kanten gestrichen sind;

 

 

1.3   Algorithmus zur Bestimmung der Komponenten des starken Zusammenhangs

xo fest ausgewählt:

+ Markierung bekommen jene Knoten, die von x0 aus erreichbar sind

Markierung bekommen jene Knoten, von dennen x0 aus erreichbar ist

Step1: x0 beliebig auswählen (Komponente von x0 wird bestimmt)

x0 wird mit + und –  markiert

IND:= 0 (=Indikator, soll angeben, ob überhaupt in einem Durchlauf ein Knoten markiert worden ist)

Step2: Für alle x e V(X) wird untersucht, ob überhaupt ein Nachfolger – oder Vorgänger makiert worden ist.

Wir durchlaufen alle Kanten <x,y>:

a)     x wird + markiert. Ist y nicht mit + markiert, dann wird y mit + markiert, IND := 1.

b)     y wird mit – markeirt. Ist x nicht mit – markiert, dann wird x mit – markiert, IND:=1.

Step3:

Ist IND = 1, so IND:=0 and goto Step2.

Ist IND = 0, dann gehören zur Komponente von X genau jene Knoten, die mit + und mit – markiert sind.

Komponentennummer 1

Zur Bestimmung der übrigen Komponenten werden neue x0 –Algorithmen durchgeführt. Sind beim 1. Durchlauf alle Knoten mit + oder – markiert, dann ist der Graph G stark zusammenhängend.

 

1.4  Algorithmus zur Bestimmung des reduzierten Graphen

zunächst ein Algorithmus zur Bestimmung der Komponentennummer (KNR). KNR von x ist k(x).

V(GR) = {K1, ….Kr}

Bestimmung dr Knaten von GR.

Wir durchlaufen alle kanten <x,y> des Grqphen G.

Ist k(x) = k(y) -> nächste Kante untersuchen.

Ist k(x) ¹ k(y) -> <Kk(x), Kk(y)> e E(GR)

Netzwerke:

G = (V,E) gerichter, ungerichtete oder gemischte Graphen mit Kantenbewertungen.

b(<x,y>) = b(x,y)eR+

z.B. : Straßennetz : b(x,y) = Länge der Strecke <x,y>

oder Telefonnetz: b(x,y)= Kosten des Baus der „Strecke“  <x,y> (richtungsunabhängig)

typische Problemstellung zum Beispiel: kürzester Weg zwischen zwei Knoten a und b

 

1.5  Algorithmus zur Bestimmung des kürzesten Weges von einem Startknoten a zu allen übrigen Knoten x (MOORE)

G zusammenhängend, wenn mehrere kürzeste Wege zwischen a und b existieren, so wählen wir einen aus. Wenn eine Bahn existiert, so gibt es eine kürzeste. Der Algorithmus liefert eine kürzeste kantenfolge von a nach b.

Voraussetzung.

Es gibt keinen Zyklus mit negativer Bewertung (Bewertung eines Zyklus = S der Bewertung der Kanten) dies ist sicher erfüllt wenn b(x,y) eR+)

l(x) = die Länge des bisher gefundenen kürzesten Weges (am Ende: Länge des kürzesten Weges von a nach x)

V(x) = Vorgänger auf diesem Weg

s(x) =  Anzahl der Kanten in dem bisher kantenreichsten Weg

Step1: Anzs:= 0, l(a) := 0, V(a):=0, s(a):=0 für x ¹ a: l(x) := ¥, V(x) := ¥, s(x):= ¥

Step2: IND:= 0, Durchlaufen aller Punkte x des Graphen

2a) Ist s(x) = Anzs, so durchlaufen wir alle Kanten <x,y>.

2aa) Ist l(y) =< l(x) + b(x,y),

der bisher gefundene Weg ist nicht schlechter als der neue, goto Step2a

2ab) Ist l(x) > l(x) + b(x,y), dann wird

l(y):= l(x) + b(x,y),

V(y) := x

s(y) := Anzs +1

IND := 1, goto Step 2a

2b) Ist IND = 0, dann Ende erreicht.

l(b) = Abstand von a nach b = d(a,b).

Ist IND = 1, dann ist Anzs:= Anzs + 1, gogo Step 2

 

Typische Problemstellung zum 2. Beispiel . Legen von Leitungen mit minimalen Gesmtkosten. Jeder Knoten ist mit jedem verbunden. Vorraussetzung. G ist zusammenhängend, gesuchter Teilgraph = spanndender Baum mit minimaler Bewertung, B(T) =

 

 

1.6  Algorithmus zur bestimmung des minimalsten spannen den Baums (Algorithmus von Kruskal)

Step1: mark(x) = 0 für alle x e V(G), KNR:=0

Step2. kanten nach Bewertung aufsteigend sortieren

Step3: Durchlaufen der Kanten in dieser Reihenfolge <x,y>

Fall 1:) mark(x) = mark(y)

1a) mark(x) = 0, KNR:= KNR+1

     mark(x) := mark(y) := KNR, <x,y> e E(T)

1b) mark(x) ¹ 0 (Kante erzeugt Kreis) goto next Kante

Fall 2: mark(x) ¹ mark(y)

2a) mark(x) = 0, so <x,y > e E(T) und mark(x):= mark(y)

2b) mark(y) = 0, so <x,y > e E(T) und mark(y):= mark(x)

2a) mark(x) ¹ 0 und mark(y) ¹ 0, so wird <x,y > e E(T) bei allen z mit mark(z) = mark(y) wird mark(z):= mark(x)

Step 4: minimales Gerüst gefunden; ist G nicht zusammenhängend, so ist das minimale Gerüst ein Wald und die verschiedenen Komponenten sind durch verschiedene Werte von mark(x) gekennzeichnet.

 

Exzentrizität klären und bei Beispiel dazuschreiben

was ist d+ bei der def. des 2. Algorithmus bzw. der Azyklizität

(264)

Allgemeines und Ergänzungen

zurück zu Allgemeines

Allgemeines

Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht. Viele algorithmische Probleme können auf Graphen zurückgeführt werden können und andererseits werden die Lösung graphentheoretischer Probleme oft in Algorithmen umgesetzt, ist die Graphentheorie auch in der Informatik, insbesondere der Komplexitätstheorie und in der Netzwerktheorie von großer Bedeutung.

Ein Graph ist eine Menge von Punkten (Knoten oder Ecken), die durch Linien (Kanten bzw. Bögen) miteinander verbunden sein können. Prinzipiell unterscheidet man in:

  • endlichen Graphen, bei denen die Menge der Knoten und Kanten endlich ist
  • unendlichen Graphen
  • gerichteten Graphen, bei denen die Kanten gerichtet sein können (dargestellt durch Pfeile statt Linien)
  • ungerichteten Graphen

Komplexere Graphen sind z.B.: Multigraphen, bei denen im Gegensatz zu einfachen Graphen Kanten zwischen den Knoten mehrfach vorkommen dürfen und Hypergraphen, bei denen im Gegensatz zu einfachen Graphen Kanten mehr als nur zwei Knoten verbinden können. Knoten und Kanten können auch mit Farben oder Gewichten versehen werden (knoten- bzw. kantengefärbte oder -gewichtete Graphen).

Ergänzungen

Unter 3 Isomorphie wird die Darstellung in einer Adjazenzmatrix ausgeführt. Eine Alternative dazu wäre die Adjazenzlistendarstellung, wobei für jeden Knoten alle adjazenten Knoten in einer linearen Liste gespeichert werden. Diese ist geeignet, für Graphen mit wenigen Kanten. Linearer Speicheraufwand – gut; dfs gut, Rechenaufwand O(|V|+|E|); nicht geeignet zur Überprüfung von Adjazenzeigenschaften.

(316)

14 Bäume

zurück zu Grundbegriffe II

14 Bäume

Bäume sind zusammenhängend und kreislos (ungerichtet) bzw. zyklusfrei (gerichtet).

Ein Wald ist nichtzusammenhängend und kreislos. Wald bereits ab zwei Bäumen; Man unterscheidet. binäre Bäume, Wurzelbäume u.a. Ein Gerüst ist ein spannender Teilbaum.

Wurzel
Äste
Blätter

X=(V,E)
|V| = n(α0(x))
|E| = m(a1(x))

Matrix-Baum-Theorem (Kirchhoff)

A(x)
D(x) dij = {i ≠ j → 0 und i = j → d(i)}

Zeilen oder Spaltensumme &grarr; Grad

M(x) = D(x) -A(x)

M(inor)B = Matrix die aus n(x) hervorgeht durch Streichen der i-ten Zeile und Spalte (wobei i beliebig ist).

Determinante det(B) = Anzahl der Gerüste.

A(x)=

0 1 1 0
1 0 1 0
1 1 0 1
0 0 1 0

Grad ist Zeilensumme.

D(x)=

2 0 0 0
0 2 0 0
0 0 3 0
0 0 0 1

äquivalente Aussagen:

  1. X = Baum
  2. je 2 Knoten (X) sind durch genau 1 Weg verbunden
  3. X = zusammenhangend und jeder Konten von X ist eine Brücke
  4. X ist zusammenhängend und m = n-1
  5. X besitzt keinen Kreis und es gilt m=n-1
  6. X besitzt keinen Kreis, verbindet man aber2 Knoten von V(X) die in X nicht verbunden sind durch eine Kante (hinzufügeneiner Kante), so erhält man einen #Graph mit genau einem Kreis

Ein Baum besitzt mindestens zwei Endknoten wenn (2 = < |V|)

14.1 Wurzelbäume

Jeder Knoten ist entweder ein Endknoten oder eine Artikulation.

14.2 Binärer Baum

Für alle Knoten gilt D = 1 oder 3 und ein Knoten D(2).

Die Anzahl der Knoten ist immer ungerade, da |V| ungeraden Grades = gerade + Wurzel.

Endknoten = D(1)
n+1/2 Endknoten und
n-1/2 innere Knoten

14.2.1 Niveau eines Knoten

n(x) = d(w,x)

[Achtung d mit einem Parameter steht für degree (Knotengrad) und d mit zwei Parameter für distance (Abstand)]

k = Niveaustufe; entspricht.

Die Bezeichnen die Knoten mit x für den obersten Knoten, der am Niveau 0 liegt, x1 und x2 liegen am Niveau 1 und die weiteren Knoten x3 bis xr liegen am Niveau 3. Die maximale Anzahl an Knoten auf einem Niveau beträgt 2k H(x) = max n(x)

∈ V(x)
Balance für innere Knoten
b(alancd) (x) =|H(Tl(x)) -H(Tr(x))

Tl = Teilbaum links

Für einen balancierten bzw. ausgeglichenen Baum gilt:

^(d(x)>=2 → b (x) = <1)
x ∈ V(x)

14.2.2 Exzentrizität

e(x) = max d(x,y)mit y ∈ V(x)

V(x) – min e(x) (kleinste vorkommende Exzentrizität)
mit x ∈ V(x)

Zentraler Knoten e(x) = -(X)
Zentrum X
Z(X) = {x| + (x) = v(x)}

Binärer Baum -> 1 oder 2 Zentren;

das Zentrum verschiebt sich von der Wurzel mit dem Niveauunterschied >= 2;

gerader Niveauunterschied -> 1 Zentrum

ungerader Niveauunterschied -> 2 Zentren

14.2.3 Gerüst

(spannender Teilbaum)
Jeder zusammenhängender Graph besitzt zumindest 1 Gerüst (Matrix-Baum-Theorem)

Minimalgerüst:

3 Blöcke

x {B1 ….Bn} 5 über 3 = 5!/3!2!=10

Wege ohne Kreise je Block:
3 * 1 * 8 = 24 -> Minimalgerüst = 25?
Minimalgerüst: n-1 Kanten -kein Kreis ?

bewerteter Graph – > Kanten werden gewichtet z.B. bei einem Netzwerk;

f: E(x) ->R+ d.h. jeder Kante wird eine reele Zahl zugeordnet;

(a,b)
(b,c)
(c,d)
(a,e)

nach oben

(336)

13 Matrizen

zurück zu Grundbegriffe II

13 Matrizen

13.1 Matrizen bei ungerichteten Graphen

13.1.1 Einfacher ungerichteter Graph

Ein einfacher ungerichteter Graph besteht aus:

  • V(X) = {1,2,3,4,…….α0}
  • E(X) = {(i,j)/i≠j}

α0 = Anzahl der Knoten eines Graph
α1 = Anzahl der Kanten eines Graph.
Zum Beispiel:

aij ist „1“ wenn eine Kante von j nach j führt, sonst „0“ mit (i,j) ∈E(X)

Adjazenzenmatrix (bei Nummerierung im Uhrzeigersinn):

1 2 3 4
1 1 1 0
2 1 1 1
3 0 1 1
4 0 1 1

V-V-Matrix = Konoten-Knoten-Matrix = Adjazenzenmatrix

Graph mit 4 Blöcken ohne Brücken und ohne Artikulationen?
Die 4 Blöcke dürfen nicht zusammenhängend sein. Z.B.: 4 Blöcke als Dreiecke

13.2 Netzwerke

Innerhalb einer Firma kann ein Intranet installiert sein, wenn das Netz aber nicht als LAN konzipiert werden kann, durch bauliche Trennung der Clients, muß das Internet als Übertragungsmittel verwendet werden. Man spricht dann von einem Extranet, welches 2 od. mehrere Intranet miteinander über das Internet verbindet.

13.2.1 Extranet als Graph dargestellt

Die 2 dargestellten Intranets fungieren zusammen als Extranet, welche über das Internet verbunden sind. Die jeweiligen Router adressieren nicht nur die Nachrichtenpakete, sondern fungieren auch als Firewall gegen Zutritt nichtberechtigter User aus dem Internet, der Webserver steht außerhalb der Firewall, da dieser freizugänglich sein soll. Mithilfe der Firewall kann auch der Weg ins Internet für die Mitarbeiter geregelt werden, so dass man nur innerhalb des Extranet bzw. auch nur innerhalb des eigenen Intranets berechtigt ist Daten zu senden.

nach oben

 

(308)