Metoda kompozycji łacińskiej

Z Wikipedii

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⁽¹⁾ 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⁽¹⁾[i,j] wpisujemy ij. Wszystkim pozostałym elementom macierzy przypisujemy wartość 0.

Krok 2

Tworzymy macierz M'⁽¹⁾. Aby utworzyć macierz M'^(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: Jest ono zbliżone do mnożenia macierzy, ale zamiast mnożyć ciągi znaków, łączymy je. Jeżeli w nowopowstał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.