Úplný bipartitní graf

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

Ú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 K n , m {\displaystyle K_{n,m}} .

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

Vlastnosti

Počet kružnic

∑ k = 2 min ( m , n ) ( m k ) ( n k ) k ! ( k − 1 ) ! 2 {\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. ↑ a b 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

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