Edición de «Práctica 5: Clases de Grafos (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 66: | Línea 66: | ||
*Sup. m(G') > (n-2)(n-3)/2 | *Sup. m(G') > (n-2)(n-3)/2 | ||
** Si d(v) > 0 -> v conecta con algun vert. de G' -> Como G' es conexo, G sigue siendo conexo | ** Si d(v) > 0 -> v conecta con algun vert. de G' -> Como G' es conexo, G sigue siendo conexo | ||
** Si d(v) = 0 -> m(G) = m(G') > (n-1)(n-2)/2. Pero G' no puede tener mas ejes que el grafo completo K(n-1) -> ABS | ** Si d(v) = 0 -> m(G) = m(G') > (n-1)(n-2)/2. Pero m(G') no puede tener mas ejes que el grafo completo K(n-1) -> ABS | ||
*Sup. m(G') <= (n-2)(n-3)/2 | *Sup. m(G') <= (n-2)(n-3)/2 | ||
**(n-1)(n-2)/2 < m(G) = m(G') + d(v) <= (n-2)(n-3)/2 + d(v) --> n > d(v) > n-2 --> d(v) = n-1 --> G es conexo. | **(n-1)(n-2)/2 < m(G) = m(G') + d(v) <= (n-2)(n-3)/2 + d(v) --> n > d(v) > n-2 --> d(v) = n-1 --> G es conexo. |