Пропускная способность графа

В теории графов проблема пропускной способности графа чтобы пометить $n$ вершин $v i$ графа состоит в том , $G$ разными целыми числами . $f(v_{i})$ ⁠ так, чтобы количество $\max\{\,|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}$ минимизируется ( $E$ — множество ребер $G$ ). ^[1]Проблему можно представить себе как размещение вершин графа в различных целочисленных точках вдоль оси x так, чтобы длина самого длинного ребра была минимизирована. Такое размещение называется расположением линейного графика , расположением линейного графика или размещением линейного графика . ^[2]

Проблема пропускной способности взвешенного графа представляет собой обобщение , в котором ребрам присваиваются веса $w ij$ , а функция стоимости, которую необходимо минимизировать, равна $\max\{\,w_{ij}|f(v_{i})-f(v_{j})|:v_{i}v_{j}\in E\,\}$ .

С точки зрения матриц, (невзвешенная) пропускная способность графа — это минимальная пропускная способность симметричной матрицы , которая является матрицей смежности графа.Пропускную способность также можно определить как величину, меньшую на единицу, чем максимальный размер клики в соответствующем интервальном суперграфе данного графа, выбранном для минимизации размера клики ( Kaplan & Shamir 1996 ).

Циклически интервальные графики

Для фиксированного $k$ определить для каждого $i$ набор $I_{k}(i):=[i,i+k+1)$ . $G_{k}(n)$ — соответствующий график интервалов, сформированный изинтервалы $I_{k}(1),I_{k}(2),...I_{k}(n)$ . Это именно тот интервалграфики графиков, имеющих пропускную способность $k$ . Эти графики называются be циклически интервальные графики , поскольку интервалы можно назначать слоям $L_{1},L_{2},...L_{k+1}$ в циклическом порядке, где интервалы слоя непересекаться.

Таким образом, можно увидеть связь с шириной пути . Графы с ограниченной шириной пути являются второстепенными, но закрытыми.множество подграфов циклически интервальных графов таковыми не являются. Это следует из того, что мышлениеВершины степени 2 могут увеличить пропускную способность.

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

Формулы пропускной способности для некоторых графов

Для нескольких семейств графов пропускная способность $\varphi (G)$ задается явной формулой.

Пропускная способность графа путей P _n на n вершинах равна 1, а для полного графа K _m имеем $\varphi (K_{n})=n-1$ . Для полного двудольного графа K _{m , n} ,

\varphi (K_{m,n})=\lfloor (m-1)/2\rfloor +n

, предполагая

m\geq n\geq 1,

который исполнил Хватал. ^[3] Как частный случай этой формулы, звездный граф $S_{k}=K_{k,1}$ на k + 1 вершинах имеет пропускную способность $\varphi (S_{k})=\lfloor (k-1)/2\rfloor +1$ .

Для графа гиперкуба $Q_{n}$ на $2^{n}$ вершин, полоса пропускания была определена Харпером (1966) как

\varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.

Хваталова показала ^[4] что пропускная способность m × n графа с квадратной сеткой $P_{m}\times P_{n}$ , то есть декартово произведение двух графов путей на $m$ и $n$ вершин, равно min{ m , n }.

Границы

Пропускная способность графа может быть ограничена с точки зрения различных других параметров графа. Например, обозначая χ( ) хроматическое число G G ,

\varphi (G)\geq \chi (G)-1;

полагая diam( G ) обозначать диаметр G : , выполняются следующие неравенства ^[5]

\lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),

где $n$ это количество вершин в $G$ .

Если граф G имеет пропускную способность k , то ширина его пути не превышает k ( Kaplan & Shamir 1996 ), а глубина его дерева не превышает k log( n / k ) ( Gruber 2012 ). Напротив, как отмечалось в предыдущем разделе, звездчатый граф , _Sk структурно очень простой пример дерева , имеет сравнительно большую пропускную способность. что ширина Sk пути равна _{Обратите внимание ,} 1, а глубина дерева равна 2.

Некоторые семейства графов ограниченной степени имеют сублинейную пропускную способность: Чунг (1988) доказал, что если T — дерево максимальной степени не выше ∆, то

\varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.

В более общем смысле, для плоских графов ограниченной максимальной степени не выше ∆ аналогичная оценка справедлива (см. Böttcher et al. 2010 ):

\varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.

Вычисление пропускной способности

И невзвешенная, и взвешенная версии являются частными случаями квадратичной задачи о назначении узкого места .Проблема с пропускной способностью является NP-сложной , даже в некоторых особых случаях. ^[6] Что касается существования эффективных В алгоритмах аппроксимации известно, что полосу пропускания NP-трудно аппроксимировать в пределах любой константы, и это справедливо даже тогда, когда входные графы ограничены деревьями-гусеницами с максимальной длиной волос 2 ( Dubey, Feige & Unger 2010 ).Для случая плотных графов алгоритм 3-аппроксимации был разработан Карпински, Виртгеном и Зеликовским (1997) .С другой стороны, известен ряд полиномиально решаемых частных случаев. ^[2] Эвристическим алгоритм алгоритмом получения линейных макетов графов с низкой пропускной способностью является Катхилла-Макки . В работе предложен быстрый многоуровневый алгоритм расчета пропускной способности графа. ^[7]

