Problemes d'optimització en grafs: Problema del carter xinès

Pregunta 1 (Variant 1). Problema del carter xinès

Considerem el graf $G$ amb vèrtexs $\{A, B, C, D, E, F, G, H\}$ i amb pesos a les arestes donats per la matriu de costos següent, la qual indica la distància que separa cada parell de vèrtexs (el valor 0 indica que no hi ha aresta directa entre ells):

· A · B · C · D · E · F · G · H

A · 0 · 6 · 0 · 0 · 41 · 0 · 0 · 0

B · 6 · 0 · 0 · 47 · 0 · 0 · 0 · 0

C · 0 · 0 · 0 · 0 · 0 · 13 · 0 · 11

D · 0 · 47 · 0 · 0 · 12 · 0 · 45 · 0

E · 41 · 0 · 0 · 12 · 0 · 0 · 32 · 0

F · 0 · 0 · 13 · 0 · 0 · 0 · 0 · 0

G · 0 · 0 · 0 · 45 · 32 · 0 · 0 · 45

H · 0 · 0 · 11 · 0 · 0 · 0 · 45 · 0

Apliqueu l'algorisme d'Edmonds per resoldre el problema del carter xinès sobre aquest graf:

a.

Quins són els vèrtexs del graf que cal aparellar per poder construir un circuit eulerià? Escriviu-los en ordre alfabètic i sense espais ni comes.

b.

Calculeu la distància mínima entre cada parella dels vèrtexs identificats a l'apartat anterior i completeu la taula triangular corresponent.

· D · E · F · G

D · 0

E · · 0

F · · · 0

G · · · · 0

c.

Quin és el cost de cadascun dels tres aparellaments perfectes possibles entre aquests vèrtexs? Indiqueu els valors ordenats de menor a major.

d.

Quines arestes del graf original cal duplicar per aconseguir el circuit eulerià de cost mínim? Indiqueu-les en ordre alfabètic, separades per comes i sense espais (per exemple, AB,CD).

e.

Quin és el cost total de les arestes que cal duplicar?

f.

Quin és el cost total final del circuit eulerià obtingut?

Pregunta 1 (Variant 2). Problema del carter xinès

Considerem el graf $G$ amb vèrtexs $\{A, B, C, D, E, F, G, H\}$ i amb pesos a les arestes donats per la següent matriu de costos:

A

B

C

D

E

F

G

H

A · 0 · 0 · 17 · 0 · 32 · 0 · 50 · 30

B · 0 · 0 · 0 · 0 · 0 · 0 · 7 · 0

C · 17 · 0 · 0 · 0 · 0 · 37 · 0 · 0

D · 0 · 0 · 0 · 0 · 0 · 0 · 0 · 6

E · 32 · 0 · 0 · 0 · 0 · 0 · 0 · 0

F · 0 · 0 · 37 · 0 · 0 · 0 · 45 · 0

G · 50 · 7 · 0 · 0 · 0 · 45 · 0 · 0

H · 30 · 0 · 0 · 6 · 0 · 0 · 0 · 0

Resoleu el problema del carter xinès aplicant l'algorisme d'Edmonds:

a.

Identifiqueu quins vèrtexs tenen grau senar i s'han d'aparellar per construir un circuit eulerià. Escriviu-los en ordre alfabètic, sense comes ni espais.

b.

Determineu la distància mínima entre cada parella dels vèrtexs de grau senar i ompliu la matriu de distàncies corresponent.

B

D

E

G

B

0

D

0

E

0

G

0

c.

Calculeu el cost dels tres possibles aparellaments perfectes d'aquests vèrtexs i escriviu els tres valors ordenats de menor a major.

d.

Quines arestes concretes del graf s'han de duplicar per obtenir el circuit eulerià de cost mínim? Escriviu les arestes amb els vèrtexs en ordre alfabètic, separades per comes i sense espais (ex. AB,BE,CD).

e.

Quin és el cost total associat a les arestes que cal duplicar?

f.

Quin és el cost total definitiu del circuit eulerià?