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 de los grafos, como etiquetas o dibujos particulares del grafo. ^[1]

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 en la clase y falsa en caso contrario; nuevamente, 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]

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 grafo P es hereditaria si cada subgrafo inducido de un grafo con la propiedad P también tiene 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 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]

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.
• 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.

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.

• Grafos conectados
• Grafos bipartitos
• Gráficos planares
• Gráficos sin triángulos
• Gráficos perfectos
• Grafos eulerianos
• Gráficas hamiltonianas

• Orden , el número de vértices
• Tamaño , el número de aristas
• Número de componentes conectados
• Rango de circuito , una combinación lineal de los números de aristas, vértices y componentes.
• diámetro , la más larga de las longitudes de camino 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 número más pequeño de colores para los vértices en una coloración adecuada.
• Índice cromático , el número más pequeño de colores para los bordes en una coloración de bordes adecuada.
• Elegibilidad (o número cromático de lista ), 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 Hosoya
• Índice de Viena
• Invariante del gráfico de Colin de Verdière
• Boxicidad

• Coeficiente de agrupamiento
• Centralidad de intermediación
• Número cromático fraccionario
• Conectividad algebraica
• Número isoperimétrico
• Índice de Estrada
• Fortaleza

• Secuencia de grados
• Espectro gráfico
• Polinomio característico de la matriz de adyacencia
• Polinomio cromático , el número de coloraciones visto como una función de${\estilo de visualización k}$${\estilo de visualización k}$
• Polinomio de Tutte , una función bivariada que codifica gran parte de la conectividad del gráfico.

• Propiedad hereditaria
• Lógica de gráficos , uno de varios lenguajes formales utilizados para especificar propiedades de gráficos.
• Índice topológico , un concepto estrechamente relacionado con la teoría de grafos químicos

• Lista de invariantes de números enteros