Gráfico de líneas

Las propiedades de un grafo G que dependen únicamente de la adyacencia entre aristas pueden traducirse en propiedades equivalentes en L ( G ) que dependen de la adyacencia entre vértices. Por ejemplo, un emparejamiento en G es un conjunto de aristas, de las cuales no hay dos adyacentes, y corresponde a un conjunto de vértices en L ( G ), de los cuales no hay dos adyacentes, es decir, un conjunto independiente . ^{[ 4 ]}

De este modo,

• El grafo de líneas de un grafo conexo es conexo. Si G es conexo, contiene un camino que conecta cualesquiera dos de sus aristas, lo que se traduce en un camino en L ( G ) que contiene cualesquiera dos de los vértices de L ( G ) . Sin embargo, un grafo G que tiene algunos vértices aislados y, por lo tanto, es desconectado, puede tener un grafo de líneas conexo. ^{[ 5 ]}
• Un gráfico de líneas tiene un punto de articulación si y solo si el gráfico subyacente tiene un puente para el cual ninguno de los extremos tiene grado uno. ^{[ 2 ]}
• Para un grafo G con n vértices y m aristas, el número de vértices del grafo de líneas L ( G ) es m , y el número de aristas de L ( G ) es la mitad de la suma de los cuadrados de los grados de los vértices en G , menos m . ^{[ 6 ]}
• Un conjunto independiente en L ( G ) corresponde a un emparejamiento en G . En particular, un conjunto independiente máximo en L ( G ) corresponde a un emparejamiento máximo en G . Dado que los emparejamientos máximos se pueden encontrar en tiempo polinomial, también se pueden encontrar los conjuntos independientes máximos de grafos de líneas, a pesar de la dificultad del problema del conjunto independiente máximo para familias de grafos más generales. ^{[ 4 ]} De manera similar, un conjunto independiente arcoíris en L ( G ) corresponde a un emparejamiento arcoíris en G .
• El número cromático de aristas de un grafo G es igual al número cromático de vértices de su grafo de líneas L ( G ) . ^{[ 7 ]}
• El grafo de líneas de un grafo transitivo por aristas es transitivo por vértices . Esta propiedad se puede utilizar para generar familias de grafos que (como el grafo de Petersen ) son transitivos por vértices pero no son grafos de Cayley : si G es un grafo transitivo por aristas que tiene al menos cinco vértices, no es bipartito y tiene grados de vértice impares, entonces L ( G ) es un grafo no Cayley transitivo por vértices. ^{[ 8 ]}
• Si un grafo G tiene un ciclo euleriano , es decir, si G es conexo y tiene un número par de aristas en cada vértice, entonces el grafo de líneas de G es hamiltoniano . Sin embargo, no todos los ciclos hamiltonianos en grafos de líneas provienen de ciclos eulerianos de esta manera; por ejemplo, el grafo de líneas de un grafo hamiltoniano G es hamiltoniano en sí mismo, independientemente de si G también es euleriano. ^{[ 9 ]}
• Si dos grafos simples son isomorfos , entonces sus grafos de líneas también lo son. El teorema de isomorfismo de grafos de Whitney proporciona un recíproco para todos los pares de grafos conexos, excepto uno.
• En el contexto de la teoría de redes complejas , el grafo de líneas de una red aleatoria conserva muchas de las propiedades de la red, como la propiedad de mundo pequeño (la existencia de caminos cortos entre todos los pares de vértices) y la forma de su distribución de grados . ^{[ 10 ]} Evans y Lambiotte (2009) observan que cualquier método para encontrar grupos de vértices en una red compleja se puede aplicar al grafo de líneas y utilizarse para agrupar sus aristas.

Si los grafos de líneas de dos grafos conexos son isomorfos, entonces los grafos subyacentes son isomorfos, excepto en el caso del grafo triangular K ₃ y la garra K _1,3 , que tienen grafos de líneas isomorfos pero no son isomorfos entre sí. ^{[ 3 ]}

