Grafo línea
De Wikipedia, la enciclopedia encyclopedia
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, 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).