Úplný bipartitní graf

Ú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}$.

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

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

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

Externí odkazy

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