TEORÍA DE TÉRMINOS DE GRAFOS

En la teoría de grafos , una rama de las matemáticas, canonización gráfico es el problema para encontrar una forma canónica de un gráfico dado G . Una forma canónica es un gráfico marcado Canon ( G ) que es isomorfo a G , de manera que cada gráfico que es isomorfo a G tiene la misma forma canónica como G . Por lo tanto, a partir de una solución al problema de canonización de gráficos, también se podría resolver el problema del isomorfismo de gráficos : para probar si dos gráficos G y H son isomorfos, calcule sus formas canónicas Canon ( G ) y Canon (H ), y pruebe si estas dos formas canónicas son idénticas.

La forma canónica de un gráfico es un ejemplo de un gráfico completo invariante : cada dos gráficos isomórficos tienen la misma forma canónica, y cada dos gráficos no isomórficos tienen diferentes formas canónicas. ^[1] [2] Por el contrario, cada invariante completo de gráficos se puede utilizar para construir una forma canónica. ^[3] El conjunto de vértices de un gráfico de n -vértices puede identificarse con los enteros de 1 a n , y al usar dicha identificación, una forma canónica de un gráfico también puede describirse como una permutación de sus vértices. Las formas canónicas de un gráfico también se denominan etiquetados canónicos , ^[4]y la canonización de grafos también se conoce a veces como canonicalización de grafos .

Complejidad computacional [ editar ]

Claramente, el problema de canonización de gráficos es al menos tan difícil desde el punto de vista computacional como el problema de isomorfismo de gráficos . De hecho, el isomorfismo gráfico es incluso AC ⁰ - reducible a la canonización gráfica. Sin embargo, todavía es una pregunta abierta si los dos problemas son polinomiales equivalentes al tiempo . ^[2]

Si bien la existencia de algoritmos polinomiales (deterministas) para el isomorfismo gráfico sigue siendo un problema abierto en la teoría de la complejidad computacional , en 1977 László Babai informó que con probabilidad de al menos 1 - exp (−O ( n )), un algoritmo de clasificación de vértices simple produce un etiquetado canónico de un gráfico elegido uniformemente al azar del conjunto de todos los gráficos de n -vértices después de solo dos pasos de refinamiento. Pequeñas modificaciones y un paso adicional de búsqueda de profundidad producen el etiquetado canónico de tales gráficos aleatorios elegidos uniformemente en el tiempo lineal esperado. Este resultado arroja algo de luz sobre el hecho de que muchos algoritmos de isomorfismo gráfico reportados se comporten bien en la práctica. ^[5] [6]Este fue un avance importante en la teoría de la complejidad probabilística que se hizo ampliamente conocido en su forma de manuscrito y que todavía se citó como un "manuscrito no publicado" mucho después de que se informara en un simposio.

Una forma canónica comúnmente conocida es el gráfico lexicográficamente más pequeño dentro de la clase de isomorfismo , que es el gráfico de la clase con matriz de adyacencia lexicográficamente más pequeña considerada como una cadena lineal. Sin embargo, el cálculo del gráfico lexicográficamente más pequeño es NP-hard . ^[1]

Para los árboles, Read (1972) presenta un algoritmo conciso de canonización polinomial que requiere espacio O (n ) . ^[7] Comience etiquetando cada vértice con la cadena 01. Iterativamente para cada x que no sea de hoja, elimine el 0 inicial y el 1 posterior de la etiqueta de x; luego clasifique la etiqueta de x junto con las etiquetas de todas las hojas adyacentes en orden lexicográfico. Concatene estas etiquetas ordenadas, agregue un 0 inicial y un 1 posterior, haga de esta la nueva etiqueta de x y elimine las hojas adyacentes. Si quedan dos vértices, concatene sus etiquetas en orden lexicográfico.

Aplicaciones [ editar ]

La canonización gráfica es la esencia de muchos algoritmos de isomorfismo gráfico. Una de las herramientas principales es Nauty. ^[8]

Una aplicación común de la canonización de gráficos es la minería de datos gráficos , en particular en aplicaciones de bases de datos químicas . ^[9]

