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:==
==Ejercicio 04.10:==
(Sale con Coloreo de Grafos)

Revisión actual - 03:58 4 may 2020

Plantilla:Back

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)