Además de K ₃ y K _1,3 , existen otros grafos pequeños excepcionales cuya propiedad es que su grafo de líneas posee un grado de simetría mayor que el del propio grafo. Por ejemplo, el grafo diamante K _1,1,2 (dos triángulos que comparten una arista) tiene cuatro automorfismos de grafo, pero su grafo de líneas K _1,2,2 tiene ocho. En la ilustración del grafo diamante mostrada, rotar el grafo 90 grados no es una simetría del grafo, sino de su grafo de líneas. Sin embargo, todos estos casos excepcionales tienen como máximo cuatro vértices. Una versión reforzada del teorema de isomorfismo de Whitney establece que, para grafos conexos con más de cuatro vértices, existe una correspondencia biunívoca entre los isomorfismos de los grafos y los isomorfismos de sus grafos de líneas. ^{[ 11 ]}

Se han demostrado análogos del teorema de isomorfismo de Whitney para los grafos de líneas de multigrafos , pero son más complicados en este caso. ^{[ 12 ]}

El gráfico de línea del gráfico completo K _n también se conoce como el gráfico triangular , el gráfico de Johnson J ( n , 2) , o el complemento del gráfico de Kneser KG _{n ,2} . Los gráficos triangulares se caracterizan por sus espectros , excepto para n = 8 . ^{[ 13 ]} También se pueden caracterizar (nuevamente con la excepción de K ₈ ) como los gráficos fuertemente regulares con parámetros srg( n ( n − 1)/2, 2( n − 2), n − 2, 4) . ^{[ 14 ]} Los tres gráficos fuertemente regulares con los mismos parámetros y espectro que L ( K ₈ ) son los gráficos de Chang , que se pueden obtener mediante el intercambio de gráficos desde L ( K ₈ ) .

El grafo de líneas de un grafo bipartito es perfecto (véase el teorema de Kőnig ), pero no necesariamente bipartito, como muestra el ejemplo del grafo de garra. Los grafos de líneas de grafos bipartitos forman uno de los bloques de construcción clave de los grafos perfectos, utilizados en la demostración del teorema del grafo perfecto fuerte . ^{[ 15 ]} Un caso especial de estos grafos son los grafos de torre , grafos de líneas de grafos bipartitos completos . Al igual que los grafos de líneas de grafos completos, se pueden caracterizar, con una excepción, por su número de vértices, número de aristas y número de vecinos compartidos para puntos adyacentes y no adyacentes. El único caso excepcional es L ( K _4,4 ) , que comparte sus parámetros con el grafo de Shrikhande . Cuando ambos lados de la bipartición tienen el mismo número de vértices, estos grafos son nuevamente fuertemente regulares. ^{[ 16 ]} Se ha demostrado que, excepto para C ₃ , C ₄ y C ₅ , todos los grafos fuertemente regulares conectados pueden hacerse no fuertemente regulares dentro de dos transformaciones de grafos de línea. ^{[ 17 ]} La extensión a grafos desconectados requeriría que el grafo no sea una unión disjunta de C ₃ .

En términos más generales, se dice que un grafo G es un grafo perfecto por líneas si L ( G ) es un grafo perfecto . Los grafos perfectos por líneas son precisamente aquellos que no contienen un ciclo simple de longitud impar mayor que tres. ^{[ 18 ]} De forma equivalente, un grafo es perfecto por líneas si y solo si cada uno de sus componentes biconexos es bipartito o de la forma K₄ (el tetraedro) o K₁ _{, ₁, ₙ} ​​(un libro de uno o más triángulos que comparten una arista común). ^{[ 19 ]} Todo grafo perfecto por líneas es en sí mismo perfecto. ^{[ 20 ]}

Todos los grafos de líneas son grafos libres de garras , grafos sin un subgrafo inducido en forma de árbol de tres hojas. ^{[ 21 ]} Al igual que con los grafos libres de garras en general, todo grafo de líneas conexo L ( G ) con un número par de aristas tiene un emparejamiento perfecto ; ^{[ 22 ]} equivalentemente, esto significa que si el grafo subyacente G tiene un número par de aristas, sus aristas se pueden particionar en caminos de dos aristas.

