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 .








Příklady
- Grafy se nazývají hvězdy , všechny úplné bipartitní grafy, které jsou stromy , jsou hvězdy.

- Graf se nazývá dráp a používá se k definování grafů bez drápů .

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


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

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 .