Solución:
Esta respuesta depende de si sus gráficos pueden tener bucles automáticos o no. Por simplicidad, voy a asumir que no lo son.
Si tiene un componente conectado con x nodos, el número máximo de aristas que puede tener en ese componente conectado es x (x – 1) / 2. Por lo tanto, si tiene n nodos totales y k componentes conectados diferentes, puede imagine distribuir los nodos en los componentes conectados de una manera que maximice la suma de x (x – 1) / 2 entre los componentes conectados.
Específicamente, suponga que sus CC tienen n1, …, nk nodos cada uno. Quieres resolver el siguiente programa cuadrático:
Maximizar: n1(norte1 – 1) / 2 + … + nk(nortek – 1) / 2
Sujeto a: n1 + … + nk = n
Voy a afirmar que esto se maximiza cuando k – 1 de los componentes conectados tienen 1 nodo y el último componente conectado tiene n – k + 1 nodos. Intuitivamente, esto es cierto porque cualquier nodo que elimine del enorme CC provocará una gran caída en el número de posibles bordes que no se compensarán con el escaso aumento en el número de posibles bordes en el otro componente conectado al que se agregó el nodo. .
Bajo esta configuración, el número máximo de bordes posibles en los CC singleton k – 1 será 0 y el número máximo de bordes posibles en el otro CC será (n – k + 1) (n – k) / 2. Por lo tanto, el total debe ser (n – k + 1) (n – k) / 2.
¡Espero que esto ayude!