Las identidades de Gallai

Las identidades de Gallai en la teoría de grafos son relaciones entre las características numéricas de un gráfico arbitrario : número de independencia , número de cobertura de vértices , número coincidente y número de cobertura de bordes . $GRAMO$ ${\ estilo de visualización \ alfa (G)}$ ${\ estilo de visualización \ tau (G)}$ ${\ estilo de visualización \ nu (G)}$ ${\ estilo de visualización \ rho (G)}$

Las identidades fueron publicadas por el matemático húngaro Tibor Gallai en 1959 1El propio Gallai afirmó que había obtenido estos resultados ya en 1932, aunque creía que Koenig ya los conocía en ese momento.

Primera identidad de Gallai

En cualquier gráfico , la relación se cumple . $G=(V,E)$ ${\ estilo de visualización \ alfa (G) + \ tau (G) = | V |}$

Prueba

Sea la cubierta de vértice más pequeña en el gráfico . Considere un conjunto de vértices . Como cualquier arista incide en al menos un vértice del conjunto , ninguna arista conecta dos vértices del conjunto . Por lo tanto, es un conjunto independiente de vértices en el gráfico y su tamaño no excede el tamaño del conjunto independiente de vértices más grande, es decir, . $T$ $GRAMO$ $V\setminus T$ ${\ estilo de visualización e \ en E}$ $T$ $V\setminus T$ $V\setminus T$ $GRAMO$ ${\ estilo de visualización | V | - \ tau (G)}$ ${\ estilo de visualización \ alfa (G)}$

Considerando el mayor conjunto independiente de vértices del gráfico y haciendo el mismo razonamiento a la inversa, obtenemos la desigualdad , que junto con la primera desigualdad da . $GRAMO$ ${\ estilo de visualización | V | - \ alfa (G) \ geq \ tau (G)}$ ${\ estilo de visualización \ alfa (G) + \ tau (G) = | V |}$

La segunda identidad de Gallai

En cualquier gráfico que no contenga vértices aislados (es decir, vértices con grado 0), se cumple la siguiente relación . $G=(V,E)$ ${\ estilo de visualización \nu (G)+\rho (G)=|V|}$

Nota:

Si hay al menos un vértice aislado en el gráfico, entonces no hay cobertura de borde, por lo tanto, el número de cobertura de borde no está definido. ${\ estilo de visualización \ rho (G)}$

Prueba

Considere la cobertura de borde más pequeña en el gráfico . Si contuviera ciclos , entonces sería posible quitar uno de los bordes del ciclo, obteniendo un recubrimiento de borde de tamaño uno menos. Por lo tanto, forma un bosque en el conjunto de vértices , y se cumple la igualdad , donde es el número de componentes de conectividad en este bosque. Tomando una arista de cada componente conectado, obtenemos una coincidencia en un gráfico de tamaño . Por lo tanto, el tamaño de la coincidencia más grande es . $R$ $GRAMO$ $R$ $R$ $V$ ${\ estilo de visualización | V | - | R | = K}$ $k$ $GRAMO$ ${\ estilo de visualización | V | - \ rho (G)}$ ${\ estilo de visualización \ nu (G) \ geq | V | - \ rho (G)}$

A continuación, considere la coincidencia más grande en el gráfico . Satura los vértices del gráfico , por lo tanto, los vértices permanecen sin saturar. Tomemos un borde para cada vértice no saturado del gráfico, denotemos el conjunto de dichos bordes . Si al menos una arista de conectara dos vértices no saturados a la vez, esta arista podría agregarse a la coincidencia , lo cual es imposible, ya que esta es la coincidencia más grande. Por tanto, el conjunto contiene exactamente aristas. El conjunto es una cubierta de borde en el gráfico , por lo tanto, su tamaño no es menor que el tamaño de la cubierta de borde más pequeña . $norte$ $GRAMO$ $2\cdot\nu (G)$ $GRAMO$ $|V|-2\cdot\nu (G)$ $N_1$ $N_1$ $norte$ $N_1$ $|V|-2\cdot\nu (G)$ ${\displaystyle N\taza N_{1))$ $GRAMO$ ${\ estilo de visualización | V | - \ nu (G)}$ ${\ estilo de visualización \ rho (G)}$

Combinando las desigualdades y , obtenemos la identidad deseada . ${\ estilo de visualización \ nu (G) \ geq | V | - \ rho (G)}$ ${\ estilo de visualización | V | - \ nu (G) \ geq \ rho (G)}$ ${\ estilo de visualización \nu (G)+\rho (G)=|V|}$

Enlaces

↑ T. Gallai: Über extreme Punkt- und Kantenmengen. Ana. Universidad ciencia budapest Secta Eötvös. Matemáticas. 2 (1959), 133–138.