img203

203

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

b)    numer porządkowy lj każdego wierzchołka n, etykietowanego przez

flj, j = 1.....r, w generowanym grafie g jest obliczany jako:

gdzie /' jest numerem porządkowym wierzchołka n_;- w prawej stronie produkcji, zaś p jest numerem porządkowym wierzchołka n w generowanym grafie g;

c)    stosujemy transformację osadzenia: załóżmy, że wierzchołek n' w generowanym grafie g:

-    jest etykietowany takim samym symbolem nieterminalnym co pewien wierzchołek nj (etykietowany przez Bj),

-    jest oznaczony przez ¹,

-    numer porządkowy wierzchołka rij jest wielokrotnością numeru porządkowego wierzchołka n',

-    nie istnieje krawędź idąca od poprzednika(¹) wierzchołka n' do wierzchołka rij (patrz przykładowo, rys. 12.3 - wierzchołki Afa i ).

Wtedy wierzchołek n' usuwamy, a wszystkie krawędzie po nim dziedziczy wierzchołek n_}.

Wprowadźmy pojęcia służące do określenia jednoznacznej reprezentacji scen przez grafy klasy IE [36], która jest podklasą rodziny grafów EDG.

Krawędzie grafów będą używane do definiowania relacji przestrzennych pomiędzy parami obiektów sceny reprezentowanymi przez wierzchołki grafów. Relacje te będą opisywane za pomocą zbioru etykiet krawędziowych T, który jest traktowany jako rodzina relacji przeciwsymetrycznych [36]. Dla każdej etykiety A 6 T zdefiniujemy etykietę odwrotną A^-1 € T taką, że dla dowolnych wierzchołków grafu u oraz w reprezentujących obiekty sceny i takich, że (v, A, w) 6 E, krawędź (w, A^-1, u) opisuje tą samą relację pomiędzy obiektami. Mówimy, że te krawędzie są semantycznie równoważne i zapisujemy

(v,X,w)—sem — (w,X~^l,v).

1

Poprzednikiem wierzchołka n' nazywamy wierzchołek n taki, że istnieje krawędź (n,/3,n')6£.