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 68: | Línea 55: | ||
** 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:== | ||
<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:== | ||
Línea 95: | Línea 73: | ||
<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 79: | ||
<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:== | ||
Línea 112: | Línea 87: | ||
==Ejercicio 05.12:== | ==Ejercicio 05.12:== | ||
<br>=>) Si d1,..,dn es una secuencia valida de grados de un grafo -> Σ di = 2*m = par | <br>=>) Si d1,..,dn es una secuencia valida de grados de un grafo -> Σ di = 2*m = par | ||
<br><=) | <br><=) Mm.. esto creo que sale usando el algoritmo que esta en 5.13 | ||
==Ejercicio 05.13:== | ==Ejercicio 05.13:== | ||
Línea 126: | Línea 101: | ||
</i> | </i> | ||
<br> Usando esto se deberia llegar a que las del ej. no lo son. | <br> Usando esto se deberia llegar a que las del ej. no lo son. | ||
<br>b) | <br>b) | ||
Línea 142: | Línea 112: | ||
==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 129: | ||
<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 142: | ||
==Ejercicio 05.17:== | ==Ejercicio 05.17:== | ||
==Ejercicio 05.18:== | ==Ejercicio 05.18:== | ||
<br> 1. | <br> 1. () 2. Si 3. () 4. Si | ||
==Ejercicio 05.19:== | ==Ejercicio 05.19:== | ||
Línea 187: | Línea 154: | ||
==Ejercicio 05.20:== | ==Ejercicio 05.20:== | ||
<br>a) | <br>a) | ||
<br>b) | <br>b) | ||
==Ejercicio 05.21:== | |||
<br>a) | |||
<br>b) | |||
==Ejercicio 05. | ==Ejercicio 05.22:== | ||
<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: | ||
Línea 199: | Línea 169: | ||
<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. | ==Ejercicio 05.23:== | ||
<br>a) | <br>a) | ||
<pre> | <pre> | ||
Línea 208: | Línea 178: | ||
B 101010 B 100000 | B 101010 B 100000 | ||
C 110111 C 010001 | C 110111 C 010001 | ||
D 101011 D | D 101011 D 001011 | ||
E 011101 E 011100 | E 011101 E 011100 | ||
F 001110 F 000010 | F 001110 F 000010 | ||
Línea 229: | Línea 199: | ||
<br>g) | <br>g) | ||
==Ejercicio 05. | ==Ejercicio 05.24:== | ||
Asegurando la simetria, es decir, que para todo i,j, Aij = Aji | |||
==Ejercicio 05. | ==Ejercicio 05.25:== | ||
<br>a) Si se toman como filas/columnas de la matriz de adyacencia de un grafo bipartito a v1,..,vm,w1,..,wn, donde v1,..,vm son los vertices de una particion y w1,..wn los de la otra, entonces la matriz se puede dividir de la siguiente forma: | <br>a) Si se toman como filas/columnas de la matriz de adyacencia de un grafo bipartito a v1,..,vm,w1,..,wn, donde v1,..,vm son los vertices de una particion y w1,..wn los de la otra, entonces la matriz se puede dividir de la siguiente forma: | ||
<pre> | <pre> | ||
Línea 242: | Línea 210: | ||
<br>b) Como n es impar -> aii^n = cant. de recorridos de long. n desde el vertice vi a si mismo = cant. de circuitos de long. impar que contienen el vertice vi. Con lo cual, si aii^n = 0 para todo i y todo n impar, se esta asegurando que el grafo sea bipartito | <br>b) Como n es impar -> aii^n = cant. de recorridos de long. n desde el vertice vi a si mismo = cant. de circuitos de long. impar que contienen el vertice vi. Con lo cual, si aii^n = 0 para todo i y todo n impar, se esta asegurando que el grafo sea bipartito | ||
==Ejercicio 05. | ==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 225: | ||
<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 232: | ||
<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) | ||