Siguiente: Arboles y gramáticas Un nivel arriba: Arboles de derivación Anterior: Arboles de derivación

Gráficas y árboles

Recordamos que una gráfica G=(V,A) consta de un conjunto de vértices $V=\{v_0,\ldots,v_{n-1}\}$ y de un conjunto de aristas A donde cada arista es una pareja de vértices. Para una arista $a=\{v_i,v_j\}$ se dice que la arista incide en sus extremos v_i,v_j y que éstos son adyacentes. Para cada vértice $v\in V$, el grado o la valencia de v es el número de vértices que le son adyacentes:

$$\partial (v)=\mbox{\rm card}\{u\in V\vert\exists a\in A: a=\{v,u\}\}.$$

Un camino entre dos vértices u,v es una sucesión de aristas $[a_1,\ldots, a_k]$ tal que u es un extremo de a₁, v lo es de a_k y cualesquiera dos aristas contiguas tienen un extremo común. Una gráfica dirigida es una gráfica tal que cada arista es un elemento del producto cartesiano $V\times V$, es decir, cada arista posee un inicio y un fin. En tal caso, las valencias externa e interna cuentan, respectivamente, las aristas que salen de y las que entran a ese vértice, es decir, para cualquier $v\in V$:

$$\begin{eqnarray*}\partial (v)^+ &=& \mbox{\rm card}\{u\in V\vert\exists a\in A: ... ...v)^- &=& \mbox{\rm card}\{u\in V\vert\exists a\in A: a=(u,v)\}. \end{eqnarray*}$$

Un árbol es una gráfica dirigida $\mbox{\it Ar\/}=(V,A)$ tal que

• Existe un único vértice $r\in V$ de grado interior cero. Ese vértice se dice ser la raiz de $\mbox{\it Ar\/}$.
• Cualquier vértice que no es raiza posee un grado interior igual a 1.

Un vértice $v\in V$ es interior si su grado exterior es mayor que 0. Los vértices que no son interiores son hojas. Si $(u,v)\in A$ entonces v se dice ser un hijo de u y u el padre de v. Dos vértices con un mismo padre se dicen ser hermanos.

Observación 1.1  

1.

Cada vértice $v\in V$ tiene un camino único que lo conecta con la raiz. El número de aristas en ese camino es la altura del vértice. Los vértices visitados por ese camino son los ancestros de v.

2.

Para cada vértice $u\in V$ el conjunto $\mbox{\it Ar\/}_u=\{v\vert u \mbox{\rm ancestro de }v\}$ adquiere naturalmente una estructura de árbol. Se dice ser el subárbol enraizado en u.

3.

En cada vértice $u\in V$ el subárbol $\mbox{\it Ar\/}_u$ es la unión de $\{u\}$ junto con los subárboles enraizados en los hijos de u.

Todo árbol tiene una estructura de conjunto ordenado mediante el orden

$$u\leq_{\mbox{\scriptsize\it Ar}}v \;\Leftrightarrow\; (u \mbox{\rm es ancestro de }v).$$

Sin embargo, el árbol se dice ordenado sólo si en cada vértice interior el conjunto de sus hijos posee un orden lineal, es decir, a los hijos $v_{i_1},\ldots,v_{i_k}$ de todo vértice u se los puede ordenar de menor a mayor. Denotemos por $\leq_u$ al orden de los hijos de u. Para cada familia ${\cal O}=\left\{\leq_u\vert u\mbox{\rm interior en }\mbox{\it Ar\/}\right\}$ de órdenes en hijos de vértices interiores se puede definir, por ejemplo, los órdenes siguientes en el árbol Ar:

Preorden:

Cada padre precede a sus hermanos mayores y a los vértices del que es ancestro.

Entreorden:

En cada vértice interior se divide al conjunto de sus hijos en dos conjuntos $\mbox{\it Primeros\/}_u$ y $\mbox{\it Ultimos\/}_u$ de manera que para cualquier pareja $(v_1,v_2)\in\mbox{\it Primeros\/}_u\times\mbox{\it Ultimos\/}_u$ se cumpla $v_1\leq_u v_2$. En el entreorden se tiene que cada padre precede a sus hermanos mayores y a sus últimos hijos, pero sucede a sus hijos primeros.

Postorden:

Cada padre sucede a sus hermanos menores y a los vértices del que es ancestro.

Cualquiera de estos órdenes es un orden de izquierda a derecha: $\preceq$ es un orden de izquierda a derecha si cualesquiera dos vértices con subárboles ajenos son tales que todos los vértices en el subárbol de uno anteceden a cualquier vértice en el subárbol del otro, i. e. $\forall u,v \in V$:

$$\mbox{\it Ar\/}_u\cap\mbox{\it Ar\/}_v=\emptyset\;\Rightarrow... ... &\Rightarrow& \left.v_1\preceq u_1\right) \end{array}\right.$$

Todo orden de izquierda a derecha es total: cualesquiera dos vértices en el árbol son comparables. En un tal orden, la hoja mínima se dice ser la hoja siniestra (leftmost) y la máxima es la hoja diestra (rightmost).
Siguiente: Arboles y gramáticas Un nivel arriba: Arboles de derivación Anterior: Arboles de derivación