Плотный граф
В математике — плотный граф это граф , в котором количество ребер близко к максимальному числу ребер (где каждая пара вершин соединена одним ребром). Напротив, граф с несколькими ребрами является разреженным графом . Различие в том, что представляет собой плотный или разреженный граф, нечетко определено и часто выражается утверждениями «примерно равно». В связи с этим способ определения плотности часто зависит от контекста проблемы.
Плотность простых графов определяется как отношение числа ребер | Е | относительно максимально возможных ребер.
Для неориентированных простых графов плотность графа равна:
Для ориентированных простых графов максимально возможное количество ребер в два раза больше, чем у неориентированных графов (поскольку к ребру есть два направления), поэтому плотность равна:
где E — количество ребер, а V — количество вершин в графе. Максимальное количество ребер неориентированного графа равно , поэтому максимальная плотность равна 1 (для полных графов ), а минимальная плотность равна 0 ( Coleman & Moré 1983 ).
Семейства графов возрастающего размера часто называют разреженными, если как . Иногда в информатике используется более строгое определение разреженности, например или даже .
Верхняя плотность
[ редактировать ]Верхняя плотность — это расширение концепции плотности графа, определенной выше, с конечных графов на бесконечные графы. Интуитивно понятно, что бесконечный граф имеет сколь угодно большие конечные подграфы с любой плотностью меньше его верхней плотности и не имеет сколь угодно больших конечных подграфов с плотностью больше его верхней плотности. Формально верхняя плотность графа G — это нижняя грань значений α таких, что конечные подграфы графа G с плотностью α имеют ограниченное число вершин. можно показать Используя теорему Эрдеша – Стоуна, , что верхняя плотность может быть только равна 1 или одному из суперчастных отношений 0, 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 ≤ l < 2 k .
Для семейства графов существование k и l таких, что все графы в семействе ( k , l ) -разрежены, эквивалентно тому, что графы в семействе имеют ограниченную вырожденность или ограниченную древесность . Точнее, из результата Нэша-Уильямса (1964) следует , что графы древесности не выше a являются в точности ( a , a ) -разреженными графами. Аналогично, графики вырождения не выше d имеют вид -разреженные графы ( 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 .