Gráfico de líneas
En la disciplina matemática de la teoría de grafos , el gráfico lineal de un gráfico no dirigido G es otro gráfico L ( G ) que representa las adyacencias entre los bordes de G. L ( G ) se construye de la siguiente manera: para cada borde en G , haga un vértice en L ( G ); por cada dos aristas en G que tengan un vértice en común, haga una arista entre sus vértices correspondientes en L ( G ).
El nombre del gráfico de líneas proviene de un artículo de Harary y Norman (1960), aunque tanto Whitney (1932) como Krausz (1943) utilizaron la construcción antes de este. [1] Otros términos utilizados para el gráfico de líneas incluyen el gráfico de cobertura , la derivada , el dual de borde a vértice , el conjugado , el gráfico representativo y el ϑ-obrazom , [1] así como el gráfico de borde , el gráfico de intercambio , gráfico adjunto y gráfico derivado . [2]
Hassler Whitney ( 1932 ) demostró que, en un caso excepcional, la estructura de un gráfico conectado G puede recuperarse completamente de su gráfico lineal. [3] Se siguen muchas otras propiedades de los gráficos de líneas al traducir las propiedades del gráfico subyacente de los vértices a los bordes, y según el teorema de Whitney, la misma traducción también se puede hacer en la otra dirección. Los gráficos de líneas no tienen garras y los gráficos de líneas de los gráficos bipartitos son perfectos . Los gráficos de líneas se caracterizan por nueve subgráficos prohibidos y pueden reconocerse en tiempo lineal .
Se han estudiado varias extensiones del concepto de gráfico de líneas, incluidos gráficos de líneas de gráficos de líneas, gráficos de líneas de gráficos múltiples, gráficos de líneas de hipergráficos y gráficos de líneas de gráficos ponderados.
Es decir, es el gráfico de intersección de los bordes de G , que representa cada borde por el conjunto de sus dos puntos finales. [2]
Las siguientes figuras muestran un gráfico (izquierda, con vértices azules) y su gráfico lineal (derecha, con vértices verdes). Cada vértice del gráfico lineal se muestra etiquetado con el par de puntos finales del borde correspondiente en el gráfico original. Por ejemplo, el vértice verde de la derecha con la etiqueta 1,3 corresponde al borde 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 los bordes que comparten el punto final 1 en el gráfico azul) y 4,3 (correspondiente a un borde que comparte el punto final 3 en el gráfico azul).
