Matematyka.pl

Proszę o pomoc w zadaniu
W odpowiedziach jest \(\displaystyle{ (4!)^2.}\)

Szkoda, że nie ma przypisu definiującego trasę komiwojażera. Przypuszczam, że chodziło tam o 12-wierzchołkowe cykle.

Dwie kliki \(\displaystyle{ K_6}\) połączono dwoma gałęziami. Komiwojażer przechodząc przez jedną z nich musi obejść wierzchołki kliki i wrócić drugą gałęzią. Oznacza to, że we fragmencie cyklu obejmującym klikę pierwszy i ostatni wierzchołek są zdefiniowane, a pozostałe cztery wierzchołki są odwiedzane w dowolnej kolejności na \(\displaystyle{ 4!}\) sposobów. Ta sytuacja powtarza się przy drugiej klice, bo i tam komiwojażer może wybrać \(\displaystyle{ 4!}\) tras. A stąd i wynik \(\displaystyle{ (4!) \cdot (4!)}\).

PS
Moim zdaniem tras jest dwukrotnie więcej, gdyż każdym cyklem komiwojażer może przemieszczać się w dwóch kierunkach.

Szczerze nie jestem do tego wcale przekonany, komiwojażer za 1 razem może wybrać 5 miast, bardziej bym wolał zrobić macierz sąsiedztwa i policzyć ścieżki ...

arek1357 pisze: ↑22 lis 2023, o 21:54 komiwojażer za 1 razem może wybrać 5 miast,

Skoro za pierwszym razem może wybrać 5 miast, niezależnie od tego z którego miasta startuje, to wynikiem będzie \(\displaystyle{ 2 \cdot (4!)^2}\) tras.

To też zależy od którego miasta zacznie