Плотный граф

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

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

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

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

.

Максимальное число рёбер равно так что максимальная плотность графа равна 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, 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.