В математике плотный граф — это граф , в котором количество ребер близко к максимальному числу ребер (где каждая пара вершин соединена одним ребром). Напротив, граф с несколькими ребрами является разреженным графом . Различие в том, что представляет собой плотный или разреженный граф, нечетко определено и часто выражается утверждениями «примерно равно». В связи с этим способ определения плотности часто зависит от контекста проблемы.
Плотность простых графов определяется как отношение числа ребер | Е | относительно максимально возможных ребер.
Для неориентированных простых графов плотность графа равна:
Для ориентированных простых графов максимальное количество ребер в два раза больше, чем у неориентированных графов (поскольку к ребру есть два направления), поэтому плотность равна:
где E — количество ребер, а V — количество вершин в графе. Максимальное количество ребер для неориентированного графа равно , поэтому максимальная плотность равна 1 (для полных графов ), а минимальная плотность равна 0 (Coleman & Moré, 1983).
Семейства графов увеличивающегося размера часто называют разреженными, если как . Иногда в информатике используется более строгое определение разреженности, например или даже .
Верхняя плотность — это расширение концепции плотности графа, определенной выше, с конечных графов на бесконечные графы. Интуитивно понятно, что бесконечный граф имеет сколь угодно большие конечные подграфы с любой плотностью меньше его верхней плотности и не имеет сколь угодно больших конечных подграфов с плотностью больше его верхней плотности. Формально верхняя плотность графа G — это нижняя грань значений α таких, что конечные подграфы графа G с плотностью α имеют ограниченное число вершин. Используя теорему Эрдеша – Стоуна, можно показать , что верхняя плотность может быть только равна 1 или одному из суперчастных отношений 0,1/2,2/3,3/4,4/5, …н/п + 1(см., напр., Дистель, изд. 5, стр. 189).
Ли и Стрейну (2008) и Стрейну и Теран (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).
Нешетржил и Оссона де Мендес (2010) считали, что дихотомия разреженности/плотности делает необходимым рассматривать бесконечные классы графов вместо отдельных экземпляров графа. Они определили где-то плотные классы графов как те классы графов, для которых существует порог t, такой, что каждый полный граф появляется как t -подразделение в подграфе графа в классе. Напротив, если такого порога не существует, класс нигде не является плотным . Свойства дихотомии «нигде плотный» и «где-то плотный» обсуждаются в работе Нешетрила и Оссона де Мендес (2012).
Классы графов с ограниченной вырождением и нигде не плотные графы включены в графы без биклик , семейства графов, которые исключают некоторый полный двудольный граф в качестве подграфа (Telle & Villanger 2012).
