img204

204

D4. Wybrane pojęcia teorii języków drzewowych i grafowych

Na przykład, krawędzie typu: „znajduje się na lewo od” i „znajduje się na prawo od” są semantycznie równoważne. W tak określonym zbiorze T wprowadzamy relację liniowego porządku

r = {Ti, • ■ • ,7t I Ti < • < 7*}-

Następnie na zbiór krawędzi F nakładamy następujący warunek: dla każdego v 6 V: jeśli istnieje (u, A, w) € E, to nie istnieje (u, 7, z) 6 E taka, że X = 7 i nie istnieje (z,/?,u) 6 E, taka, że A = /?^_1.

Niech scena P składająca się z n obiektów Ki,..., K„, których położenie jest opisane przez współrzędne kartezjańskie (*i,yi),..., (x„,y_n) będzie reprezentowana przez graf EDG g. Wierzchołek v, € g odpowiadający obiektowi Ii_$ nazywamy S-wierzchołkiem jeśli(²)

(x_s,y_s) - min{min{(xi,yj)}}, i,j = l,...,n.

Vj ^x•

Graf EDG H = (V, E, E, I', <j>) nazywamy zindeksowanym, krawędzio-wo-jednoznacznym grafem (grafem IE - ang. Indexed Edge-unambiguous Graph) [36], jeśli:

1)    T i E mają własności opisane powyżej;

2)    zbiór wierzchołków V jest zindeksowany według następujących reguł:

a)    5-wierzchołek - vo indeksujemy przez 1,

b)    indeksujemy wszystkie wierzchołki przyległe do vo zgodnie z relacją < w zbiorze etykiet krawędzi łączących v₀ z wierzchołkami przyległymi; indeksacji dokonujemy w porządku rosnącym i = 2,3,... ,k pamiętając, że każdą krawędź wchodzącą do Vo traktujemy jako krawędź odwrotną wychodzącą z vo;

c)    kolejno wybieramy wierzchołki zindeksowane i — 2,3,..., k i indeksujemy wierzchołki przyległe do nich, które do tej pory nie zostały zindeksowane;

d)    powtarzamy punkt c), aż zindeksujemy wszystkie wierzchołki;

(²) Tak zdefiniowany S-wierecholek odpowiada „obiektowi obrazu, umieszczonemu najniżej z lewej strony". Czasem wygodnie jest przyjąć inną regułę np. „najwyżej umieszczonemu, górnemu obiektowi obrazu". Istotą pojęcia 5-wierzcholka jest, aby dało się go w jednoznaczny sposób określić.