Приложения

Интерес к этой проблеме обусловлен некоторыми прикладными областями.

Одной из областей является обработка разреженной / полосной матрицы , и общие алгоритмы из этой области, такие как алгоритм Катхилла – Макки , могут применяться для поиска приближенных решений проблемы пропускной способности графа.

Другая область применения – автоматизация электронного проектирования . В методологии проектирования стандартных ячеек обычно стандартные ячейки имеют одинаковую высоту, и их размещение организовано в несколько рядов. В этом контексте проблема пропускной способности графа моделирует проблему размещения набора стандартных ячеек в одной строке с целью минимизировать максимальную задержку распространения (которая предполагается пропорциональной длине провода).

См. также

Cutwidth и pathwidth — различные задачи NP-полной оптимизации, включающие линейную компоновку графов.

Ссылки

^ ( Чинн и др. 1982 )
^ Перейти обратно: ^а ^б «Решение NP-трудности проблемы пропускной способности графа», Уриэль Файги, Конспект лекций по информатике , том 1851, 2000 г., стр. 129–145, два : 10.1007/3-540-44985-X_2
^ Замечание к проблеме Харари. В. Хватал, Чехословацкий математический журнал 20 (1): 109–111, 1970. http://dml.cz/dmlcz/100949.
^ Оптимальная маркировка продукта двух путей. Дж. Хваталова, Дискретная математика 11 , 249–253, 1975.
^ Чинн и др. 1982 год
^ Гэри-Джонсон: GT40
^ Илья Сафро, Дорит Рон и Ачи Брандт (2008). «Многоуровневые алгоритмы решения задач линейного порядка». Журнал экспериментальной алгоритмики ACM . 13 : 1,4–1,20. дои : 10.1145/1412228.1412232 .

Бетчер, Дж.; Прюсманн, КП; Тараз, А.; Вюрфль, А. (2010). «Пропускная способность, расширение, ширина дерева, разделители и универсальность графов ограниченной степени». Европейский журнал комбинаторики . 31 (5): 1217–1227. arXiv : 0910.3014 . дои : 10.1016/j.ejc.2009.10.010 .
Чинн, ПЗ ; Хваталова, Ю.; Дьюдни, AK ; Гиббс, штат Невада (1982). «Проблема пропускной способности для графиков и матриц — обзор». Журнал теории графов . 6 (3): 223–254. дои : 10.1002/jgt.3190060302 .
Чанг, Фан Р.К. (1988), «Разметка графов», в Бейнеке, Лоуэлл В.; Уилсон, Робин Дж. (ред.), Избранные темы теории графов (PDF) , Academic Press, стр. 151–168, ISBN 978-0-12-086203-0
Дубей, К.; Файги, У.; Унгер, В. (2010). «Результаты твердости для аппроксимации полосы пропускания» . Журнал компьютерных и системных наук . 77 : 62–90. дои : 10.1016/j.jcss.2010.06.006 .
Гэри, MR ; Джонсон, DS (1979). Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 0-7167-1045-5 .
Грубер, Герман (2012), «О сбалансированных сепараторах, ширине дерева и ранге цикла», Journal of Combinatorics , 3 (4): 669–682, arXiv : 1012.1344 , doi : 10.4310/joc.2012.v3.n4.a5
Харпер, Л. (1966). «Оптимальные нумерации и изопериметрические задачи на графах» . Журнал комбинаторной теории . 1 (3): 385–393. дои : 10.1016/S0021-9800(66)80059-5 .
Каплан, Хаим; Шамир, Рон (1996), «Проблемы ширины пути, пропускной способности и завершения правильных интервальных графов с небольшими кликами», SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137/s0097539793258143
Карпински, Марек; Виртген, Юрген; Зеликовский, Александр (1997). «Алгоритм аппроксимации проблемы пропускной способности на плотных графах» . Электронный коллоквиум по вычислительной сложности . 4 (17).

Внешние ссылки

Проблема минимальной пропускной способности , в: Пьерлуиджи Крещенци и Вигго Канн (ред.), Сборник проблем оптимизации NP. По состоянию на 26 мая 2010 г.

[1] ( Чинн и др. 1982 )

[feige-2] Перейти обратно: ^а ^б «Решение NP-трудности проблемы пропускной способности графа», Уриэль Файги, Конспект лекций по информатике , том 1851, 2000 г., стр. 129–145, два : 10.1007/3-540-44985-X_2

[3] Замечание к проблеме Харари. В. Хватал, Чехословацкий математический журнал 20 (1): 109–111, 1970. http://dml.cz/dmlcz/100949.

[4] Оптимальная маркировка продукта двух путей. Дж. Хваталова, Дискретная математика 11 , 249–253, 1975.

[5] Чинн и др. 1982 год

[6] Гэри-Джонсон: GT40

[multilevellinord-7] Илья Сафро, Дорит Рон и Ачи Брандт (2008). «Многоуровневые алгоритмы решения задач линейного порядка». Журнал экспериментальной алгоритмики ACM . 13 : 1,4–1,20. дои : 10.1145/1412228.1412232 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]