Los grafos de líneas de árboles son exactamente los grafos de bloques sin garras . ^{[ 23 ]} Estos grafos se han utilizado para resolver un problema en la teoría extremal de grafos , que consiste en construir un grafo con un número dado de aristas y vértices cuyo árbol más grande inducido como subgrafo sea lo más pequeño posible. ^{[ 24 ]}

Todos los valores propios de la matriz de adyacencia A de un grafo de líneas son al menos −2. La razón de esto es que A se puede escribir como${\displaystyle A=J^{\mathsf {T}}J-2I}$donde J es la matriz de incidencia sin signo del grafo prelineal e I es la identidad. En particular, A + 2 I es la matriz de Gram de un sistema de vectores: todos los grafos con esta propiedad se han denominado grafos lineales generalizados. ^{[ 25 ]}

Para un grafo arbitrario G y un vértice arbitrario v en G , el conjunto de aristas incidentes a v corresponde a una camarilla en el grafo de líneas L ( G ) . Las camarillas formadas de esta manera dividen las aristas de L ( G ) . Cada vértice de L ( G ) pertenece a exactamente dos de ellas (las dos camarillas correspondientes a los dos extremos de la arista correspondiente en G ).

La existencia de tal partición en camarillas puede usarse para caracterizar los grafos de línea: Un grafo L es el grafo de línea de algún otro grafo o multigrafo si y solo si es posible encontrar una colección de camarillas en L (permitiendo que algunas de las camarillas sean vértices individuales) que particionen las aristas de L , de tal manera que cada vértice de L pertenezca a exactamente dos de las camarillas. ^{[ 21 ]} Es el grafo de línea de un grafo (en lugar de un multigrafo) si este conjunto de camarillas satisface la condición adicional de que no haya dos vértices de L que estén en las mismas dos camarillas. Dada dicha familia de camarillas, el grafo subyacente G para el cual L es el grafo de línea puede recuperarse haciendo un vértice en G para cada camarilla, y una arista en G para cada vértice en L con sus extremos siendo las dos camarillas que contienen el vértice en L. Según la versión fuerte del teorema de isomorfismo de Whitney, si el grafo subyacente G tiene más de cuatro vértices, solo puede haber una partición de este tipo.

Por ejemplo, esta caracterización se puede utilizar para demostrar que el siguiente gráfico no es un gráfico de líneas:

En este ejemplo, las aristas que parten del vértice central de grado cuatro hacia arriba, a la izquierda y a la derecha no comparten ningún grupo. Por lo tanto, cualquier partición de las aristas del grafo en grupos tendría que tener al menos un grupo para cada una de estas tres aristas, y estos tres grupos se intersectarían en ese vértice central, lo que incumple el requisito de que cada vértice aparezca en exactamente dos grupos. En consecuencia, el grafo mostrado no es un grafo de líneas.

Otra caracterización de los grafos de líneas fue demostrada en Beineke (1970) (y reportada anteriormente sin demostración por Beineke (1968) ). Demostró que existen nueve grafos mínimos que no son grafos de líneas, de modo que cualquier grafo que no sea un grafo de líneas tiene uno de estos nueve grafos como subgrafo inducido . Es decir, un grafo es un grafo de líneas si y solo si ningún subconjunto de sus vértices induce uno de estos nueve grafos. En el ejemplo anterior, los cuatro vértices superiores inducen una garra (es decir, un grafo bipartito completo K _1,3 ), que se muestra en la parte superior izquierda de la ilustración de subgrafos prohibidos. Por lo tanto, según la caracterización de Beineke, este ejemplo no puede ser un grafo de líneas. Para grafos con grado mínimo de al menos 5, solo se necesitan los seis subgrafos de las columnas izquierda y derecha de la figura en la caracterización. ^{[ 26 ]}

Roussopoulos (1973) y Lehot (1974) describieron algoritmos de tiempo lineal para reconocer grafos de líneas y reconstruir sus grafos originales. Sysło (1982) generalizó estos métodos a grafos dirigidos . Degiorgi y Simon (1995) describieron una estructura de datos eficiente para mantener un grafo dinámico, sujeto a inserciones y eliminaciones de vértices, y mantener una representación de la entrada como un grafo de líneas (cuando existe) en un tiempo proporcional al número de aristas modificadas en cada paso.

