Wikipedia

Metoda kompozycji łacińskiej: Różnice pomiędzy wersjami

Przeglądaj historię interaktywnie
[wersja przejrzana][wersja przejrzana]
← poprzednia edycja
Usunięta treść Dodana treść
WizualnieWikikod
m drobne techniczne
 
Linia 3:
'''Krok 1'''
 
Wierzchołki [[graf (matematyka)|grafu]] oznaczamy kolejnymi [[litera]]mi [[alfabet]]u. Budujemy [[macierz]] <math>M^{(1)}</math> [[Rząd macierzy|rzędu]] równego [[Rząd grafu|rzędowi grafu]]. [[Wiersz macierzyMacierz|wiersze]] i [[Kolumna macierzyMacierz|kolumny macierzy]] również oznaczamy kolejnymi literami.
 
Jeżeli istnieje w grafie krawędź z wierzchołka ''<math>i''</math> do wierzchołka ''<math>j''</math> i ''<math>i''</math> jest różne od ''<math>j'',</math> to w kratkę macierzy <math>M^{(1)}[i,j]</math> wpisujemy ''<math>ij''.</math> Wszystkim pozostałym elementom macierzy przypisujemy wartość 0.
 
'''Krok 2'''
 
Tworzymy macierz <math>M'^{(1)}.</math>. Aby utworzyć macierz <math>M'^{(k)},</math>, należy z każdego elementu macierzy <math>M^{(k)}</math> wykreślić pierwszą literę.
 
'''Krok 3'''
 
Szukamy macierzy <math>M^{(n - 1)},</math>, gdzie ''<math>n''</math> jest rzędem grafu. W tym celu stosujemy mastępujące działanie:
<math>M^{(p+q)} = M^{(p)}\ L\ M'^{(q)}</math>
Jest ono zbliżone do [[Mnożenie macierzy|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.
Linia 21:
'''Krok 4'''
 
Aby znaleźć cykle Hamiltona, należy jeszcze obliczyć macierz <math>M^{*(n)} = M'^{(n-1)}\ L\ M'^{(1)},</math>, 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.
 
[[Kategoria:Algorytmy grafowe]]
Źródło: „https://pl.wikipedia.org/wiki/Metoda_kompozycji_łacińskiej”