1.4. Grafy, drzewa
Graf zorientowany
Graf zorientowany jest parą
gdzie:
K
- skończony, niepusty zbiór wierzchołków
D ⊆ K × K - zbiór krawędzi
Funkcje etykietujące
f: K ! MK - przypisuje etykietę (nazwę) każdemu wierzchołkowi
g: D ! MD - przypisuje etykietę (nazwę) każdej krawędzi
Inne definicje
Ciąg (k0,..., kn) ki ∈ K, n ≥ 1 wierzchołków tworzy ścieżkę o długości n, jeśli
(ki-1 , ki)∈D, i = 1,2,...,n
Ścieżka jest cyklem, gdy k0 = kn
Graf zorientowany jest acykliczny, gdy nie zawiera cykli.
Przykład:
1
4
K = {1, 2, 3, 4}
D = {(1, 2), (2, 3), (3, 2), (3, 4), (4, 4), (1, 3)}
(2, 3, 2, 3, 4, 4, 4)
(2, 3, 2)
2
3
- graf zorientowany
- ścieżka
- cykl
nie jest grafem acyklicznym
Drzewo o korzeniu k0 jest zorientowanym grafem acyklicznym, w którym dla każdego
wierzchołka k ≠ k0 istnieje dokładnie jedna ścieżka (k0,..., k).
k1
k1
k2
- przodek k2
- potomek k1
Każdy k ≠ k0 ma dokładnie jednego przodka
Korzeń
- jedyny wierzchołek nie posiadający przodka
Liść
- wierzchołek bez potomków
k2
Cięcie w drzewie jest to podzbiór C ⊆ K, taki że dla każdego liścia km . na ścieżce
(k0,..., km) od korzenia do tego liścia leży dokładnie jeden element podzbioru C.
Korona drzewa jest to ciąg k1,k2,...,kn; ki∈K liści drzewa wypisanych od lewej do prawej
strony.
Korona cięcia drzewa jest to ciąg k1,k2,...,kn; ki∈C ⊂ K elementów cięcia drzewa wypisanych
od lewej do prawej strony.
0
2
1
4
5
0
4, 5, 6, 7, 8
Cięcia:
{0}, {4, 5, 6, 7, 8}, {1, 2, 3},
{4, 5, 6, 3}, {1, 2, 7, 8} itd...
3
6
7
8
- korzeń
- liście
Korona drzewa: 4, 5, 6, 7, 8
Korona cięcia: {2, 4, 7, 8} : 4, 2, 7, 8
... zobacz całą notatkę
Komentarze użytkowników (0)