Gráfico de líneas

En la teoría de grafos , el gráfico de línea L ( G ) de un grafo no dirigido G , es un gráfico que representa la relación de adyacencia entre los bordes de G . El nombre del gráfico de líneas proviene de un artículo de Harary y Norman publicado en 1960. Sin embargo, Whitney ya había utilizado la misma construcción en 1932 y Krausz en 1943. También se le llama gráfico adjunto .

Uno de los primeros y más importantes teoremas de los gráficos lineales lo establece Hassler Whitney en 1932, quien demuestra que, aparte de un solo caso excepcional, la estructura de G se puede encontrar completamente a partir de L ( G ) en el caso de gráficos relacionados .

Definicion formal

Dado un gráfico G , su gráfico lineal L ( G ) es el gráfico definido de la siguiente manera:

Cada vértice de L ( G ) representa una arista de G ;
Dos vértices de L ( G ) son adyacentes si y solo si los bordes correspondientes comparten un punto final común en G (decimos que son adyacentes).

Ejemplos de

Ejemplo de construcción

La siguiente figura ilustra un gráfico (a la izquierda, con vértices azules) y su gráfico lineal (a la derecha, con vértices verdes). Cada vértice del gráfico lineal está etiquetado con los puntos finales del borde correspondiente en el gráfico original.

Gráfico G
Vértices de L ( G ) construidos a partir de aristas de G
Agregar bordes de L ( G )
El gráfico lineal L ( G )

Algunas gráficas lineales

El gráfico de Petersen es el gráfico complementario del gráfico de línea de la gráfica completa . $K_5$
El gráfico de línea de la gráfica tetraédrica es la gráfica octaédrica .
La gráfica lineal de la gráfica hexaédrica es la gráfica cuboctaédrica .
La gráfica lineal de la gráfica dodecaédrica es la gráfica icosaédrica .

Propiedades

Propiedades elementales

Las propiedades de un gráfico G que dependen solo de la adyacencia entre los bordes se pueden traducir en L ( G ) en propiedades equivalentes dependiendo de la adyacencia entre los vértices. Por ejemplo, un acoplamiento en G , es decir un conjunto de aristas que no tienen vértice en común, corresponde a un conjunto de vértices dos por dos no adyacentes en L ( G ), por lo tanto a un establo de L ( G ).

En consecuencia, tenemos las siguientes propiedades:

El gráfico lineal de un gráfico conectado está conectado. Sin embargo, lo contrario no es cierto. Un gráfico G que tiene vértices aislados puede tener un gráfico lineal conectado.
Un conjunto estable de peso máximo en un gráfico de líneas L ( G ) corresponde a un juego máximo en G . Como se puede encontrar un acoplamiento máximo en tiempo polinomial, la búsqueda de un conjunto estable de peso máximo también se realiza en tiempo polinomial en un gráfico lineal , aunque en el caso general es un problema NP-completo. En el sentido de la teoría de la complejidad .
El índice cromático de un gráfico G es igual al número cromático de su gráfico lineal L ( G ). De hecho, colorear los bordes de un gráfico equivale a colorear los vértices de su gráfico lineal .
El gráfico lineal de un gráfico de vértice transitivo es un gráfico de borde transitivo .
Si un gráfico G tiene un ciclo euleriano , es decir, si G está conectado y todos sus vértices son de grado par, entonces el gráfico lineal L ( G ) es un gráfico hamiltoniano . Sin embargo, puede ciclos hamiltonianos en L ( G ) que no viene ciclos de Euler en G .

Relaciones con otras familias de gráficos

Los gráficos lineales son gráficos sin garras , es decir gráficos que no permiten la garra del gráfico como subgrafo inducido .

El gráfico lineal de un gráfico bipartito es un gráfico perfecto (consulte el teorema de König ). La gráfica lineal de las gráficas bipartitas se usa en la demostración del teorema de la gráfica perfecta .

Caracterización de gráficos lineales

Una gráfica G es la gráfica lineal de otra gráfica, si y solo si es posible encontrar un conjunto de camarillas en G que divida los bordes de G de manera que cada vértice de G pertenezca exactamente a dos de las camarillas. Algunas de estas camarillas se pueden reducir a un solo vértice.

