Pregunta 4 · Matemática Discreta UAB 2024

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.