Diferencia entre revisiones de «Práctica 4: Problemas de Grafos (Algoritmos III)»
De Cuba-Wiki
Sin resumen de edición |
Sin resumen de edición |
||
| (No se muestran 14 ediciones intermedias de 3 usuarios) | |||
| Línea 1: | Línea 1: | ||
{{Back|Algoritmos y Estructuras de Datos III}} | |||
==Ejercicio 04.01:== | ==Ejercicio 04.01:== | ||
(Sale con Matching) | |||
==Ejercicio 04.02:== | ==Ejercicio 04.02:== | ||
Es equivalente a preguntar si hay camino hamiltoniano. El grafo resultante (un cubo de 9 subcubos/vertices por cara) tendria 27 vertices y 26 ejes. Como la suma de ? es impar -> No hay. | |||
==Ejercicio 04.03:== | ==Ejercicio 04.03:== | ||
<br>a) | <br>a)Son las aristas puente | ||
<br>b) | <br>b)Recub. minimal de vertices | ||
<br>c) | <br>c)Uno es: (a,b)-(b,d)-(d,e)-(e,f)-(f,g)-(g,h)-(h,i)-(i,j) | ||
<br>d) | <br>d)Si, tomando el arbol generador se tienen n-1 ejes y todo sigue conectado | ||
==Ejercicio 04.04:== | ==Ejercicio 04.04:== | ||
(Sale con Vertex Cover) | |||
==Ejercicio 04.05:== | ==Ejercicio 04.05:== | ||
<br>a) | <br>a) | ||
| Línea 16: | Línea 25: | ||
<br>c) | <br>c) | ||
==Ejercicio 04.07:== | ==Ejercicio 04.07:== | ||
<br>a) | <br>a) 1.No 2.Si | ||
<br>b) | <br>b) Es equivalente a preguntar si hay circuito euleriano. Hay cuando para todo v, d(v) es par. | ||
<br>c) | <br>c) Un grafo es euleriano <=> tiene un particion en circuitos siempre disjuntos en ejes. | ||
==Ejercicio 04.08:== | ==Ejercicio 04.08:== | ||
(Sale con Circuito Hamiltoniano) | |||
==Ejercicio 04.09:== | ==Ejercicio 04.09:== | ||
(Sale con Coloreo de Grafos) | |||
Revisión actual - 03:58 4 may 2020
Ejercicio 04.01:
(Sale con Matching)
Ejercicio 04.02:
Es equivalente a preguntar si hay camino hamiltoniano. El grafo resultante (un cubo de 9 subcubos/vertices por cara) tendria 27 vertices y 26 ejes. Como la suma de ? es impar -> No hay.
Ejercicio 04.03:
a)Son las aristas puente
b)Recub. minimal de vertices
c)Uno es: (a,b)-(b,d)-(d,e)-(e,f)-(f,g)-(g,h)-(h,i)-(i,j)
d)Si, tomando el arbol generador se tienen n-1 ejes y todo sigue conectado
Ejercicio 04.04:
(Sale con Vertex Cover)
Ejercicio 04.05:
a)
b)
c)
Ejercicio 04.06:
a)
b)
c)
Ejercicio 04.07:
a) 1.No 2.Si
b) Es equivalente a preguntar si hay circuito euleriano. Hay cuando para todo v, d(v) es par.
c) Un grafo es euleriano <=> tiene un particion en circuitos siempre disjuntos en ejes.
Ejercicio 04.08:
(Sale con Circuito Hamiltoniano)
Ejercicio 04.09:
(Sale con Coloreo de Grafos)
