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: | ||
<div style="border: 1px solid #CECEFF; padding: 5px; background-color: #EEEEFF; margin: 0px 0px 15px 0px;">[[Image:Back.png|14px|]] [[Algoritmos y Estructuras de Datos III|Volver a la página de la materia]]</div> | |||
==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 25: | ||
<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 34: | ||
==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 57: | ||
** 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 84: | ||
<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 98: | ||
==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 112: | ||
</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 139: | Línea 120: | ||
<br>Sea vi de grado impar -> dG(vi) = 2k+1. Si dG(vi) = 2k+1 -> dGc(vi) = (n-1)-(2k+1)=n-2-2k | <br>Sea vi de grado impar -> dG(vi) = 2k+1. Si dG(vi) = 2k+1 -> dGc(vi) = (n-1)-(2k+1)=n-2-2k | ||
<br>->Si n es impar habra n-1 vertices de grado impar, sino habra 1 | <br>->Si n es impar habra n-1 vertices de grado impar, sino habra 1 | ||
Otra forma seria asi: | |||
(7,6,5,4,3,3,2), si la miramos fijo vemos que n=6 , pero hay un nodo que tiene 7 ejes...por lo cual eso no es posible en un grafo simple. | |||
Si no se ve lo que dije, piensenlo desde un grafo completo, solamenente hay un nodo con n-1 ejes. | |||
(6,6,5,4,3,3,1), en un grafo simple no pueden existir dos nodos con n-1 ejes. | |||
(Sale pensando en un grafo completo) | |||
==Ejercicio 05.15:== | ==Ejercicio 05.15:== | ||
Línea 172: | Línea 159: | ||
==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 191: | Línea 175: | ||
==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 187: | ||
<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 196: | ||
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 217: | ||
<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 228: | ||
<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 259: | Línea 245: | ||
<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 252: | ||
<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) |