Mostrar que $$|E(G)| ≤ \alpha_{0} (G) \beta_{0} (G)$$ where $\alpha_{0} (G)$ is the maximum independent set number and $\beta_{0} (G)$ es el mínimo vértice de la cubierta número de un bipartito gráfico G.
He intentado un enfoque usando el hecho de que arithematic media mayor o igual a la media geométrica (aplicada por $\alpha_{0} (G)$$\beta_{0} (G)$, ya que la suma es n), pero que me dieron no se donde. Se agradece cualquier ayuda, gracias!
No importa, lo resuelto (hice la pregunta sin iniciar sesión): deje que el bipartito gráfico sea G[X, Y]. Vamos $m = |X|$, $n = |Y|$. Vamos $p = max(m, n)$, $q = min(m, n)$.
A continuación, $\alpha_{0} >= p$ (ya que ningún elemento en una partición es adyacente a cualquier elemento de la misma partición) y $\beta_{0} >= q$ (ya que para cubrir todos los bordes, es suficiente, pero es necesario, para incluir todos los vértices en la partición más pequeña).
Por lo $$\alpha_{0}\beta_{0} ≥ pq = mn ≥ |E|$$
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
