ScanImage006 (14)

WPROWADZENIE

Rysunek 1.2 Przykład analizy bardzo dużej liczby połączeń

Obiekty z problemu połączeniowego mogą reprezentować punkty lutownicze, a pary ścieżki drukowane, jak pokazano na wyidealizowanym schemacie połączeń elementów elektronicznych na płytce. Taki rysunek pozwala zauważyć węzły, które nie są ze sobą połączone, ale pamiętajmy, że algorytm operuje nie na rysunku, ale na parach liczb naturalnych. Na rysunku wyróżniono dwa węzły. Czy są one połączone?

Specyfikacje wymienione w poprzednim akapicie zawierają żądanie większej ilości informacji niż ich pierwotne wersje, ale można również zażądać mniej informacji. Możemy po prostu zadać następujące pytanie: „Czy m połączeń wystarczy do połączenia wszystkich n obiektów?”. Ten problem dowodzi, że w celu opracowania efektywnego algorytmu, potrzebujemy często rozumowania na wysokim poziomic dotyczącego abstrakcyjnych obiektów, które przetwarzamy. W tym przypadku można się posłużyć podstawowym twierdzeniem z teorii grafów, z którego wynika, że wszystkie n obiektów będzie połączonych wtedy i tylko wtedy, gdy liczba par wyznaczona przez algorytm połączeniowy wyniesie dokładnie n - l (patrz podrozdział 5.4). Inaczej mówiąc, algorytm połączeniowy nie da w wyniku nigdy więcej par niż n - l, ponieważ każda para napotkana po wyznaczeniu pierwszych n - 1 par będzie już połączona. Podobnie przez drobną przeróbkę tego algorytmu możemy napisać program dający w wyniku swojego działania tylko odpowiedź typu „tak” lub „nie”. Program rozwiązujący problem połączeniowy zamiast wypisywać każdą parę obiektów, które nic były wcześniej połączone, powinien tylko zwiększać licznik. Pozytywną odpowiedź da nam wtedy, gdy licznik osiągnie war-