Definicja didrzewa
Niech D(V,E) oznacza digraf elementarny, spójny, skierowany z ponumerowanymi wierzchołkami od 0 do n.
V={0, 1,...n} - zbiór wierzchołków, 0-korzeń D, |V|=n+1.
E⊂VxV={(i, j):i,j∈V; i≠j} - zbiór łuków, |E|=m, m≤n(n-1).
(i, j) oznacza łuk skierowany od wierz. i do wierz. j.
Niech droga d(i, j) oznacza zbiór odpowiednio skierowanych od wierz. i do wierz. j łuków: d(i, j)={(i,u),...,(v,j)} = {(i,u,...,v,j)}; i,j,u,v ∈V.
Niech T oznacza zbiór wszystkich didrzew T=U{ti}. Wtedy N=|T|.
DEFINICJA: Didrzewem t digrafu D(V, E) nazwiemy taki jego
podgraf, że:
10. Ilość łuków równa się n, tzn. t={(i, j): i, j∈V}, |t|=n.
20. Od każdego wierzchołka istnieje droga do korzenia w kierunku
strzałek wybranych luków, tzn. t={d(i,0): i=1,...,n}, |t|=n.
Algorytm generowania didrzew na podstawie iloczynu kartezjańskiego
Niech Ei = {(i, j): i, j ∈V, i ≠ j} oznacza zbiór łuków wychodzących z wierzchołka i. Wtedy E=E0∪ E1∪... ∪En, E0∩ E1∩... ∩En=∅.
Niech Vk=E1× E2×... ×En, |Vk|=|E1|⋅|E2|⋅...⋅|En| >N.
Łatwo udowodnić, że T⊂Vk.
3
1
2
3
4
0
3
1
2
4
0
1
0
4
3
2
1
d)
c)
b)
a)
Rys. 4-2
Vk=E1× E2×... ×En={(0000), (0001), (0002), (0003), (0010), (0011),...,(4443)}
n=9
99 =387420489
108=100000000
/ =3.8742
(1,48)
n=7
77=823543
86=262144
/ =3.1415
(1,45)
n=4
44=256
53=125
/ =2,13
(1,3)
E1=[0, 2, 3, 4]
E2=[0, 1, 3, 4]
E3=[0, 1, 2, 4]
E4=[0, 1, 2, 3]
T
Vk
2
4
0
Wyszukiwarka