Bipartitní graf

Úplný bipartitní graf K3, 3 s barevně odlišenými partitami Pojmem bipartitní graf nebo sudý graf 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.

Definice

Graf G = (V, E) je bipartitní, pokud platí V = V_1 \cup V_2, V_1 \cap V_2 = \empty\; a \forall e = \left \{u, v \right \}\;, e \in E: u \in V_1 \wedge v \in V_2. Platí-li navíc E = V_1 \times V_2 (tedy v grafu existují všechny hrany s touto vlastností), nazývá se tento graf úplný bipartitní. +more Značí se 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é k\ge 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. +more 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 n_1, n_2, \ldots, n_k, pak se tento graf značí K_{n_1, n_2, \ldots, n_k} a nazývá se úplný k-partitní graf.

Související články

Párování grafu

Odkazy

Reference

Externí odkazy

Kategorie:Typy grafů