ALG&6

266 RozdziaHO. Elementy algorytmiki grafów

•    Promotor 4 porzuca swój aktualny wybór A na rzecz E;

•    Wybierającym staje się A i próbuje on temat (promotora) 3;

próbuje on temat (promotora) 2;

•    Temat (promotor) 2 był wolny i zostaje on przyznany studentowi A.

Ostateczne wyniki:

(Promotor 0, student C)

(Promotor 1. student B)

(Promotor 2, student A)

(Promotor 3, student D)

(Promotor 4, student E)

Omówiony algorytm doboru nie jest idealny, gdyż jak łatwo się przekonać testując go praktycznie, liniowy charakter pętli for, która czyni aktywnymi uczestnikami wyłącznie studentów (oni bowiem proponują, a promotorzy czekają biernie na nadchodzące oferty), nie wpływa na sprawiedliwość ostatecznego wyniku. Skomplikowane wersje powyższego algorytmu zmieniają uczestników aktywnych w danym etapie na uczestników biernych i odwrotnie. Powodem prezentacji obecnej wersji była jej prostota i chęć pokazania ciekawej techniki rozwiązywania pozornie złożonych zagadnień.

10.8.Podsumowanie

Na tym zakończymy naszą krótką przygodę z grafami. Jak już wspomniałem na początku, poznaliśmy wyłącznie elementy teorii grafów. Liczę jednak na to, że zaprezentowany do tej pory materiał - pomimo że znacznie „ocenzurowany” wobec bogactwa istniejących tematów - przyda się znacznej ilości Czytelników, zachęcając ich być może do sięgnięcia po zacytowaną na początku rozdziału literaturę.