Encuentra el máximo no. de bordes en el gráfico

Hay 'n' vértices y 0 bordes de un gráfico no dirigido. ¿Cuál puede ser el número máximo de bordes que podemos dibujar de manera que el gráfico permanezca desconectado?Encuentra el máximo no. de bordes en el gráfico

He tomado la solución de que podemos excluir un vértice y podemos encontrar el número máximo de aristas entre n-1 vértices del gráfico no dirigido, de modo que el gráfico permanece desconectado. que es n (n-1)/2 para n vértices y será (n-1) (n-2)/2 para n-1 vértices ¿Puede haber una mejor solución?

Fuente

2012-04-08 Luv

Su solución debe ser la mejor solución.

Porque cualquier borde nuevo agregado debe tener el n-ésimo vértice en un extremo.

Fuente

2012-04-08 10:35:58 sukunrt

La razón provista '" porque cualquier borde nuevo agregado debe tener el n-ésimo vértice en un extremo "' proporciona una explicación de por qué es un * máximo local * y no un * máximo global *. Esta explicación no cubre soluciones con una estructura completamente diferente, que podría tener más bordes, sin una prueba adecuada de por qué no podrían hacerlo. – amit

El número de aristas para un multigrafo es obviamente infinito. Ahora bien, si no puede tener auto bucles, entonces tiene que seleccionar dos vértices para agregar un borde. Has conectado por completo los primeros vértices (n-1). Para agregar un borde más, los vértices no pueden venir del conjunto inicial de vértices n-1 porque has hecho que todos los bordes sean posibles desde los vértices iniciales n-1. Entonces uno de los bordes tiene que ser el enésimo. Si tiene bucles automáticos permitidos, puede agregar n bordes más porque los bucles automáticos no se agregan a la conectividad. – sukunrt

Eso no cubre en absoluto la posibilidad de gráficos que consisten en dos subgrafos completos de tamaños diferentes de 1, n-1. La solución es (accidentalmente) correcta, pero el razonamiento no lo es. – voidengine

Si el gráfico puede tener bordes múltiples, la respuesta es infinito para n> = 3.
Si también puede contener bucles automáticos, la respuesta es infinito para n> = 2,

Si ninguno de ellos contiene la solución, es correcto.

Fuente

2012-04-08 10:56:32 kilotaras

Puede resolver esto mediante el análisis. Toma tu idea y generalizala. Divides los n vértices en dos grupos, del tamaño x y n-x. Ahora el número de aristas es una función de x, expresada por

f(x)= x(x-1)/2 + (n-x)(n-x-1)/2 
    f(x) = 1/2(2x^2 - 2nx +n^2 - n)

El valor que maximizan esta función es el tamaño de la partición que desea. Si realiza el cálculo, encuentra que disminuye de x=0 a x=n/2, luego aumente a x=n. Como x = 0 o x = n significa que se recoge el gráfico, se toma el siguiente valor máximo que es x=1. Entonces tu intuición es óptima.

Fuente

2012-04-08 11:18:11 UmNyobe

+1 Esta solución demuestra por qué la respuesta dada es también un máximo local. Para cubrirse completamente, también puede buscar f '', y descubrir que 'f '' (MIN) <0', y también validar que f (n), f (0) no son soluciones factibles, y valida f (1), f (n-1) – amit

@amit f '(x) = 4x - 2n ... – UmNyobe

y está en lo correcto para f' ' – UmNyobe

Encuentra el máximo no. de bordes en el gráfico

Respuesta

Cuestiones relacionadas