Según Hassler Whitney, si G no es un triángulo, entonces solo puede haber una de esas particiones. Si existe tal partición, es posible encontrar la gráfica original de la cual G es la gráfica lineal . Para ello, basta con crear un vértice por cada clic y conectarse por parejas bordes camarillas que comparten un vértice común en G . Roussopoulos utilizó en 1973 este resultado como base para construir un algoritmo que permitiera identificar los 'gráficos de líneas en tiempo lineal.

Un corolario de este resultado es que, excepto en los casos de la gráfica completa y la gráfica bipartita completa , si las gráficas lineales L ( G ) y L ( H ) de dos gráficas G y H son isomorfas, entonces las gráficas G y H son isomorfos. $K_ {3}$ $K _ {{1,3}}$

Beineke propuso otra caracterización de los gráficos de líneas en 1968 (luego probada en 1970). Mostró que había nueve gráficos mínimos que no eran gráficos de líneas, de modo que cualquier gráfico que no fuera un gráfico de líneas tenía al menos uno de estos gráficos mínimos como subgrafo inducido.

Iteración del operador de gráfico lineal

En 1965, van Rooij y Wilf estaban interesados en la iteración del operador de gráfico de líneas . Considere la siguiente secuencia:

G, L (G), L (L (G)), L (L (L (G))), \ puntos. \

Entonces, si G es un gráfico conectado finito, solo cuatro comportamientos diferentes son posibles para esta secuencia:

Si G es un gráfico de ciclo, entonces L ( G ), así como cada gráfico de la secuencia, es un gráfico isomorfo a G mismo. Las gráficas de ciclo son las únicas gráficas conectadas que son isomorfas a su gráfica lineal .
Si G es el gráfico de garras K 1,3 , entonces L ( G ) y todos los gráficos que siguen en la secuencia son gráficos triangulares (por lo tanto, gráficos cíclicos de longitud 3).
Si G es un gráfico de ruta , entonces cada gráfico que sigue en la secuencia es una ruta más corta hasta que termina con el gráfico singleton y finalmente el gráfico nulo.
En todos los demás casos, el tamaño de los gráficos de la secuencia aumenta sin estar acotado.

Si G no está conectado, a continuación, esta clasificación se aplica por separado a cada componente conectado de G .

Aplicaciones y usos

El concepto de gráfico lineal se utiliza en particular en la teoría de la computación distribuida , por ejemplo, en el límite inferior de Nati Linial para colorear en el modelo local.

Notas y referencias

(fr) Este artículo está tomado parcial o totalmente del artículo de Wikipedia en inglés titulado " Gráfico de líneas " ( consulte la lista de autores ) .

(in) F. Harary y RZ Norman , " Algunas propiedades de los dígrafos lineales " , Rendiconti del Circulo Mathematico di Palermo , vuelo. 9,1960, p. 161–169 ( DOI 10.1007 / BF02854581 ).
(en) H. Whitney , “ gráficos congruentes y la conectividad de los gráficos ” , American Journal of Mathematics , vol. 54, n o 1,1932, p. 150–168 ( DOI 10.2307 / 2371086 , leer en línea ).
(en) J. Krausz , " Nueva demostración del teorema de Whitney en redes " , Mat. Fiz. Lapok , vol. 50,1943, p. 75–85.
Didier Müller. Introducción a la teoría de grafos. Cahiers de la CRM número 6, Comisión Romande de Mathématiques, 2012 [1] .
(in) ND Roussopoulos , " max { m , n } Algoritmo para determinar el gráfico H a partir del gráfico de líneas icts G " , Information Processing Letters , vol. 2, n o 4,1973, p. 108–112 ( DOI 10.1016 / 0020-0190 (73) 90029-X ).
(en) LW Beineke , Beiträge zur Graphentheorie , Leipzig, Teubner,1968, 17–33 pág..
(in) LW Beineke , " Caracterizaciones de gráficos derivados " , Journal of Combinatorial Theory , vol. 9,1970, p. 129-135 ( DOI 10.1016 / S0021-9800 (70) 80019-9 ).
(in) ACM van Rooij y HS Wilf , " El gráfico de intercambio de un gráfico finito " , Acta Mathematica Hungarica , vol. 16, n hueso 3-4,1965, p. 263–269 ( DOI 10.1007 / BF01904834 ).
(in) Nathan Linial , " Localidad en algoritmos de gráficos distribuidos " , SIAM Journal we Computing , vol. 21, n o 1,1992, p. 193-201.

Ver también