Úplný bipartitní graf

Úplný bipartitní graf K_{3,5} hvězda: K_{1,3}, K_{1,4}, K_{1,5} a K_{1,6} Úplný bipartitní graf (také úplný dvoudílný graf nebo úplný sudý graf) 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 K_{n,m}.

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

Vlastnosti

Počet kružnic

\textstyle \sum_{k=2}^{\min(m,n)} \binom{m}{k}\binom{n}{k} \frac{k!(k - 1)!}{2}

Odkazy

Reference

Externí odkazy

Kategorie:Bipartitní grafy Kategorie:Teorie grafů