Komivojažiera uzdevuma atrisināšana ar Hamiltona cikla palīdzību

Individuālais uzdevums.

Atrast dotām grafām Hamiltona kontūru ar minimālo garumu, izmantojot programmas cikla noteikšanai, patstāvīgi sastādīto ieejas matricu un pilno grafu ar 8 virsotnēm un 56 lokiem. Uzdevuma sākuma dati iekļauj noteiktas valsts (Somijas) pilsētas un attālumus starp tām. Izvēloties kādu no pilsētam par sākuma punktu, jāatrod uzkonstruetājā grafā Hamiltona ciklu. Ar šo kontūra palīdzību jāatrisinā komivojažiera uzdevums.

2. Grafa zīmējums.

Konstruēsim grafu, pamatojoties uz datiem par Somijas pilsētam un jau izmērītiem attālumiem starp tām. Mūsu grafā pilsētas atbilst virsotnēm, bet ceļi starp tām atbilst lokiem ar noteikto nenegatīvo garumu. Izvēlamies vienu sākuma virsotni (pilsēta Helsinki), no kuras būs sasniedzamas visas parējas virsotnes.
Jāievēro, ka grafam jābūt pilnam, t.i. tājā katrām virsotņu parīm jābūt savienotam ar šķautni (jeb ar 2 lokiem: vienā un pretējā virzienos). Loku skaits tiek aprēķināts pēc formulas:
n2 – n = n(n-1),
kur n – grafa virsotņu skaits.…