WikiSort.ru - Не сортированное

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

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

${\displaystyle 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]).

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

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

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

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

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

Примечания

Литература

• 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.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.