Metoda kompozycji łacińskiej

Metoda kompozycji łacińskiej – metoda pozwalająca w łatwy sposób znaleźć wszystkie ścieżki i cykle Hamiltona w grafie.

Krok 1

Wierzchołki grafu oznaczamy kolejnymi literami alfabetu. Budujemy macierz $M^{(1)}$ rzędu równego rzędowi grafu. wiersze i kolumny macierzy również oznaczamy kolejnymi literami.

Jeżeli istnieje w grafie krawędź z wierzchołka $i$ do wierzchołka $j$ i $i$ jest różne od $j,$ to w kratkę macierzy $M^{(1)}[i,j]$ wpisujemy $ij.$ Wszystkim pozostałym elementom macierzy przypisujemy wartość 0.

Krok 2

Tworzymy macierz $M{\text{'}}^{(1)}.$ Aby utworzyć macierz $M{\text{'}}^{(k)},$ należy z każdego elementu macierzy $M^{(k)}$ wykreślić pierwszą literę.

Krok 3

Szukamy macierzy $M^{(n-1)},$ gdzie $n$ jest rzędem grafu. W tym celu stosujemy mastępujące działanie: $M^{(p+q)}=M^{(p)}LM{\text{'}}^{(q)}$ Jest ono zbliżone do mnożenia macierzy, ale zamiast mnożyć ciągi znaków, łączymy je. Jeżeli w nowo powstałym ciągu znaków jakiś znak się powtórzy, zastępujemy go zerem. Przemnożenie ciągu znaków przez 0 również daje 0. Zamiast sumować ciągi znaków wpisujemy je jeden nad drugim w tej samej kolumnie.

Ciągi znaków w otrzymanej w tym kroku macierzy przedstawiają wszystkie możliwe ścieżki Hamiltona.

Krok 4

Aby znaleźć cykle Hamiltona, należy jeszcze obliczyć macierz $M^{*(n)}=M{\text{'}}^{(n-1)}LM{\text{'}}^{(1)},$ a następnie dopisać na początku każdego ciągu znaków literę odpowiadającą wierszowi macierzy, w którym się znajduje. Otrzymana macierz zawiera wszystkie cykle Hamiltona w grafie.