En la teoría de grafos , una propiedad de grafo o invariante de grafo es una propiedad de grafos que depende solo de la estructura abstracta, no de representaciones de grafos como etiquetas particulares o dibujos del grafo. [1]
Definiciones
Si bien el dibujo y la representación de gráficos son temas válidos en la teoría de gráficos, para centrarse solo en la estructura abstracta de los gráficos, una propiedad de gráfico se define como una propiedad que se conserva bajo todos los isomorfismos posibles de un gráfico. En otras palabras, es una propiedad del gráfico en sí, no de un dibujo o representación específicos del gráfico. De manera informal, el término "gráfico invariante" se usa para propiedades expresadas cuantitativamente, mientras que "propiedad" generalmente se refiere a caracterizaciones descriptivas de gráficos. Por ejemplo, el enunciado "el gráfico no tiene vértices de grado 1" es una "propiedad" mientras que "el número de vértices de grado 1 en un gráfico" es un "invariante".
Más formalmente, una propiedad de gráfico es una clase de gráficos con la propiedad de que dos gráficos isomorfos cualesquiera pertenecen a la clase o no pertenecen a ella. [1] De manera equivalente, una propiedad de gráfico puede formalizarse usando la función indicadora de la clase, una función desde gráficos hasta valores booleanos que es verdadera para gráficos en la clase y falsa en caso contrario; de nuevo, dos gráficos isomorfos cualesquiera deben tener el mismo valor de función que el otro. Un gráfico invariante o un parámetro de gráfico se puede formalizar de manera similar como una función de gráficos a una clase más amplia de valores, como enteros, números reales , secuencias de números o polinomios , que nuevamente tiene el mismo valor para dos gráficos isomórficos cualesquiera. [2]
Propiedades de las propiedades
Muchas propiedades de los gráficos se comportan bien con respecto a ciertos pedidos parciales naturales o preordenes definidos en los gráficos:
- Una propiedad gráfico P es hereditaria si cada subgrafo inducido de un gráfico con la propiedad P también tiene la propiedad P . Por ejemplo, ser un gráfico perfecto o ser un gráfico cordal son propiedades hereditarias. [1]
- Una propiedad gráfica es monótona si cada subgrafo de un gráfico con la propiedad P también tiene la propiedad P . Por ejemplo, ser un gráfico bipartito o ser un gráfico sin triángulos es monótono. Toda propiedad monótona es hereditaria, pero no necesariamente al revés; por ejemplo, los subgrafos de los grafos de acordes no son necesariamente acordes, por lo que ser un grafo de acordes no es monótono. [1]
- Una propiedad gráfica es de menor importancia-cerrado si cada menor gráfica de un gráfico con la propiedad P también tiene la propiedad P . Por ejemplo, ser un gráfico plano es menor-cerrado. Cada propiedad menor cerrada es monótona, pero no necesariamente al revés; por ejemplo, los menores de los gráficos sin triángulos no necesariamente están libres de triángulos. [1]
Estas definiciones pueden extenderse desde propiedades a invariantes numéricos de gráficos: un invariante de gráfico es hereditario, monótono o menor cerrado si la función que formaliza el invariante forma una función monótona del orden parcial correspondiente en los gráficos a los números reales.
Además, se han estudiado las invariantes de gráficos con respecto a su comportamiento con respecto a las uniones disjuntas de gráficos:
- A invariante gráfica es aditivo si, para todos los dos gráficos G y H , el valor de la invariante en la unión de la desunión de G y H es la suma de los valores de G y de H . Por ejemplo, el número de vértices es aditivo. [1]
- A invariante gráfica es multiplicativo si, para todos los dos gráficos G y H , el valor de la invariante en la unión de la desunión de G y H es el producto de los valores de G y de H . Por ejemplo, el índice de Hosoya (número de coincidencias) es multiplicativo. [1]
- A invariante gráfico se maxing si, para todos los dos gráficos G y H , el valor de la invariante en la unión de la desunión de G y H es el máximo de los valores de G y de H . Por ejemplo, el número cromático está al máximo. [1]
Además, las propiedades de los gráficos se pueden clasificar de acuerdo con el tipo de gráfico que describen: si el gráfico no está dirigido o no está dirigido , si la propiedad se aplica a los gráficos múltiples , etc. [1]
Valores de invariantes
El conjunto objetivo de una función que define una gráfica invariante puede ser uno de los siguientes:
- Un valor de verdad, verdadero o falso, para la función indicadora de una propiedad gráfica.
- Un número entero, como el número de vértices o el número cromático de un gráfico.
- Un número real , como el número cromático fraccionario de un gráfico.
- Una secuencia de números enteros, como la secuencia de grados de un gráfico.
- Un polinomio , como el polinomio de Tutte de un gráfico.
Gráficos invariantes e isomorfismo gráfico
Los invariantes de gráficos fácilmente calculables son fundamentales para el reconocimiento rápido del isomorfismo del gráfico , o más bien el no isomorfismo, ya que para cualquier invariante, dos gráficos con valores diferentes no pueden (por definición) ser isomorfos. Sin embargo, dos gráficos con las mismas invariantes pueden ser o no isomórficos.
A invariante gráfica I ( G ) se llama completa si la identidad de los invariantes I ( G ) y I ( H ) implica la isomorfismo de los gráficos G y H . Encontrar una invariante que se pueda calcular de manera eficiente (el problema de la canonización de grafos ) implicaría una solución fácil al desafiante problema de isomorfismo de grafos . Sin embargo, incluso los invariantes con valores de polinomio, como el polinomio cromático , no suelen estar completos. El gráfico de garra y el gráfico de ruta en 4 vértices tienen el mismo polinomio cromático, por ejemplo.
Ejemplos de
Propiedades
- Gráficos conectados
- Gráficos bipartitos
- Gráficos planos
- Gráficos sin triángulos
- Gráficos perfectos
- Gráficos eulerianos
- Gráficos hamiltonianos
Invariantes enteros
- Orden , el número de vértices
- Tamaño , el número de bordes
- Número de componentes conectados
- Rango de circuito , una combinación lineal de la cantidad de aristas, vértices y componentes
- diámetro , la más larga de las trayectorias más cortas entre pares de vértices
- circunferencia , la longitud del ciclo más corto
- Conectividad de vértices , el menor número de vértices cuya eliminación desconecta el gráfico
- Conectividad de borde , el menor número de bordes cuya eliminación desconecta el gráfico
- Número cromático , el menor número de colores para los vértices en una coloración adecuada
- Índice cromático , la menor cantidad de colores para los bordes en un color de borde adecuado
- Elección (o enumerar el número cromático ), el menor número k tal que G es k-elegible
- Número de independencia , el tamaño más grande de un conjunto independiente de vértices
- Número de camarilla , el orden más grande de un subgrafo completo
- Arboricidad
- Género gráfico
- Número de página
- Índice de Hosoya
- Índice de salchicha
- Gráfico de Colin de Verdière invariante
- Boxicidad
Invariantes de números reales
- Coeficiente de agrupamiento
- Centralidad de intermediación
- Número cromático fraccional
- Conectividad algebraica
- Número isoperimétrico
- Índice de Estrada
- Fuerza
Secuencias y polinomios
- Secuencia de grados
- Espectro gráfico
- Polinomio característico de la matriz de adyacencia
- Polinomio cromático , el número de-colorings vistos en función de
- Polinomio de Tutte , una función bivariada que codifica gran parte de la conectividad del gráfico
Ver también
- Lógica de gráficos , uno de los varios lenguajes formales que se utilizan para especificar las propiedades de los gráficos
- Índice topológico , un concepto estrechamente relacionado en la teoría de grafos químicos.
Referencias
- ^ a b c d e f g h i Lovász, László (2012), "4.1 Parámetros de gráficos y propiedades de gráficos", Grandes redes y límites de gráficos , Publicaciones del coloquio, 60 , American Mathematical Society, págs. 41-42.
- ^ Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "3.10 Graph Parameters", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, 28 , Springer, pp. 54–56, doi : 10.1007 / 978-3-642-27875- 4 , ISBN 978-3-642-27874-7, MR 2920058.