Úplný bipartitní 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 ${\displaystyle K_{n,m}}$.

Úplný bipartitní graf ${\displaystyle K_{3,5}}$

Několik úplných bipartitních grafů typu hvězda^[1]: ${\displaystyle K_{1,3},K_{1,4},K_{1,5}}$ a ${\displaystyle K_{1,6}}$

Otázka rovinnosti úplného bipartitního grafu ${\displaystyle K_{3,3}}$ je jádrem úlohy o třech domech a třech studnách.

Vlastnosti

Počet kružnic

${\displaystyle \textstyle \sum _{k=2}^{\min(m,n)}{\binom {m}{k}}{\binom {n}{k}}{\frac {k!(k-1)!}{2}}}$

Odkazy

Reference

1. SEDLÁČEK, Jiří. Úvod do teorie grafů. Praha: Academia, 1977. Kapitola 7. Strom a kostra grafu.
2. NEŠETŘIL, Jaroslav. Teorie grafů. Praha: Státní nakladatelství technické literatury, 1979. Kapitola 2.3 Speciální neorientované grafy, s. 49.
3. SEDLÁČEK, Jiří. Úvod do teorie grafů. Praha: Academia, 1977. Kapitola 15.Chromatické číslo.

Externí odkazy

• Obrázky, zvuky či videa k tématu úplný bipartitní graf na Wikimedia Commons