Grafo línea

Grafo línea

En teoría de grafos, el grafo línea, de línea, lineal o representativo[1] L(G) de un grafo no dirigido G es un grafo que representa las adyacencias entre las aristas de G.

Su nombre se debe a un artículo de Harary y Norman (1960), aunque tanto Whitney (1932) como Krausz (1943) los definieron antes.[2]

Uno de los primeros y más importantes teoremas sobre grafos de línea se debe a Hassler Whitney,[3] quien demostró que con un caso excepcional la estructura del grafo G puede ser recuperada completamente desde su grafo línea. En otras palabras, con una excepción, el grafo entero puede ser deducido si conocemos las adyacencias de sus aristas (líneas).

Contenido

Definición formal

Dado un grafo G, su grafo línea L(G) es el grafo que cumple estas dos condiciones:

  1. cada vértice de L(G) representa una arista de G; y
  2. dos vértices de L(G) son adyacentes si y sólo si sus aristas correspondientes comparten un punto final en común (es decir, son adyacentes) en G.

En otras palabras, el grafo línea es el grafo de intersección de las aristas de G, representando cada arista por el conjunto de sus dos puntos finales.

Ejemplo

La siguiente figura muestra un grafo (a la izquierda, con vértices azules) y su grafo línea (derecha, con vértices verdes). Cada vértice del grafo línea está etiquetado con el par de nodos finales de la correspondiente arista en el grafo original. Por ejemplo, el vértice verde en la derecha etiquetado como 1,3 corresponde a la arista de la izquierda entre los vértices azules 1 y 3. El vértice verde 1,3 es adyacente a otros tres vértices verdes: 1,4 y 1,2 (correspondientes a aristas que comparten el nodo final 1 en el grafo azul) y 4,3 (correspondiente a una arista compartiendo el nodo final 3 en el grafo azul).

Referencias

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Mira otros diccionarios:

  • Grafo autocomplementario — El estilo de esta traducción aún no ha sido revisado por terceros. Si eres hispanohablante nativo y no has participado en esta traducción puedes colaborar revisando y adaptando el estilo de ésta u otras traducciones ya acabadas …   Wikipedia Español

  • Línea de tiempo de lenguajes de programación — Esta es una línea de tiempo, una cronología de lenguajes de programación. Leyenda: (Entrada ) significa un lenguaje de programación no universal * <AÑO> significa un lenguaje original (sin antecesor directo) ==Enlaces externos== ● Diagrama… …   Enciclopedia Universal

  • Ciclo euleriano — Un ciclo euleriano es aquel camino que recorre todas las aristas de un grafo pasando una y sólo una vez por cada arco (arista) del grafo, siendo condición necesaria que regrese al vértice inicial de salida (ciclo = camino en un grafo donde… …   Wikipedia Español

  • Coloración de grafos — Una vértice coloración propia del grafo de Petersen con 3 colores, el número mínimo posible. En Teoría de grafos, la coloración de grafos es un caso especial de etiquetado de grafos; es una asignación de etiquetas llamadas colores a elementos del …   Wikipedia Español

  • Red semántica — Saltar a navegación, búsqueda Un ejemplo de red semántica Una red semántica o esquema de representación en Red es una forma de representación de conocimiento lingüístico en la que los conceptos y sus interrelaciones se representan mediante un… …   Wikipedia Español

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Algoritmo Húngaro — Saltar a navegación, búsqueda EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue… …   Wikipedia Español

  • Algoritmo húngaro — EL algoritmo Húngaro es un algoritmo de optimización el cual resuelve problemas de asignación en tiempo . La primera versión conocida del método Húngaro, fue inventado y publicado por Harold Kuhn en 1955. Este fue revisado por James Munkres en… …   Wikipedia Español

  • Vector propio y valor propio — Fig. 1. En esta transformación de la Mona Lisa, la imagen se ha deformado de tal forma que su eje vertical no ha cambiado. (nota: se han recortado las esquinas en la imagen de la derecha) …   Wikipedia Español

  • Algoritmo de Prim — El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas. En otras palabras, el algoritmo encuentra un subconjunto de… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”