Problem istnienia systemu reprezentantów rodziny zbiorów (porównanie rozwiązań matematycznych i algorytmicznych).

Abstract

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.