Metoda kompozycji łacińskiej

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

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.