Щільний граф

У математиці граф називається щільним, якщо кількість його ребер близька до максимальної. На противагу, граф з малою кількістю ребер називається розрідженим. Різниця між щільним і розпливчатим графом розмита, і залежить від контексту.

Для неорієнтованих простих графів щільність визначається як:

$D=\frac{2|E|}{|V|(|V|-1)}.$

Для орієнтованих графів:

$D=\frac{|E|}{|V|(|V|-1)},$

де E — кількість ребер, а V — кількість вершин графа. Максимальна кількість ребер для неорієнтованого графа $|V|(|V|-1)/2$, тому максимальна щільність дорівнює 1 (для повних графів), а мінімальна щільність дорівнює 0 Шаблон:Harv.

Верхня щільність

Верхня щільність — розширення поняття щільності для графів нескінченої розмірності. Інтуїтивно зрозуміло, що нескінчений граф містить скінченні підграфи довільної величини з будь-якою щільністю, що менша за верхню щільність нескінченого графа. Також інтуїтивно зрозуміло, що нескінчений граф не містить підграфів (скінченних) зі щільністю, вищою за його верхню щільність. Формально кажучи, верхня щільність графа G — це точна нижня межа таких значень α, що скінченні підграфи G зі щільністю α мають обмежений порядок. Використовуючи теорему Ердьоша-Стоуна, можна показати, що верхня щільність може бути або 1, або одним зі значень послідовності 0, 1/2, 2/3, 3/4, 4/5, … n/(n + 1), …Шаблон:Sfn

Розріджені і тугі графи

Згідно з Шаблон:Harvtxt та Шаблон:Harvtxt, граф є $(k,l)$-розрідженим, якщо кожен непорожній підграф з n ребрами має щонайбільше $kn-l$ ребер, і $(k,l)$-тугим, якщо він є $(k,l)$-розрідженим і має точно $kn-l$ ребер. Таким чином, дерева є точно $(1,1)$-тугими графами, ліси — точно $(1,1)$-розрідженими, а графи з деревністю $k$ є точно $(k,k)$-розрідженими графами. Псевдоліси є точно $(1,0)$-розрідженими, а Графи Ламана (це поняття зустрічається, наприклад, у теорії жорсткості) є точно $(2,3)$-тугими графами.

Інші сім'ї графів, що не характеризуються такою якістю, як розрідженість, також може бути описано подібним чином. Наприклад, будь-який планарний граф з $n$ ребрами має щонайбільше $3n-6$ ребер, і що будь-який підграф планарного графа також є планарним. З цього витікає, що планарні графи є $(3,6)$-розрідженими. Але не кожен $(3,6)$-розріджений граф є планарним. Аналогічно, зовніпланарні графи є $(2,3)$-розрідженими, а планарні двочасткові графи — $(2,4)$-розрідженими.

Штрейну і Теран показують, що перевірка $(k,l)$-розрідженості може бути виконана за поліноміальний час, якщо $k$ і $l$ — цілі числа, і $0\le l<2k$.

Джерела

• Шаблон:Citation Шаблон:Ref-en
• Шаблон:Citation Шаблон:Ref-en
• Шаблон:Citation Шаблон:Ref-en