Edición de «Práctica 5: Clases de Grafos (Algoritmos III)»

De Cuba-Wiki
Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si inicias sesión o creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.

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.22:==
==Ejercicio 05.23:==
<br>a)
<br>a)
<pre>
<pre>
Línea 229: Línea 233:
<br>g)
<br>g)


==Ejercicio 05.23:==
==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.24:==
==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.25:==
==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.26:==
==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.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 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.28:==
==Ejercicio 05.29:==
<br>a)
<br>a)
<br>b)
<br>b)
<br>c)
<br>c)
==Ejercicio 05.29:==
==Ejercicio 05.30:==
<br>a)
<br>a)
<br>b)
<br>b)
Ten en cuenta que todas las contribuciones a Cuba-Wiki pueden ser editadas, modificadas o eliminadas por otros colaboradores. Si no deseas que las modifiquen sin limitaciones, no las publiques aquí.
Al mismo tiempo, asumimos que eres el autor de lo que escribiste, o lo copiaste de una fuente en el dominio público o con licencia libre (véase Cuba-Wiki:Derechos de autor para más detalles). ¡No uses textos con copyright sin permiso!

Para editar esta página, responde la pregunta que aparece abajo (más información):

Cancelar Ayuda de edición (se abre en una ventana nueva)

Plantilla usada en esta página: