В математике плотный граф — это граф , в котором число ребер близко к максимальному числу ребер (где каждая пара вершин соединена одним ребром). Противоположность, граф с несколькими ребрами, является разреженным графом . Различие между тем, что составляет плотный или разреженный граф, определено нечетко и часто представляется утверждениями «примерно равно». Из-за этого способ определения плотности часто зависит от контекста задачи.
Плотность графа простых графов определяется как отношение числа ребер | E | к максимально возможному числу ребер.
Для неориентированных простых графов плотность графа равна:
Для ориентированных простых графов максимально возможное количество ребер в два раза больше, чем для неориентированных графов (поскольку существует два направления к ребру), поэтому плотность равна:
где E — число ребер, а V — число вершин в графе. Максимальное число ребер для неориентированного графа равно , поэтому максимальная плотность равна 1 (для полных графов ), а минимальная плотность равна 0 (Coleman & More 1983).
Для семейств графов увеличивающегося размера их часто называют разреженными, если как . Иногда в информатике используется более узкое определение разреженного типа как или даже .
Верхняя плотность — это расширение концепции плотности графа, определенной выше, с конечных графов на бесконечные графы. Интуитивно, бесконечный граф имеет произвольно большие конечные подграфы с любой плотностью, меньшей его верхней плотности, и не имеет произвольно больших конечных подграфов с плотностью, большей его верхней плотности. Формально верхняя плотность графа G — это инфимум значений α, такой что конечные подграфы графа G с плотностью α имеют ограниченное число вершин. Можно показать с помощью теоремы Эрдеша–Стоуна , что верхняя плотность может быть равна только 1 или одному из суперчастных отношений 0, 1/2 , 2/3 , 3/4 , 4/5 , … н/н + 1 (см., напр., Дистель, вып. 5, стр. 189).
Lee & Streinu (2008) и Streinu & Theran (2009) определяют граф как ( 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 вершинами), и что любой подграф планарного графа является планарным, вместе подразумевают, что планарные графы являются (3,6) -разреженными. Однако не каждый (3,6) -разреженный граф является планарным. Аналогично, внешнепланарные графы являются (2,3) -разреженными, а планарные двудольные графы являются (2,4) -разреженными.
Стрейну и Теран показывают, что тестирование ( k , l ) -разреженности может быть выполнено за полиномиальное время, когда k и l являются целыми числами и 0 ≤ l < 2 k .
Для семейства графов существование k и l таких, что все графы в семействе являются ( k , l ) -разреженными, эквивалентно тому, что графы в семействе имеют ограниченную вырожденность или ограниченную древесность . Точнее, из результата Нэша-Вильямса (1964) следует, что графы древесности не более a являются в точности ( a , a ) -разреженными графами. Аналогично, графы вырожденности не более d являются -разреженными графами (Lick & White 1970).
Nešetřil & Ossona de Mendez (2010) считали, что дихотомия разреженности/плотности делает необходимым рассмотрение бесконечных классов графов вместо отдельных экземпляров графов. Они определили где-то плотные классы графов как те классы графов, для которых существует порог t такой, что каждый полный граф появляется как t -подразделение в подграфе графа в классе. Напротив, если такого порога не существует, класс является нигде не плотным . Свойства дихотомии нигде не плотный против где-то плотный обсуждаются в Nešetřil & Ossona de Mendez (2012).
Классы графов с ограниченной вырожденностью и нигде не плотных графов включены в графы, свободные от биклики , семейства графов, которые исключают некоторый полный двудольный граф как подграф (Telle & Villanger 2012).
