Wypisujemy wszystkie pary przy których mamy ptaszki.
(1,3)(1,4)(2,5)(2,6)(2,8)(3,4)(3,5)(3,6)(4,5)(5,6)(5,7)(5,8)(6,7)(6,8) uff sporo tego
Teraz musimy wyznaczyć zbiór maksymalnych klas zgodnych . Czyli rysujemy graf i wypisujemy wszystkie kliki. Ale tutaj to będzie masakra z grafem, więc zrobimy to inaczej.
Z wypisanych par wynika, że 1 jest zgodne z 3 oraz z 4. Widzimy też że 3 jest zgodne z 4. W takim razie według panujących zasad (1,3,4) są ze sobą zgodne ;] To mamy jedną parę. Analogicznie postępujemy z resztą. Staramy się zrobić jak największe klasy. Po chłopsku to będzie tak: staramy się wrzucić w poszczególne nawiasy, jak najwięcej stanów które są ze sobą zgodne. Ostatecznie, nasz zbiór maksymalnych klas zgodnych wygląda tak: {(1,3,4) (2,5,6,8) (3,4,5,6) (5,6,7)} od razu mniej cyferek :]
Ok, mamy MKZ, musimy teraz wybrać klasy które spełnią nam warunek pokrycia. Warunek pokrycia brzmi: „Każdy stan musi wchodzić co najmniej do jednej klasy”. A więc musimy wybrać takie klasy, żeby łącznie zawierały się w nich wszystkie stany.
Warunek pokrycia spełnia nam taka grupa: (1,3,4) (2,5,6,8) (5,6,7)
Teraz musimy sprawdzić czy ta grupa spełnia warunek zamknięcia: „Dla każdej litery wejściowej, wszystkie następniki danej klasy musza wchodzić do jednej klasy”
Robimy sobie tabelkę
wtorek, 24 stycznia 2012
Subskrybuj:
Komentarze do posta (Atom)
Brak komentarzy:
Prześlij komentarz