Bipartitní graf

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 4. října 2020; kontroly vyžadují 12 úprav .

Bipartitní graf nebo bigraf v teorii grafů je graf, jehož množinu vrcholů lze rozdělit na dvě části tak, že každá hrana grafu spojuje vrchol jedné části s některým vrcholem druhé části, tzn. žádné hrany mezi vrcholy stejných částí grafu.

Definice

Neorientovaný graf se nazývá bipartitní, pokud lze množinu jeho vrcholů rozdělit na dvě části tak, že: $G=(W,E)$ $U\pohár V=W$

žádný vertex in není spojen s vertices in $U$ $U$
žádný vertex in není spojen s vertices in $PROTI$ $PROTI$

V tomto případě se podmnožiny vrcholů a nazývají části bipartitního grafu . $U$ $PROTI$ $G$

Související definice

Bipartitní graf se nazývá úplný bipartitní graf (tento koncept se liší od úplného grafu ; to znamená takového, ve kterém je každá dvojice vrcholů spojena hranou), pokud pro každou dvojici vrcholů existuje hrana . Pro $u\v U,v\ve V$ $(u,v)\v E$

|U|=i,|V|=j

takový graf je označen symbolem . $K_{{i,j}}$

Příklady

Bipartitní grafy přirozeně vznikají při modelování vztahů mezi dvěma různými třídami objektů. Například graf fotbalistů a klubů: hrana spojuje příslušného hráče a klub, pokud hráč v tomto klubu hrál. Abstraktnější příklady bipartitních grafů:

Strom .
Jednoduchý cyklus sestávající ze sudého počtu vrcholů.
Libovolný rovinný graf , jehož každá plocha je ohraničena sudým počtem hran.

K popisu kódů LDPC se používají bipartitní grafy .

Vlastnosti

Graf je bipartitní právě tehdy, když neobsahuje cyklus liché délky.
- Zejména bipartitní graf nemůže obsahovat kliku o velikosti větší než 2.
Graf je bipartitní právě tehdy, když je 2-chromatický; to znamená, že jeho chromatické číslo je dvě.
Graf je rozdělen do dvojic různobarevných vrcholů právě tehdy, když jsou některé prvky jednoho podílu spojeny alespoň s prvky druhého ( Wedding teorém ). $k$ $k$
Kompletní bipartitní graf s více než 2 vrcholy v každé části je nerovinný .
Jakýkoli bipartitní graf je dokonalý .

Kontrola bipartity

Pro kontrolu bipartitnosti grafu stačí vybrat libovolný vrchol v každé připojené komponentě a zbylé vrcholy označit při procházení grafu (například vyhledáváním na šířku ) střídavě jako sudé a liché (viz obrázek) . Pokud nedojde ke konfliktu, všechny sudé vrcholy tvoří množinu a všechny liché vrcholy tvoří . $U$ $PROTI$

Aplikace

Petriho sítě
hrabě Levy
Teorie kódování
- faktorový graf
- hrabě z Tanner