- 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:
- cada vértice de L(G) representa una arista de G; y
- 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).
-
Grado G
-
Vértices en L(G) construidas desde aristas en G
-
Aristas añadidas en L(G)
-
El grafo línea L(G)
Referencias
- ↑ Hemminger y Beineke (1978, pp. 273); Balakrishnan (1997, p. 44).
- ↑ Hemminger y Beineke (1978, p. 273).
- ↑ Whitney, H. (1932), «Congruent graphs and the connectivity of graphs», American Journal of Mathematics 54 (1): 150–168, doi:, http://jstor.org/stable/2371086
Enlaces externos
Categoría:- Familias de grafos
Wikimedia foundation. 2010.
