Bipartitní graf

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.

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

Definice

Graf ${\displaystyle G=(V,E)}$ je bipartitní, pokud platí ${\displaystyle V=V_{1}\cup V_{2},V_{1}\cap V_{2}=\emptyset \;}$ a ${\displaystyle \forall e=\left\{u,v\right\}\;,e\in E:u\in V_{1}\wedge v\in V_{2}}$. Platí-li navíc ${\displaystyle E=V_{1}\times V_{2}}$ (tedy v grafu existují všechny hrany s touto vlastností), nazývá se tento graf úplný bipartitní. Značí se ${\displaystyle K_{m,n}}$, kde m a n jsou velikosti obou partit.

Vlastnosti

• 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 dvoubarevné 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 hloubky)
• každý strom je bipartitní
• graf je bipartitní právě tehdy, neobsahuje-li kružnici liché délky

K-partitní graf

Pojem bipartitnosti lze zobecnit na libovolné ${\displaystyle k\geq 2}$. 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 ${\displaystyle n_{1},n_{2},\ldots ,n_{k}}$, pak se tento graf značí ${\displaystyle K_{n_{1},n_{2},\ldots ,n_{k}}}$ a nazývá se úplný k-partitní graf.

Související články

• Párování grafu