El mayor número de aristas de un grafo bipartito

Question

Sea $G$ sea un grafo bipartito en $p$ vértices. Halla una fórmula en términos de $p$ que determina el mayor número de aristas que $G$ podría tener. Demuestra que esta fórmula es correcta.

Sea $V$ sea el conjunto de vértices de $G$ . Entonces $\lvert V \rvert = p$ .

Sea $M$ sea el conjunto de vértices del grupo uno para $G$ .

Sea $N$ sea el conjunto de vértices del grupo dos para $G$ .

El número máximo de aristas que $G$ puede tener es:

$$\lvert M\rvert \lvert N\rvert$$

Lo que implica que cada vértice del grupo uno es adyacente a cada vértice del grupo dos.

Imagínese $\lvert M\rvert$ y $\lvert N \rvert$ como lados de un rectángulo. Entonces dicho rectángulo tendría un perímetro igual a $2p$ y una superficie de $\lvert M\rvert \lvert N\rvert$ .

Utilizando el perímetro para resolver $\lvert N \rvert = p - \lvert M\rvert$ . Introduce este valor en la fórmula de Área y toma la derivada para maximizar el área del rectángulo:

$$\frac{dA}{d\lvert M\rvert} = p-2\lvert M \rvert$$ $$\frac{p}{2} = \vert M \rvert$$

Tenga en cuenta que $N \cup M = V$ y así $\lvert M \rvert + \lvert N \rvert = p$

Sustitución $\frac{p}{2}$ para $\lvert M \rvert$ se revela que $\lvert N \rvert = \lvert M \rvert$ .

Por lo tanto, la fórmula para el mayor número de aristas en un grafo bipartito en $p$ bordes es $\frac{p^2}{4}$ . $\blacksquare$

¿Es una prueba válida? Agradecería cualquier consejo.

Answer 1

Todo se ve bien excepto cuando $p$ es impar, la parte donde dices que tiene como mucho $MN$ bordes si las piezas tienen tamaños $M$ y $N$ es muy bueno.

Yo procedería de la siguiente manera:

Claramente $M+N=p$ por lo que podemos suponer $M\geq N$ y $M=\frac{p+k}{2}$ y $N=\frac{p-k}{2}$ para un número entero no negativo $k$ . Las opciones de $k$ son $0,2,\dots,p$ si $p$ es par y $1,3,\dots p$ cuando $p$ es impar.

Obsérvese que el número de aristas es entonces $\frac{p^2-k^2}{4}$ . Por tanto, se maximiza cuando $k=1$ si $p$ es impar y cuando $k=0$ cuando $p$ es par. Así que la respuesta final es $\frac{p^2}{4}$ cuando $p$ es par y $\frac{p^2-1}{4}$ cuando $p$ es impar.

Answer 2

Como se ha señalado en los comentarios, el uso de técnicas continuas como la diferenciación cuando se trata de un problema discreto como éste es un poco sospechoso. Aunque a menudo es una buena heurística, convertirla en una prueba adecuada puede ser a veces un poco tedioso.

La respuesta de Carry on Smiling es una buena manera de resolver este problema sin salirse del ámbito discreto. A continuación mostraré otra técnica general, ya que a menudo puede ser útil en estas situaciones: es una versión discreta de la técnica variacional.

Muy a menudo, estos problemas de optimización discreta se resuelven considerando las variables lo más iguales posible, por ejemplo, cuando se maximiza una función convexa con la suma de las variables fija. Por ejemplo, aquí tenemos dos variables, $M$ y $N$ con la función $MN$ a maximizar y la restricción $M + N = p$ .

Sin pérdida de generalidad, podemos suponer $M \ge N$ . Queremos demostrar que $M$ y $N$ deben ser lo más iguales posible. Por contradicción, supongamos $M - N \ge 2$ . Considerar la disminución $M$ por $1$ y aumentando $N$ por $1$ es decir, establecer $M' = M - 1$ y $N' = N+1$ . Entonces $M' + N' = M - 1 + N + 1 = p$ y $$ M' N' = (M - 1)(N + 1) = MN - N + M - 1 = MN + (M - N - 1) > MN, $$ desde $M \ge N + 2$ .

Por lo tanto, si $(M,N)$ es óptima, deben ser lo más iguales posible, por lo que $M = \left\lceil \frac{p}{2} \right\rceil$ y $N = \left\lfloor \frac{p}{2} \right\rfloor$ .

También se puede aplicar este argumento a nivel de grafo: consideremos el grafo bipartito completo con partes de tamaño $M$ y $N$ y si $M \ge N + 2$ mueve un vértice de la parte más grande a la más pequeña y cuenta lo que ocurre con el número de aristas.

Aunque esto puede no parecer tan útil, considere el problema más general de determinar el número máximo de aristas en un $k$ -partito en $p$ vértices. Escribir la forma exacta del máximo es un coñazo, pero este argumento variacional se resuelve con bastante facilidad. Dejaré los detalles como ejercicio para el lector ;-)