|| Inicio ||

Sobre Traversals...

Última modificación: 14 de Diciembre de 2013, y ha tenido 294 vistas

Etiquetas utilizadas: || ||

Definición formal de Traversals sobre Esquemas de Grafos:

Sea \(S(S_V,S_E)\) un grafo dirigido que llamaremos Esquema, a sus vértices les llamaremos tipos, y a sus aristas, relaciones. Un grafo dirigido \(G(V,E)\) (con conjunto de nodos \(V\) y conjunto de aristas \(E\)), decimos que se ajusta al esquema \(S\) si existen aplicaciones \(tipo_V: V \rightarrow S_V\) (resp. \(tipo_E:E\rightarrow S_E\)) verificando que para toda arista, \(e\), que conecta los nodos \(v_1\) con \(v_2\) en \(G\), se tiene que \(tipo_E(e)\) conecta los nodos \(tipo_V(v_1)\) y \(tipo_V(v_2)\) en \(S\).

Habitualmente, para cada \(t \in S_V\) y \(r\in S_E\) notaremos por:

$$V_t=\{v\in V:\ tipo_V(v)=t\}$$

$$E_t=\{e\in V:\ tipo_E(e)=t\}$$

Un traversal sobre \(S\), \(P\), es un camino en \(S\), es decir, una sucesión \((t_1 r_1 t_2 r_2\dots r_n t_{n+1})\), donde \(t_i\in S_V\) y \(r_i\in S_E\) es una relación que conecta el tipo \(v_i\) con el tipo \(t_{i+1}\)).

Aplicación de un traversal sobre un grafo:

En las condiciones anteriores, podemos definir la aplicación de un traversal sobre un grafo de la siguiente forma:

Si \(P\) es un traversal sobre \(S\) (en las condiciones anteriores) y \(Q\) una subsucesión ordenada, \(t_{i_1}\dots t_{i_k}\), de los tipos que aparecen en \(P\). La acción del par \(<P,Q>\) sobre \(G\), que notaremos \(<P,Q>(G)\) es el hipergrafo ponderado \(H(V_H,E_H)\) dado por:

$$V_H\subseteq V_{t_{i_1