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: 'netlogo'

Entradas en este sitio con 'netlogo'

  • NetLogo: Interfaz Gráfica
    Añadir elementos Finalidad y Parámetros Button Slider Switch Chooser Input Monitor Plot Output Note Además de un lenguaje de programación natural y fácil, una de las grand
  • NetLogo: Procedimientos Anónimos, Iteración en Listas
    Procedimientos Anónimos Primitivas de Procedimientos Anónimos Parámetros de entrada Listas Iteraciones sobre listas Listas de agentes Cómo trabajar sobre una lista de Agen
  • NetLogo: Conjuntos de Agentes, Procedimientos, Variables y Listas
    Agentes Conjuntos de Agentes Procedimientos Procedimientos con entrada Procedimientos con devolución Variables Definir variables Lectura y modificación Variables Locales L
  • NetLogo: Conceptos Básicos
    ¿Qué es NetLogo? Conceptos Básicos Agentes Variables Conjuntos de Agentes y Funciones Conjuntos de agentes Estructuras de control Especies Rutinas y funciones Experimentos
  • 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
  • Usando Patches de NetLogo para modelar Autómatas Celulares
    Gracias a la similitud existente entre la distribución topológica de los patches que forman el mundo bidimensional de NetLogo y la distribución de las celdas de un autómat
  • Cuadernos del CIS: Simulación basada en agentes. Introducción a Netlogo
    Ha salido ya el nuevo libro en español sobre NetLogo, de García-Valdecasas , orientado a disciplinas relacionadas con Ciencias Sociales. Se ha publicado dentro de la seria
  • Programming Mathematical Models ... with NetLogo
    This post has the goal to serve as guide for the session  "Programming Mathematical Models ... with NetLogo"  from the  5th International Summer School of Mathematics  in
  • Classical elements in NetLogo: Fire
    Following with the simulation of Classical Elements in NetLogo , and after Earth and Water , we will address in this post how to simulate some fire features, but taking in
  • Classical elements in NetLogo: Water
    After  Earth , and to continue with the simulation of Classical Elements in NetLogo , in this post we will give some simple, but very graphical and good looking, models to
  • Classical elements in NetLogo: Earth
    With this post we begin a series of posts that aim to simulate the creation and behavior of the 4 classic elements of nature in NetLogo: Earth, Water, Fire and Air. In thi
  • Self Organizing Maps (SOM) in NetLogo
    In this post we present how to implement Self Organizing Maps (Kohonen, 1992) in NetLogo. Specifically, we will implement two versions, a first introduction example to pro
  • Artificial Neural Networks in NetLogo
    As a way to continue with AI algorithms implemented in  NetLogo , in this post we will see how we can make a simple model to investigate about Artificial Neural Networks (
  • Local Search Algorithms in NetLogo
    In this post we will see implementations of a couple of methods that, starting from initial states, will search in the state space by local moves that take us closer to th
  • A General A* Solver in NetLogo
    Among the different search algorithms that make use of partial information by using heuristics, the most famous is the A* algorithm, and in this post we will present sever
  • A general BFS Solver in NetLogo
    In this post we will provide an agent based model that solves BFS in a generic way (as generic as it can be done with a standard  NetLogo  programming style). For that, we
  • NetLogo: Una herramienta de modelado / A Modeling Tool
      Ya está disponible el nuevo libro de modelado con NetLogo, con versiones en inglés y español, con el que podrás aprender desde los fundamentos del lenguaje hasta concept
  • Ejercicios de Algoritmos Genéticos
    Aplica adecuadamente un procedimiento basado en Algoritmos Genéticos para resolver el problema del viajante. Resuelve el problema de las 8 reinas con un Algoritmo Genético
  • Llegan las Jornadas Forma'15
    Por tercer año consecutivo, se celebrarán las  Jornadas FORMA  en la Universidad de Sevilla, fruto de la colaboración del departamento de  Ciencias de la Computación e Int
  • Aprendizaje por refuerzo: algoritmo Q Learning
    En entradas anteriores destacábamos dos tipos principales de aprendizaje automático: por una parte, el Aprendizaje Supervisado , y por otra el Aprendizaje no Supervisado .
  • Jornadas FORMA'14
    Por segundo año, y tras el éxito de la convocatoria del año pasado, se celebrarán las Jornadas FORMA en la Universidad de Sevilla, fruto de la colaboración del departament
  • Optimización en el espacio de parámetros de un modelo
    Uno de los problemas más habituales cuando se construye un modelo para simular un proceso es que, tras haber definido un buen número de parámetros para darle más flexibili
  • Redes Neuronales: una visión superficial
    Una Red Neuronal Artificial ( RNA ) es un modelo matemático inspirado en el comportamiento biológico de las neuronas y en cómo se organizan formando la estructura del cere
  • Algoritmos de hormigas y el problema del viajante
    Los Algoritmos de Hormigas son  una metodología inspirada en el  comportamiento colectivo  de las hormigas en su búsqueda de alimentos. Se debe recordar que las hormigas s
  • PSO: Optimización por enjambres de partículas
    La  Optimización por Enjambres de Partículas  (conocida como  PSO , por sus siglas en inglés,  Particle swarm optimization ) es una técnica de optimización/búsqueda en el
  • Jornadas FORMA
    Las jornadas FORMA son una iniciativa que busca acercar algunas herramientas se simulación a colectivos de múltiples ámbitos (sociales, biológicos, ambientales, económicos
  • Sobre el modelado matemático
    De entre todas las opciones para crear modelos, la del modelado matemático destaca sobre las demás por su eficacia y buenas propiedades. Se presenta bajo formas tan dispar
  • Curso MOOC de NetLogo en Difundi
    Ya ha comenzado el curso MOOC de NetLogo dentro de la plataforma Difundi .    NetLogo  es una plataforma para la simulación y modelado de sistemas dinámicos por medio de s
  • Mapas semánticos: clasificación y representación
    El problema de la clasificación de objetos es, a grandes rasgos, uno de los problemas centrales de la investigación y donde, quizás de forma más clara, podemos observar la
  • Clustering por K-medias
     El  algoritmo de las K-medias  (presentado por MacQueen en 1967) es uno de los algoritmos de aprendizaje no supervisado más simples para resolver el problema de la  clust
  • Algoritmo A*
    El algoritmo de búsqueda A* se clasifica dentro de estos algoritmos de búsqueda informada. Fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bert
  • 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
  • Self Organizing Maps
    Los Self Organizing Feature Maps (Mapas de Características Auto-organizativos), o SOM, fueron inventados por Teuvo Kohonen, profesor de la Academia de Finlandia, y proporc
  • Algoritmo ID3
    Los algoritmos de árboles de decisión construyen modelos de regresión o clasificación en forma de estructura de árbol. Habitualmente, dividen el conjunto de datos en conju
  • Ejercicios de Búsqueda no Informada
    Muchos de los ejercicios que se plantean a continuación se pueden (y deben) resolver por diversos procedimientos de búsqueda, por lo que se propone que, a medida que se va
  • Espacios de estados
    Sin lugar a dudas, una de las principales características de la inteligencia es su capacidad para resolver problemas. Si consideramos una inteligencia como la humana, adem
  • 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
  • Ejercicios NetLogo I
    1.- Propagación de fuego por un tereno : En este modelo haremos uso únicamente de los patches. La idea es analizar cómo influye la densidad de madera seca en el terreno pa
  • NetProLogo = NetLogo + Prolog
     Por fin nos hemos decidido y la extensión de NetLogo que preparó Juan Galán para poder ejecutar intérpretes de Prolog desde NetLogo tiene su propia página y está disponib
  • 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, grafos