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 3: | Línea 3: | ||
==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 26: | ||
<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 35: | ||
==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 58: | ||
** 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:== | ||
Línea 95: | Línea 85: | ||
<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 112: | Línea 99: | ||
==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 191: | Línea 178: | ||
==Ejercicio 05.21:== | ==Ejercicio 05.21:== | ||
<br>a) | |||
<br>b) | |||
==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 190: | ||
<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 229: | Línea 220: | ||
<br>g) | <br>g) | ||
==Ejercicio 05. | ==Ejercicio 05.24:== | ||
Si D es el grafo dirigido y G el subyacente, y MD y MG sus respectivas matrices de adyacencia, entonces: | Si D es el grafo dirigido y G el subyacente, y MD y MG sus respectivas matrices de adyacencia, entonces: | ||
Para todo i,j | Para todo i,j | ||
MG(i,j) = max(MD(i,j), MD(j,i)) | MG(i,j) = max(MD(i,j), MD(j,i)) | ||
==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 233: | ||
<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. | ==Ejercicio 05.27:== | ||
Si dos grafos son isomorfos, entonces debe existir una forma de intercambiar las filas y luego las columnas de la matriz de adyacencia de uno para que sea igual a la del otro. Como el problema de isomorfismo es NP, no se conoce un buen algoritmo para decidirlo. | Si dos grafos son isomorfos, entonces debe existir una forma de intercambiar las filas y luego las columnas de la matriz de adyacencia de uno para que sea igual a la del otro. Como el problema de isomorfismo es NP, no se conoce un buen algoritmo para decidirlo. | ||
==Ejercicio 05. | ==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 266: | Línea 257: | ||
<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) |