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:
- X = Baum
- je 2 Knoten (X) sind durch genau 1 Weg verbunden
- X = zusammenhangend und jeder Konten von X ist eine Brücke
- X ist zusammenhängend und m = n-1
- X besitzt keinen Kreis und es gilt m=n-1
- 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)