Examen de Matemática Discreta UAB 2023 · Segon Parcial 2023-2024

Pregunta 1 (0,5 punts). Característiques d'un políedre

Considerem un políedre format per 24 vèrtexs i 36 arestes. Aquest políedre té únicament dues tipologies de cares: cares acotades per 6 arestes i cares acotades per 4 arestes.

a.

Quin és el nombre total de cares del políedre?

b.

Quantes d'aquestes cares tenen 6 arestes i quantes en tenen 4?

Pregunta 2 (0,6 punts). Polinomi cromàtic i nombre cromàtic

a.

Sigui un graf $G$ que té com a polinomi cromàtic l'expressió:

$$f(G,t) = t^9 - 6t^8 + 14t^7 - 16t^6 + at^5 - bt^4$$

1. Determineu el nombre de vèrtexs, arestes i components connexos del graf $G$.

2. Trobem el valor dels coeficients $a$ i $b$ sabent que el nombre cromàtic del graf compleix $\chi(G) > 2$.

b.

Calculeu el polinomi cromàtic i deduïu el nombre cromàtic del graf següent:

Pregunta 3 (0,5 punts). Propietats eulerianes i hamiltonianes

a.

Sigui $K_{r,s}$ un graf bipartit complet que té exactament 16 arestes.

1.

És aquest graf eulerià?

2.

Si tenim la certesa que és hamiltonià, quants vèrtexs conté en total?

b.

Emprant les condicions necessàries o suficients estudiades, analitzeu i justifiqueu si pot ser hamiltonià un graf pla que conté 21 regions fitades per 5 arestes, 3 regions fitades per 8 arestes i la cara exterior envoltada per 9 arestes.

Pregunta 4 (1 punt). TSP mètric sobre K6 (Algorisme de Christofides)

Considerem el graf complet $K_6$ amb vèrtexs $\{A, B, C, D, E, F\}$ amb pesos a les arestes que compleixen la desigualtat triangular, donats per la matriu de distàncies següent:

A

B

C

D

E

F

A

0 · 21 · 21 · 26 · 62 · 22

B

21 · 0 · 42 · 7 · 41 · 14

C

21 · 42 · 0 · 47 · 83 · 43

D

26 · 7 · 47 · 0 · 36 · 19

E

62 · 41 · 83 · 36 · 0 · 55

F

22 · 14 · 43 · 19 · 55 · 0

Apliqueu l'algorisme de Christofides per determinar un cicle hamiltonià aproximat $H$ el cost del qual verifiqui $c(H) \le \frac{3}{2} c(H_0)$, on $H_0$ és el cicle òptim.

1.

2.

3.

4.

5.

Pregunta 5 (0,4 punts). Reduccions en temps polinòmic i complexitat

Suposem que un problema de decisió $A$ es pot reduir en temps polinòmic a un problema $B$ ($A \le_p B$). Indiqueu raonadament si cadascuna de les afirmacions següents és certa o falsa:

a.

Si $A$ és el problema de decidir si un graf $G$ donat és hamiltonià, llavors $B$ podria ser el problema SAT.

Certa

Falsa

b.

Si $A$ és NP-hard, llavors $B$ és NP-complet.

Certa

Falsa

c.

Si $A$ pertany a NP, llavors és possible que $B$ es pugui resoldre en temps polinòmic.

Certa

Falsa

d.

Si $B$ es pot reduir en temps polinòmic a un altre problema $C$ ($B \le_p C$), on $C$ té complexitat temporal $O(n^{10})$, llavors $A$ pertany a la classe P.

Certa

Falsa