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 1: | Línea 1: | ||
==Ejercicio 05.01:== | ==Ejercicio 05.01:== | ||
< | <br>3*n = Σ<sub>v</sub> 3 <= Σ<sub>v</sub> d(v) = 2*m = 2*19 = 38 | ||
Entonces n <= 38/3 ∼ 12 | <br>Entonces n <= 38/3 ∼ 12 | ||
==Ejercicio 05.02:== | ==Ejercicio 05.02:== | ||
Línea 26: | Línea 23: | ||
<br>Sup. que vale para un digrafo de n-1 vertices. qvq vale para G, si agregamos un vertice w de k ejes de entrada y j de salida. Sabemos que | <br>Sup. que vale para un digrafo de n-1 vertices. qvq vale para G, si agregamos un vertice w de k ejes de entrada y j de salida. Sabemos que | ||
<br>Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w) | <br>Σ{i=1..n} din(vi) = Σ{i=1..n-1} din(vi) + j + din(w) | ||
<br>Σ{i=1..n} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w) | <br>Σ{i=1..n-1} dout(vi) = Σ{i=1..n-1} dout(vi) + k + dout(w) | ||
<br>Entonces | <br>Entonces | ||
<br>Σ{i=1..n} din(vi) = Σ{i=1..n} dout(vi) <=> Σ{i=1..n-1} din(vi) + j + din(w) = Σ{i=1..n-1} dout(vi) + k + dout(w) <=> (Por HI Σ{i=1..n-1} din(vi) = Σ{i=1..n-1} dout(vi)) j + din(w) = k + dout(w) <=> j + k = k + j -> OK | <br>Σ{i=1..n} din(vi) = Σ{i=1..n} dout(vi) <=> Σ{i=1..n-1} din(vi) + j + din(w) = Σ{i=1..n-1} dout(vi) + k + dout(w) <=> (Por HI Σ{i=1..n-1} din(vi) = Σ{i=1..n-1} dout(vi)) j + din(w) = k + dout(w) <=> j + k = k + j -> OK | ||
Línea 35: | Línea 32: | ||
==Ejercicio 05.05:== | ==Ejercicio 05.05:== | ||
Si esto pasara entonces Σ<sub>v</sub> d(v) = 2*m <=> 21 = 3*7 = Σ<sub>v</sub> 3 = 2*m <=> Impar = Par ABS => No es posible. | |||
==Ejercicio 05.06:== | ==Ejercicio 05.06:== | ||
=>) 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 57: | Línea 44: | ||
==Ejercicio 05.07:== | ==Ejercicio 05.07:== | ||
<br>Por induccion en n: | <br>Por induccion en n: | ||
* CB | * CB; n=2 | ||
m > (n-1)(n-2)/2 = 0. G es conexo <=> G=K2 -> m = 1 > 0 -> OK | <br>m > (n-1)(n-2)/2 = 0. G es conexo <=> G=K2 -> m = 1 > 0 -> OK | ||
* PI: | * PI: | ||
Sea G'= G-v, tq { si m(G') > ((n-1)-1)((n-1)-2)/2 = (n-2)(n-3)/2 -> G' es conexo } | <br>Sea G'= G-v, tq { si m(G') > ((n-1)-1)((n-1)-2)/2 = (n-2)(n-3)/2 -> G' es conexo } | ||
<br>'''qvq si m(G) > (n-1)(n-2)/2 -> G es conexo''' | |||
m(G) = m(G')+d(v) | <br>m(G) = m(G')+d(v) | ||
<br>Sup. m(G') > (n-2)(n-3)/2 -> | |||
** Si d(v) > 0 -> v conecta con algun vert. de G' -> | ** Si d(v) > 0 -> v conecta con algun vert. de 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 | ||
<br>Sup. m(G') <= (n-2)(n-3)/2 -> | |||
<br>(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:== | ||
<br>a) Sup. hay dos caminos C1={vi, | <br>a) Sup. hay dos caminos C1={vi,wi,..,wn,vf} y C2={vi,xl,..,xm,vf} tq {wi,..,wn}∩{xl,..,xm}={}. | ||
Entonces, si se elige otro camino C3 = {vi, | Entonces, si se elige otro camino C3 = {vi,wi,..,wn,vf,xm,..,x1,vi} se obtiene un circuito. | ||
<br>b) | <br>b) | ||
==Ejercicio 05.09:== | ==Ejercicio 05.09:== | ||
Sean G conexo y 2 de los caminos de long. maxima C1 = {vi,vi+1,.., | Sean G conexo y 2 de los caminos de long. maxima C1 = {vi,vi+1,..,wi+k} y C2 = {wi,wi+1,..,wi+k}. Sup. que no tienen un vertice en comun. Como es conexo, hay un camino de Vi a Vj. | ||
* 1. Si vi y vj estan conectados -> ABS (el camino simple de long. maxima seria la union de C1 y C2, que es mas largo que la long. maxima) | |||
* 2. Si no estan conectados a traves que no estan en C1 o C2, esos vertices podrian ser agregados a C1 o C2 -> ABS (C1 y C2 ya no tendria long maxima) | |||
* | |||
==Ejercicio 05.10:== | ==Ejercicio 05.10:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br> =>) | <br> =>) ! | ||
<br> <=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G' | <br> <=) Sup G' es f. conexo. Si G' = G listo. Si G != G, Ex. v en G-G' | ||
<br>Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C. | <br>Como G es conexo, Ex. camino C de v a w (w en G'). Me quedo con el ultimo eje de C. | ||
Línea 104: | Línea 76: | ||
<br>Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo | <br>Por HI e pertenece a un ciclo => G'U{C} es f. conexo -> G es f.conexo | ||
<br>c) | <br>c) | ||
==Ejercicio 05.11:== | ==Ejercicio 05.11:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 05.12:== | ==Ejercicio 05.12:== | ||
==Ejercicio 05.13:== | ==Ejercicio 05.13:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 05.14:== | ==Ejercicio 05.14:== | ||
<br>Si G tiene m ejes -> Gc tiene n(n-1)/2 - m ejes | <br>Si G tiene m ejes -> Gc tiene n(n-1)/2 - m ejes | ||
Línea 142: | Línea 93: | ||
==Ejercicio 05.15:== | ==Ejercicio 05.15:== | ||
R es el conj. de grafos tq: | R es el conj. de grafos tq: | ||
* | * Г(v) inc Г(w) o Г(w) inc Г(v) v,w ady | ||
* | * Г'(v) inc Г'(w) o Г'(w) inc Г'(v) v,w no ady | ||
<pre> | <pre> | ||
Línea 159: | Línea 110: | ||
<br>b) | <br>b) | ||
<br>Sup. no vale | <br>Sup. no vale prop. -> Todo vertices tiene un ady o un no ady. | ||
<br>Sean v el vertice de mayor grado, w | <br>Sean v el vertice de mayor grado, w no en Г(v) | ||
<br>|Г(w)|<=|Г(v)| | <br>|Г(w)|<=|Г(v)| y 1. ->(4). Г(v) inc Г(w) | ||
<br>d(w)>0 | <br>d(w)>0 -> Ex. z en Г(w) -> z en Г(v) | ||
<br>|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y | <br>|Г'(z)| = d(z)+1 <= d(v)+1 = |Г'(v)| y 2. -> Г(z) inc Г(v) -> w en Г(v) ABS | ||
==Ejercicio 05.16:== | ==Ejercicio 05.16:== | ||
Línea 172: | Línea 123: | ||
==Ejercicio 05.17:== | ==Ejercicio 05.17:== | ||
==Ejercicio 05.18:== | ==Ejercicio 05.18:== | ||
==Ejercicio 05.19:== | ==Ejercicio 05.19:== | ||
<br>a) Vale por la biyeccion entre V y V' | <br>a) Vale por la biyeccion entre V y V' | ||
Línea 182: | Línea 128: | ||
<br>c) Es equivalente a decir que d(v) = d(f(v)) | <br>c) Es equivalente a decir que d(v) = d(f(v)) | ||
<br>d) Vale por la biyeccion entre circuitos simples entre G y H | <br>d) Vale por la biyeccion entre circuitos simples entre G y H | ||
<br>e) | <br>e) | ||
<br>f) | <br>f) | ||
<br>g) | <br>g) | ||
==Ejercicio 05.20:== | ==Ejercicio 05.20:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 05.21:== | ==Ejercicio 05.21:== | ||
<br>a) o-o-o-o | <br>a) o-o-o-o | ||
<br>b) Si G es autocomplementario entonces m = n(n-1)/2 - m -> 2m = n(n-1)/2 -> m = n(n-1)/4 (entonces m ≡ 0(4)). Viendo las congruencias modulo 4: | <br>b) Si G es autocomplementario entonces m = n(n-1)/2 - m -> 2m = n(n-1)/2 -> m = n(n-1)/4 (entonces m ≡ 0(4)). Viendo las congruencias modulo 4: | ||
<br>n=4k -> 4k(4k-1)/4 ≡ 0(4) | <br> n=4k -> 4k(4k-1)/4 ≡ 0(4) | ||
<br>n=4k+1 -> (4k+1)(4k+1-1)/4 = (4k+1)4k/4 ≡ 0(4) | <br> n=4k+1 -> (4k+1)(4k+1-1)/4 = (4k+1)4k/4 ≡ 0(4) | ||
<br>n=4k+2 -> (4k+2)(4k+2-1)/4 = (4k+2)(4k+1)/4 ≡ 2(4) | <br> n=4k+2 -> (4k+2)(4k+2-1)/4 = (4k+2)(4k+1)/4 ≡ 2(4) | ||
<br>n=4k+3 -> (4k+3)(4k+3-1)/4 = (4k+3)(4k+2)/4 ≡ 2(4) | <br> n=4k+3 -> (4k+3)(4k+3-1)/4 = (4k+3)(4k+2)/4 ≡ 2(4) | ||
<br>-> Con lo cual solo puede pasar que n=4k o n=4k+1 | <br> -> Con lo cual solo puede pasar que n=4k o n=4k+1 | ||
==Ejercicio 05.22:== | ==Ejercicio 05.22:== | ||
<br>a) | <br>a) | ||
< | <br>b) | ||
==Ejercicio 05.23:== | |||
<br>a) | |||
< | |||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
Línea 228: | Línea 155: | ||
<br>f) | <br>f) | ||
<br>g) | <br>g) | ||
==Ejercicio 05.24:== | ==Ejercicio 05.24:== | ||
==Ejercicio 05.25:== | ==Ejercicio 05.25:== | ||
<br>a) | |||
<br>b) | |||
==Ejercicio 05.26:== | |||
Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables) | Se puede hacer A^(n-1) y tomar todos los distintos de 0 como 1 (ya que son alcanzables) | ||
==Ejercicio 05.27:== | ==Ejercicio 05.27:== | ||
==Ejercicio 05.28:== | |||
<br>a) Usando la prop. de 5.25 b) | <br>a) Usando la prop. de 5.25 b) | ||
<pre> | <pre> | ||
Línea 259: | Línea 174: | ||
<br>b) | <br>b) | ||
<pre> | <pre> | ||
for i = 1..n | for i = 1..n (i impar) | ||
for j = 1..n | for j = 1..n (i impar) | ||
invertir A[i,j]; | invertir A[i,j]; | ||
</pre> | </pre> | ||
Línea 266: | Línea 181: | ||
<br>c) a. O(n^4), b. O(n^2) | <br>c) a. O(n^4), b. O(n^2) | ||
==Ejercicio 05. | ==Ejercicio 05.29:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||
==Ejercicio 05. | ==Ejercicio 05.30:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
<br>c) | <br>c) | ||