Varios identificadores de sustancias químicas , como SMILES e InChI, utilizan pasos de canonicalización en su cálculo, que es esencialmente la canonicalización del gráfico que representa la molécula. ^{[10] [11] [12]} Estos identificadores están diseñados para proporcionar una forma estándar (y a veces legible) para codificar información molecular y facilitar la búsqueda de dicha información en bases de datos y en la web.

Informalmente, la conjetura de reconstrucción en la teoría de grafos dice que los gráficos están determinados únicamente por sus subgrafos. Se debe a Kelly ^[1] y Ulam . 

Declaraciones formales [ editar ]

Un gráfico y el mazo asociado de subgrafías eliminadas de un solo vértice. Tenga en cuenta que algunas de las tarjetas muestran gráficos isomórficos.

Dado un gráfico $${\ displaystyle G = (V, E)}, un subgrafo de vértice eliminado$${\ displaystyle G}es un subgrafo formado eliminando exactamente un vértice de$${\ displaystyle G}. Por definición, es un subgrafo inducido de$${\ displaystyle G}.

Para un gráfico $${\ displaystyle G}, el mazo de G , denotado$${\ displaystyle D (G)}, es el conjunto múltiple de clases de isomorfismo de todas las subgrafías eliminadas de vértices de$${\ displaystyle G}. Cada gráfico en$${\ displaystyle D (G)}que se llama una tarjeta . Se dice que dos gráficos que tienen el mismo mazo son hipomórficos .

Con estas definiciones, la conjetura puede expresarse como:

• Conjetura de reconstrucción: Cualquiera de los dos gráficos hipomórficos en al menos tres vértices son isomorfos.

(El requisito de que los gráficos tengan al menos tres vértices es necesario porque ambos gráficos en dos vértices tienen los mismos mazos).

Harary ^[4] sugirió una versión más fuerte de la conjetura:

• Conjetura de reconstrucción de conjuntos: dos gráficos en al menos cuatro vértices con los mismos conjuntos de subgrafos eliminados por vértice son isomorfos.

Dado un gráfico $${\ displaystyle G = (V, E)}, un subgrafo de borde borrado de$${\ displaystyle G}es un subgrafo formado eliminando exactamente un borde de$${\ displaystyle G}.

Para un gráfico $${\ displaystyle G}, la cubierta de borde de G , denotada$${\ displaystyle ED (G)}, es el conjunto múltiple de todas las clases de isomorfismo de subgrafías borradas de borde de$${\ displaystyle G}. Cada gráfico en$${\ displaystyle ED (G)}se llama una tarjeta de borde .

• Conjetura de reconstrucción de bordes: (Harary, 1964) ^[4] Cualquiera de los dos gráficos con al menos cuatro bordes y que tengan las mismas cubiertas de bordes son isomorfos.

Propiedades reconocibles [ editar ]

En el contexto de la conjetura de reconstrucción, una propiedad de gráfico se llama reconocible si se puede determinar la propiedad desde el mazo de un gráfico. Las siguientes propiedades de los gráficos son reconocibles:

