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 41: | Línea 41: | ||
Para todo <math>v \in V</math>, <math>d(v) = 3</math>. Entonces, <math>\sum_{i=1}^{7} d(v_i) = \sum_{i=1}^{7} 3 = 21 = 2m \Rightarrow m = \frac{21}{2} \notin \mathbb{N}</math> | Para todo <math>v \in V</math>, <math>d(v) = 3</math>. Entonces, <math>\sum_{i=1}^{7} d(v_i) = \sum_{i=1}^{7} 3 = 21 = 2m \Rightarrow m = \frac{21}{2} \notin \mathbb{N}</math> | ||
'''Absurdo!''' m debe ser | '''Absurdo!''' m debe ser par. | ||
==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. |