Graphs - Grafos (matrices)

graphs - Grafos

 Representaciones matriciales

Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo. , 26 Febrero 2013


 

 

  • 0003.gn
  • Referencias Google: EN: 117.000.000; ES: 3.810.000, a Febrero 25 2013;
  • Autoridades:
  • 1. graphs, según Wikipedia
  • 2. digraphs, según Wikipedia
  • 3. graph_glossary, según Wikipedia

 

Descripción

Los grafos son estructuras formadas por un conjunto finito de “nodos” o “vértices” (entes, objetos, normalmente representados por círculos) relacionados geométricamente entre sí mediante aristas o arcos. El nombre de vértice posiblemente haya surgido de “mirador”, es decir un lugar desde el cual puede observarse no solo la estructura a la cual se pertenece sino a todo lo que la rodea. Las unidades superiores nodos y arcos y mediante las cuales puede definirse a un grafo en detalle son los “pares ordenados” (a, b) que indican el par que va del nodo a al nodo b.  

Las preguntas que podemos hacernos acerca de cualquier grafo G y sus respuestas serían:

Nodos:

  • Adyacencia [G, a, b] que tendrá como respuesta un Sí o un NO;
  • Vecindad [G, a]: listado de nodos que están conectados en forma directa al nodo (a);
  • Contenido del nodo [G, a]: devuelve o muestra el contenido asociado al nodo (a);
  • Contenido del nodo [G, a, b]: asigna el contenido del nodo (a) al nodo (b);

Nota: luego veremos cómo en función de la representación se agregan o borran nodos.

Arcos:

  • Relación del arco [G, a, b]: muestra la relación del arco que va de nodo (a) a nodo (b);
  • Asigna Relación del arco [G, a, b, c]: asigna la relación del arco que va de nodo (a) a nodo (b) a nodo (c);

Tipos de Representación de Grafos:

Como Matriz de Adyacencias: La forma convencional y fundamentalmente histórica de representarlos es mediante matrices bidimensionales binarias denominadas Matrices de Adyacencias.Veamos las matrices correspondientes a los dos grafos de arriba: el de la derecha un grafo direccionado o “dígrafo” y el de la izquierda en el que el sentido no afecta. Este tipo de representación abstracta es además muy claro y elegante pero muy poco práctico para el manejo de grandes matrices de adyacencia como las dables en encontrar en Internet de miles a millones de nodos, por diversas razones pero fundamentalmente porque el espacio de memoria necesario es proporcional al cuadrado de la cantidad de nodos y porque el agregado o borre de un nodo involucra copia y rearmado total de la matriz.

Como Matriz de Incidencias: otra forma de representación matricial en la que en las filas están los nodos y en las columnas los arcos. Para los dos casos de nuestro ejemplo hemos generado sus correspondientes matrices de incidencias. Para grafos direccionados hay que diferenciar el arco saliente del entrante, en forma arbitraria, aunque habitualmente se opta por (-1) para arco saliente, (1) para entrante y (0) para inexistencia. Hemos agregado en rojo algunos controles de coherencia básica, tales que todo arco sólo debe conectar a dos nodos o que cada arco de un grafo direccionado debe salir de un nodo (-1) para entrar a otro (1) dando suma cero para todas las columnas de la matriz.

Metadata

ES: [representaciones matriciales,matriz de incidencia,matriz de adyacencia,matrrices booleanas,nodos, vértices,pares ordenados,dígrafos]

EN: [matricial representation,incidence matrices,adyacence matrices,boolean matrices,ordered pairs, ordered pair,digraphs,vertex, nodes]

Additional information