Gráfico de líneas

En la teoría de grafos, el gráfico lineal L ( G ) de un gráfico no dirigido G es el gráfico L ( G ) que representa la vecindad de los bordes del gráfico G .

El concepto de un gráfico lineal para un gráfico dado es tan natural que muchos autores lo han introducido de forma independiente. Por supuesto, cada uno de ellos dio su propio nombre: Ore [1] llamó a este gráfico "gráfico de adyacencia" , Sabidussi [2] - "gráfico derivado" , Beinecke [3] - "gráfico derivado" , Sechu y Read [4] - "borde -vértice-dual" , Castelein [5] - "gráfico de cobertura" , Menon [6] - "adjunto" ("adjunto") [7] [8] [9] .

Uno de los primeros y más importantes teoremas de gráficos lineales se debe a Whitney, quien demostró que, con una excepción, la estructura de un gráfico G está completamente definida por un gráfico lineal. En otras palabras, con una excepción, el gráfico completo se puede reconstruir a partir del gráfico de líneas.

Formal definición

Sea dada una gráfica G , entonces su gráfica lineal L ( G ) es una gráfica tal que

Ejemplos

Ejemplo de construcción

La siguiente figura muestra un gráfico (a la izquierda, con vértices azules) y su gráfico de líneas (a la derecha, con vértices verdes). Cada vértice del gráfico lineal está etiquetado con un par de números de vértice 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, 1,2 ( correspondiente a las aristas que comparten el vértice 1 en el gráfico azul), y 4,3 (correspondiente a las aristas con un vértice común 3 en el gráfico azul).

Grafos cordales

El gráfico lineal de un gráfico completo K n se conoce como gráfico cordal (o gráfico triangulado ). Un teorema importante sobre grafos cordales es el teorema que establece que un grafo cordal se caracteriza por un espectro , excepto para n = 8 cuando hay otros tres grafos con el mismo espectro que L ( K 8 ). Las excepciones se explican en Cambio de gráfico .

Gráficos lineales de poliedros convexos

La fuente de ejemplos de gráficos lineales se puede encontrar en geometría, para gráficos de politopos simples . Si construimos un gráfico lineal para un gráfico de tetraedro , obtenemos un gráfico de octaedro . Del gráfico del cubo obtenemos el gráfico del cuboctaedro . Del gráfico del dodecaedro se obtiene el gráfico del icosidodecaedro , etc.. Geométricamente, la operación consiste en cortar todos los vértices del poliedro por un plano que corta todas las aristas conjugadas al vértice por su medio.

Si el poliedro no es simple (es decir, tiene más de tres caras por vértice), el gráfico lineal no será plano.

Gráfico de la mediana

Un gráfico de mediana es una variante de un gráfico de líneas para un gráfico plano. En un grafo medio, dos vértices son adyacentes si y solo si las aristas correspondientes del grafo original son dos aristas consecutivas de alguna área del grafo plano. Para polígonos simples, el gráfico de la mediana y el gráfico de líneas son los mismos, pero para los polígonos complejos, el gráfico de la mediana permanece plano. Así, las gráficas intermedias de un cubo y un octaedro son isomorfas a la gráfica de un cuboctaedro, y las gráficas intermedias de un dodecaedro y un icosaedro son isomórficas a la gráfica de un icosidodecaedro.

Propiedades

Las propiedades del grafo G que dependen solo de la adyacencia de los bordes se pueden traducir en propiedades equivalentes del grafo L ( G ) que dependen solo de la adyacencia de los vértices. Por ejemplo, una coincidencia en G  es un conjunto de arcos, ninguno de los cuales es adyacente al otro, y un conjunto correspondiente de vértices en L ( G ), ninguno de los cuales es adyacente al otro, es decir, un conjunto independiente de vértices _

Asi que,

Dado que la coincidencia máxima se puede encontrar en tiempo polinomial, el conjunto independiente máximo de un gráfico lineal también se puede encontrar en tiempo polinomial, a pesar de la dificultad de encontrar dicho conjunto para familias de gráficos más generales.

Características y reconocimiento

Un grafo G es un grafo lineal de otro grafo si y solo si es posible encontrar un conjunto de cliques en G que dividen los arcos de G de tal manera que cada vértice de G pertenece exactamente a dos cliques. Puede suceder que para lograr esto, sea necesario seleccionar vértices individuales en camarillas. Por el teorema de Whitney  [10] [11] , si G no es un triángulo, solo puede haber una partición de este tipo. Si existe una partición, podemos construir un gráfico para el cual G es un gráfico lineal creando un vértice para cada camarilla y conectando los vértices resultantes con una arista si el vértice pertenece a ambas camarillas. Por lo tanto, con la excepción de y , si dos gráficas lineales de gráficas conexas son isomorfas a , entonces las gráficas también son isomorfas. Roussopoulos [12] usó esta observación como base para un algoritmo lineal en el tiempo para reconocer gráficos lineales y reconstruir sus gráficos originales.

