Pregunta 4 · Matemática Discreta UAB 2023

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.