Плотный график - Dense graph

В математике , А плотный граф является графиком , в котором число ребер близко к максимальному числу ребер. Напротив, граф с несколькими ребрами является разреженным графом . Различие между разреженными и плотными графами довольно расплывчато и зависит от контекста.

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

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

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

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

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

Верхняя плотность - это расширение концепции плотности графов, определенной выше, от конечных графов до бесконечных графов. Интуитивно бесконечный граф имеет произвольно большие конечные подграфы с любой плотностью, меньшей, чем его верхняя плотность, и не имеет сколь угодно больших конечных подграфов с плотностью, большей, чем его верхняя плотность. Формально верхняя плотность графа G - это нижняя грань таких значений α, что конечные подграфы G с плотностью α имеют ограниченное число вершин. С помощью теоремы Эрдеша – Стоуна можно показать, что верхняя плотность может быть только 1 или одним из суперпартикулярных отношений 0,1/2, 2/3, 3/4, 4/5, ... п/п  + 1, ... (см., например, Diestel, издание 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 - это в точности (( d + 1) / 2, 1) -разреженные графы.

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

Nešetřil и Ossona de Mendez (2010) считали, что дихотомия разреженности / плотности заставляет рассматривать бесконечные классы графов вместо отдельных экземпляров графов. Они определили где-то плотные классы графов как те классы графов, для которых существует порог t, такой, что каждый полный граф появляется как t -подразделение в подграфе графа в классе. Напротив, если такой порог не существует, класс нигде не плотный . Свойства дихотомии «нигде не плотное» и «где-то плотное» обсуждаются в Nešetřil & Ossona de Mendez (2012) .

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

Смотрите также

использованная литература

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