Úplný bipartitní graf

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Úplný bipartitní graf
Několik úplných bipartitních grafů typu hvězda[1]: a

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

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

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

  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[editovat | editovat zdroj]