Kompletní bipartitní graf

Kompletní bipartitní graf ( biklik ) je speciální typ bipartitního grafu , ve kterém je libovolný vrchol první části spojen se všemi vrcholy druhé části vrcholů.

Definice

Kompletní bipartitní graf je bipartitní graf takový, že pro jakékoli dva vrcholy a , je hrana v . Kompletní bipartitní graf s částmi velikosti a je označen jako . $G:=(V_{1}+V_{2},E)$ $v_{1}\in V_{1}$ $v_{2}\in V_{2}$ $(v_{1},v_{2})$ $G$ $|V_{1}|=m$ $|V_{2}|=n$ $K_{{m,n}}$

Příklady

Grafy se nazývají hvězdy , všechny úplné bipartitní grafy, které jsou stromy , jsou hvězdy. $K_{{1,k}}$
Graf se nazývá dráp a používá se k definování grafů bez drápů . $K_{{1,3}}$
Graf se někdy nazývá „komunální graf“, název se vrací ke klasickému problému „ domy a studny “, v moderní interpretaci používající „komunální“ formulaci (napojit tři domy na vodu, elektřinu a plyn bez křížení čar na letadlo); problém je neřešitelný kvůli nerovinnosti grafu . $K_{{3,3}}$ $K_{{3,3}}$

Vlastnosti

Problém najít pro daný bipartitní graf úplný bipartitní podgraf s daným parametrem je NP-kompletní . $K_{{n,n}}$ $n$
Rovinný graf nemůže obsahovat graf jako vedlejší . Vnější rovinný graf nemůže obsahovat jako vedlejší (Toto není dostatečná podmínka rovinnosti a vnější rovinnosti, ale je nutná). Naopak jakýkoli nerovinný graf obsahuje buď , nebo celý graf jako vedlejší ( Pontryagin-Kuratovského teorém ). $K_{{3,3}}$ $K_{{3,2}}$ $K_{{3,3}}$ $K_{5}$
Kompletní bipartitní grafy jsou Mooreovy grafy a -buňky . $K_{{n,n}}$ $(n,4)$
Kompletní bipartitní grafy jsou Turanovy grafy . $K_{{n,n}}$ $K_{{n,n+1}}$
Kompletní bipartitní graf má velikost pokrytí vrcholů a velikost pokrytí okrajů . $K_{{m,n}}$ $\min(m,n)$ $\max(m,n)$
Kompletní bipartitní graf má maximální nezávislou sadu velikostí . $K_{{m,n}}$ $\max(m,n)$
Matice sousedství úplného bipartitního grafu má vlastní hodnoty a s násobky a . $K_{{m,n}}$ ${\sqrt{nm))$ $-{\sqrt{nm))$ $0$ $jeden$ $jeden$ $n+m-2$
Laplaceova matice úplného bipartitního grafu má vlastní hodnoty , , , s násobnostmi , , resp . $K_{{m,n}}$ $n+m$ $n$ $m$ $0$ $jeden$ $m-1$ $n-1$ $jeden$
Kompletní bipartitní graf má kostry . $K_{{m,n}}$ $m^{{n-1}}\cdot n^{{m-1}}$
Kompletní bipartitní graf má maximální shodu velikosti . $K_{{m,n}}$ $\min(m,n)$
Kompletní bipartitní graf má vhodné zabarvení okraje odpovídající latinskému čtverci . $K_{{n,n}}$ $n$

Poslední dva výsledky jsou důsledkem Hallova teorému aplikovaného na -regulární bipartitní graf. $k$

Viz také

Literatura

John Adrian Bondy, USR Murty. Teorie grafů s aplikacemi. - North-Holland, 1976. - S. 5 . — ISBN 0-444-19451-7 . Archivováno z originálu 13. dubna 2010.
Reinhard Diestel. Teorie grafů // 3. - Springer , 2005. - S. 17 . — ISBN 3-540-26182-6 .