En la disciplina matemática de la teoría de grafos , el grafo lineal de un grafo no dirigido G es otro grafo L( G ) que representa las adyacencias entre aristas de G . L( G ) se construye de la siguiente manera: para cada arista en G , haz un vértice en L( G ) ; para cada dos aristas en G que tengan un vértice en común, haz una arista entre sus vértices correspondientes en L( G ) .
El nombre gráfico lineal proviene de un artículo de Harary y Norman (1960), aunque tanto Whitney (1932) como Krausz (1943) utilizaron la construcción antes de esto. [1] Otros términos utilizados para el gráfico lineal incluyen el gráfico de cobertura , la derivada , el dual de arista a vértice , el conjugado , el gráfico representativo y el θ-obrazom , [1] así como el gráfico de arista , el gráfico de intercambio , el gráfico adjunto y el gráfico derivado . [2]
Hassler Whitney (1932) demostró que con un caso excepcional la estructura de un grafo conexo G puede ser recuperada completamente a partir de su grafo lineal. [3] Muchas otras propiedades de los grafos lineales se deducen traduciendo las propiedades del grafo subyacente de vértices a aristas, y por el teorema de Whitney la misma traducción también puede hacerse en la otra dirección. Los grafos lineales no tienen garras y los grafos lineales de grafos bipartitos son perfectos . Los grafos lineales se caracterizan por nueve subgrafos prohibidos y pueden reconocerse en tiempo lineal .
Se han estudiado varias extensiones del concepto de gráfico lineal, incluidos gráficos lineales de gráficos lineales, gráficos lineales de multigrafos, gráficos lineales de hipergrafos y gráficos lineales de gráficos ponderados.
Dado un grafo G , su grafo lineal L ( G ) es un grafo tal que
Es decir, es el gráfico de intersección de las aristas de G , representando cada arista 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 de la arista correspondiente en el gráfico original. Por ejemplo, el vértice verde de la derecha etiquetado 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 (que corresponden a las aristas que comparten el punto final 1 en el gráfico azul) y 4,3 (que corresponde a una arista que comparte el punto final 3 en el gráfico azul).
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, una correspondencia 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,
Si los gráficos lineales de dos gráficos conexos son isomorfos, entonces los gráficos subyacentes son isomorfos, excepto en el caso del gráfico triangular K 3 y la garra K 1,3 , que tienen gráficos lineales isomorfos pero no son isomorfos en sí mismos. [3]
Además de K 3 y K 1,3 , existen otros grafos pequeños excepcionales con la propiedad de que su grafo lineal tiene un grado de simetría mayor que el grafo mismo. Por ejemplo, el grafo de diamante K 1,1,2 (dos triángulos que comparten una arista) tiene cuatro automorfismos de grafo , pero su grafo lineal K 1,2,2 tiene ocho. En la ilustración del grafo de diamante que se muestra, rotar el grafo 90 grados no es una simetría del grafo, sino una simetría de su grafo lineal. 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 lineales. [11]
Se han demostrado análogos del teorema de isomorfismo de Whitney para los gráficos lineales de multigrafos , pero en este caso son más complicados. [12]
El gráfico lineal del grafo completo K n también se conoce como grafo triangular , grafo de Johnson J ( n , 2) o el complemento del grafo de Kneser KG n ,2 . Los grafos triangulares se caracterizan por sus espectros , excepto para n = 8. [ 13] También se pueden caracterizar (de nuevo con la excepción de K 8 ) como los grafos fuertemente regulares con parámetros srg( n ( n – 1)/2, 2( n – 2), n – 2, 4) . [14] Los tres grafos fuertemente regulares con los mismos parámetros y espectro que L ( K 8 ) son los grafos de Chang , que se pueden obtener mediante el cambio de grafo de L ( K 8 ) .
El gráfico lineal de un grafo bipartito es perfecto (véase el teorema de König ), pero no necesita ser bipartito como lo muestra el ejemplo del grafo de garra. Los gráficos lineales de grafos bipartitos forman uno de los bloques de construcción clave de los grafos perfectos, utilizados en la prueba del teorema del grafo perfecto fuerte . [15] Un caso especial de estos grafos son los grafos de torre , grafos lineales de grafos bipartitos completos . Al igual que los grafos lineales de grafos completos, se pueden caracterizar con una excepción por sus números de vértices, números 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]
En términos más generales, se dice que un grafo G es un grafo perfecto lineal si L ( G ) es un grafo perfecto . Los grafos perfectos lineales son exactamente los grafos que no contienen un ciclo simple de longitud impar mayor que tres. [17] De manera equivalente, un grafo es perfecto lineal si y solo si cada uno de sus componentes biconectados es bipartito o de la forma K 4 (el tetraedro) o K 1,1, n (un libro de uno o más triángulos que comparten un borde común). [18] Todo grafo perfecto lineal es en sí mismo perfecto. [19]
Todos los gráficos de líneas son gráficos sin garras , gráficos sin un subgrafo inducido en forma de un árbol de tres hojas. [20] Al igual que con los gráficos sin garras de manera más general, cada gráfico de línea conectado L ( G ) con un número par de aristas tiene una correspondencia perfecta ; [21] equivalentemente, esto significa que si el gráfico subyacente G tiene un número par de aristas, sus aristas se pueden dividir en caminos de dos aristas.
Los gráficos lineales de los árboles son exactamente los gráficos de bloques sin garras . [22] Estos gráficos se han utilizado para resolver un problema en la teoría de grafos extremales , de 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. [23]
Todos los valores propios de la matriz de adyacencia A de un grafo lineal son al menos −2. La razón de esto es que A puede escribirse como , 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 Gramiana de un sistema de vectores: todos los grafos con esta propiedad se han denominado grafos lineales generalizados. [24]
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 lineal L ( G ) . Las camarillas formadas de esta manera dividen las aristas de L ( G ) . Cada vértice de L ( G ) pertenece exactamente a dos de ellas (las dos camarillas correspondientes a los dos puntos extremos de la arista correspondiente en G ).
La existencia de tal partición en camarillas se puede utilizar para caracterizar los grafos lineales: Un grafo L es el grafo lineal 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 únicos) que dividan las aristas de L , de modo que cada vértice de L pertenezca exactamente a dos de las camarillas. [20] Es el grafo lineal de un grafo (en lugar de un multigrafo) si este conjunto de camarillas satisface la condición adicional de que no hay dos vértices de L en las mismas dos camarillas. Dada tal familia de camarillas, el grafo subyacente G para el cual L es el grafo lineal se puede recuperar haciendo un vértice en G para cada camarilla, y una arista en G para cada vértice en L con sus puntos finales 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 lineal:
En este ejemplo, las aristas que van hacia arriba, hacia la izquierda y hacia la derecha desde el vértice central de grado cuatro no tienen ninguna camarilla en común. Por lo tanto, cualquier partición de las aristas del grafo en camarillas tendría que tener al menos una camarilla para cada una de estas tres aristas, y estas tres camarillas se intersectarían en ese vértice central, violando el requisito de que cada vértice aparezca en exactamente dos camarillas. Por lo tanto, el grafo mostrado no es un grafo lineal.
Otra caracterización de los grafos lineales fue demostrada en Beineke (1970) (y reportada anteriormente sin prueba por Beineke (1968)). Él demostró que hay nueve grafos mínimos que no son grafos lineales, de modo que cualquier grafo que no sea un grafo lineal tiene uno de estos nueve grafos como subgrafo inducido . Es decir, un grafo es un grafo lineal 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, por la caracterización de Beineke, este ejemplo no puede ser un grafo lineal. Para grafos con un grado mínimo de al menos 5, solo los seis subgrafos en las columnas izquierda y derecha de la figura son necesarios en la caracterización. [25]
Roussopoulos (1973) y Lehot (1974) describieron algoritmos de tiempo lineal para reconocer gráficos de líneas y reconstruir sus gráficos originales. Sysło (1982) generalizó estos métodos a gráficos dirigidos . Degiorgi y Simon (1995) describieron una estructura de datos eficiente para mantener un gráfico dinámico, sujeto a inserciones y eliminaciones de vértices, y mantener una representación de la entrada como un gráfico de líneas (cuando existe) en el 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 lineales que involucran triángulos impares (triángulos en el grafo lineal con la propiedad de que existe otro vértice adyacente a un número impar de vértices de triángulos). Sin embargo, el algoritmo de Degiorgi & Simon (1995) utiliza únicamente el teorema de isomorfismo de Whitney. Es complicado por la necesidad de reconocer eliminaciones que hacen que el grafo restante se convierta en un grafo lineal, pero cuando se especializa al problema de reconocimiento estático solo se necesitan realizar inserciones, y el algoritmo realiza los siguientes pasos:
Cada paso lleva un tiempo constante o implica encontrar una cubierta de vértice 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 para todo el algoritmo es proporcional a la suma de los números de vecinos de todos los vértices, que (por el lema de handshaking ) es proporcional al número de aristas de entrada.
van Rooij y Wilf (1965) consideran la secuencia de gráficos
Muestran que, cuando G es un grafo conexo finito , sólo son posibles cuatro comportamientos para esta secuencia:
Si G no está conectado , esta clasificación se aplica por separado a cada componente de G.
Para gráficos conectados que no son caminos, todos los números suficientemente altos de iteraciones de la operación del gráfico lineal producen gráficos que son hamiltonianos. [27]
Cuando un grafo planar G tiene un grado máximo de vértice tres, su grafo lineal es planar, y cada incrustación planar de G puede extenderse a una incrustación de L ( G ) . Sin embargo, existen grafos planares con un grado mayor cuyos grafos lineales son no planares. Estos incluyen, por ejemplo, el grafo de 5 estrellas K 1,5 , el grafo de gema formado al agregar 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. [28]
Una construcción alternativa, el grafo medial , coincide con el grafo lineal para grafos planares con grado máximo tres, pero siempre es planar. Tiene los mismos vértices que el grafo lineal, 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 plana. El grafo medial del grafo dual de un grafo plano es el mismo que el grafo medial del grafo plano original. [29]
Para los poliedros regulares o simples, la operación del grafo medial se puede representar geométricamente mediante la operación de cortar cada vértice del poliedro por un plano que pase por los puntos medios de todas sus aristas incidentes. [30] Esta operación se conoce de diversas formas como segundo truncamiento, [31] truncamiento degenerado, [32] o rectificación . [33]
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 puede obtenerse subdividiendo cada arista de G y luego tomando el cuadrado del grafo subdividido. [34]
El concepto de grafo lineal 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 clique 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. [35]
Sin embargo, en el caso de los multigrafos, hay un mayor número de pares de grafos no isomorfos que tienen los mismos grafos lineales. Por ejemplo, un grafo bipartito completo K 1, n tiene el mismo grafo lineal 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 analogías al teorema de isomorfismo de Whitney. [12]
También es posible generalizar los grafos lineales a grafos dirigidos. [36] Si G es un grafo dirigido, su grafo lineal dirigido o digrafo lineal 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 dígrafo lineal cuando v = w . Es decir, cada arista en el dígrafo lineal de G representa una trayectoria dirigida de longitud dos en G . Los grafos de De Bruijn pueden formarse repitiendo este proceso de formación de grafos lineales dirigidos, comenzando a partir de un grafo dirigido completo . [37]
En un grafo lineal L ( G ) , cada vértice de grado k en el grafo original G crea k ( k − 1)/2 aristas en el grafo lineal. Para muchos tipos de análisis esto significa que los nodos de alto grado en G están sobrerrepresentados en el grafo lineal L ( G ) . Por ejemplo, considere un paseo aleatorio en los vértices del grafo original G . Este pasará a lo largo de alguna arista e con alguna frecuencia f . Por otro lado, esta arista e está mapeada a un vértice único, digamos v , en el grafo lineal L ( G ) . Si ahora realizamos el mismo tipo de paseo aleatorio en los vértices del grafo lineal, la frecuencia con la que se visita v puede ser completamente diferente de f . Si nuestra arista e en G estuviera conectada a nodos de grado O ( k ) , será atravesada O ( k 2 ) con mayor frecuencia en el grafo lineal L ( G ) . Dicho de otro modo, el teorema de isomorfismo del grafo de Whitney garantiza que el grafo lineal 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 lineal ponderado, es decir, un grafo lineal con aristas ponderadas . Hay varias formas naturales de hacer esto. [38] 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 lineal L ( G ) la arista que conecta los dos vértices d y e puede tener un peso de 1/( k − 1) . De esta manera, cada arista en G (siempre que ninguno de sus extremos esté conectado a un vértice de grado 1) tendrá una fuerza 2 en el grafo lineal L ( G ) correspondiente a los dos extremos que tiene la arista en G. Es sencillo extender esta definición de un grafo lineal ponderado a los casos en los que el grafo original G estaba dirigido o incluso ponderado. [39] El principio en todos los casos es garantizar que el gráfico lineal L ( G ) refleje la dinámica así como la topología del gráfico original G .
Los bordes de un hipergrafo pueden formar una familia arbitraria de conjuntos , por lo que el gráfico lineal de un hipergrafo es el mismo que el gráfico de intersección de los conjuntos de la familia.
El grafo de disjunción de G , denotado D ( G ) , se construye de la siguiente manera: para cada arista en G , haz un vértice en D ( G ) ; para cada dos aristas en G que no tengan un vértice en común, haz una arista entre sus vértices correspondientes en D ( G ) . [40] En otras palabras, D ( G ) es el grafo complementario de L ( G ) . Una camarilla en D ( G ) corresponde a un conjunto independiente en L ( G ) , y viceversa.
, existe una correspondencia uno a uno entre las correspondencias de un gráfico y los conjuntos independientes de su gráfico lineal.
