En la disciplina matemática de la teoría de grafos , la gráfica lineal de un gráfico no dirigido G es otra gráfica L( G ) que representa las adyacencias entre aristas de G. L( G ) se construye de la siguiente manera: para cada arista 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 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 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 bordes , el gráfico de intercambio , el gráfico adjunto y el gráfico derivado . [2]
Hassler Whitney (1932) demostró que, en un caso excepcional, la estructura de un gráfico conexo G se puede recuperar completamente a partir de su gráfico lineal. [3] Muchas otras propiedades de los gráficos lineales se derivan de la traducción de las propiedades del gráfico subyacente de los vértices a las aristas, y según el teorema de Whitney, la misma traducción también se puede realizar 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 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 gráfico G , su gráfico lineal L ( G ) es un gráfico tal que
Es decir, es la gráfica de intersección de las aristas de G , representando cada arista por el conjunto de sus dos puntos finales. [2]
Las siguientes figuras muestran una gráfica (izquierda, con vértices azules) y su gráfica 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 etiquetado como 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 aristas que comparten el punto final 1 en el gráfico azul) y 4,3 (correspondiente a una arista que comparte el punto final 3 en el gráfico azul).
Las propiedades de un gráfico 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 coincidencia 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 conectados son isomórficos, entonces los gráficos subyacentes son isomórficos, excepto en el caso del gráfico triangular K 3 y la garra K 1,3 , que tienen gráficos lineales isomórficos pero no son isomórficos en sí mismos. [3]
Además de K 3 y K 1,3 , existen otros gráficos pequeños excepcionales con la propiedad de que su gráfico lineal tiene un mayor grado de simetría que el gráfico mismo. Por ejemplo, el gráfico de diamante K 1,1,2 (dos triángulos que comparten una arista) tiene cuatro automorfismos de gráfico , pero su gráfico de líneas K 1,2,2 tiene ocho. En la ilustración del gráfico de diamantes que se muestra, girar el gráfico 90 grados no es una simetría del gráfico, sino una simetría de su gráfico lineal. Sin embargo, todos estos casos excepcionales tienen como máximo cuatro vértices. Una versión reforzada del teorema del isomorfismo de Whitney establece que, para gráficos conectados con más de cuatro vértices, existe una correspondencia uno a uno entre los isomorfismos de los gráficos y los isomorfismos de sus gráficos lineales. [11]
Se han demostrado análogos del teorema del isomorfismo de Whitney para los gráficos lineales de multigrafos , pero en este caso son más complicados. [12]
La gráfica lineal de la gráfica completa K n también se conoce como gráfica triangular , gráfica de Johnson J ( n , 2) , o complemento de la gráfica de Kneser KG n ,2 . Los gráficos triangulares se caracterizan por sus espectros , excepto n = 8 . [13] También pueden caracterizarse (nuevamente con la excepción de K 8 ) como 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 8 ) son los gráficos de Chang , que se pueden obtener cambiando el gráfico desde L ( K 8 ) .
La gráfica lineal de una gráfica bipartita es perfecta (ver el teorema de Kőnig ), pero no necesita ser bipartita como muestra el ejemplo de la gráfica de garras. Las gráficas lineales de las gráficas bipartitas forman uno de los componentes clave de las gráficas perfectas, utilizadas en la prueba del teorema del grafo perfecto fuerte . [15] Un caso especial de estas gráficas son las gráficas de torre , gráficas lineales de gráficas bipartitas completas . Al igual que los gráficos lineales de los gráficos 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 gráfico de Shrikhande . Cuando ambos lados de la bipartición tienen el mismo número de vértices, estas gráficas vuelven a ser fuertemente regulares. [dieciséis]
De manera más general, se dice que una gráfica G es una gráfica lineal perfecta si L ( G ) es una gráfica perfecta . Las gráficas lineales perfectas son exactamente las gráficas que no contienen un ciclo simple de longitud impar mayor que tres. [17] De manera equivalente, una gráfica es recta perfecta si y sólo 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] Cada gráfico lineal perfecto es en sí mismo perfecto. [19]
Todos los gráficos lineales son gráficos sin garras , gráficos sin subgrafo inducido en forma de árbol de tres hojas. [20] Al igual que con los gráficos sin garras en general, cada gráfico lineal conectado L ( G ) con un número par de aristas tiene una coincidencia perfecta ; [21] de manera equivalente, 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 extremos , de construir un gráfico 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 gráfico lineal son al menos −2. La razón de esto es que A se puede escribir como , donde J es la matriz de incidencia sin signos del gráfico prelineal e I es la identidad. En particular, A + 2 I es la matriz de Gramian de un sistema de vectores: todas las gráficas con esta propiedad se han llamado gráficas lineales generalizadas. [24]
Para un gráfico arbitrario G y un vértice arbitrario v en G , el conjunto de aristas incidentes en v corresponde a una camarilla en el gráfico lineal L ( G ) . Las camarillas formadas de esta manera dividen los bordes de L ( G ) . Cada vértice de L ( G ) pertenece exactamente a dos de ellos (las dos camarillas correspondientes a los dos puntos finales del borde correspondiente en G ).
La existencia de tal partición en camarillas se puede utilizar para caracterizar los gráficos lineales: Un gráfico L es el gráfico lineal de algún otro gráfico o multigrafo si y sólo si es posible encontrar una colección de camarillas en L (permitiendo algunas de las camarillas para ser vértices únicos) que dividen los bordes de L , de modo que cada vértice de L pertenece exactamente a dos de las camarillas. [20] Es el gráfico lineal de un gráfico (en lugar de un multigrafo) si este conjunto de camarillas satisface la condición adicional de que no hay dos vértices de L que estén en las mismas dos camarillas. Dada una familia de camarillas de este tipo, el gráfico subyacente G para el cual L es el gráfico lineal se puede recuperar haciendo un vértice en G para cada camarilla, y un borde en G para cada vértice en L , siendo sus puntos finales los dos camarillas que contienen el vértice en L . Según la versión fuerte del teorema de isomorfismo de Whitney, si el gráfico subyacente G tiene más de cuatro vértices, sólo puede haber una partición de este tipo.
Por ejemplo, esta caracterización se puede utilizar para mostrar que el siguiente gráfico no es un gráfico lineal:
En este ejemplo, los bordes que van hacia arriba, hacia la izquierda y hacia la derecha desde el vértice central de grado cuatro no tienen camarillas en común. Por lo tanto, cualquier partición de los bordes del gráfico en camarillas tendría que tener al menos una camarilla para cada uno de estos tres bordes, y estas tres camarillas se cruzarían en ese vértice central, violando el requisito de que cada vértice aparezca exactamente en dos camarillas. Por lo tanto, el gráfico que se muestra no es un gráfico lineal.
Otra caracterización de los gráficos lineales fue probada en Beineke (1970) (e informada anteriormente sin pruebas por Beineke (1968)). Demostró que hay nueve gráficos mínimos que no son gráficos lineales, de modo que cualquier gráfico que no sea un gráfico lineal tiene uno de estos nueve gráficos como subgrafo inducido . Es decir, una gráfica es una gráfica lineal si y sólo si ningún subconjunto de sus vértices induce una de estas nueve gráficas. En el ejemplo anterior, los cuatro vértices superiores inducen una garra (es decir, un gráfico 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 gráfico lineal. Para gráficos con un grado mínimo de al menos 5, solo se necesitan en la caracterización los seis subgrafos en las columnas izquierda y derecha de la figura. [25]
Roussopoulos (1973) y Lehot (1974) describieron algoritmos de tiempo lineal para reconocer gráficos lineales 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 lineal (cuando existe) en el tiempo proporcional al número de aristas cambiadas en cada paso.
Los algoritmos de Roussopoulos (1973) y Lehot (1974) se basan en caracterizaciones de gráficos lineales que involucran triángulos impares (triángulos en el gráfico lineal con la propiedad de que existe otro vértice adyacente a un número impar de vértices del triángulo). Sin embargo, el algoritmo de Degiorgi y Simon (1995) utiliza únicamente el teorema de isomorfismo de Whitney. Es complicado por la necesidad de reconocer eliminaciones que hacen que el gráfico restante se convierta en un gráfico de líneas, pero cuando se especializa en el problema de reconocimiento estático solo es necesario realizar inserciones y el algoritmo realiza los siguientes pasos:
Cada paso requiere un tiempo constante o implica encontrar una cobertura de vértice de tamaño constante dentro de un gráfico 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 del número de vecinos de todos los vértices, que (según el lema del protocolo de enlace ) es proporcional al número de aristas de entrada.
van Rooij y Wilf (1965) consideran la secuencia de gráficas
Muestran que, cuando G es un gráfico conexo finito , sólo cuatro comportamientos son posibles para esta secuencia:
Si G no es conexo, 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 gráfico plano G tiene un grado máximo de vértice tres, su gráfico lineal es plano y cada incrustación plana de G se puede extender a una incrustación de L ( G ) . Sin embargo, existen gráficos planos de mayor grado cuyos gráficos lineales no son planos. Estos incluyen, por ejemplo, el K 1,5 de 5 estrellas , el gráfico de gemas formado al sumar 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 gráfico medial , coincide con el gráfico lineal para gráficos planos con grado máximo tres, pero siempre es plano. Tiene los mismos vértices que el gráfico lineal, pero potencialmente menos aristas: dos vértices del gráfico medial son adyacentes si y sólo si las dos aristas correspondientes son consecutivas en alguna cara de la incrustación plana. La gráfica medial de la gráfica dual de un gráfico plano es la misma que la gráfica medial del gráfico plano original. [29]
Para poliedros regulares o poliedros simples, la operación del gráfico medial se puede representar geométricamente mediante la operación de cortar cada vértice del poliedro por un plano que pasa por los puntos medios de todos sus bordes incidentes. [30] Esta operación se conoce como segundo truncamiento, [31] truncamiento degenerado, [32] o rectificación . [33]
El gráfico total T ( G ) de un gráfico 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. La gráfica total también se puede obtener subdividiendo cada arista de G y luego tomando el cuadrado de la gráfica subdividida. [34]
El concepto de gráfico lineal de G puede, naturalmente, extenderse al caso en el que G es un multigrafo. En este caso, las caracterizaciones de estos grafos se pueden simplificar: la caracterización en términos de particiones clique ya no necesita impedir que dos vértices pertenezcan a la misma clique, y la caracterización por grafos prohibidos tiene siete grafos prohibidos en lugar de nueve. [35]
Sin embargo, para los multigrafos, hay un mayor número de pares de gráficos no isomorfos que tienen los mismos gráficos lineales. Por ejemplo, un gráfico bipartito completo K 1, n tiene el mismo gráfico lineal que el gráfico dipolo y el multigrafo de Shannon con el mismo número de aristas. Sin embargo, en este caso todavía se pueden derivar analogías con el teorema del isomorfismo de Whitney. [12]
También es posible generalizar gráficos lineales a gráficos dirigidos. [ 36] Si G es un gráfico dirigido, su gráfico lineal dirigido o dígrafo lineal tiene un vértice para 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 un camino dirigido de longitud dos en G. Las gráficas de De Bruijn se pueden formar repitiendo este proceso de formar gráficas lineales dirigidas, a partir de una gráfica dirigida completa . [37]
En un gráfico lineal L ( G ) , cada vértice de grado k en el gráfico original G crea k ( k − 1)/2 aristas en el gráfico lineal. Para muchos tipos de análisis, esto significa que los nodos de alto grado en G están sobrerrepresentados en el gráfico lineal L ( G ) . Por ejemplo , considere un paseo aleatorio sobre los vértices del gráfico original G. Esto pasará a lo largo de algún borde e con cierta frecuencia f . Por otro lado, este borde e se asigna a un vértice único, digamos v , en el gráfico lineal L ( G ) . Si ahora realizamos el mismo tipo de paseo aleatorio en los vértices del gráfico lineal, 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 ) , será atravesada O ( k 2 ) con más frecuencia en el gráfico lineal L ( G ) . Dicho de otra manera, el teorema del isomorfismo del gráfico de Whitney garantiza que el gráfico lineal casi siempre codifica fielmente la topología del gráfico original G , pero no garantiza que la dinámica en estos dos gráficos tenga una relación simple. Una solución es construir un gráfico de líneas ponderadas, es decir, un gráfico de líneas con bordes ponderados . Hay varias formas naturales de hacer esto. [38] Por ejemplo, si los bordes d y e en el gráfico G inciden en un vértice v con grado k , entonces en el gráfico lineal L ( G ) al borde que conecta los dos vértices d y e se le puede dar un peso 1/( k − 1) . De esta forma cada arista en G (siempre que ninguno de sus extremos esté conectado a un vértice de grado 1) tendrá fuerza 2 en el gráfico lineal L ( G ) correspondiente a los dos extremos que tiene la arista en G . Es sencillo extender esta definición de gráfico lineal ponderado a casos en los que el gráfico 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 y la topología del gráfico original G .
Los bordes de un hipergrafo pueden formar una familia arbitraria de conjuntos , por lo que la gráfica lineal de un hipergrafo es la misma que la gráfica de intersección de los conjuntos de la familia.
El gráfico de disjunciones de G , denotado D ( G ) , se construye de la siguiente manera: para cada arista en G , haga un vértice en D ( G ) ; por 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 gráfico complemento 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 coincidencias de un gráfico y los conjuntos independientes de su gráfico lineal.
