Jump to content

Плотный граф

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

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

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

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

где 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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 86ec7a606b40da90c1de5f2218976e9b__1711347060
URL1:https://arc.ask3.ru/arc/aa/86/9b/86ec7a606b40da90c1de5f2218976e9b.html
Заголовок, (Title) документа по адресу, URL1:
Dense graph - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)