Los algoritmos de Roussopoulos (1973) y Lehot (1974) se basan en caracterizaciones de grafos de líneas que involucran triángulos impares (triángulos en el grafo de líneas con la propiedad de que existe otro vértice adyacente a un número impar de vértices triangulares). Sin embargo, el algoritmo de Degiorgi y Simon (1995) utiliza únicamente el teorema de isomorfismo de Whitney. Se complica por la necesidad de reconocer eliminaciones que hacen que el grafo restante se convierta en un grafo de líneas, pero cuando se especializa al problema de reconocimiento estático, solo es necesario realizar inserciones, y el algoritmo realiza los siguientes pasos:

• Construye el grafo de entrada L añadiendo vértices uno a uno, eligiendo en cada paso un vértice adyacente a al menos un vértice añadido previamente. Mientras añades vértices a L , mantén un grafo G tal que L = L ( G ) ; si el algoritmo no encuentra un grafo G adecuado , entonces la entrada no es un grafo lineal y el algoritmo finaliza.
• Al añadir un vértice v a un grafo L ( G ) con cuatro o menos vértices , es posible que la representación mediante grafo de líneas no sea única. Sin embargo, en este caso, el grafo aumentado es lo suficientemente pequeño como para que se pueda encontrar su representación mediante una búsqueda exhaustiva en tiempo constante.
• Al agregar un vértice v a un grafo mayor L que es igual al grafo de líneas de otro grafo G , sea S el subgrafo de G formado por las aristas que corresponden a los vecinos de v en L. Verifique que S tenga una cobertura de vértices que consista en un vértice o dos vértices no adyacentes. Si hay dos vértices en la cobertura, aumente G agregando una arista (correspondiente a v ) que conecte estos dos vértices. Si solo hay un vértice en la cobertura, agregue un nuevo vértice a G , adyacente a este vértice.

Cada paso requiere un tiempo constante o implica encontrar una cobertura de vértices de tamaño constante dentro de un grafo S cuyo tamaño es proporcional al número de vecinos de v . Por lo tanto, el tiempo total del algoritmo es proporcional a la suma de los números de vecinos de todos los vértices, que (según el lema del apretón de manos ) es proporcional al número de aristas de entrada.

Cuando un grafo planar G tiene un grado máximo de vértice de tres, su grafo de líneas es planar, y toda incrustación planar de G puede extenderse a una incrustación de L ( G ) . Sin embargo, existen grafos planares de mayor grado cuyos grafos de líneas no son planares. Estos incluyen, por ejemplo, el grafo de 5 estrellas _K1,5 , el grafo gema formado al añadir dos diagonales que no se cruzan dentro de un pentágono regular, y todos los poliedros convexos con un vértice de grado cuatro o más. ^{[ 29 ]}

Una construcción alternativa, el grafo medial , coincide con el grafo de líneas para grafos planares con grado máximo tres, pero siempre es planar. Tiene los mismos vértices que el grafo de líneas, pero potencialmente menos aristas: dos vértices del grafo medial son adyacentes si y solo si las dos aristas correspondientes son consecutivas en alguna cara de la incrustación planar. El grafo medial del grafo dual de un grafo planar es el mismo que el grafo medial del grafo planar original. ^{[ 30 ]}

Para poliedros regulares o simples, la operación gráfica medial puede representarse geométricamente mediante la operación de cortar cada vértice del poliedro con un plano que pasa por los puntos medios de todas sus aristas incidentes. ^{[ 31 ]} Esta operación se conoce con diversos nombres, como segunda truncación, ^{[ 32 ]} truncación degenerada, ^{[ 33 ]} o rectificación . ^{[ 34 ]}

El grafo total T ( G ) de un grafo G tiene como vértices los elementos (vértices o aristas) de G , y tiene una arista entre dos elementos siempre que sean incidentes o adyacentes. El grafo total también se puede obtener subdividiendo cada arista de G y luego elevando al cuadrado el grafo subdividido. ^{[ 35 ]}

