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 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.
| |
| | |
| | |
| == 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).
| |
