En teoría de grafos , una propiedad de grafo o invariante de grafo es una propiedad de los grafos que depende únicamente 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 grafos son temas válidos en la teoría de grafos, para enfocarnos solo en la estructura abstracta de los grafos, una propiedad de grafo se define como una propiedad que se conserva bajo todos los isomorfismos posibles de un grafo. En otras palabras, es una propiedad del grafo en sí, no de un dibujo o representación específicos del grafo. De manera informal, el término "invariante de grafo" se utiliza para propiedades expresadas cuantitativamente, mientras que "propiedad" generalmente se refiere a caracterizaciones descriptivas de grafos. Por ejemplo, la afirmación "el grafo no tiene vértices de grado 1" es una "propiedad", mientras que "la cantidad de vértices de grado 1 en un grafo" es una "invariante".
Más formalmente, una propiedad de grafo es una clase de grafos con la propiedad de que dos grafos isomorfos cualesquiera pertenecen a la clase, o ambos no pertenecen a ella. [1] De manera equivalente, una propiedad de grafo puede formalizarse utilizando la función indicadora de la clase, una función de grafos a valores booleanos que es verdadera para los grafos de la clase y falsa en caso contrario; de nuevo, dos grafos isomorfos cualesquiera deben tener el mismo valor de función entre sí. Un invariante de grafo o parámetro de grafo puede formalizarse de manera similar como una función de grafos 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 grafos isomorfos cualesquiera. [2]
Propiedades de las propiedades
Muchas propiedades de gráficos se comportan bien con respecto a ciertos órdenes parciales o preórdenes naturales definidos en los gráficos:
Una propiedad de un grafo es monótona si cada subgrafo de un grafo con la propiedad P también tiene la propiedad P . Por ejemplo, ser un grafo bipartito o ser un grafo 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 grafo es menor-cerrada si cada menor de un grafo con propiedad P también tiene la propiedad P . Por ejemplo, ser un grafo plano es menor-cerrado. Toda propiedad menor-cerrada es monótona, pero no necesariamente al revés; por ejemplo, los menores de grafos sin triángulos no son necesariamente libres de triángulos. [1]
Estas definiciones pueden extenderse desde las propiedades a los invariantes numéricos de los gráficos: un invariante gráfico es hereditario, monótono o menor cerrado si la función que formaliza el invariante forma una función monótona a partir del orden parcial correspondiente en los gráficos de los números reales.
Además, se han estudiado los invariantes de grafos con respecto a su comportamiento con respecto a las uniones disjuntas de grafos:
Un invariante de grafo es aditivo si, para todos los dos grafos 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 en H . Por ejemplo, el número de vértices es aditivo. [1]
Un invariante de grafo es multiplicativo si, para todos los dos grafos G y H , el valor del invariante en la unión disjunta de G y H es el producto de los valores en G y en H . Por ejemplo, el índice de Hosoya (número de coincidencias) es multiplicativo. [1]
Un invariante de grafo es máx. si, para todos los dos grafos 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 en H . Por ejemplo, el número cromático es máx. [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 multigráficos , etc. [1]
Valores de invariantes
El conjunto de destino de una función que define un invariante gráfico 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.
Los invariantes de grafos fácilmente computables son fundamentales para el reconocimiento rápido del isomorfismo de grafos , o más bien del no isomorfismo, ya que para cualquier invariante, dos grafos con valores diferentes no pueden (por definición) ser isomorfos. Sin embargo, dos grafos con los mismos invariantes pueden o no ser isomorfos.
Un invariante de grafo I ( G ) se llama completo si la identidad de los invariantes I ( G ) e I ( H ) implica el isomorfismo de los grafos G y H . Encontrar un invariante de este tipo computable de manera eficiente (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 polinómicos, como el polinomio cromático, no suelen ser completos. El grafo de garra y el grafo de trayectoria en 4 vértices tienen ambos el mismo polinomio cromático, por ejemplo.
^ abcdefghi Lovász, László (2012), "4.1 Parámetros y propiedades de gráficos", Large Networks and Graph Limits , Colloquium Publications, vol. 60, American Mathematical Society, págs. 41–42, ISBN 978-1-4704-1583-9.
^ Nešetřil, Jaroslav ; Ossona de Mendez, Patrice (2012), "3.10 Parámetros de grafos", Sparsity: Graphs, Structures, and Algorithms , Algorithms and Combinatorics, vol. 28, Springer, págs. 54–56, doi :10.1007/978-3-642-27875-4, ISBN978-3-642-27874-7, Sr. 2920058.
