Examen de Matemática Discreta UAB 2024 · Segon Parcial de Matemàtica Discreta (Curs 2024-2025)

Pregunta 1 (2 punts). Octàedre truncat i fórmula d'Euler

Un octàedre truncat és un políedre arquimedià que consta de 8 cares hexagonals i 6 cares quadrades.

a.

Determineu el nombre d'arestes ($|A|$) del políedre.

b.

Calculeu el nombre de vèrtexs ($|V|$) fent servir la fórmula d'Euler per a grafs planars i políedres convexos.

Pregunta 2 (2 punts). Polinomi cromàtic i coloració

Determineu el polinomi cromàtic $P(G, t)$ per a cadascun dels grafs següents:

a.

El graf de 4 vèrtexs representat a continuació:

b.

El graf de 5 vèrtexs representat a continuació:

c.

El graf que s'obté en afegir un nou vèrtex connectat mitjançant una sola aresta a un dels vèrtexs del graf complet $K_n$. Expresseu la relació en funció de $P(K_n, t)$ o directament en funció de $n$ i $t$:

d.

Tenint en compte el graf de l'apartat a):

Considereu el graf no dirigit de 13 vèrtexs que es mostra a la figura següent, on el vèrtex central 13 està connectat als vèrtexs parells de la circumferència:

a.

És hamiltonià aquest graf? Justifiqueu la resposta.

Sí

No

b.

És eulerià? Justifiqueu la resposta.

Sí

No

c.

Conté algun camí eulerià? Justifiqueu la resposta.

Sí

No

Considereu el graf no dirigit de 13 vèrtexs que es mostra a la figura següent, on el vèrtex central 13 està connectat als vèrtexs parells de la circumferència:

d.

Assumint que totes les arestes tenen cost unitari (pes = 1), determineu el cost mínim d'un recorregut tancat que passi com a mínim una vegada per cada aresta (problema del carter xinès), indicant quines arestes cal duplicar i un possible circuit resultant.

Pregunta 4 (3 punts). Problema del viatjant de comerç (TSP) i algorisme de Christofides

La taula següent conté la matriu de pesos/distàncies de les arestes d'un graf complet $K_7$ amb vèrtexs $\{A, B, C, D, E, F, G\}$:

A

B

C

D

E

F

G

A · 0 · 33 · 40 · 36 · 45 · 46 · 6

B · 33 · 0 · 20 · 30 · 25 · 35 · 27

C · 40 · 20 · 0 · 50 · 5 · 34 · 34

D · 36 · 30 · 50 · 0 · 55 · 65 · 42

E · 45 · 25 · 5 · 55 · 0 · 29 · 39

F · 46 · 35 · 34 · 65 · 29 · 0 · 52

G · 6 · 27 · 34 · 42 · 39 · 52 · 0

Suposant que les distàncies satisfan la desigualtat triangular, apliqueu l'algorisme de Christofides per trobar un circuit hamiltonià $H$ el cost del qual verifiqui:

$$\mathrm{cost}(H) < \frac{3}{2}\mathrm{cost}(H_0)$$

on $H_0$ denota el circuit hamiltonià de cost òptim.

1.

2.

3.

4.

5.