¿Cómo puedo probar la cantidad máxima de bordes?

Question

En mi libro dice que el número máximo de bordes E, en un gráfico sin ponderar no dirigido y sin conexión$G(V,E)$ es$\dfrac{|V|(|V|-1)}{2}$.

¿Cómo puedo demostrar que es verdad? ¡Gracias!

Answer 1

Otra forma de ver este problema es utilizar el `Lema del apretón de manos". La visualización de los vértices de las personas y de los bordes como los apretones de manos, podríamos preguntar ¿cuántos apretones de manos son posibles entre los $n$ personas si cada par de personas se sacude las manos exactamente una vez. Cada persona puede estrechar la mano con los otros $n-1$ de personas en la habitación. No hay, sin embargo, $n(n-1)$ apretones de manos, ya que estamos contando cada apretón de manos exactamente el doble de esta manera (esto vale Alice temblor de Bob mano como un apretón de manos de Bob sacudir a Alice de la mano). Por lo tanto, $\frac{1}{2}n(n-1)$ nos da el número correcto.

Answer 2

Voy a suponer por un momento que usted significó $\dfrac{|V|(|V| - 1)}{2}$, ya que es difícil describir el número de bordes mediante el número de aristas. Y esto surge de forma natural, ya que este es el número de pares de $|V|$ vértices, es decir, este es ${|V| \choose 2}$. Si tenía alguna más, que la gráfica no sería sencillo.

Alternativamente, usted puede ahora saber acerca completa de gráficos, que tienen el máximo número de aristas de un conjunto de vértices. Ellos tienen exactamente este número de aristas. A tener más fuerza para ser no-simple, de nuevo.

Answer 3

Tal vez podrías usar la inducción. Cada nuevo vértice que agregue debe tener suficientes bordes agregados para conectarse a cada uno de los otros vértices. Se supondría que cada uno de los otros ya está conectado.

Answer 4

Suponga que hay V número de personas.

Vamos a dar a cada apretón de manos a todos los demás, uno por uno, sin ningún tipo de duplicación

Persona 1:
1. Persona 1 apretones de manos con todos los demás (V-1) de las personas, por lo que en total (V-1) apretones de manos se realiza
2. Vamos a eliminar de la Persona 1, desde el grupo de nuevo, para eliminar duplicados de los apretones de manos cuando se selecciona a otras personas

Persona 2
1. Persona 2 apretones de manos con todos los demás (V-2) personas, por lo que en total (V-2) apretones de manos se realiza, V-2, ya que hemos eliminado 1 persona
2. Vamos a eliminar a la Persona 2, del grupo, para eliminar duplicados de los apretones de manos cuando se selecciona a otras personas

etc..

Tenemos 1 apretón de manos desde el pasado dos personas

--

Así, obtenemos (V-1), (V-2), etc. los apretones de manos sin ningún tipo de duplicación

Así, la Suma de todos los apretones de manos = (V-1) + (V-2) ..
Sabemos, N + (N-1) .. es N*(N+1)/2
Reemplazando N con V-1, obtenemos
total de apretones de manos = (V-1) * (V-1+1) /2 = (V-1)*V/2

No duplicar los apretones de manos analogía es similar al número Máximo de aristas, en un simplemente conectado grafo no ponderado gráfica de V vértices

Así, el total de los bordes en el gráfico simple = (V-1)*V/2

La mejor de las suertes