Por ejemplo, tal característica se puede usar para mostrar que el siguiente gráfico no es un gráfico lineal:

En este ejemplo, las aristas que van desde el vértice central del 4º grado hacia arriba, hacia la izquierda y hacia la derecha no contienen camarillas comunes. Entonces, cualquier partición de los bordes del gráfico en cliques debe contener al menos un clique para cada uno de estos tres bordes, y los tres cliques se cruzan en el vértice central, lo que viola la condición de que cada vértice pertenece exactamente a dos cliques. Por lo tanto, el gráfico que se muestra no puede ser un gráfico lineal.

Otra característica de un grafo fue demostrada por Beinecke [13] (y mencionada anteriormente sin demostración por él [3] ). Mostró que hay nueve gráficos mínimos que no son de línea, de modo que cualquier gráfico que no sea de línea contiene uno de estos nueve gráficos como un subgráfico generado . Por lo tanto, un gráfico es un gráfico lineal si y solo si ningún subconjunto de vértices genera uno de estos nueve. En el ejemplo anterior, los cuatro vértices superiores generan una garra (es decir, un gráfico bipartito completo K 1,3 ), que se muestra en la parte superior izquierda de la ilustración del subgráfico prohibido. Por lo tanto, de acuerdo con la característica de Beinecke, este gráfico no puede ser un gráfico lineal. Para gráficos con grado de vértice de al menos 5, el gráfico solo puede generar seis subgráficos en las columnas izquierda y derecha de la figura [14] . Este resultado es similar al resultado de los gráficos de líneas hipergráficas [15] .

Repetición de la operación de construcción de un gráfico lineal

Ruij y Wilf [16] consideraron la secuencia de grafos

Demostraron que para un gráfico finito de un gráfico conexo G , solo son posibles cuatro comportamientos de esta secuencia:

Si G está desconectado, esta clasificación se aplica a todos los componentes conectados de G.

Relación con otras familias de grafos

Cualquier gráfico de líneas no contiene garras .

El gráfico lineal de un gráfico bipartito es perfecto (ver el teorema de König ). Los gráficos lineales de los gráficos bipartitos forman uno de los bloques de construcción clave que se utilizan para probar el teorema del gráfico perfecto. Un caso especial son los gráficos de torre , gráficos lineales de gráficos bipartitos completos .

Generalizaciones

Multigrafos

El concepto de un gráfico lineal para un gráfico G puede extenderse naturalmente al caso en que G es un multigrafo, aunque en este caso el teorema de unicidad de Whitney se vuelve inválido. Por ejemplo, el gráfico bipartito completo K 1, n tiene el mismo gráfico lineal que el gráfico dipolar y el multigráfico de Shannon con el mismo número de aristas.

dígrafos de borde

También se pueden generalizar gráficos lineales a gráficos dirigidos [17] . Si G  es un gráfico dirigido, entonces su gráfico de línea dirigida o dígrafo de línea tiene un vértice para cada arco en G. Dos vértices correspondientes a arcos de u a v y de w a x del gráfico G están conectados por un arco de uv a wx en un dígrafo de línea cuando v = w . Así, cada arco en el dígrafo de línea corresponde a un camino de longitud 2 en el gráfico original. Los gráficos de De Bruijn se pueden obtener construyendo repetidamente gráficos de líneas dirigidas, comenzando con un dígrafo completo [18] .

Gráficos de línea ponderada

Cada vértice de grado k en el gráfico original G crea k(k-1)/2 aristas en el gráfico lineal L ( G ). Para muchos tipos de análisis, esto significa que los vértices de alto grado en G se representan con mayor fuerza en el gráfico lineal L ( G ). Imagine, por ejemplo, un paseo aleatorio sobre los vértices del gráfico original G. Pasaremos por la arista e con alguna probabilidad f . Por otro lado, la arista e corresponde a un solo vértice, digamos v , en el gráfico lineal L ( G ). Si ahora realizamos el mismo tipo de recorrido aleatorio sobre los vértices de un gráfico lineal, la frecuencia de visitas v puede resultar bastante diferente de f . Si nuestra arista e en G estuviera conectada a vértices de grado O(k) , sería atravesada O(k 2 ) más a menudo en el gráfico lineal L ( G ). Así, mientras que el teorema de Whitney [10] garantiza que un gráfico lineal casi siempre contiene la topología codificada de G , no garantiza que los dos gráficos tengan conexiones dinámicas simples. Una solución a este problema es crear un gráfico lineal ponderado, es decir, un gráfico lineal cuyos bordes estén ponderados. Hay varias formas naturales de hacer esto [19] . Por ejemplo, si las aristas d y e en un gráfico G están conjugadas en un vértice v de grado k , entonces en un gráfico lineal L ( G ) a la arista que conecta dos vértices d y e se le puede asignar un peso de 1/(k- 1) . De la misma forma, cualquier arista en G (a menos que esté conectada a un vértice de grado 1 ) tendrá peso 2 en el gráfico lineal L ( G ), correspondiente a dos extremos de la arista en G.

