Sobre Traversals...

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}} \cup\dots\cup V_{t_{i_k}}$$

\((a_1,\dots,a_k)\in E_H\) si y sólo si existe un camino en \(G\), \((v_1 e_1 v_2 e_2\dots e_n v_{n+1})\), verificando:

  1. \(\forall 1\leq i\leq n+1\ (tipo_V(v_i)=t_i)\).
  2. \(\forall 1\leq i\leq n\ (tipo_E(e_i)=r_i)\) (se deduce de las condición anterior y de que \(G\) se ajusta a \(S\)).
  3. \(\forall 1\leq j\leq k\ (v_{i_j}=a_j)\).

Normalmente, se tomará como \(V_H\) el conjunto de nodos de \(V\) que intervienen en alguna de las hiperaristas anteriores.

El peso de una hiperarista \(h\in E_H\) se define como:

$$w( h )=\#\{\mbox{caminos que verifican las 3 propiedades anteriores}\}$$

Consultas Traversals sobre Grafos ajustados a Esquemas:

En las condiciones anteriores, podemos definir las operaciones siguientes entre traversals:

Visión general de etiquetas para: 'grafos'

Entradas en este sitio con 'grafos'

  • Resolviendo Problemas de Satisfacción de Restricciones con Hormigas
      Al igual que hemos visto metaheurísticas varias (como  BFS ,  A* , o  Templado Simulado ) para dar soluciones a familias de problemas siempre y cuando pudiéramos represe
  • Complex Networks Toolbox (NetLogo)
    This NetLogo model is a toy tool to launch experiments for Complex Networks. It provides some basic commands to generate and analyze small networks by using the most commo
  • El modelado de problemas
    En numerosas ciencias se hace necesario el estudio y análisis de fenómenos del mundo real, y por ello se hace necesaria la aplicación del método científico a este estudio.
  • Estructurando y consultando información en grafos
    La  Información Estructurada  es información que ha sido analizada y procesada de alguna forma, en el sentido de que ha sido dividida en sus componentes estructurales. Par
  • Redes Booleanas
    La  Teoría de Sistemas Complejos  trabaja sobre sistemas dinámicos que tienen un gran número de variables, en los que el comportamiento puede ser arbitrariamente complejo.
  • Introducción a las redes complejas
    Entre los avances realizados en redes complejas (tanto naturales como artificiales) destacan aquellos relacionados con las propiedades de mundo pequeño y libres de escala
  • Bases de Datos en Grafo
    En los últimos años ha aparecido una buena colección de bases de datos basadas en grafo mpara dar soluciones a diversos problemas que venían apareciendo en el mundo de las
  • Sobre Traversals...
    Topics Navigator  is a prototype model to experiment with some uses of graphs and hypergraphs for storing, recovering and analyzing connected information. Topics Navigator
  • Ejercicios NetLogo II
    Para comprobar que la realización de los siguientes ejericios es correcta se debe tener algún grafo creado en NetLogo, por ello se recomienda hacer todos en el mismo model
  • Sobre Traversals...
    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 arist

Etiquetas relacionadas

algoritmos, netlogo