Grafo línea

En teoría de grafos, el grafo línea, de línea, lineal o representativo​ 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.​

Uno de los primeros y más importantes teoremas sobre grafos de línea se debe a Hassler Whitney,​ quien demostró que, a excepción de un caso especial, la estructura de un grafo conexo G siempre puede ser restablecida completamente a partir de su grafo línea. En otras palabras, con una única excepción, un grafo conexo siempre puede ser obtenido si conocemos las adyacencias de sus aristas (líneas).

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).

• 
  Grafo G
• 
  Vértices en L(G) construidas desde aristas en G
• 
  Aristas añadidas en L(G)
• 
  El grafo línea L(G)

Enlaces externos

• line graphs, Information System on Graph Classes and their Inclusions .

• Datos: Q1378376