Przy okazji omawiania wzorca Odwiedzający skorzystałem z przykładu przechodzenia skoczkiem przez wszystkie pola szachownicy tak, aby każde pole odwiedzić tylko raz, zaczynając z różnych miejsc na szachownicy. Mechanizm szuka kolejnych pól, przechodzi dalej lub cofa się, jeżeli nie jest możliwe dalsze przejście. Rozwiązanie takiego problemu istnieje i pewnie nie jeden pasjonat szachów próbował to zrobić na kartce lub szachownicy. Szachownica zaprezentowana jest na poniższych diagramach. Zaznaczone są także przykładowe przejścia.
Wyobraźmy sobie, że każde pole szachownicy umieszczamy na grafie w węźle, a te węzły, które można ze sobą połączyć, łączymy krawędzią, stosując “wirtualną” odległość opartą o 2 kratki w pionie lub poziomie i 1 odpowiednio w poziomie lub pionie. W taki sposób można rozwiązać także inne sytuacje, np. łączenie wykładowców i przedmioty lub inne sytuacje biznesowe. Fragment takiego grafu jest zaprezentowany na poniższym diagramie.
W tym przykładzie w zależności od położenia pola na szachownicy, dany węzeł grafu ma 2 (kolor czerwony), 3 (kolor zielony), 4 (kolor szary), 6 (kolor niebieski) lub 8 (kolor żółty) wyjść. Na powyższym diagramie takie miejsca grafu zosały odpowiednio oznaczone kolorami. W zależności od węzła, od którego rozpoczynamy wędrówkę, mamy więcej lub mniej możliwości zmiany kierunku. Na animacji droga przechodzi przez różne punkty – rozpoczyna się w punkcie z 2 wyjściami (A1), potem przechodzi przez punkty z 6, 8, 4 wyjściami a kończy w punkcie z 4 wyjściami (F8). Nie przechodzi przez punkt z 3 wyjściami.
Powyższe zadanie to tzw. poszukiwanie ścieżki Hamiltona na nieskierowanym grafie, czyli takim, w którym po każdej krawędzi można przejść w 2 strony. Z racji, że każdemu z węzłów można przypisać jeden z dwóch kolorów i nie ma połączenia/krawędzi między dwoma węzłami tego samego koloru, jest to równocześnie graf dwudzielny. W publikacjach można znaleźć różne algorytmy wyszukiwania takiej ścieżki. Więcej można przeczytać o powyższym problemie choćby we wpisie na anglojęzycznej wersji Wikipedii. Niestety w polskiej wersji informacje te są bardzo ograniczone.
Modelowanie procesów biznesowych 