2. Základní pojmy / Bipartitní graf
Popis
Bipartitní graf je takový graf, jehož množinu vrcholů lze rozdělit na dvě části, přičemž z každého vrcholu jedné části jde hrana pouze do vrcholů druhé části a naopak.
Pokud jde z každého vrcholu jedné části hrana do každého vrcholu druhé části, mluvíme o úplném bipartitním grafu.
Obr. č. 2.4 - Bipartitní graf - ilustrace
Podobně jako se úplné grafy značí Kn, kde n je počet vrcholů, pro označení úplných bipartitních grafů se používá značení Km,n, kde m a n odpovídá počtu vrcholů jednotlivých částí.
Obr. č. 2.5 - Příklady úplných bipartitních grafů
Příklad v praxi
Jako příklad grafu, který musí být bipartitní, si můžeme představit graf znázorňující obsazení pracovních míst (obr. č. 2.6). V takovém grafu nikdy nespojíme dvě pracovní místa, ani dva zaměstnance.
Obr. č. 2.6 - Příklad popisu obsazení pracovních míst pomocí bipartitního grafu