Solución:
Si usted tiene N nodos, hay N - 1 bordes dirigidos que pueden derivar de él (yendo a todos los demás nodos). Por lo tanto, el número máximo de aristas es N * (N - 1).
Gráfico dirigido:
Pregunta: ¿Cuál es el número máximo de aristas en un gráfico dirigido con n vértices?
- Suponga que no hay bucles propios.
- Suponga que hay como máximo una arista desde un vértice inicial dado hasta un vértice final dado.
Cada arista se especifica por su vértice inicial y su vértice final. Hay n opciones para el vértice inicial. Dado que no hay bucles propios, hay n-1 opciones para el vértice final. Al multiplicarlos, se cuentan todas las opciones posibles.
Respuesta: n(n−1)
Gráfico no dirigido
Pregunta: ¿Cuál es el número máximo de aristas en un gráfico no dirigido con n vértices?
- Suponga que no hay bucles propios.
- Suponga que hay como máximo una arista desde un vértice inicial dado hasta un vértice final dado.
En un gráfico no dirigido, cada borde se especifica mediante sus dos extremos y el orden no importa. Por tanto, el número de aristas es el número de subconjuntos de tamaño 2 elegidos del conjunto de vértices. Dado que el conjunto de vértices tiene un 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.
Respuesta: (n*(n-1))/2
En un gráfico no dirigido (excluidos los multigrafos), la respuesta es n * (n-1) / 2. En un gráfico dirigido, un borde puede ocurrir en ambas direcciones entre dos nodos, entonces la respuesta es n * (n-1).