Gráficos lineales de hipergrafías

Las aristas de un hipergráfico pueden formar cualquier familia de conjuntos, por lo que el gráfico lineal de un hipergráfico  es el mismo que el gráfico de intersección de los conjuntos de una familia.

Notas

  1. ↑ O. Ore. Gráficos conectados de Hamilton // J. Math. Pures Appl. - 1963. - T. 42 . - S. 21-27 .
  2. ↑ G. Sabidussi. Gráficos con grupo dado y propiedades praf-teóricas dadas  // Canad. Matemáticas J. - 1957. - T. 9 . - S. 515-525 .
  3. ↑ 1 2 L. W. Beineke. Beitrage zur Graphentheorie. —Leipzig: Teubner, 1968.
  4. ↑ Seshu S., Reed M. Gráficos lineales y circuitos eléctricos. - M. : Escuela Superior, 1971. - T. 42. - S. 21-27.
  5. ↑ Kasteleyn P. W. Un problema de caminar autoevitable soluble // Physica. - 1968. - T. 23 . - S. 85-89 .
  6. ↑ Menon V. Sobre gráficos de intercambio repetidos // Amer Math Monthly. - 1966. - T. 13 . - S. 986-989 .
  7. ↑ F. Harari . Graph Theory = Graph Theory / Traducción del inglés y prólogo de V.P. Kozyrev. - 2. - M. : Editorial URSS, 2003. - 296 p.
  8. ↑ Esquema de teoría de grafos de Balakrishnan VK Schaum. — 1er. - McGraw-Hill, 1997. - ISBN 0-07-005489-4 .
  9. ↑ R. L. Hemminger, L. W. Beineke. Temas seleccionados en teoría de grafos. - Academic Press Inc., 1978. - S. 271-305 .
  10. ↑ 1 2 H. Whitney. Gráficos congruentes y conectividad de gráficos  // American Journal of Mathematics. - 1932. - T. 54 , núm. 1 . - S. 150-168 . -doi : 10.2307/ 2371086 . — .
  11. ↑ J. Krausz. Demostración nouvelle d'un théorème de Whitney sur les réseaux // Mat. Fiz. Lapok. - 1943. - T. 50 . - S. 75-85 .
  12. ↑ ND Roussopoulos. Un algoritmo max { m , n } para determinar el gráfico H a partir de su gráfico lineal G  // Letras de procesamiento de información. - 1973. - Vol. 2 , número. 4 . - S. 108-112 . -doi : 10.1016 / 0020-0190(73)90029-X .
  13. ↑ LW Beineke. Caracterizaciones de grafos derivados // Journal of Combinatorial Theory. - 1970. - vol. 9.- S. 129-135 . - doi : 10.1016/S0021-9800(70)80019-9 .
  14. ↑ Yury Metelsky, Regina Tyshkevich. Gráficos en línea de hipergrafías lineales de 3 uniformes // Journal of Graph Theory. - 1997. - T. 25 , núm. 4 . - S. 243-251 . - doi : 10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K .
  15. ↑ Weisstein, Eric W. Line Graph  en el sitio web de Wolfram MathWorld .
  16. ↑ ACM van Rooij, H. S. Wilf. El grafo de intercambio de un grafo finito // Acta Mathematica Hungarica. - 1965. - T. 16 , núm. 3-4 . - S. 263-269 . -doi : 10.1007/ BF01904834 .
  17. ↑ Frank Harary, RZ Norman. Algunas propiedades de los dígrafos de línea // Rendiconti del Circolo Matematico di Palermo . - 1960. - T. 9 , núm. 2 . - S. 161-169 . -doi : 10.1007/ BF02854581 .
  18. ↑ Fu Ji Zhang, Guo Ning Lin. Sobre los gráficos de Bruijn-Good // Acta Math. Sínica. - 1987. - T. 30 , núm. 2 . - S. 195-205 .
  19. ↑ T. S. Evans, R. Lambiotte. Gráficos de líneas, particiones de enlaces y comunidades superpuestas // Phys.Rev.E. - 2009. - T. 80 . -doi : 10.1103/ PhysRevE.80.016105 .

Enlaces