• Orden del gráfico : el orden de un gráfico$${\ displaystyle G}, $${\ displaystyle | V (G) |} es reconocible desde $${\ displaystyle D (G)} como el multiset $${\ displaystyle D (G)} contiene cada subgrafo de $${\ displaystyle G} creado al eliminar un vértice de $${\ displaystyle G}. Por lo tanto$${\ displaystyle | V (G) | = | D (G) |} ^[5]
• Número de bordes del gráfico : el número de bordes en un gráfico$${\ displaystyle G} con $${\ displaystyle n} vértices $${\ displaystyle | E (G) |}es reconocible Primera nota que cada borde de$${\ displaystyle G} ocurre en $${\ displaystyle n-2} miembros de $${\ displaystyle D (G)}. Esto es cierto por la definición de$${\ displaystyle D (G)} lo que garantiza que cada borde se incluya cada vez que cada uno de los vértices con los que incide se incluya en un miembro de $${\ displaystyle D (G)}, por lo que se producirá una ventaja en cada miembro de $${\ displaystyle D (G)}a excepción de los dos en los que se eliminan sus puntos finales. Por lo tanto,$${\ displaystyle | E (G) | = \ sum {\ frac {q_ {i}} {n-2}}} dónde $${\ displaystyle q_ {i}}es el número de aristas en el i- ésimo miembro de$${\ displaystyle D (G)} ^[5]
• Secuencia de grados: la secuencia de grados de un gráfico$${\ displaystyle G}es reconocible porque el grado de cada vértice es reconocible. Para encontrar el grado de un vértice$${\ displaystyle v_ {i}}, examinaremos el gráfico creado al eliminarlo, $${\ displaystyle G_ {i}}. Este gráfico contiene todos los bordes que no inciden con$${\ displaystyle v_ {i}}, Así que si $${\ displaystyle q_ {i}} es el número de aristas en $${\ displaystyle G_ {i}} y $${\ displaystyle q} es el número de aristas en $${\ displaystyle G}, luego $${\ displaystyle q-q_ {i} = \ deg (v_ {i})}. Si podemos decir el grado de cada vértice en el gráfico, podemos decir la secuencia de grados del gráfico. ^[5]
• (Vértice-) Conectividad : por definición, un gráfico es$${\ displaystyle n}-vertex-conectado al eliminar cualquier vértice crea un $${\ displaystyle n-1}-vertex conectado gráfico; así, si cada tarjeta tiene un$${\ displaystyle n-1}gráfico conectado a vértices, sabemos que el gráfico original era $${\ displaystyle n}-vertex-conectado. También podemos determinar si el gráfico original estaba conectado, ya que esto es equivalente a tener cualquiera de los dos$${\ displaystyle G_ {i}}estar conectado ^[5]
• Polinomio de Tutte
• Planaridad
• Los tipos de árboles de expansión en un gráfico
• Polinomio cromático
• Ser un gráfico perfecto o un gráfico de intervalo , o ciertas otras subclases de gráficos perfectos ^[6]

Verificación [ editar ]

Brendan McKay ha verificado tanto las conjeturas de reconstrucción como las de reconstrucción de conjuntos para todos los gráficos con un máximo de 11 vértices . ^[7]

En un sentido probabilístico, Béla Bollobás ha demostrado que casi todas las gráficas son reconstruibles. ^[8] Esto significa que la probabilidad de que un gráfico elegido al azar en$${\ displaystyle n} vértices no es reconstruible va a 0 como $${\ displaystyle n}va al infinito De hecho, se demostró que no solo son casi todas las gráficas reconstruibles, sino que de hecho no es necesario reconstruir todo el mazo; casi todas las gráficas tienen la propiedad de que existen tres cartas en su mazo que determinan de manera única la gráfica.

Familias gráficas reconstruibles [ editar ]

La conjetura se ha verificado para varias clases infinitas de gráficos (y, trivialmente, sus complementos).

• Gráficos regulares ^[9] : los gráficos regulares son reconstruibles mediante la aplicación directa de algunos de los hechos que pueden reconocerse desde el mazo de un gráfico. Dado un$${\ displaystyle n}gráfico regular $${\ displaystyle G} y su cubierta $${\ displaystyle D (G)}, podemos reconocer que el mazo es de un gráfico regular al reconocer su secuencia de grados. Examinemos ahora un miembro de la baraja.$${\ displaystyle D (G)}, $${\ displaystyle G_ {i}}. Este gráfico contiene cierto número de vértices con un grado de$${\ displaystyle n} y $${\ displaystyle n} vértices con un grado de $${\ displaystyle n-1}. Podemos agregar un vértice a este gráfico y luego conectarlo al$${\ displaystyle n} vértices de grado $${\ displaystyle n-1} para crear un $${\ displaystyle n}gráfico regular que es isomorfo al gráfico con el que comenzamos. Por lo tanto, todos los gráficos regulares son reconstruibles desde sus mazos. Un tipo particular de gráfico regular que es interesante es el gráfico completo. ^[5]
• Árboles ^[9]
• Gráficos desconectados ^[9]
• Gráficos de intervalos unitarios ^[6]
• Gráficos separables sin vértices finales ^[10]
• Gráficos planos máximos
• Gráficos del plano exterior máximo
• Gráficos de plano exterior
• Bloques críticos

