Sé que en un gráfico con n vértices hay m = (n(n-1)/2) aristas, pero en un gráfico con m aristas, ¿cuántos vértices hay?
Respuesta
¿Demasiados anuncios?
Laars Helenius
Puntos
3310
No está claro en su pregunta si está asumiendo que $G$ es un gráfico completo. Para responder a esto con precisión, necesitamos saber algo más sobre el gráfico que contiene el $m$ bordes.
Por ejemplo:
- A la combinación perfecta con $m$ bordes tiene exactamente $2m$ vértices.
- A árbol con $m$ bordes tiene exactamente $m+1$ vértices.
- A gráfico completo con $m$ los bordes tendrán $\dfrac{1+\sqrt{1+8m}}{2}$ vértices.
En general, a medida que la conectividad de $G$ aumenta para un número fijo de aristas, el número de vértices necesariamente disminuye.
