img201

201

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

2) wierzchołek vj jest maksymalnym (w sensie indeksu) wierzchołkiem o własności przedstawionej w punkcie 1.

Spójny graf EDG H o macierzy przyległości A = [a^]_mlm nazywamy grafem klasy Q (grafem Q) wtedy i tylko wtedy, gdy jego wierzchołki można zindeksować tak, że spełnione są następujące warunki:

1)    a_{j = 0 V« > j,

2)    dla każdego aij takiego, że = 1 oraz i ^ maxind(j), istnieje uporządkowany ciąg indeksów i < j\ < j? <■■■ < j_r < j taki, że

i = maxind(j\), j\ — maxind(j2),j_r = maxind(j).

Niech n* będzie wierzchołkiem o indeksie k i etykiecie n* grafu U. Czwórkę

(n_t, r, «i...e_r, »i... t_r),

gdzie r - stopień wyjściowy n* (tzn. liczba krawędzi wychodzących z n*), t’i .. .«V - uporządkowany rosnąco ciąg indeksów wierzchołków, do których wchodzą krawędzie wychodzące z n*, e\ ... e_r - ciąg etykiet krawędziowych odpowiadających krawędziom wchodzącym do wierzchołków o indeksach nazywamy opisem charakterystycznym wierzchlka n*. Ciąg opisów charakterystycznych kolejnych wierzchołków grafu H nazywamy opisem charakterystycznym grafu H.

Ekspansywną gramatyką grafową ®EXP nazywamy piątkę

<S>EXP = (N,Z,r,P,S),

gdzie N - skończony zbiór nieterminalnych etykiet wierzchołkowych, S -zbiór terminalnych etykiet wierzchołkowych, T - skończony zbiór etykiet krawędziowych, S € N - symbol startowy, P - skończony zbiór produkcji o jednej z dwóch postaci:

a)    o postaci zredukowanej A —* a, gdzie A € N, a € £,

b)    o postaci ekspansywnej przedstawionej na rysunku D4.1 i zapisywanej skrótowo:

A—>ax\B\ x₂S|³ • • x_rB‘ ,