Плотный граф

В математике — плотный граф это граф , в котором количество ребер близко к максимальному числу ребер (где каждая пара вершин соединена одним ребром). Напротив, граф с несколькими ребрами является разреженным графом . Различие в том, что представляет собой плотный или разреженный граф, нечетко определено и часто выражается утверждениями «примерно равно». В связи с этим способ определения плотности часто зависит от контекста проблемы.

Плотность простых графов определяется как отношение числа ребер $| Е |$ относительно максимально возможных ребер.

Для неориентированных простых графов плотность графа равна:

D={\frac {|E|}{\binom {|V|}{2}}}={\frac {2|E|}{|V|(|V|-1)}}

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

D={\frac {|E|}{2{\binom {|V|}{2}}}}={\frac {|E|}{|V|(|V|-1)}}

где $E$ — количество ребер, а $V$ — количество вершин в графе. Максимальное количество ребер неориентированного графа равно ${\binom {|V|}{2}}={\frac {|V|(|V|-1)}{2}}$ , поэтому максимальная плотность равна 1 (для полных графов ), а минимальная плотность равна 0 ( Coleman & Moré 1983 ).

Семейства графов возрастающего размера часто называют разреженными, если $D\rightarrow 0$ как $|V|\rightarrow \infty$ . Иногда в информатике используется более строгое определение разреженности, например $|E|=O(|V|\log |V|)$ или даже $|E|=O(|V|)$ .

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

Верхняя плотность — это расширение концепции плотности графа, определенной выше, с конечных графов на бесконечные графы. Интуитивно понятно, что бесконечный граф имеет сколь угодно большие конечные подграфы с любой плотностью меньше его верхней плотности и не имеет сколь угодно больших конечных подграфов с плотностью больше его верхней плотности. Формально верхняя плотность графа $G$ — это нижняя грань значений α таких, что конечные подграфы графа $G$ с плотностью α имеют ограниченное число вершин. можно показать Используя теорему Эрдеша – Стоуна, , что верхняя плотность может быть только равна 1 или одному из суперчастных отношений $0, .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ 1 / 2 ⁠ , ⁠ 2 / 3 ⁠ , ⁠ 3 / 4 ⁠ , ⁠ 4 / 5 ⁠ , … ⁠ n / n + 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 \leq l < 2 k$ .

Для семейства графов существование $k$ и $l$ таких, что все графы в семействе $(k, l)$ -разрежены, эквивалентно тому, что графы в семействе имеют ограниченную вырожденность или ограниченную древесность . Точнее, из результата Нэша-Уильямса (1964) следует , что графы древесности не выше $a$ являются в точности $(a, a)$ -разреженными графами. Аналогично, графики вырождения не выше $d$ имеют вид $\left(d,{\binom {d+1}{2}}\right)$ -разреженные графы ( Lick & White 1970 ).

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

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

Классы графов с ограниченной вырождением и нигде не плотные графы включены в графы без биклик , семейства графов, которые исключают некоторый полный двудольный граф в качестве подграфа ( Telle & Villanger 2012 ).

См. также

Ссылки

Пол Э. Блэк, Разреженный граф , из Словаря алгоритмов и структур данных, Пол Э. Блэк (редактор), NIST . Проверено 29 сентября 2005 г.
Коулман, Томас Ф .; Море, Хорхе Дж. (1983), «Оценка разреженных матриц Якобиана и проблемы раскраски графов», SIAM Journal on Numerical Analysis , 20 (1): 187–209, doi : 10.1137/0720013 .
Дистель, Рейнхард (2005), Теория графов , Тексты для выпускников по математике , Springer-Verlag, ISBN 3-540-26183-4 , OCLC 181535575 .
Ли, Одри; Стрейну, Илеана (2008), «Алгоритмы игр с галькой и разреженные графы», Discrete Mathematics , 308 (8): 1425–1437, arXiv : math/0702129 , doi : 10.1016/j.disc.2007.07.104 , MR 2392060 .
Нэш-Уильямс, К. Ст. Дж. А. (1964), «Разложение конечных графов на леса», Журнал Лондонского математического общества , 39 (1): 12, doi : 10.1112/jlms/s1-39.1.12 , MR 0161333
Лик, Дон Р.; Уайт, Артур Т. (1970). «k-Вырожденные графы» . Канадский математический журнал . 22 (5): 1082–1096.
Прейсс, первый (1998), Структуры данных и алгоритмы с объектно-ориентированными шаблонами проектирования в C++ , John Wiley & Sons, ISBN 0-471-24134-2 .
Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2010), «От разреженных графов к нигде не плотным структурам: разложения, независимость, двойственность и пределы», Европейский математический конгресс , Европейское математическое общество, стр. 135–165.
Нешетржил, Ярослав ; Оссона де Мендес, Патрис (2012), Разреженность: графы, структуры и алгоритмы , Алгоритмы и комбинаторика, том. 28, Гейдельберг: Springer, номер номера : 10.1007/978-3-642-27875-4 , ISBN. 978-3-642-27874-7 , МР 2920058 .
Стрейну, И. ; Теран, Л. (2009), «Разреженные гиперграфы и алгоритмы игр с камушками», Европейский журнал комбинаторики , 30 (8): 1944–1964, arXiv : math/0703921 , doi : 10.1016/j.ejc.2008.12.018 .
Телле, Ян Арне; Вилланджер, Ингве (2012), «Алгоритмы FPT для доминирования в графах без биклик», в Эпштейне, Лия; Феррагина, Паоло (ред.), Алгоритмы - ESA 2012: 20-й ежегодный европейский симпозиум, Любляна, Словения, 10–12 сентября 2012 г., Труды , Конспекты лекций по информатике , том. 7501, Springer, стр. 802–812, номер документа : 10.1007/978-3-642-33090-2_69 .