Examen de Matemática Discreta UAB 2022 · Juny

Consideremos un poliedro convexo que consta de 12 vértices y 24 aristas. Se sabe que todas sus caras están delimitadas bien por $j$ aristas o bien por 4 aristas.

a.

Determina el número total de caras que posee el poliedro.

b.

Halla el valor entero de $j$.

c.

Calcula cuántas caras están delimitadas por $j$ aristas y cuántas caras tienen 4 aristas.

Dado el polinomio cromático de un grafo simple $G$:

$$f(G, t) = t^5 - 3t^4 - at^3 + t^2$$

a.

¿Cuántos vértices y cuántas componentes conexas tiene $G$? Determina el valor de la constante $a$ y calcula el número cromático $\chi(G)$ a partir de la expresión de $f(G,t)$.

b.

Si un grafo $G$ de orden $n$ posee $k$ componentes conexas, siendo cada una de ellas un árbol, ¿cuál es la expresión de su polinomio cromático $f(G,t)$ en función de $n$ y $k$?

a.

Justifica que, si un grafo bipartito completo $K_{m,n}$ es euleriano, entonces su número de aristas es necesariamente múltiplo de 4.

b.

Haciendo uso de las condiciones necesarias o suficientes vistas en el curso (como el teorema de Grinberg), justifica razonadamente si puede ser hamiltoniano un grafo plano con 7 regiones interiores delimitadas por 3 aristas, 4 regiones interiores delimitadas por 4 aristas y una región exterior cuya frontera contiene 8 aristas.

Sí

No

Ejercicio 4 (1,0 puntos). Algoritmo de Christofides para el TSP

La siguiente tabla de distancias recoge los costes de las aristas de un grafo completo ponderado $K_6$ con vértices $\{A, B, C, D, E, F\}$:

· A · B · C · D · E · F

A · 0 · 42 · 29 · 30 · 37 · 39

B · 42 · 0 · 13 · 28 · 21 · 23

C · 29 · 13 · 0 · 37 · 8 · 10

D · 30 · 28 · 37 · 0 · 42 · 27

E · 37 · 21 · 8 · 42 · 0 · 15

F · 39 · 23 · 10 · 27 · 15 · 0

Se sabe que estos pesos satisfacen la desigualdad triangular. Encuentra un ciclo hamiltoniano $H$ aplicando el algoritmo de aproximación basado en emparejamiento perfecto de peso mínimo (algoritmo de Christofides), de modo que su coste verifique $\text{coste}(H) \le \frac{3}{2}\text{coste}(H_0)$, donde $H_0$ es el ciclo hamiltoniano óptimo. Indica asimismo cuáles son las cotas o posibles valores del coste óptimo $\text{coste}(H_0)$.

Ejercicio 5 (0,4 puntos). Complejidad computacional y reducciones

Supongamos que un problema $A$ se puede reducir en tiempo polinómico a un problema $B$, denotado por $A \le_p B$. Justifica razonadamente la veracidad o falsedad de cada una de las siguientes afirmaciones:

a.

Si $A$ es el problema de decisión de determinar si un grafo $G$ es hamiltoniano, entonces $B$ es NP-completo.

b.

Si $A$ es NP-hard, entonces $B$ es NP-completo.

c.

Si $A \in \text{NP}$, entonces es posible que $B$ se pueda resolver en tiempo polinómico.

d.

Si $B$ es verificable en tiempo polinómico, entonces $A \in \text{NP}$.