Bipartitní graf

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

Definice

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.

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

Odkazy

Reference

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

Externí odkazy

Média použitá na této stránce

Graph K3-3.svg
Autor: (of code) w:cs:User:-xfi-, Licence: CC BY-SA 3.0
Bipartitní graf K3, 3 s barevně odlišenými partitami.