Ves esta página sin formato porque esta hecha cumpliendo el estándar web CSS 2.
Tu navegador no soporta este estándar, o tienes dicho soporte desactivado.
si estas en el primer caso, actualízate. merece mucho la pena.

Una aventura personal hacia las redes complejas.


Inicio > Historias > Saliendo al ruedo: Grafos y red

2005-08-01

Saliendo al ruedo: Grafos y red

Por malambo en Invariancia.Matemáticas | 2005-08-01


En los trabajos actuales existen muchas definiciones de los conceptos de grafo y red. Muchas coinciden más o menos y otras menos. Las diferencias generalmente no son esenciales y están dadas por el contexto en el que se aplican.

Luciano da Fontoura Costa, por ejemplo, en A Generalized Approach to Complex Networks, define una red G (con G de grafo) sin conectores múltiples como una estructura discreta de un conjunto de nodos V(G) y un conjunto E(G) de conectores (u, v) establecidos entre pares específicos de nodos de V(G), tal que la red es representada como G = (V, E).

Sin embargo, para quienes están más interesados por la evolución estadística de sistemas concretos representables por redes, la de Costa es una elegante definición de grafo, no de red. Es preferible definir a esta última como un ensemble (conjunto estadístico) de grafos.

Muchos de los que estudian la evolución estadística de las redes (mira el recuadro de arXiv en la barra lateral) en algún momento utilizaron esta herramienta. Pero hablar de ensembles implica asignarle un puntaje o ponderación a cada grafo que pueda generarse a partir de un conjunto de nodos y como para eso hace falta un poco más de cuidado lo voy a dejar para una próxima entrada.

Ahora, que para eso estoy acá, voy a salir al ruedo con una definición mía de grafo. No busques originalidad porque no la hay. Lo que hay es una definición elaborada con vistas a próximas aplicaciones (por lo tanto puede que la tenga que corregir).

Grafo extendido

Sean N y E dos conjuntos disjuntos de nodos, C un conjunto de conectores <i, j> en el que al menos uno de los elementos del par es el índice de un nodo de N. Llamamos grafo extendido al par Ge = <N, C>.
Al conjunto E lo llamaré entorno de N y también voy a decir que los nodos con índices i y j son partícipes del conector <i, j>.






Grafo Los círculos celestes representan nodos del conjunto N y los amarillos del entorno E. Los segmentos de color violeta repersentan conectores pertenecientes a la endoestructura D mientras que los turquesa a la exoestructura X; los grises, que unen elementos del entorno, quedan fuera de estudio.

Endoestructura

Se llama endoestructura D del grafo extendido Ge al subconjunto de C formado por conectores <i, j> tales que los nodos indicados con i y j pertenecen a N.


Exoestructura

La exoestructura del grafo extendido Ge es el conjunto X = CD.


img. Grafo

Grafo

Un grafo es el par G = <N, D>.
Un grafo es dirigido si y sólo si D es un conjunto de conectores dirigidos.


Frontera

La frontera de G es el grafo F = <N, X>.




2005-08-01 19:52 | 0 Comentarios


Referencias (TrackBacks)

URL de trackback de esta historia http://invariancia.blogalia.com//trackbacks/32059

Comentarios

Nombre
Correo-e
URL
Dirección IP: 54.234.247.118 (9bcb52b9fd)
Comentario
¿Cuánto es: mil + uno?

portada | subir

(CC) 2005-2006 - malambo