Reducción [ editar ]

La conjetura de la reconstrucción es cierta si todas las gráficas conectadas en 2 son reconstruibles ^[11]

Dualidad [ editar ]

La conjetura de reconstrucción del vértice obedece a la dualidad que si $${\ displaystyle G} puede ser reconstruido desde su cubierta de vértice $${\ displaystyle D (G)}, entonces su complemento $${\ displaystyle G '} puede ser reconstruido desde $${\ displaystyle D (G ')} de la siguiente manera: Comience con $${\ displaystyle D (G ')}, toma el complemento de cada carta para obtener $${\ displaystyle D (G)}, usa esto para reconstruir $${\ displaystyle G}, luego toma el complemento nuevamente para obtener $${\ displaystyle G '}.

La reconstrucción de bordes no obedece a tal dualidad: de hecho, para algunas clases de gráficos de reconstrucción de bordes no se sabe si sus complementos son reconstruibles.

Otras estructuras [ editar ]

Se ha demostrado que los siguientes no son en general reconstruibles:

• Dígrafos : se conocen infinitas familias de dígrafos no reconstruibles, incluidos los torneos (Stockmeyer ^[12] ) y los no torneos (Stockmeyer ^[13] ). Un torneo es reconstruible si no está fuertemente conectado. ^[14] Se ha conjeturado una versión más débil de la conjetura de reconstrucción para los dígrafos, ver nueva conjetura de reconstrucción del dígrafo .
• Hypergraphs ( Kocay ^[15] ).
• Gráficos infinitos . Sea T un árbol en un número infinito de vértices, de modo que cada vértice tenga un grado infinito, y sea n T la unión disjunta de n copias de T. Estas gráficas son hipomórficas y, por lo tanto, no reconstruibles. Cada subgrafo eliminado de vértice de cualquiera de estos gráficos es isomorfo: todos son la unión disjunta de un número infinito de copias de T.
• Gráficos localmente finitos. La cuestión de la reconstructibilidad para árboles infinitos localmente finitos (la conjetura de Harary-Schwenk-Scott de 1972) fue un problema abierto de larga data hasta 2017, cuando Bowler et al encontraron un árbol no reconstruible de grado máximo 3.

Este artículo trata sobre la teoría de grafos. Para el arbusto, ver Plumeria alba .

Una oruga

En teoría de grafos , una oruga o árbol de oruga es un árbol en el que todos los vértices están dentro de la distancia 1 de un camino central.

Las orugas fueron estudiadas por primera vez en una serie de documentos de Harary y Schwenk. El nombre fue sugerido por A. Hobbs . ^[1] [2] Como Harary y Schwenk (1973) escriben con colorido: "Una oruga es un árbol que se metamorfosea en un camino cuando se elimina su capullo de puntos finales".

Caracterizaciones equivalentes [ editar ]

Las siguientes caracterizaciones describen todos los árboles de oruga:

• Son los árboles para los que eliminar las hojas y los bordes incidentes produce un gráfico de ruta . ^[2] [3]
• Son los árboles en los que existe un camino que contiene cada vértice de grado dos o más.
• Son los árboles en los que cada vértice de grado al menos tres tiene como máximo dos vecinos que no son hojas.
• Son los árboles que no contienen como subgrafo el gráfico formado al reemplazar cada borde en el gráfico de estrella K _1,3 por un camino de longitud dos. ^[3]
• Son los gráficos conectados que se pueden dibujar con sus vértices en dos líneas paralelas, con bordes representados como segmentos de línea que no se cruzan y que tienen un punto final en cada línea. ^[3] [4]
• Son los árboles cuyo cuadrado es un gráfico hamiltoniano . Es decir, en una oruga, existe una secuencia cíclica de todos los vértices en la que cada par de vértices adyacentes en la secuencia está a una o dos distancias entre sí, y los árboles que no son orugas no tienen esa secuencia. Se puede obtener un ciclo de este tipo dibujando la oruga en dos líneas paralelas y concatenando la secuencia de vértices en una línea con el reverso de la secuencia en la otra línea. ^[3]
• Son los árboles cuyos gráficos de líneas contienen un camino hamiltoniano ; dicho camino puede obtenerse ordenando los bordes en un dibujo de dos líneas del árbol. En términos más generales, el número de aristas que deben agregarse al gráfico lineal de un árbol arbitrario para que contenga una ruta hamiltoniana (el tamaño de su terminación hamiltoniana ) es igual al número mínimo de orugas desunidas de arista que los bordes del árbol pueden ser descompuesto en ^[5]
• Son los gráficos conectados del ancho de ruta uno. ^[6]
• Son los gráficos de intervalos libres de triángulos conectados . ^[7]

Generalizaciones [ editar ]

Un árbol k es un gráfico cordal con exactamente n - k camarillas máximas , cada una con k + 1 vértices; en un árbol k que no es en sí una camarilla ( k + 1) , cada camarilla máxima separa el gráfico en dos o más componentes, o contiene un vértice de hoja único, un vértice que pertenece a una sola camarilla máxima. Un k -path es un k -tree con a lo sumo dos hojas, y una k -caterpillar es un k -tree que se puede dividir en un k -path y algunos k-hojas, cada una adyacente a un separador k -clique de la k -path. En esta terminología, una oruga 1 es lo mismo que un árbol oruga, y las orugas k son los gráficos de borde máximo con ancho de trayectoria k . ^[6]

Un gráfico de langosta es un árbol en el que todos los vértices están dentro de la distancia 2 de un camino central . ^[8]

Enumeración [ editar ]

Las orugas proporcionan uno de los raros problemas de enumeración de gráficos para los que se puede dar una fórmula precisa: cuando n  ≥ 3, el número de orugas con n vértices sin etiquetar es ^[1]

$${\ displaystyle 2 ^ {n-4} +2 ^ {\ lfloor (n-4) / 2 \ rfloor}.}

Para n = 1, 2, 3, ... los números de n -vertex orugas son

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... (secuencia A005418 en el OEIS ).

Complejidad computacional [ editar ]

Encontrar una oruga de expansión en un gráfico es NP-completo . Un problema de optimización relacionado es el Problema mínimo de la oruga de expansión (MSCP), donde un gráfico tiene costos dobles sobre sus bordes y el objetivo es encontrar un árbol de oruga que abarque el gráfico de entrada y tenga el costo total más pequeño. Aquí, el costo de la oruga se define como la suma de los costos de sus bordes, donde cada borde toma uno de los dos costos en función de su papel como borde de hoja o uno interno. No existe un algoritmo de aproximación f (n) para el MSCP a menos que P = NP . Aquí f (n) es cualquier función computable de tiempo polinomial de n, el número de vértices de un gráfico. ^[9]

Hay un algoritmo parametrizado que encuentra una solución óptima para el MSCP en gráficos de ancho de árbol acotado . Entonces, tanto el Problema Spanning Caterpillar como el MSCP tienen algoritmos de tiempo lineal si un gráfico es un gráfico externo, un paralelo en serie o un gráfico de Halin . ^[9]

Aplicaciones [ editar ]

Los árboles de oruga se han utilizado en la teoría de grafos químicos para representar la estructura de las moléculas de hidrocarburos benzenoides . En esta representación, uno forma una oruga en la que cada borde corresponde a un anillo de 6 carbonos en la estructura molecular, y dos bordes inciden en un vértice cuando los anillos correspondientes pertenecen a una secuencia de anillos conectados de extremo a extremo en el estructura. El-Basil (1987) escribe: "Es sorprendente que casi todos los gráficos que desempeñaron un papel importante en lo que ahora se llama" teoría de los gráficos químicos "puedan estar relacionados con los árboles de oruga". En este contexto, los árboles de oruga también se conocen como árboles benzenoides y árboles de Gutman , después del trabajo de Ivan Gutman en esta área.