Outline Relationen Graphen
Studientag zur Algorithmischen MathematikRelationen und Graphen
Winfried Hochstättler
Diskrete Mathematik und OptimierungFernUniversität in Hagen
21. Mai 2011
Outline Relationen Graphen
Outline
RelationenÄquivalenzrelationen und Partialordnungen
GraphenGraphenisomorphieCodierung von GraphenValenzsequenzen
Outline Relationen Graphen
Relationen
Kartesisches ProduktSeien M und N Mengen. Das Kartesische Produkt von M und N istdie Menge aller geordeneten Tupel
M × N = {(m, n) | m ∈ M, n ∈ N}.
RelationenEine (binäre) Relation R ist eine Teilmenge des KartesischenProduktes R ⊆ M × N. An Stelle von (m, n) ∈ R schreiben wir auchmRn oder m ∼ n und sagen, m steht in Relation mit n.Die Linksklasse eines Elementes x ∈ M ist definiert als
[x ]l := {y ∈ N | xRy}.
Outline Relationen Graphen
Relationen
Kartesisches ProduktSeien M und N Mengen. Das Kartesische Produkt von M und N istdie Menge aller geordeneten Tupel
M × N = {(m, n) | m ∈ M, n ∈ N}.
RelationenEine (binäre) Relation R ist eine Teilmenge des KartesischenProduktes R ⊆ M × N. An Stelle von (m, n) ∈ R schreiben wir auchmRn oder m ∼ n und sagen, m steht in Relation mit n.
Die Linksklasse eines Elementes x ∈ M ist definiert als
[x ]l := {y ∈ N | xRy}.
Outline Relationen Graphen
Relationen
Kartesisches ProduktSeien M und N Mengen. Das Kartesische Produkt von M und N istdie Menge aller geordeneten Tupel
M × N = {(m, n) | m ∈ M, n ∈ N}.
RelationenEine (binäre) Relation R ist eine Teilmenge des KartesischenProduktes R ⊆ M × N. An Stelle von (m, n) ∈ R schreiben wir auchmRn oder m ∼ n und sagen, m steht in Relation mit n.Die Linksklasse eines Elementes x ∈ M ist definiert als
[x ]l := {y ∈ N | xRy}.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie ist
ÄP1: reflexiv, wenn ∀x ∈ M : xRxÄ2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation. Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie istÄP1: reflexiv, wenn ∀x ∈ M : xRx
Ä2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation. Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie istÄP1: reflexiv, wenn ∀x ∈ M : xRx
Ä2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation. Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie istÄP1: reflexiv, wenn ∀x ∈ M : xRx
Ä2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation. Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie istÄP1: reflexiv, wenn ∀x ∈ M : xRx
Ä2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation. Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie istÄP1: reflexiv, wenn ∀x ∈ M : xRx
Ä2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation.
Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie istÄP1: reflexiv, wenn ∀x ∈ M : xRx
Ä2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation. Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenzrelationen und Partialordnungen
Eine Relation R ⊆ M ×M heißt Relation auf M. Sie istÄP1: reflexiv, wenn ∀x ∈ M : xRx
Ä2: symmetrisch, wenn ∀x , y ∈ M : (xRy ⇒ yRx)
P2: antisymmetrisch, wenn∀x , y ∈ M : (xRy und yRx ⇒ x = y)
ÄP3: transitiv, wenn ∀x , y , z ∈ M : (xRy und yRz ⇒ xRz)
Eine reflexive, symmetrische und transitive Relation heißtÄquivalenzrelation. Eine reflexive, antisymmetrische und transitiveRelation heißt Partialordnung.
Die Linksklassen einer Äquivalenzrelation nennen wir auchÄquivalenzklassen.
Outline Relationen Graphen
Äquivalenklassen
BeispielWir betrachten die Relation auf Z
yRz :⇐⇒ y − z ist gerade.
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Outline Relationen Graphen
Äquivalenklassen
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Outline Relationen Graphen
Äquivalenklassen
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Beweis.Wegen x ∈ [x ] ist jedes Element in mindestens einerÄquivalenzklasse enthalten. Wir müssen also zeigen, dass dieÄquivalenklassen zweier Elemente entweder gleich oder disjunktsind.
Outline Relationen Graphen
Äquivalenklassen
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Beweis.zu zeigen: [x ] ∩ [y ] 6= ∅ ⇒ [x ] = [y ].
Outline Relationen Graphen
Äquivalenklassen
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Beweis.zu zeigen: [x ] ∩ [y ] 6= ∅ ⇒ [x ] = [y ].Sei t ∈ [x ] ∩ [y ]⇒ xRt und yRt
Outline Relationen Graphen
Äquivalenklassen
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Beweis.zu zeigen: [x ] ∩ [y ] 6= ∅ ⇒ [x ] = [y ].Sei t ∈ [x ] ∩ [y ]⇒ xRt und yRtÄ2⇒ xRt und tRy ÄP3⇒ xRy ÄP3⇒ [y ] ⊆ [x ].
Outline Relationen Graphen
Äquivalenklassen
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Beweis.zu zeigen: [x ] ∩ [y ] 6= ∅ ⇒ [x ] = [y ].Sei t ∈ [x ] ∩ [y ]⇒ xRt und yRtÄ2⇒ xRt und tRy ÄP3⇒ xRy ÄP3⇒ [y ] ⊆ [x ]. Ganz symmetrisch folgt[x ] ⊆ [y ] und somit [x ] = [y ].
Outline Relationen Graphen
Äquivalenklassen
BeispielWir betrachten die Relation auf Z
yRz :⇐⇒ y − z ist gerade.
PropositionDie Äquivalenzklassen partitionieren die Grundmenge.
Im Beispiel haben wir zwei Äquivalenzklasse, die geraden und dieungeraden Zahlen.
Outline Relationen Graphen
Partialordnungen
BeispielSei S eine Menge. Dann erklären wir auf 2S die Partialordnung ≤vermöge
A ≤ B :⇐⇒ A ⊆ B.
Outline Relationen Graphen
Partialordnungen
BeispielSei S eine Menge. Dann erklären wir auf 2S die Partialordnung ≤vermöge
A ≤ B :⇐⇒ A ⊆ B.
94
8
5
2
7
{1, 2, 3}
{4}{3}{2}{1}
∅1
12
6 10
11
{1, 2, 3, 4}
{2, 3, 4}
3
Outline Relationen Graphen
Graphen
Eine Relation R auf V heißt irreflexiv, wenn ∀v ∈ V : (¬vRv).
Einesymmetrische, irreflexive Relation nennen wir Graph. Gilt uRv , sonennen wir {u, v} eine Kante von G. Wir schreiben G = (V , E) undauch (u, v) statt {u, v}.Einige Begriffe
Wege:P3 P4 P5
Kreise: C3 C4 C5
Spaziergänge: (v0e1v1e2, v2, . . . , vn−1, en, vn) mit ei = (vi−1, vi).
Outline Relationen Graphen
Graphen
Eine Relation R auf V heißt irreflexiv, wenn ∀v ∈ V : (¬vRv). Einesymmetrische, irreflexive Relation nennen wir Graph.
Gilt uRv , sonennen wir {u, v} eine Kante von G. Wir schreiben G = (V , E) undauch (u, v) statt {u, v}.Einige Begriffe
Wege:P3 P4 P5
Kreise: C3 C4 C5
Spaziergänge: (v0e1v1e2, v2, . . . , vn−1, en, vn) mit ei = (vi−1, vi).
Outline Relationen Graphen
Graphen
Eine Relation R auf V heißt irreflexiv, wenn ∀v ∈ V : (¬vRv). Einesymmetrische, irreflexive Relation nennen wir Graph. Gilt uRv , sonennen wir {u, v} eine Kante von G. Wir schreiben G = (V , E) undauch (u, v) statt {u, v}.
Einige Begriffe
Wege:P3 P4 P5
Kreise: C3 C4 C5
Spaziergänge: (v0e1v1e2, v2, . . . , vn−1, en, vn) mit ei = (vi−1, vi).
Outline Relationen Graphen
Graphen
Eine Relation R auf V heißt irreflexiv, wenn ∀v ∈ V : (¬vRv). Einesymmetrische, irreflexive Relation nennen wir Graph. Gilt uRv , sonennen wir {u, v} eine Kante von G. Wir schreiben G = (V , E) undauch (u, v) statt {u, v}.Einige Begriffe
Wege:P3 P4 P5
Kreise: C3 C4 C5
Spaziergänge: (v0e1v1e2, v2, . . . , vn−1, en, vn) mit ei = (vi−1, vi).
Outline Relationen Graphen
Graphen
Eine Relation R auf V heißt irreflexiv, wenn ∀v ∈ V : (¬vRv). Einesymmetrische, irreflexive Relation nennen wir Graph. Gilt uRv , sonennen wir {u, v} eine Kante von G. Wir schreiben G = (V , E) undauch (u, v) statt {u, v}.Einige Begriffe
Wege:P3 P4 P5
Kreise: C3 C4 C5
Spaziergänge: (v0e1v1e2, v2, . . . , vn−1, en, vn) mit ei = (vi−1, vi).
Outline Relationen Graphen
Graphen
Eine Relation R auf V heißt irreflexiv, wenn ∀v ∈ V : (¬vRv). Einesymmetrische, irreflexive Relation nennen wir Graph. Gilt uRv , sonennen wir {u, v} eine Kante von G. Wir schreiben G = (V , E) undauch (u, v) statt {u, v}.Einige Begriffe
Wege:P3 P4 P5
Kreise: C3 C4 C5
Spaziergänge: (v0e1v1e2, v2, . . . , vn−1, en, vn) mit ei = (vi−1, vi).
Outline Relationen Graphen
Graphen
Eine Relation R auf V heißt irreflexiv, wenn ∀v ∈ V : (¬vRv). Einesymmetrische, irreflexive Relation nennen wir Graph. Gilt uRv , sonennen wir {u, v} eine Kante von G. Wir schreiben G = (V , E) undauch (u, v) statt {u, v}.Einige Begriffe
Wege:P3 P4 P5
Kreise: C3 C4 C5
Spaziergänge: (v0e1v1e2, v2, . . . , vn−1, en, vn) mit ei = (vi−1, vi).
Outline Relationen Graphen
Teilgraphen und Komponenten
Sind G = (V , E) und H = (V ′, E ′) Graphen, so heißt H ein Teilgraphvon G, falls V ′ ⊆ V und E ′ ⊆ E .
Der Teilgraph H ist induziert, wenndarüber hinaus E ′ =
(V ′
2
)∩ E .
Beispiele
GraphG H1 induziert H2 nicht induziertEin Graph ist zusammenhängend, wenn je zwei Knoten durch einenWeg verbunden sind. Die Zusammenhangskomponenten einesGraphen sind die Äquivalenzklassen(!) der „Verbundenheitsrelation“.
Outline Relationen Graphen
Teilgraphen und Komponenten
Sind G = (V , E) und H = (V ′, E ′) Graphen, so heißt H ein Teilgraphvon G, falls V ′ ⊆ V und E ′ ⊆ E . Der Teilgraph H ist induziert, wenndarüber hinaus E ′ =
(V ′
2
)∩ E .
Beispiele
GraphG H1 induziert H2 nicht induziertEin Graph ist zusammenhängend, wenn je zwei Knoten durch einenWeg verbunden sind. Die Zusammenhangskomponenten einesGraphen sind die Äquivalenzklassen(!) der „Verbundenheitsrelation“.
Outline Relationen Graphen
Teilgraphen und Komponenten
Sind G = (V , E) und H = (V ′, E ′) Graphen, so heißt H ein Teilgraphvon G, falls V ′ ⊆ V und E ′ ⊆ E . Der Teilgraph H ist induziert, wenndarüber hinaus E ′ =
(V ′
2
)∩ E .
Beispiele
GraphG
H1 induziert H2 nicht induziertEin Graph ist zusammenhängend, wenn je zwei Knoten durch einenWeg verbunden sind. Die Zusammenhangskomponenten einesGraphen sind die Äquivalenzklassen(!) der „Verbundenheitsrelation“.
Outline Relationen Graphen
Teilgraphen und Komponenten
Sind G = (V , E) und H = (V ′, E ′) Graphen, so heißt H ein Teilgraphvon G, falls V ′ ⊆ V und E ′ ⊆ E . Der Teilgraph H ist induziert, wenndarüber hinaus E ′ =
(V ′
2
)∩ E .
Beispiele
GraphG H1 induziert
H2 nicht induziertEin Graph ist zusammenhängend, wenn je zwei Knoten durch einenWeg verbunden sind. Die Zusammenhangskomponenten einesGraphen sind die Äquivalenzklassen(!) der „Verbundenheitsrelation“.
Outline Relationen Graphen
Teilgraphen und Komponenten
Sind G = (V , E) und H = (V ′, E ′) Graphen, so heißt H ein Teilgraphvon G, falls V ′ ⊆ V und E ′ ⊆ E . Der Teilgraph H ist induziert, wenndarüber hinaus E ′ =
(V ′
2
)∩ E .
Beispiele
GraphG H1 induziert H2 nicht induziert
Ein Graph ist zusammenhängend, wenn je zwei Knoten durch einenWeg verbunden sind. Die Zusammenhangskomponenten einesGraphen sind die Äquivalenzklassen(!) der „Verbundenheitsrelation“.
Outline Relationen Graphen
Teilgraphen und Komponenten
Sind G = (V , E) und H = (V ′, E ′) Graphen, so heißt H ein Teilgraphvon G, falls V ′ ⊆ V und E ′ ⊆ E . Der Teilgraph H ist induziert, wenndarüber hinaus E ′ =
(V ′
2
)∩ E .
Beispiele
GraphG H1 induziert H2 nicht induziertEin Graph ist zusammenhängend, wenn je zwei Knoten durch einenWeg verbunden sind.
Die Zusammenhangskomponenten einesGraphen sind die Äquivalenzklassen(!) der „Verbundenheitsrelation“.
Outline Relationen Graphen
Teilgraphen und Komponenten
Sind G = (V , E) und H = (V ′, E ′) Graphen, so heißt H ein Teilgraphvon G, falls V ′ ⊆ V und E ′ ⊆ E . Der Teilgraph H ist induziert, wenndarüber hinaus E ′ =
(V ′
2
)∩ E .
Beispiele
GraphG H1 induziert H2 nicht induziertEin Graph ist zusammenhängend, wenn je zwei Knoten durch einenWeg verbunden sind. Die Zusammenhangskomponenten einesGraphen sind die Äquivalenzklassen(!) der „Verbundenheitsrelation“.
Outline Relationen Graphen
Graphenisomorphie
G1 = (V1, E1) und G2 = (V2, E2) sind isomorph :⇐⇒
∃f : V1 → V2 bijektiv:∀u, v ,∈ V1 : ({u, v} ∈ E1 ⇐⇒ {f (u), f (v)} ∈ E2) .
Outline Relationen Graphen
Graphenisomorphie
G1 = (V1, E1) und G2 = (V2, E2) sind isomorph :⇐⇒
∃f : V1 → V2 bijektiv:∀u, v ,∈ V1 : ({u, v} ∈ E1 ⇐⇒ {f (u), f (v)} ∈ E2) .
Outline Relationen Graphen
Graphenisomorphie
G1 = (V1, E1) und G2 = (V2, E2) sind isomorph :⇐⇒
∃f : V1 → V2 bijektiv:∀u, v ,∈ V1 : ({u, v} ∈ E1 ⇐⇒ {f (u), f (v)} ∈ E2) .
Outline Relationen Graphen
Codierung von Graphen
Adjazenzmatrix
s t i e rs 0 1 0 0 0t 1 0 1 1 0i 0 1 0 1 0e 0 1 1 0 1r 0 0 0 1 0
i
s r
t e
Outline Relationen Graphen
Codierung von Graphen
Inzidenzmatrix
s 1 0 0 0 0t 1 1 1 0 0i 0 1 0 1 0e 0 0 1 1 1r 0 0 0 0 1
i
s r
t e
Outline Relationen Graphen
Codierung von Graphen
Adjazenzlistens: tt: s,i,ei: t,e
e: t,i,rr: e
i
s r
t e
Outline Relationen Graphen
Valenzsequenzen
Ist G = (V , E) ein Graph und V = {v1, . . . , vn}, so nennen wir(deg(v1), deg(v2), . . . , deg(vn)) seine Valenzsequenz.
Sei D = (d1 ≥ d2 ≥ . . . ≥ dn). Frage: Wann ist D die Valenzsequenzeines einfachen Graphen?
Lemma (Handshakelemma)∑v∈V
deg(v) = 2|E |.
Dies liefert nur eine notwendige Bedingung. Allerdings gilt:
PropositionD ist die Valenzsequenz eines Multigraphen genau dann, wenn dieSumme aller Knotengrade gerade ist.
Outline Relationen Graphen
Valenzsequenzen
Ist G = (V , E) ein Graph und V = {v1, . . . , vn}, so nennen wir(deg(v1), deg(v2), . . . , deg(vn)) seine Valenzsequenz.
Sei D = (d1 ≥ d2 ≥ . . . ≥ dn). Frage: Wann ist D die Valenzsequenzeines einfachen Graphen?
Lemma (Handshakelemma)∑v∈V
deg(v) = 2|E |.
Dies liefert nur eine notwendige Bedingung. Allerdings gilt:
PropositionD ist die Valenzsequenz eines Multigraphen genau dann, wenn dieSumme aller Knotengrade gerade ist.
Outline Relationen Graphen
Valenzsequenzen
Ist G = (V , E) ein Graph und V = {v1, . . . , vn}, so nennen wir(deg(v1), deg(v2), . . . , deg(vn)) seine Valenzsequenz.
Sei D = (d1 ≥ d2 ≥ . . . ≥ dn). Frage: Wann ist D die Valenzsequenzeines einfachen Graphen?
Lemma (Handshakelemma)∑v∈V
deg(v) = 2|E |.
Dies liefert nur eine notwendige Bedingung. Allerdings gilt:
PropositionD ist die Valenzsequenz eines Multigraphen genau dann, wenn dieSumme aller Knotengrade gerade ist.
Outline Relationen Graphen
Valenzsequenzen
Ist G = (V , E) ein Graph und V = {v1, . . . , vn}, so nennen wir(deg(v1), deg(v2), . . . , deg(vn)) seine Valenzsequenz.
Sei D = (d1 ≥ d2 ≥ . . . ≥ dn). Frage: Wann ist D die Valenzsequenzeines einfachen Graphen?
Lemma (Handshakelemma)∑v∈V
deg(v) = 2|E |.
Dies liefert nur eine notwendige Bedingung. Allerdings gilt:
PropositionD ist die Valenzsequenz eines Multigraphen genau dann, wenn dieSumme aller Knotengrade gerade ist.
Outline Relationen Graphen
Eine notwendige und hinreichende Bedingung
Satz (Erdos, Gallai)D ist die Valenzsequenz eines einfachen Graphen genau dann, wenn
∀i = 1, . . . , n :i∑
j=1
dj ≤ i(i + 1) +n∑
j=i+1
min{i , dj}.
Outline Relationen Graphen
Noch eine notwendige und hinreichende Bedingung
Satz (Havel, Hakimi)D = (d1 ≥ d2 ≥ . . . ≥ dn) ist Valenzsequenz eines einfachen Graphengenau dann wenn d1 < n undD′ = (d2 − 1, d3 − 1, . . . , dd1+1 − 1, dd1+1. . . . , dn) Valenzsequenzeines einfachen Graphen ist.
Beweis.
Outline Relationen Graphen
Noch eine notwendige und hinreichende Bedingung
Satz (Havel, Hakimi)D = (d1 ≥ d2 ≥ . . . ≥ dn) ist Valenzsequenz eines einfachen Graphengenau dann wenn d1 < n undD′ = (d2 − 1, d3 − 1, . . . , dd1+1 − 1, dd1+1. . . . , dn) Valenzsequenzeines einfachen Graphen ist.
Beweis.
Outline Relationen Graphen
Noch eine notwendige und hinreichende Bedingung
Satz (Havel, Hakimi)D = (d1 ≥ d2 ≥ . . . ≥ dn) ist Valenzsequenz eines einfachen Graphengenau dann wenn d1 < n undD′ = (d2 − 1, d3 − 1, . . . , dd1+1 − 1, dd1+1. . . . , dn) Valenzsequenzeines einfachen Graphen ist.
Beweis.
1 2
k ijj
ik
21
Outline Relationen Graphen
Verfahren nach Havel und Hakimi
D = (5, 5, 3, 2, 2, 2, 1)
D′ = (4, 2, 1, 1, 1, 1)
D′ = (1, 0, 0, 0, 1)
Outline Relationen Graphen
Verfahren nach Havel und Hakimi
D = (5, 5, 3, 2, 2, 2, 1)
D′ = (4, 2, 1, 1, 1, 1)
D′ = (1, 0, 0, 0, 1)
Outline Relationen Graphen
Verfahren nach Havel und Hakimi
D = (5, 5, 3, 2, 2, 2, 1)
D′ = (4, 2, 1, 1, 1, 1)
D′ = (1, 0, 0, 0, 1)
Outline Relationen Graphen
Graphensuchmethoden