El concepto de grafo de líneas de G puede extenderse naturalmente al caso en que G sea un multigrafo. En este caso, las caracterizaciones de estos grafos pueden simplificarse: la caracterización en términos de particiones de cliques ya no necesita impedir que dos vértices pertenezcan al mismo clique, y la caracterización por grafos prohibidos tiene siete grafos prohibidos en lugar de nueve. ^{[ 36 ]}

Sin embargo, para los multigrafos, existen mayores cantidades de pares de grafos no isomorfos que tienen los mismos grafos de líneas. Por ejemplo, un grafo bipartito completo K _{1, n} tiene el mismo grafo de líneas que el grafo dipolar y el multigrafo de Shannon con el mismo número de aristas. No obstante, en este caso aún se pueden derivar análogos al teorema de isomorfismo de Whitney. ^{[ 12 ]}

También es posible generalizar los grafos de líneas a grafos dirigidos. ^{[ 37 ]} Si G es un grafo dirigido, su grafo de líneas dirigido o digrafo de líneas tiene un vértice por cada arista de G. Dos vértices que representan aristas dirigidas de u a v y de w a x en G están conectados por una arista de uv a wx en el digrafo de líneas cuando v = w . Es decir, cada arista en el digrafo de líneas de G representa un camino dirigido de longitud dos en G. Los grafos de De Bruijn se pueden formar repitiendo este proceso de formación de grafos de líneas dirigidos, partiendo de un grafo dirigido completo . ^{[ 38 ]}

En un grafo de líneas L ( G ) , cada vértice de grado k en el grafo original G crea k ( k -1)/2 aristas en el grafo de líneas. Para muchos tipos de análisis, esto significa que los nodos de alto grado en G están sobrerrepresentados en el grafo de líneas L ( G ) . Por ejemplo, consideremos un paseo aleatorio sobre los vértices del grafo original G. Este pasará por alguna arista e con alguna frecuencia f . Por otro lado, esta arista e se mapea a un único vértice, digamos v , en el grafo de líneas L ( G ) . Si ahora realizamos el mismo tipo de paseo aleatorio sobre los vértices del grafo de líneas, la frecuencia con la que se visita v puede ser completamente diferente de f . Si nuestra arista e en G estaba conectada a nodos de grado O ( k ) , se recorrerá O ( k² ) veces más frecuentemente en el grafo de ^líneas L ( G ) . Dicho de otro modo, el teorema de isomorfismo de grafos de Whitney garantiza que el grafo de líneas casi siempre codifica fielmente la topología del grafo original G , pero no garantiza que la dinámica en estos dos grafos tenga una relación simple. Una solución es construir un grafo de líneas ponderado, es decir, un grafo de líneas con aristas ponderadas . Hay varias maneras naturales de hacerlo. ^{[ 39 ]} Por ejemplo, si las aristas d y e en el grafo G inciden en un vértice v con grado k , entonces en el grafo de líneas L ( G ) a la arista que conecta los dos vértices d y e se le puede dar un peso de 1/( k − 1) . De esta manera, cada arista en G (siempre que ninguno de los extremos esté conectado a un vértice de grado 1) tendrá una fuerza de 2 en el grafo de líneas L ( G ) correspondiente a los dos extremos que la arista tiene en G . Es sencillo extender esta definición de un grafo de líneas ponderado a casos en los que el grafo original Gfue dirigido o incluso ponderado. ^{[ 40 ]} El principio en todos los casos es asegurar que el gráfico de línea L ( G ) refleje la dinámica así como la topología del gráfico original G .

Las aristas de un hipergrafo pueden formar una familia arbitraria de conjuntos , por lo que el grafo de líneas de un hipergrafo es el mismo que el grafo de intersección de los conjuntos de esa familia.

El grafo de disyunción de G , denotado D ( G ) , se construye de la siguiente manera: para cada arista en G , se crea un vértice en D ( G ) ; para cada par de aristas en G que no tienen un vértice en común, se crea una arista entre sus vértices correspondientes en D ( G ) . ^{[ 41 ]} En otras palabras, D ( G ) es el grafo complemento de L ( G ) . Una camarilla en D ( G ) corresponde a un conjunto independiente en L ( G ) , y viceversa.