Úplný bipartitní graf

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

Ú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

${\sum }_{k=2}^{\min (m,n)}(\genfrac{}{}{0ex}{}{m}{k})(\genfrac{}{}{0ex}{}{n}{k})\frac{k!(k-1)!}{2}$

Odkazy

Externí odkazy

• Šablona:Commonscat