algorithm - geeksforgeeks - graphs c++
¿Cuál es la cantidad máxima de bordes en un gráfico dirigido con n nodos? (11)
Gráfico dirigido:
Pregunta : ¿Cuál es la cantidad máxima de bordes en un gráfico dirigido con n vértices?
- Suponga que no hay bucles automáticos.
- Supongamos que hay como máximo un borde desde un vértice de inicio dado hasta un vértice final dado.
Cada borde está especificado por su vértice inicial y el vértice final. Hay n opciones para el vértice de inicio. Como no hay bucles automáticos, hay n-1 elecciones para el vértice final. Multiplicarlos juntos cuenta todas las opciones posibles.
Respuesta : n(n−1)
Gráfico no dirigido
Pregunta : ¿Cuál es la cantidad máxima de bordes en un gráfico no dirigido con n vértices?
- Suponga que no hay bucles automáticos.
- Supongamos que hay como máximo un borde desde un vértice de inicio dado hasta un vértice final dado.
En un gráfico no dirigido, cada borde está especificado por sus dos puntos finales y el orden no importa. El número de bordes es, por lo tanto, el número de subconjuntos de tamaño 2 elegidos del conjunto de vértices. Como el conjunto de vértices tiene el tamaño n, el número de tales subconjuntos viene dado por el coeficiente binomial C (n, 2) (también conocido como "n choose 2"). Usando la fórmula para coeficientes binomiales, C (n, 2) = n (n-1) / 2.
Respuesta : (n*(n-1))/2
¿Cuál es la cantidad máxima de bordes en un gráfico dirigido con n nodos? ¿Hay algún límite superior?
Además de la explicación intuitiva que proporcionó Chris Smith, podemos considerar por qué este es el caso desde una perspectiva diferente: considerando los gráficos no dirigidos.
Para ver por qué en un gráfico DIRIGIDO la respuesta es n*(n-1) , considere un gráfico no dirigido (lo que simplemente significa que si hay un enlace entre dos nodos (A y B) puede ir en ambos sentidos: desde A a B y de B a A). El número máximo de bordes en un gráfico no dirigido es n(n-1)/2 y, obviamente, en un gráfico dirigido hay el doble .
Bien , podrías preguntar, pero ¿por qué hay un máximo de n(n-1)/2 bordes en un gráfico no dirigido ? Para eso, considere n puntos (nodos) y pregunte cuántos bordes puede hacer desde el primer punto. Obviamente, n-1 bordes. Ahora, ¿cuántos bordes puede extraer uno del segundo punto, dado que conectó el primer punto? Como el primero y el segundo punto ya están conectados, hay n-2 bordes que se pueden hacer. Y así. Entonces la suma de todos los bordes es:
Sum = (n-1)+(n-2)+(n-3)+...+3+2+1
Como hay (n-1) términos en la suma, y el promedio de la suma en dicha serie es ((n-1)+1)/2 {(último + primero) / 2}, Sum = n(n-1)/2
En un gráfico dirigido que tiene N vértices, cada vértice puede conectarse a N-1 otros vértices en el gráfico (Asumiendo, no hay bucle). Por lo tanto, el número total de bordes puede ser N (N-1).
En un gráfico no dirigido (excluyendo multigrafos), la respuesta es n * (n-1) / 2. En un gráfico dirigido, puede aparecer un borde en ambas direcciones entre dos nodos, luego la respuesta es n * (n-1).
La respuesta correcta es n * (n-1) / 2. Cada borde se ha contado dos veces, de ahí la división por 2. Un gráfico completo tiene el número máximo de bordes, que viene dado por n elige 2 = n * (n-1) / 2.
No dirigido es N ^ 2. Simple: cada nodo tiene N opciones de bordes (incluido él mismo), un total de N nodos, por lo tanto N * N
Poniéndolo de otra manera:
Un gráfico completo es un gráfico no dirigido en el que cada par distinto de vértices tiene un borde único que los conecta. Esto es intuitivo en el sentido de que, básicamente, eliges 2 vértices de una colección de n vértices.
nC2 = n!/(n-2)!*2! = n(n-1)/2
Este es el número máximo de bordes que un gráfico no dirigido puede tener. Ahora, para el gráfico dirigido, cada borde se convierte en dos bordes dirigidos. Así que simplemente multiplique el resultado anterior por dos. Eso te da el resultado: n (n-1)
Puede haber tantos como n(n-1)/2 bordes en el gráfico si no se permite multi-edge.
Y esto se puede lograr si etiquetamos los vértices 1,2,...,n y hay un borde de i a j iff i>j .
Mira here .
Si el gráfico no es un gráfico múltiple, entonces es claramente n * (n - 1), ya que cada nodo puede, como máximo, tener bordes para cada otro nodo. Si esto es un multigrafo, entonces no hay un límite máximo.
También se puede considerar como el número de formas de elegir pares de nodos n elegir 2 = n (n-1) / 2. Verdadero si solo un par puede tener solo un borde. Multiplica por 2 de lo contrario
Si tiene N nodos, hay N - 1 bordes dirigidos que pueden conducir desde él (yendo a cada otro nodo). Por lo tanto, el número máximo de bordes es N * (N - 1) .