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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

Литература

• Paul E. Black, от 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 .