Loading AI tools
граф, в котором число рёбер близко к максимальному Из Википедии, свободной энциклопедии
Пло́тный граф — граф, в котором число рёбер близко к максимально возможному у полного графа с числом вершин :
Граф, имеющий малое число рёбер, принято называть разреженным графом.
Вообще говоря, разница между разреженным и плотным графом условна и зависит от контекста.
Для неориентированного простого графа (рёберная)[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].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.