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 23: |
Línea 23: |
|
| |
|
| (c) Escribir un algoritmo eficiente basado en el resultado anterior que determine el radio y el diámetro de un árbol T. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto. | | (c) Escribir un algoritmo eficiente basado en el resultado anterior que determine el radio y el diámetro de un árbol T. Mostrar la correctitud y determinar la complejidad del algoritmo propuesto. |
|
| |
|
| |
| == Ejercicio 4 ==
| |
| (a) Sea <math>G = (V_G, E_G)</math> un grafo no trivial. Demostrar que <math>G</math> es bipartito sí y solo sí existe <math>I \subseteq V_G</math> tal que <math>I</math> es un conjunto independiente y también un recubrimiento de ejes por vértices (vertex cover).
| |
|
| |
| (b) Diseñar un algoritmo eficiente que dado un grafo <math>G = (V_G, E_G)</math>, encuentre un conjunto independiente mínimo de <math>G</math> que sea también un recubrimiento de ejes por vértices; si tal conjunto de vértices no existe, el algoritmo debe informarlo. Mostrar que algoritmo propuesto es correcto y determinar su complejidad. Justificar. El mejor algoritmo que conocemos tiene complejidad <math>O(m + n)</math>, donde <math>m = |E_G|</math> y <math>n = |V_G|</math>.
| |
|
| |
|
| |
| == Ejercicio 5 ==
| |
| El problema del conjunto dominante es: dado un grafo <math>G = (V_G, E_G)</math> y un entero <math>k</math>, ¿existen un subconjunto <math>W \subseteq V_G</math> con a lo sumo <math>k</math> vértices tal que cualquier vértice <math>u \in V_G \ W</math>, <math>u</math> es vecino de algún vértice <math>w \in W</math>? Este problema es NP-Completo para la clase general de grafos. Probar que este problema sigue siendo NP-Completo para grafos bipartitos. (sugenerencia: utilizar subdivisiones de aristas que es agregar vértices de grado 2).
| |