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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/4e/Graph_K3-3.svg/140px-Graph_K3-3.svg.png)
Definice
editovatGraf 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.
Vlastnosti
editovat- 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
editovatPojem 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ánky
editovatOdkazy
editovatReference
editovat- ↑ SEDLÁČEK, Jiří. Úvod do teorie grafů. Praha: Academia, 1977. Kapitola 15.Chromatické číslo.
Externí odkazy
editovat- Obrázky, zvuky či videa k tématu bipartitní graf na Wikimedia Commons