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 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 do wierzchołka i jest różne od to w kratkę macierzy wpisujemy Wszystkim pozostałym elementom macierzy przypisujemy wartość 0.
Krok 2
Tworzymy macierz Aby utworzyć macierz należy z każdego elementu macierzy wykreślić pierwszą literę.
Krok 3
Szukamy macierzy gdzie jest rzędem grafu. W tym celu stosujemy mastępujące działanie: 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 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.