Úplný bipartitní graf
graf
Ú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 .
![](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)
Otázka rovinnosti úplného bipartitního grafu je jádrem úlohy o třech domech a třech studnách.
Vlastnosti
editovatPočet kružnic
editovat
Odkazy
editovatReference
editovat- ↑ 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- Obrázky, zvuky či videa k tématu úplný bipartitní graf na Wikimedia Commons