El número máximo de aristas en un gráfico no dirigido de Node sin bucles propios es
(A) n 2
(B) n(n – 1)/2
(C) n – 1
(D) (n + 1) (n)/2
Respuesta : (B)
Explicación: Antecedentes requeridos – Combinatoria básica
Dado que el gráfico dado no está dirigido, eso significa que el orden de los bordes no importa.
Dado que tenemos que insertar una arista entre todos los pares posibles de vértices, el problema se reduce a encontrar el recuento del número de subconjuntos de tamaño 2 elegidos del conjunto de vértices.
Dado que el conjunto de vértices tiene tamaño n, el número de dichos subconjuntos viene dado por el coeficiente binomial C(n,2) (también conocido como “n elige 2”). Usando la fórmula para coeficientes binomiales, C(n,2) = n(n-1)/2.e
Esta explicación ha sido aportada por Pranjul Ahuja.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA