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 191: | Línea 191: | ||
==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 203: | ||
<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 233: | ||
<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 246: | ||
<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 270: | ||
<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) |