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 45: | Línea 45: | ||
==Ejercicio 05.06:== | ==Ejercicio 05.06:== | ||
Probar que un grafo <math>G=(V,X)</math> es conexo si y sólo si para toda partición de <math>V</math> en dos subconjuntos <math>V_{1}</math> y <math>V_{2}</math> | Probar que un grafo <math>G=(V,X)</math> es conexo si y sólo si para toda partición de <math>V</math> en dos subconjuntos <math>V_{1}</math> y <math>V_{2}</math> | ||
(<math>V_{1} \ne \ | (<math>V_{1} \ne \empty</math>, <math>V_{2} \ne \empty</math>, <math>V_{1} \bigcap V_{2} = \empty</math>, <math>V_{1} \cup V_{2} = V</math>) | ||
hay un arco de G que une un punto de <math>V_{1}</math> con uno de <math>V_{2}</math>. | hay un arco de G que une un punto de <math>V_{1}</math> con uno de <math>V_{2}</math>. | ||
=>) Sup. que no hay arcos de V1 a V2. Sea W1={V1} y W2={V2,..,Vn}. Pero como no hay arco de V1 a V2, entonces no existe camino de V1 a V2. G no es conexo. ABS | =>) Sup. que no hay arcos de V1 a V2. Sea W1={V1} y W2={V2,..,Vn}. Pero como no hay arco de V1 a V2, entonces no existe camino de V1 a V2. G no es conexo. ABS | ||
<=) Sup. que no es conexo -> existen 2 vertices vi,vj | <=) Sup. que no es conexo -> existen 2 vertices vi,vj / no hay camino entre ellos. | ||
<br>Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi. | <br>Elegimos W1={vi} U Z1, / Z1 = conj. de vertices alcanzables desde vi. | ||
<br>Elegimos W2={vj} U Z2 U X, /Z2 = conj. de vertices alcanzables desde vj y X conj. de vertices NO alcanzables desde vi y vj. | <br>Elegimos W2={vj} U Z2 U X, /Z2 = conj. de vertices alcanzables desde vj y X conj. de vertices NO alcanzables desde vi y vj. | ||
Línea 68: | Línea 68: | ||
** 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 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-1)(n-2)/2 < m(G) = m(G') + d(v) <= (n-2)(n-3)/2 + d(v) -> d(v) > n-1 -> ABS | ||
==Ejercicio 05.08:== | ==Ejercicio 05.08:== |