Streszczenie:
Definiujemy problem istnienia systemu reprezentantów rodziny zbiorów (również w terminologii
grafów dwudzielnych). Prezentujemy twierdzenie Hall’a wraz z dowodem, które podaje
warunki konieczne i wystarczające na to, by istniał system różnych reprezentantów dla
danej rodziny zbiorów. Problem istnienia transwersali, utożsamiony ze skojarzeniem całkowitym
w grafie dwudzielnym, sprowadzamy do problemu znajdowania maksymalnego przepływu
w sieci przepływowej. Przedstawiamy dwa algorytmy znajdowania maksymalnego przepływu
w sieci, jeden opierający się na ścieżkach rozszerzających, drugi zaś, opierający się na nadmiarowym
przepływie. Testujemy oba algorytmy na grafach o różnej charakterystyce. Przedstawiamy
analizę kilku problemów stanowiących przykłady zastosowań twierdzenia Hall’a, ze
zmodyfikowanymi założeniami.
