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

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

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

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

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

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

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

где E - количество ребер, а V - количество вершин в графе. Максимальное количество ребер для неориентированного графа равно ${ Displaystyle { binom {| V |} {2}} = | V | (| V | -1) / 2}$ , поэтому максимальная плотность равна 1 (для полные графики ), а минимальная плотность равна 0 (Коулман и Море, 1983 ).

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

Верхняя плотность является расширением концепции плотности графов, определенной выше, с конечных графов на бесконечные графы. Интуитивно бесконечный граф имеет сколь угодно большие конечные подграфы с любой плотностью, меньшей, чем его верхняя плотность, и не имеет сколь угодно больших конечных подграфов с плотностью, большей, чем его верхняя плотность. Формально верхняя плотность графа г это инфимум значений α таких, что конечные подграфы г с плотностью α имеют ограниченное число вершин. Это можно показать с помощью Теорема Эрдеша – Стоуна что верхняя плотность может быть только 1 или одной из сверхчастичные отношения 0, 1/2, 2/3, 3/4, 4/5, ... п/(п + 1), ... (см., Например, Diestel, издание 5, с. 189).

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

Ли и Стрейну (2008) и Стрейну и Теран (2009) определить граф как (k,л) -разреженный, если каждый непустой подграф с п вершин не более кн − л края и (k,л) -плотно, если это (k,л)-разреженный и имеет ровно кн − л края. Таким образом деревья - это в точности (1,1) -жатые графы, леса - это в точности (1,1) -разреженные графы, а графы с родословие k точно (k,k) -разреженные графы. Псевдолеса являются в точности (1,0) -разреженными графами, а Графы Ламана возникающий в теория жесткости являются в точности (2,3) -жатыми графами.

Другие семейства графов, не характеризующиеся разреженностью, также могут быть описаны таким же образом. Например, факты, что любой планарный граф с участием п вершин не более 3п - 6 ребер (за исключением графов с менее чем 3 вершинами) и то, что любой подграф плоского графа является плоским, вместе означают, что плоские графы являются (3,6)-разреженными. Однако не всякий (3,6) -резкий граф является плоским. Так же, внешнепланарные графы являются (2,3) -редкими и плоскими двудольные графы являются (2,4) -редкими.

Стрейну и Теран показывают, что тестирование (k,л) -разреженность может выполняться за полиномиальное время, когда k и л являются целыми числами и 0 ≤л < 2k.

Для семейства графов существование k и л такие, что графы в семье все (k,л) -разреженный эквивалентно графам семейства с ограниченными вырождение или ограничив родословие. Точнее, это следует из результата Нэш-Уильямс (1964) что графики древовидности не более а точно (а,а) -разреженные графы. Аналогично, графики вырождения не более d точно такие ((d + 1) / 2,1) -разреженные графы.

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

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

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

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

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

Пол Э. Блэк, Разреженный график, от Словарь алгоритмов и структур данных, Пол Э. Блэк (ред.), NIST. Проверено 29 сентября 2005 г.
Коулман, Томас Ф .; Море, Хорхе Дж. (1983), "Оценка разреженных якобиевых матриц и проблемы раскраски графов", Журнал SIAM по численному анализу, 20 (1): 187–209, Дои:10.1137/0720013.
Дистель, Рейнхард (2005), Теория графов, Тексты для выпускников по математике, Springer-Verlag, ISBN 3-540-26183-4, OCLC 181535575.
Ли, Одри; Стрейну, Илеана (2008), «Алгоритмы игры в гальку и разреженные графы», Дискретная математика, 308 (8): 1425–1437, arXiv:математика / 0702129, Дои:10.1016 / j.disc.2007.07.104, Г-Н 2392060.
Нэш-Уильямс, К. Сент-Дж. А. (1964), «Разложение конечных графов на леса», Журнал Лондонского математического общества, 39 (1): 12, Дои:10.1112 / jlms / s1-39.1.12, Г-Н 0161333
Прейсс, первый (1998), Структуры данных и алгоритмы с объектно-ориентированными шаблонами проектирования в C ++, Джон Уайли и сыновья, ISBN 0-471-24134-2.
Нешетржил, Ярослав; Оссона де Мендес, Патрис (2010), От разреженных графов к нигде не плотным структурам: декомпозиции, независимость, двойственность и пределы, Европейское математическое общество, стр. 135–165.
Нешетржил, Ярослав; Оссона де Мендес, Патрис (2012), Разреженность: графики, структуры и алгоритмы, Алгоритмы и комбинаторика, 28, Гейдельберг: Springer, Дои:10.1007/978-3-642-27875-4, HDL:10338.dmlcz / 143192, ISBN 978-3-642-27874-7, Г-Н 2920058.
Стрейну, И.; Теран, Л. (2009), "Разреженные гиперграфы и алгоритмы игры в гальку", Европейский журнал комбинаторики, 30 (8): 1944–1964, arXiv:математика / 0703921, Дои: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.