Propiedad gráfica

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 las representaciones del grafo, como etiquetas o dibujos particulares del mismo. ^{[ 1 ]}

Si bien el dibujo y la representación de grafos son temas válidos en la teoría de grafos, para centrarnos únicamente 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 mismo. De manera informal, el término "invariante de grafo" se usa para propiedades expresadas cuantitativamente, mientras que "propiedad" generalmente se refiere a caracterizaciones descriptivas de los grafos. Por ejemplo, la afirmación "un grafo no tiene vértices de grado 1" es una "propiedad", mientras que "el número de vértices de grado 1 en un grafo" es un "invariante".

De forma más formal, una propiedad de grafo es una clase de grafos con la propiedad de que cualesquiera dos grafos isomorfos pertenecen a la clase o no pertenecen a ella. ^{[ 1 ]} De forma equivalente, una propiedad de grafo puede formalizarse utilizando la función indicadora de la clase, una función que asigna valores booleanos a los grafos de la clase y es verdadera para los grafos de la clase y falsa en caso contrario; de nuevo, cualesquiera dos grafos isomorfos deben tener el mismo valor de función. Un invariante o parámetro de grafo puede formalizarse de forma similar como una función que asigna valores a los grafos de una clase más amplia de valores, como enteros, números reales , secuencias de números o polinomios , que también tiene el mismo valor para cualesquiera dos grafos isomorfos. ^{[ 2 ]}

Muchas propiedades de los grafos se comportan adecuadamente con respecto a ciertos órdenes parciales naturales o preórdenes definidos en los grafos:

• Una propiedad P de un grafo es hereditaria si todo subgrafo inducido de un grafo con la propiedad P también posee la propiedad P. Por ejemplo, ser un grafo perfecto o ser un grafo cordal son propiedades hereditarias. ^{[ 1 ]}
• Una propiedad de un grafo es monótona si todo subgrafo de un grafo con la propiedad P también posee la propiedad P. Por ejemplo, ser un grafo bipartito o ser un grafo libre de triángulos es monótono. Toda propiedad monótona es hereditaria, pero no necesariamente a la inversa; 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 cerrada por menores si todo menor de un grafo con la propiedad P también posee la propiedad P. Por ejemplo, ser un grafo planar es cerrado por menores. Toda propiedad cerrada por menores es monótona, pero no necesariamente a la inversa; por ejemplo, los menores de grafos libres de triángulos no son necesariamente libres de triángulos. ^{[ 1 ]}

Estas definiciones pueden extenderse desde propiedades a invariantes numéricos de grafos: un invariante de grafo es hereditario, monótono o cerrado en menores si la función que formaliza el invariante forma una función monótona desde el orden parcial correspondiente en los grafos hasta los números reales.

Además, se han estudiado los invariantes de grafos con respecto a su comportamiento en relación con uniones disjuntas de grafos:

• Un invariante de grafo es aditivo si, para cualquier par de 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 cualquier par de 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 emparejamientos) es multiplicativo. ^{[ 1 ]}
• Un invariante de grafo es máximo si, para cualquier par de 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áximo. ^{[ 1 ]}

Además, las propiedades de los grafos se pueden clasificar según el tipo de grafo que describen: si el grafo es no dirigido o dirigido , si la propiedad se aplica a multigrafos , etc. ^{[ 1 ]}

El conjunto objetivo de una función que define un invariante de grafo 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 grafo.
• Un número real , como por ejemplo el número cromático fraccionario de un gráfico.
• Una secuencia de números enteros, como por ejemplo la secuencia de grados de un grafo.
• Un polinomio , como el polinomio de Tutte de un grafo.

Los invariantes de grafos fácilmente computables son fundamentales para el reconocimiento rápido del isomorfismo de grafos , o más bien de la no isomorfía, 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 denomina 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 que se pueda calcular eficientemente (el problema de la canonización de grafos ) implicaría una solución sencilla al complejo problema del isomorfismo de grafos . Sin embargo, incluso los invariantes con valores polinomiales, como el polinomio cromático, no suelen ser completos. Por ejemplo, el grafo de garra y el grafo de camino con 4 vértices tienen el mismo polinomio cromático.

• Propiedad hereditaria
• Lógica de grafos , uno de los diversos lenguajes formales utilizados para especificar las propiedades de los grafos.
• Índice topológico , un concepto estrechamente relacionado en la teoría de grafos químicos.

• Lista de invariantes enteros