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 = C – D.
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
