Úplný bipartitní graf
Vzhled
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Biclique_K_3_5.svg/220px-Biclique_K_3_5.svg.png)
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Star_graphs.svg/220px-Star_graphs.svg.png)
Úplný bipartitní graf (také úplný dvoudílný graf[2] nebo úplný sudý graf[3][2]) je pojem z matematiky, z teorie grafů. Rozumí se jím takový bipartitní graf, do kterého již nelze přidat žádnou hranu. Jeho vrcholy lze tedy rozdělit na dvě disjunktní množiny a každý vrchol z první množiny je spojen hranou s každým vrcholem z druhé množiny. Tyto grafy jsou až na isomorfismus určeny jednoznačně počtem vrcholů obou množin a značí se .
Otázka rovinnosti úplného bipartitního grafu je jádrem úlohy o třech domech a třech studnách.
Vlastnosti[editovat | editovat zdroj]
Počet kružnic[editovat | editovat zdroj]
Odkazy[editovat | editovat zdroj]
Reference[editovat | editovat zdroj]
- ↑ SEDLÁČEK, Jiří. Úvod do teorie grafů. Praha: Academia, 1977. Kapitola 7. Strom a kostra grafu.
- ↑ a b NEŠETŘIL, Jaroslav. Teorie grafů. Praha: Státní nakladatelství technické literatury, 1979. Kapitola 2.3 Speciální neorientované grafy, s. 49.
- ↑ SEDLÁČEK, Jiří. Úvod do teorie grafů. Praha: Academia, 1977. Kapitola 15.Chromatické číslo.
Externí odkazy[editovat | editovat zdroj]
Obrázky, zvuky či videa k tématu úplný bipartitní graf na Wikimedia Commons