Úplný bipartitní graf K3, 3 s barevně odlišenými partitami

Pojmem bipartitní graf nebo sudý graf[1] se v teorii grafů označuje takový graf, jehož množinu vrcholů je možné rozdělit na dvě disjunktní množiny tak, že žádné dva vrcholy ze stejné množiny nejsou spojeny hranou.

DefiniceEditovat

Graf   je bipartitní, pokud platí   a  . Platí-li navíc   (tedy v grafu existují všechny hrany s touto vlastností), nazývá se tento graf úplný bipartitní. Značí se  , kde m a n jsou velikosti obou partit.

VlastnostiEditovat

  • obě partity grafu jsou podle definice nezávislé množiny a graf přímo implikuje jedno možné 2-obarvení
  • platí i obrácené tvrzení - všechny 2-barevné grafy jsou bipartitní
  • jednoduchým algoritmem lze v lineárním čase zjistit, zda je daný graf bipartitní a také nalézt jeho 2-obarvení (průchodem do šířky)
  • každý strom je bipartitní
  • graf je bipartitní právě tehdy, neobsahuje-li kružnici liché délky

K-partitní grafEditovat

Pojem bipartitnosti lze zobecnit na libovolné  . Je-li G = (V, E) graf a V lze rozložit na k disjunktních podmnožin takových, že žádné dva vrcholy ze stejné podmnožiny nejsou spojeny hranou, pak tento graf nazýváme k-partitním grafem. Je-li tento graf úplný (ve stejném smyslu jako úplný bipartitní graf, viz výše) a počty vrcholu v jednotlivých partitách jsou  , pak se tento graf značí   a nazývá se úplný k-partitní graf.

Související článkyEditovat

OdkazyEditovat

ReferenceEditovat

  1. SEDLÁČEK, Jiří. Úvod do teorie grafů. Praha: Academia, 1977. Kapitola 15.Chromatické číslo. 

Externí odkazyEditovat