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

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert