Diferencia entre revisiones de «Final del 20/12/19 (Algoritmos III)»
Sin resumen de edición |
|||
Línea 10: | Línea 10: | ||
El grafo <math>Q_d</math>, también llamado hipercubo de orden <math>d</math>, se define inductivamente de la siguiente manera: <math>Q_0 = K_1</math>, y <math>Q_d</math> con <math>d \in N_>0</math> es el grafo que se obtiene al tomar dos copias de <math>Q_d-1</math> y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo <math>Q_1 = K_2</math>, <math>Q_2 = C_4</math> (ciclo simple de 4 vértices). | El grafo <math>Q_d</math>, también llamado hipercubo de orden <math>d</math>, se define inductivamente de la siguiente manera: <math>Q_0 = K_1</math>, y <math>Q_d</math> con <math>d \in N_>0</math> es el grafo que se obtiene al tomar dos copias de <math>Q_d-1</math> y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo <math>Q_1 = K_2</math>, <math>Q_2 = C_4</math> (ciclo simple de 4 vértices). | ||
a) Determinar los valores de <math>d</math> para los cuales <math>Q_d</math> es planar. Justificar. | (a) Determinar los valores de <math>d</math> para los cuales <math>Q_d</math> es planar. Justificar. | ||
b) Determinar <math>\chi(Q_d)</math>. Justificar. | (b) Determinar <math>\chi(Q_d)</math>. Justificar. | ||
== Ejercicio 3 == | |||
Dado un grafo <math>G = (V_G, E_G)</math>, se define la excentricidad de un vértice <math>v \in V_G</math> como <math>e_G (v) = max{dist_G (v,w) / \forall w \in V_G}</math> y <math>dist_G (v,w)</math> como la cantidad de aristas del camino más corto entre <math>v</math> y <math>w</math>. Y también se definen el radio y el diámetro de <math>G</math> como <math>r(G) = min{e_G (v) / \forall v \in V_G}</math> y <math>d_G = max{e_G (v) / \forall v \in V_G}</math>. Un vértice <math>v \in E_G</math> es centro de <math>G</math> si <math>e_G (v) = r(G)</math>. | |||
(a) Mostrar infinitos grafos conexos (distintos de completos y ciclos) donde todos los vértices son centros. | |||
(b) Probar que todo árbol tiene uno o dos centros. | |||
(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. |
Revisión del 18:18 24 ene 2020
Final escrito de Min Chih Lin.
Enunciados
Ejercicio 1
Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia creciente máxima de una secuencia de números (el mejor algoritmo conocido es de tiempo y usa espacio ). Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.
Ejercicio 2
El grafo , también llamado hipercubo de orden , se define inductivamente de la siguiente manera: , y con es el grafo que se obtiene al tomar dos copias de y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo , (ciclo simple de 4 vértices).
(a) Determinar los valores de para los cuales es planar. Justificar.
(b) Determinar . Justificar.
Ejercicio 3
Dado un grafo , se define la excentricidad de un vértice como y como la cantidad de aristas del camino más corto entre y . Y también se definen el radio y el diámetro de como y . Un vértice es centro de si .
(a) Mostrar infinitos grafos conexos (distintos de completos y ciclos) donde todos los vértices son centros.
(b) Probar que todo árbol tiene uno o dos centros.
(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.