Плотный граф

Пло́тный граф — граф, в котором число рёбер ${\displaystyle E}$ близко к максимально возможному у полного графа с числом вершин ${\displaystyle V}$:

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

Граф, имеющий малое число рёбер, принято называть разреженным графом.

Вообще говоря, разница между разреженным и плотным графом условна и зависит от контекста.

Для неориентированного простого графа (рёберная)[1] плотность графа с числом вершин ${\displaystyle V}$ определяется как отношение числа его рёбер ${\displaystyle E}$ к числу рёбер полного графа:

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

Максимальное число рёбер равно ${\displaystyle E={\frac {V(V-1)}{2}},}$ так что максимальная плотность графа равна 1 (для полных графов) и минимальная равна 0 — для несвязанного графа[2].

Верхняя плотность

Верхняя плотность — это расширение понятия плотности графа с конечных графов на бесконечные. Интуитивно понятно, что бесконечный граф имеет произвольно большие конечные подграфы с любой плотностью, меньшей верхней плотности, и не имеет произвольно больших конечных подграфов с плотностью, большей верхней плотности. Формально, верхняя плотность графа G — это нижняя грань таких значений α, что конечные подграфы графа G с плотностью больше α имеют ограниченный порядок. Используя теорему Эрдёша — Стоуна^[англ.] можно показать, что верхняя плотность может быть только 1 или одним из значений последовательности 0, 1/2, 2/3, 3/4, 4/5, … n/(n + 1), … (см, например, Дистель. Упражнения к главе 7[1]).

Разреженные и тугие графы

Штрейну[3] и Теран[4] определяют граф как (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)-разреженным, может быть выполнена за полиномиальное время.

Разреженные и плотные классы графов

Оссона и Нешетрил[5] полагают, что при делении на разреженные/плотные графы необходимо рассматривать бесконечные классы графов, а не отдельных представителей. Они определили местами плотные классы графов как классы, для которых существует такой порог t, что любой полный граф появляется как t-подраздел в подграфе графов класса. И наоборот, если такой порог не существует, класс называется нигде не плотным. Свойства деления на местами плотные/нигде не плотные обсуждается в статье Оссона и Нешетрил[6].

Примечания

1. Рейнгард Дистель. Теория графов. — Новосибирск: Издательство института математики, 2002. — ISBN 5-86134-101-X.
2. Thomas F. Coleman, Jorge J. Moré. Estimation of sparse Jacobian matrices and graph coloring Problems // SIAM Journal on Numerical Analysis. — 1983. — Т. 20, вып. 1. — С. 187—209. — doi:10.1137/0720013.
3. Audrey Lee, Ileana Streinu. Pebble game algorithms and sparse graphs // Discrete Mathematics. — 2008. — Т. 308, вып. 8. — С. 1425—1437. — doi:10.1016/j.disc.2007.07.104.
4. I. Streinu, L. Theran. Sparse hypergraphs and pebble game algorithms // European Journal of Combinatorics. — 2009. — Т. 30, вып. 8. — С. 1944—1964. — doi:10.1016/j.ejc.2008.12.018. — arXiv:math/0703921.
5. Patrice Ossona de Mendez, Jaroslav Nešetřil. European Congress of Mathematics. — European Mathematical Society, 2010. — С. 135—165.
6. Jaroslav Nešetřil, Patrice Ossona de Mendez. Sparsity: Graphs, Structures, and Algorithms. — Heidelberg: Springer, 2012. — Т. 28. — ISBN 978-3-642-27874-7. — doi:10.1007/978-3-642-27875-4.

Литература

• Paul E. Black, Sparse graph Архивная копия от 16 декабря 2008 на Wayback Machine, from Dictionary of Algorithms and Data Structures, Paul E. Black (ed.), NIST. Retrieved on 29 September 2005.
• Preiss. Data Structures and Algorithms with Object-Oriented Design Patterns in C++. — John Wiley & Sons, 1998. — ISBN 0-471-24134-2.