Teorie grafů

Diplomová práce, MFF UK
Lukáš Jirovský
Matematika - MIUZV


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.

Bipartitní graf
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í.

Úplné bipartitní grafy - příklady
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.

Příklad popisu zaměstnání/lidí pomocí bipartitního grafu
Obr. č. 2.6 - Příklad popisu obsazení pracovních míst pomocí bipartitního grafu


Úvod

Základní pojmy

Vybrané problémy

Procvičování