Плотный граф

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Максимальное число рёбер равно ½ |V| (|V|−1), так что максимальная плотность равна 1 (для полных графов) и минимальная равна 0 [2]

Верхняя плотность[править | править вики-текст]

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

Разреженные и тугие графы[править | править вики-текст]

Штрейну (Streinu, 2008) [3] и Теран (Theran, 2009) [4] определяют граф как (k,l)-разреженный, если любой непустой подграф с n вершинами имеет максимум kn − l рёбер, и как (k,l)-тугой, если он (k,l)-разреженный и имеет в точности kn − l рёбер. Таким образом деревья в точности (1,1)-тугие графы, леса – в точности (1,1)-разреженные графы, а графы с древесностью[en] k – в точности (k,k)-разреженные графы. Псевдолеса[en] – это в точности (1,0)-разреженные графы, а Ламановы графы, появляющиеся в теории жёсткости[en], это в точности (2,3)-тугие графы.

Другие семейства графов также могут быть описаны подобным образом. Например, из того, что любой планарный граф с n вершинами имеет максимум 3n - 6 ребра, и что любой подграф планарного графа является планарным, вытекает, что планарные графы являются (3,6)-разреженными графами. Однако не всякий (3,6)-разреженный граф будет планарным. Аналогично, внешнепланарные графы[en] являются (2,3)-разреженными и планарные двудольные графы являются (2,4)-разреженными.

Штрейну и Теран показали, что проверка, является ли граф (k,l)-разреженным, может быть выполнена за полиномиальное время.

Разреженные и плотные классы графов[править | править вики-текст]

Оссона и Нешетрил (Ossona de Mendez, Nešetřil, 2010) [5] полагают, что при делении на разреженные/плотные графы необходимо рассматривать бесконечные классы графов, а не отдельных представителей. Они определили местами плотные классы графов как классы, для которых существует такой порог t, что любой полный граф появляется как t-подраздел в подграфе графов класса. И наоборот, если такой порог не существует, класс называется нигде не плотным. Свойства деления на местами плотные/нигде не плотные обсуждается в статье Оссона и Нешетрил (Ossona de Mendez, Nešetřil, 2012) [6].

Ссылки[править | править вики-текст]

  1. 1 2 Рейнгард Дистель Теория графов. — Новосибирск: Издательство института математики, 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. — В. 1. — Т. 20. — С. 187–209. — DOI:10.1137/0720013.
  3. Audrey Lee, Ileana Streinu Pebble game algorithms and sparse graphs // Discrete Mathematics. — 2008. — В. 8. — Т. 308. — С. 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. — В. 8. — Т. 30. — С. 1944–1964. — DOI:10.1016/j.ejc.2008.12.018 — arΧivmath/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, first (1998), «Data Structures and Algorithms with Object-Oriented Design Patterns in C++», John Wiley & Sons, ISBN 0-471-24134-2 .