En teoría de grafos , una propiedad de grafo o invariante de grafo es una propiedad de los grafos que depende solo de la estructura abstracta, no de representaciones gráficas como etiquetados particulares o dibujos del gráfico. [1]
Definiciones
Si bien el dibujo y la representación de gráficos son temas válidos en la teoría de grafos, para centrarse solo en la estructura abstracta de los gráficos, una propiedad de gráfico se define como una propiedad preservada 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ífica del gráfico. De manera informal, el término "invariante de gráfico" se utiliza para propiedades expresadas cuantitativamente, mientras que "propiedad" generalmente se refiere a caracterizaciones descriptivas de gráficos. Por ejemplo, la afirmación "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 una "invariante".
Más formalmente, una propiedad de gráfico es una clase de gráficos con la propiedad de que dos gráficos isomórficos cualesquiera pertenecen a la clase o no pertenecen a ella. [1] De manera equivalente, una propiedad de gráfico se puede formalizar utilizando la función indicadora de la clase, una función de gráficos a valores booleanos que es verdadera para los gráficos de la clase y falsa en caso contrario; Nuevamente, dos gráficos isomórficos cualesquiera deben tener el mismo valor de función entre sí. Una invariante de gráfico o un parámetro de gráfico puede formalizarse de manera similar como una función de gráficos a una clase más amplia de valores, como números 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 propiedades
Muchas propiedades de los gráficos se comportan bien con respecto a ciertos pedidos parciales naturales o pedidos anticipados definidos en los gráficos:
Una propiedad de un gráfico 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 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 grafos cordales no son necesariamente cordales, por lo que ser un grafo cordal no es monótono. [1]
Una propiedad de gráfico es menor cerrada si cada gráfico menor de un gráfico con propiedad P también tiene la propiedad P. Por ejemplo, ser un gráfico plano es menor-cerrado. Toda propiedad menor cerrada es monótona, pero no necesariamente al revés; por ejemplo, los menores de 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 cerrado menor si la función que formaliza el invariante forma una función monótona desde el orden parcial correspondiente en los gráficos hasta los números reales.
Además, se han estudiado los invariantes de grafos con respecto a su comportamiento frente a uniones disjuntas de grafos:
Un invariante de gráfico es aditivo si, para los dos gráficos G y H , el valor del invariante en la unión disjunta de G y H es la suma de los valores en G y H. Por ejemplo, el número de vértices es aditivo. [1]
Un invariante de gráfico es multiplicativo si, para los dos gráficos G y H , el valor del invariante en la unión disjunta de G y H es el producto de los valores de G y H. Por ejemplo, el índice de Hosoya (número de coincidencias) es multiplicativo. [1]
Un invariante de gráfico está máximo si, para los dos gráficos G y H , el valor del invariante en la unión disjunta de G y H es el máximo de los valores en G y H. Por ejemplo, el número cromático está al máximo. [1]
Además, las propiedades de los gráficos se pueden clasificar según el tipo de gráfico que describen: si el gráfico es dirigido o no dirigido , si la propiedad se aplica a multigrafos , etc. [1]
Valores de invariantes
El conjunto objetivo de una función que define una invariante gráfica puede ser uno de:
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.
Los invariantes de gráficos fácilmente computables son fundamentales para el reconocimiento rápido del isomorfismo del gráfico , o más bien del 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 isomórficos o no.
Un gráfico invariante I ( G ) se llama completo si la identidad de los invariantes I ( G ) e I ( H ) implica el isomorfismo de los gráficos G y H. Encontrar un invariante de este tipo computable eficientemente (el problema de la canonización de grafos ) implicaría una solución fácil al desafiante problema del isomorfismo de grafos . Sin embargo, incluso los invariantes con valores polinomiales, como el polinomio cromático, no suelen estar completos. Por ejemplo, el gráfico de garra y el gráfico de trayectoria en 4 vértices tienen el mismo polinomio cromático.
^ abcdefghi Lovász, László (2012), "4.1 Parámetros y propiedades de gráficos", Grandes redes y límites de gráficos , Publicaciones del coloquio, vol. 60, Sociedad Estadounidense de Matemáticas, págs. 41–42, ISBN 978-1-4704-1583-9.
^ Nešetřil, Jaroslav ; Ossona de Méndez, Patrice (2012), "3.10 Parámetros de gráficos", Escasa: gráficos, estructuras y algoritmos , Algoritmos y combinatoria, vol. 28, Springer, págs. 54–56, doi :10.1007/978-3-642-27875-4, ISBN978-3-642-27874-7, señor 2920058.
