Щільний граф

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

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

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

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

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

де E — кількість ребер, а V — кількість вершин графа. Максимальна кількість ребер для неорієнтованого графа ${\displaystyle |V|(|V|-1)/2}$, тому максимальна щільність дорівнює 1 (для повних графів), а мінімальна щільність дорівнює 0 (Coleman та Moré, 1983).

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

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

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

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

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

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

Примітки

1. Diestel, 2005.

Джерела

• Diestel, Reinhard (2005), Graph Theory, Graduate Texts in Mathematics^[en], Springer-Verlag, ISBN 3-540-26183-4, OCLC 181535575 (англ.)
• Lee, Audrey; Streinu, Ileana (2008), Pebble game algorithms and sparse graphs, Discrete Mathematics, 308 (8): 1425—1437, doi:10.1016/j.disc.2007.07.104, MR 2392060 (англ.)
• Streinu, I.; Theran, L. (2009), Sparse hypergraphs and pebble game algorithms, European Journal of Combinatorics^[en], 30 (8): 1944—1964, arXiv:math/0703921, doi:10.1016/j.ejc.2008.12.018 (англ.)