V matematice a konkrétněji v teorii grafů můžeme spojit s jakýmkoli grafem celé číslo, které se nazývá hustota grafu . Tento parametr měří, zda má graf mnoho nebo málo hran. Hustý graf ( hustý graf ) je graf, ve kterém je počet hran (nebo oblouky), se nachází v blízkosti jejich maximální počet, například kvadratické číslo vzhledem k počtu vrcholů. Dutý graf ( rozptýlený graf ) naopak málo kostí, například lineární číslo. Rozdíl mezi dutým a hustým grafem je poměrně vágní a závisí na kontextu.
Hustota grafu je definován jako poměr mezi počtem okrajů (nebo oblouky) dělený počtem hran (nebo oblouky) možné .
V případě jednoduchého neorientovaného grafu je hustota poměr:
Čitatel spočítá počet existujících hran a vynásobí je dvěma, protože každá hrana je spojena s dvojicí vrcholů. Jmenovatel spočítá celkový počet hran nutných pro připojení každého vrcholu ke všem ostatním (úplnost). Počítáme a ne , protože v jednoduchém grafu spojují hrany dva různé vrcholy.
Hustota 0 odpovídá grafu, kde jsou izolovány všechny vrcholy, a hustota 1 úplnému grafu .
Míra hustoty grafu je arboricita, která počítá minimální počet vrtáků potřebných k pokrytí grafu. Můžeme také použít degeneraci .
Pojem hustoty se objevuje v kombinatorice, zejména v Szemerédiho pravidelném lematu .
Tyto datové struktury reprezentovaly grafy lze přizpůsobit hustotě grafu. Zejména husté grafy jsou spíše reprezentovány maticemi sousedství , zatímco řídké grafy jsou lépe reprezentovány seznamy sousedství .
Některé algoritmy jsou postaveny tak, aby byly účinné v grafech určité hustoty, a jsou poměrně špatné, pokud jsou použity v libovolných grafech. Obvykle mluvíme o algoritmech pro husté grafy nebo pro duté grafy.
Existuje několik algoritmických problémů zvaných „problém nejhustšího grafu“ ( nejhustší podgraf ). Jedním z nich je nejhustší problém k -subgrafu, ve kterém pro daný graf hledáme nejhustší podgraf k - vrcholů. Je to NP-úplný problém , dokonce omezený na bipartitní grafy a kordální grafy .