Stromy
STROMY Základní pojmy Strom – T – je souvislý graf, který neobsahuje jako podgraf kružnici. Strom dále budeme značit T = (V, X). Pro graf, který je stromem platí q = n - 1, kde q = ⎪X⎥ a n = ⎪V⎥. Pro T mezi každou dvojicí vrcholů u, v ∈ V, u ≠ v existuje právě jedna cesta, každá hrana stromu je mostem a každý vrchol stromu mající st(v) ≥ 2 je artikulací. Les – je nesouvislý graf, jehož komponentami jsou stromy (popř. triviální grafy). Hvězda – speciální případ stromu, ve kterém jeden vrchol má st(v) = n – 1 a n – 1 vrcholů má stupeň st(v) = 1. Excentricita (výstřednost) vrcholu v – e(v) – je číslo, které udává e(v) = max{d (u, v)} u∈V
Vážená excentricita vrcholu v – ec(v) – je číslo, které udává ec(v) = max{d (u, v) × w(u )} , u∈V
kde w(u) je váha vrcholu u ∈ V Rádius (poloměr) grafu T = (V, X) – r(T) – je číslo, které udává r (T ) = min{e(v)} v∈V
Diametr (průměr) grafu T = (V, X) – d(T) – je číslo, které udává d (T ) = max{e(v)} v∈V
Centrální vrchol – je vrchol v ∈ V pro který platí e(v) = r(T). Centrum grafu – množina všech centrálních vrcholů. Větev vrcholu – pro v ∈ V nazýváme podgraf, který je stromem, obsahuje vrchol v a maximální počet vrcholů a platí v něm st(v) = 1. Síla vrcholu – s(v) – udává počet vrcholů větve, která obsahuje maximální počet vrcholů. Centroidní vrchol – vrchol s minimální silou. Centroid – množina všech centroidních vrcholů.
Řešené příklady 1. příklad V hranově a vrcholově ohodnoceném grafu T = (V, X) zobrazeném obr. 1, který je stromem určete hodnoty excentricity e(v) pro každý vrchol v ∈ V . Dále určete rádius r(T), diametr grafu d(T) a centrum tohoto stromu. 3 v6 3 2 10 2 v4 1
v1
v9
v5
7
4
5 9
v2 4
v7 3
2 1 8
v3 4
6 3
v10
v8 4
Obr. 1
Teorie grafů - úlohy
-1-
Stromy
Řešení: Hodnota excentricity vrcholu e(v) je definována jako maximum ze vzdáleností vrcholu v k ostatním vrcholům sítě u ∈ V. Hodnota excentricity pro vrchol v1 je maxiem ze vzdáleností d(v1, v1), d(v1, v2), d(v1, v3), d(v1, v4), d(v1, v5), d(v1, v6), d(v1, v7), d(v1, v8), d(v1, v9), d(v1, v10), tedy: e(v1) = max { d(v1, v1), d(v1, v2), d(v1, v3), d(v1, v4), d(v1, v5), d(v1, v6), d(v1, v7), d(v1, v8), d(v1, v9), d(v1, v10)} = max {0, 9, 11, 14, 21, 24, 13, 17, 15, 14} = 24 Pro ostatní vrcholy zadaného grafu jsou hodnoty excentricit: e(v2) = max {9, 0, 2, 5, 12, 15, 4, 8, 6, 5} = 15 e(v3) = max {11, 2, 0, 7, 14, 17, 6, 10, 4, 3} = 17 e(v4) = max {14, 5, 7, 0, 7, 10, 9, 13, 11, 7} = 14 e(v5) = max {21, 12, 14, 7, 0, 17, 16, 20, 18, 17} = 21 e(v6) = max {24, 15, 17, 10, 17, 0, 19, 23, 21, 20} = 24 e(v7) = max {13, 4, 6, 9, 16, 19, 0, 12, 10, 9} = 19 e(v8) = max {17, 8, 10, 13, 20, 23, 12, 0, 14, 13} = 23 e(v9) = max {15, 6, 4, 11, 18, 21, 10, 14, 0, 7} = 21 e(v10) = max {14, 5, 3, 7, 17, 20, 9, 13, 7, 0} = 20 Rádius grafu je číslo rovnající se minimální hodnotě excentricity vrcholu zadaného grafu. Pro strom na obr. 1 tedy platí: r(T) = min { e(v1), e(v2), e(v3), e(v4), e(v5), e(v6), e(v7), e(v8), e(v9), e(v10)} = = min {24, 15, 17, 14, 21, 24, 19, 23, 21, 20} = 14 Diametr grafu je naopak číslo rovnající se maximální hodnotě excentricity vrcholu zadaného grafu. Pro strom na obr. 1 tedy platí: d(T) = max { e(v1), e(v2), e(v3), e(v4), e(v5), e(v6), e(v7), e(v8), e(v9), e(v10)} = = max {24, 15, 17, 14, 21, 24, 19, 23, 21, 20} = 24 Centrum grafu je množina vrcholů, pro které platí, že hodnota excentricity se rovná hodnotě radiusu – e(v) = r(T). Centrem v zadaném grafu obr. 1 je vrchol v4, ke e(v) = r(T) = 14.
2. příklad V grafu na obr. 1 určete hodnoty vážené excentricity ec(v) pro každý vrchol v ∈ V.
Řešení: Hodnota vážené excentricity vrcholu ec(v) je definována jako maximum ze součinu vzdáleností vrcholu v k ostatním vrcholům sítě u ∈ V a váhy vrcholu u ∈ V. Hodnotu vážené excentricity pro vrchol v1 určíme z následujícím způsobem: ec(v1) = max { d(v1, v1)×w(v1), d(v1, v2) × w(v2), d(v1, v3) × w(v3), d(v1, v4) ×w(v4), d(v1, v5) × w(v5), d(v1, v6) × w(v6), d(v1, v7) × w(v7), d(v1, v8) × w(v8), d(v1, v9) × w(v9), d(v1, v10) × w(v10)} = max {0×1, 9×1, 11×4, 14×2, 21×2, 24×3, 13×3, 17×4, 15×3, 14×6} = max {0, 9, 44, 28, 42, 72, 39, 68, 45, 84} = 84
-2-
Teorie grafů - úlohy
Stromy Hodnoty vážených excentricit pro další vrcholy zadaného stromu jsou: e(v2) = max {9×1, 0×1, 2×4, 5×2, 12×2, 15×3, 4×3, 8×4, 6×3, 5×6} = = max {9, 0, 8, 10, 24, 45, 12, 32, 18, 30} = 45 e(v3) = max {11×1, 2×1, 0×4, 7×2, 14×2, 17×3, 6×3, 10×4, 4×3, 3×6} = = max {11, 2, 0, 21, 28, 51, 18, 40, 12, 18} = 51 e(v4) = max {14×1, 5×1, 7×4, 0×2, 7×2, 10×3, 9×3, 13×4, 11×3, 7×6} = = max {14, 5, 28, 0, 14, 30, 27, 52, 33, 42} = 52 e(v5) = max {21×1, 12×1, 14×4, 7×2, 0×2, 17×3, 16×3, 20×4, 18×3, 17×6} = = max {21, 12, 56, 14, 0, 51, 48, 80, 54, 102} = 102 e(v6) = max {24×1, 15×1, 17×4, 10×2, 17×2, 0×3, 19×3, 23×4, 21×3, 20×6} = = max {24, 15, 68, 20, 0, 57, 92, 63, 120} = 120 e(v7) = max {13×1, 4×1, 6×4, 9×2, 16×2, 19×3, 0×3, 12×4, 10×3, 9×6} = = max {13, 4, 24, 18, 32, 57, 0, 48, 30, 54} = 57 e(v8) = max {17×1, 8×1, 10×4, 13×2, 20×2, 23×3, 12×3, 0×4, 14×3, 13×6} = = max {17, 8, 40, 26, 40, 69, 36, 0, 42, 78} = 78 e(v9) = max {15×1, 6×1, 4×4, 11×2, 18×2, 21×3, 10×3, 14×4, 0×3, 7×6} = = max {15, 6, 16, 22, 36, 63, 30, 56, 0, 42} = 63 e(v10) = max {14×1, 5×1, 3×4, 7×2, 17×2, 20×3, 9×3, 13×4, 7×3, 0×6} = = max {14, 5, 12, 14, 34, 60, 27, 52, 21, 0} = 60
3. příklad V hranově neohodnoceném grafu zobrazeném obr. 2, který je stromem určete centrální vrchol popř. vrcholy, které tvoří centrum tohoto grafu.
v6
v1
v2 v7
v9
v5
v4
v3
v15 v10
v11 v13
v8
v12
v14
Obr. 2
Řešení: Jestliže hledáme centrum stromu, který je hranově neohodnocen, nebo ohodnocení hran je stejné pro h ∈ X je možné použít zjednodušený algoritmus na vyhledání centra stromu. Během hledání centra není potřebné určovat hodnotu excentricit vrcholů grafu a poloměru stromu. 1. krok: V grafu označíme visící hrany (silnější čárkované označené hrany obr. 3a). Visící hranou rozumíme hranu po jejímž projití do jednoho z krajních vrcholů není možné pokračovat po jiné hraně dále. Visícími hranami jsou (v2, v1), (v2, v7), (v2, v8), (v4, v6), (v4, v5), (v3, v9), (v11, v15), (v11, v12), (v13, v14).
Teorie grafů - úlohy
-3-
Stromy Visící hrany (obr. 3a) z grafu vypustíme a dále uvažujeme se vzniklým podgrafem viz. obr. 3b.
v6
v2
v1 v7
v9
v5
v4
v15 v10
v3
v11
v4 v12
v13
v8
v2
v10
v3
v11
v14
v13 b)
a)
Obr. 3 Dále opakujeme uvedený postup značení a vypouštění hran ze vzniklého podgrafu. Výsledkem krácení v následujícím kroku je vypuštění hran (v2, v4), (v11, v13) čímž vznikne podgraf na obr. 4b.
v4 v2
v10
v3
v11
v2
v10
v3
v13
a)
v11
b)
Obr. 4 2. krok: Proces označování a vypouštění hran se opakuje do doby, kdy z původního grafu zůstane pouze jedna hrana (nebo jeden vrchol). V tomto případě postupně vykrátíme hrany (v2, v3), (v10, v11). Výsledkem krácení je hrana (v10, v3) viz. obr. 5b. Centrum je v tomto případě tvořeno dvojicí krajních vrcholů nevykrácené hrany (jestliže po krácení zbývá jeden vrchol je pouze ten centrem).
v2
v10
v3
v11
a)
v10
v3 b)
Obr. 5 Centrum stromu na obr. 2 tvoří vrchol v3 a v10.
4. příklad V hranově neohodnoceném grafu zobrazeném na obr. 2, který je stromem určete sílu vrcholu pro v ∈ V a nalezněte centroid zadaného stromu.
Řešení: V první části určíme sílu vrcholů zadaného stromu. Síla vrcholu s(v) udává maximální počet vrcholů v jedné větvi. Větví vrcholu rozumíme maximální podgraf grafu T, který
-4-
Teorie grafů - úlohy
Stromy obsahuje vrchol v, pouze jednu hranu s incidencí h = (v, u), kde u ∈ V a maximální počet vrcholů. Počet větví vrcholu se rovná stupni tohoto vrcholu st(v). POZNÁMKA! Někdy bývá v síle vrcholu s(v) započten i vrchol v. Vrchol v1 má v zadaném grafu pouze jednu větev st(v1) = 1, tato větev obsahuje všechny vrcholy stromu kromě vrcholu v1. Síla vrcholu v1 v zadaném stromu je s(v1) = 14. Vrchol v2 má 5 větví, které jsou pomocí různých druhů čar vyznačeny na obr. 6. Tyto větve obsahují 1, 3, nebo 8 vrcholů. Síla vrcholu v2 je tedy s(v2) = 8.
v6
v1
v2 v7
v9
v5
v4
v3
v15 v10
v11 v13
v8
v12
v14
Obr. 6
Pro zbývající vrcholy stromu jsou nalezené hodnoty uvedené v následující tabulce: Počet Počet Vrchol větví Vrcholy v jedné větvi vrcholů vrcholu v dané větvi 1 v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15 14 v1 1 v1 8 v3, v9, v10, v11, v12, v13, v14, v15 5 v4, v5, v6 3 v2 1 v7 1 v8 v1, v2, v4, v5, v6, v7, v8 7 3 1 v3 v9 v10, v11, v12, v13, v14, v15 6 v1, v2, v3, v7, v8, v9, v10, v11, v12, v13, v14, v15 12 3 1 v4 v5 1 v6 1 v1, v2, v3, v4, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15 14 v5 1 v1, v2, v3, v4, v5, v7, v8, v9, v10, v11, v12, v13, v14, v15 14 v6 1 v1, v2, v3, v4, v5, v6, v8, v9, v10, v11, v12, v13, v14, v15 14 v7 1 v1, v2, v3, v4, v5, v6, v7, v9, v10, v11, v12, v13, v14, v15 14 v8 1 v1, v2, v3, v4, v5, v6, v7, v8, v10, v11, v12, v13, v14, v15 14 v9 v1, v2, v3, v4, v5, v6, v7, v8, v9 9 2 v10 v11, v12, v13, v14, v15 5 v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v13, v14, v15 13 2 v11 1 v12 14 1 v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v13, v14, v15 v12
Teorie grafů - úlohy
Síla vrcholu s(v) 14 8
7 12 14 14 14 14 14 9 13 14
-5-
Stromy
v13
2
v14 v15
1 1
v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v15 v14 v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v15 v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14
13 1 14 14
13 14 14
Centroidním vrcholem nazveme vrchol s minimální silou. V zadaném stromu je pouze jeden vrchol s minimální silou – vrchol v3. Vrchol v3 je centroidním vrcholem stromu a tvoří centroid grafu.
-6-
Teorie grafů - úlohy
Stromy
Cvičení 1. příklad V grafu, který je na obr. 7 nalezněte podgrafy, které jsou stromy T = (V, X) a zároveň mohutnost množiny vrcholů je ⏐V ⏐ = 1, ⏐ V ⏐ = 2, ⏐ V ⏐ = 3, ⏐ V ⏐ = 4.
v5 v6 v4 v1
v2
v3 v8
v7
Obr. 7
2. příklad V hranově ohodnoceném grafu zobrazeném obr. 8, který je stromem určete hodnoty excentricity e(v) pro každý vrchol v ∈ V . Dále určete rádius r(T), diametr grafu d(T) a centroid tohoto stromu. 12
v14
v13 9
7
v12
v16
2
v17
v15
8
6
v2
5
6
v1
7
v5
4 6
v3 v8 2
3
v4
v11 v10
v7
8
v6
4
v9
3
Obr. 8
3. příklad V hranově neohodnoceném grafu zobrazeném obr. 9, který je stromem určete centrální vrchol popř. vrcholy, které tvoří centrum tohoto grafu.
Teorie grafů - úlohy
-7-
Stromy
v6 v5 v4 v1
v12
v9
v2
v8
v3
v10
v11 v13
v7 v14
v15
Obr. 9
4. příklad V hranově neohodnoceném grafu zobrazeném na obr. 9, který je stromem určete sílu vrcholu pro v ∈ V a nalezněte centroid zadaného stromu.
5. příklad V grafu na obr. 10 určete hodnoty vážené excentricity ec(v) pro každý vrchol v ∈ V. 2
v11
15
4
v1
10
3
v2
5
v3 8
6
7 v 4
v5
3
4
5 v7
v8 9
4
2
v10
v12
9
6
v6
5
v9
3
8
1
2
8
Obr. 10
6. příklad V hranově ohodnoceném grafu zobrazeném obr. 11, který je stromem určete hodnoty excentricity e(v) pro každý vrchol v ∈ . Dále určete rádius r(T), diametr grafu d(T) a centum tohoto stromu.
-8-
Teorie grafů - úlohy
Stromy
v18
v11
v13
15
v1
10
5
v2
4 8
v3 8
v4
v5 4
v7
v8 2
3
v12
4
v17
1
v20
3
5
v14
9
6
3
2
v19
6
v15
7
v16
v6 v9
v10 Obr. 11
7. příklad V grafu zadaném na obr. 12 nalezněte libovolný podgraf, který je: a) stromem, b) hvězdou, c) lesem, d) faktorovým podgrafem. 3 20 v7 4 40 2
v9
v3
3 v1 30
30
25
10 15
v6 v2 5
7
20
v5
25
50
v10 4
45
2
v8
15
15
10
v4
35
15
15
1
6
Obr. 12
8. příklad V grafu na obr. 12 určete hodnoty vážené excentricity ec(v) pro každý vrchol v ∈ V.
9. příklad V hranově neohodnoceném grafu zobrazeném obr. 13, který je stromem určete centrální vrchol popř. vrcholy, které tvoří centrum tohoto grafu.
Teorie grafů - úlohy
-9-
Stromy
v17 v13
v18
v2
v14 v1
v3
v4
v12
v5
v15 v16
v19
v8
v6 v7 v9
v11 v10
Obr. 13
10. příklad V hranově neohodnoceném grafu zobrazeném na obr. 13, který je stromem určete sílu vrcholu pro v ∈ V a nalezněte centroid zadaného stromu.
- 10 -
Teorie grafů - úlohy
Stromy
Výsledky příkladů 1 – 10 1. příklad Ukázka řešení, které není jediné:
v1
v1
|V| = 1
v2 |V| = 2
v2
v3 v8
|V| = 3
v2 v7
v3 v8
|V| = 4
2. příklad e(v1) = 37, e(v2) = 42, e(v3) = 41, e(v4) = 47, e(v5) = 31, e(v6) = 39, e(v7) = 42, e(v8) = 41, e(v9) = 24, e(v10) = 27, e(v11) = 28, e(v12) = 29, e(v13) = 41, e(v14) = 36, e(v15) = 37, e(v16) = 45, e(v17) = 47 r(T) = 24 d(T) = 47 s(v1) = 13, s(v2) = 16, s(v3) = 15, s(v4) = 16, s(v5) = 9, s(v6) = 14, s(v7) = 16, s(v8) = 16, s(v9) = 8, s(v10) = 16, s(v11) = 16, s(v12) = 11, s(v13) = 16, s(v14) = 14, s(v15) = 16, s(v16) = 15, s(v17) = 16 Vrchol v9 je centroid zadaného stromu.
3. příklad Vrchol v8 je centrálním vrcholem stromu a tvoří centrum grafu.
4. příklad s(v1) = 14, s(v2) = 10, s(v3) = 7, s(v4) = 12, s(v5) = 14, s(v6) = 14, s(v7) = 14, s(v8) = 8, s(v9) = 14, s(v10) = 9, s(v11) = 14, s(v12) = 14, s(v13) = 12, s(v14) = 13, s(v15) = 14 Centroid zadaného grafu je vrchol v3.
5. příklad ec(v1) = 243, ec(v2) = 153, ec(v3) = 108, ec(v4) = 96, ec(v5) = 162, ec(v6) = 189, ec(v7) = 114, ec(v8) = 120, ec(v9) = 138, ec(v10) = 132, ec(v11) = 243, ec(v12) = 180
6. příklad e(v1) = 35, e(v2) = 25, e(v3) = 20, e(v4) = 28, e(v5) = 26, e(v6) = 29, e(v7) = 31, e(v8) = 32, e(v9) = 35, e(v10) = 34, e(v11) = 35, e(v12) = 23, e(v13) = 27, e(v14) = 28, e(v15) = 34, e(v16) = 35, e(v17) = 31, e(v18) = 33, e(v19) = 35, e(v20) = 32 r(T) = 20 d(T) = 35 Vrchol v3 je centrem grafu.
Teorie grafů - úlohy
- 11 -
Stromy
7. příklad Ukázky možného ne jediného řešení: v7 v9
v10
v6 v2
v1
v8
v4
v2
v5
v4
strom
v3
v7
v3
v7
v9
v3
hvězda
v7
v6
v1
v2 v4
v10
v6
v1 v5
v9
v2 v4
les
v8 v5 faktorový podgraf
8. příklad ec(v1) = 300, ec(v2) = 240, ec(v3) = 340, ec(v4) = 200, ec(v5) = 220, ec(v6) = 200, ec(v7) = 300, ec(v8) = 280, ec(v9) = 420, ec(v10) = 350
9. příklad Vrchol v5 a v12 jsou centrální vrcholy stromu a tvoří centrum grafu.
10. příklad s(v1) = 16, s(v2) = 18, s(v3) = 18, s(v4) = 15, s(v5) = 8, s(v6) = 16, s(v7) = 16, s(v8) = 17, s(v9) = 18, s(v10) = 18, s(v11) = 18, s(v12) = 11, s(v13) = 18, s(v14) = 14, s(v15) = 15, s(v16) = 18, s(v17) = 18, s(v18) = 18, s(v19) = 18 Vrchol v5 je centroid zadaného stromu.
- 12 -
Teorie grafů - úlohy
