Введение

Граф с почти максимальным количеством ребер

В математике плотный граф — это граф, в котором число ребер близко к максимально возможному числу ребер (когда каждая пара вершин соединена одним ребром). Противоположностью является разреженный граф, имеющий небольшое количество ребер. Граница между плотным и разреженным графом определена нечетко и часто выражается формулировками типа «приблизительно равно». В связи с этим, определение плотности часто зависит от контекста задачи. Плотность графа для простых графов определяется как отношение числа ребер к максимально возможному числу ребер. Для ненаправленных простых графов плотность графа равна:

Для направленных простых графов максимально возможное число ребер вдвое больше, чем у ненаправленных графов (поскольку каждое ребро имеет два направления), поэтому плотность равна:

где E — число ребер, а V — число вершин в графе. Максимальное число ребер для ненаправленного графа равно , следовательно, максимальная плотность равна 1 (для полных графов), а минимальная плотность равна 0. Для семейств графов возрастающего размера их часто называют разреженными, если . Иногда в информатике используется более строгий критерий разреженности, например или даже .

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

Верхняя плотность является обобщением понятия плотности графа, определенного выше для конечных графов, на бесконечные графы. Интуитивно, бесконечный граф содержит сколь угодно большие конечные подграфы с любой плотностью, меньшей его верхней плотности, но не содержит сколь угодно большие конечные подграфы с плотностью, превышающей его верхнюю плотность. Формально, верхняя плотность графа G — это инфимум значений α, для которых конечные подграфы G с плотностью α имеют ограниченное число вершин. С помощью теоремы Эрдеша — Стоуна можно показать, что верхняя плотность может быть равна только 1 или одному из суперчастичных отношений (см., например, Diestel, издание 5, с. 189).

Небольшие и узкие графики

и определяет граф как (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 вершинами), и что любой подграф планарного графа является планарным, вместе подразумевают, что планарные графы являются (3,6) разреженными. Однако не каждый (3,6) разреженный граф является планарным. Аналогично, внешнепланарные графы являются (2,3) разреженными, а планарные двудольные графы – (2,4) разреженными. Стрейну и Теран показали, что проверка (k,l) разреженности может быть выполнена за полиномиальное время, когда k и l – целые числа и 0 ≤ l < 2k. Для семейства графов существование k и l, при которых все графы в семействе являются (k,l) разреженными, эквивалентно тому, что графы в семействе имеют ограниченную дегенерацию или ограниченную древовидность. Более точно, из результата следует, что графы с древовидностью не более a являются точно (a,a) разреженными графами. Аналогично, графы с дегенерацией не более d являются разреженными графами.

Небольшие и большие классы графиков

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