В теории графов , то проблема график пропускной способности , чтобы обозначить , что п вершин v I графа G с различными целыми числами F ( v я ) так , что количествоминимизируется ( E - множество ребер G ). [1] Проблему можно представить как размещение вершин графа в различных целых точках вдоль оси x так, чтобы минимизировать длину самого длинного ребра. Такое размещение называется линейное расположение граф , линейный график макет или линейный график размещения . [2]
Проблема ширины полосы взвешенного графа является обобщением, в котором ребрам присваиваются веса w ij, а функция стоимости, которую необходимо минимизировать, имеет вид.
С точки зрения матриц, то (невзвешенное) Ширина полосы график показывает полосу пропускания в симметричной матрицы , которая является матрицей смежности графа. Пропускная способность также может быть определена на единицу меньше максимального размера клики в соответствующем интервальном суперграфе данного графа, выбранном для минимизации размера клики ( Kaplan & Shamir 1996 ).
Формулы пропускной способности для некоторых графиков
Для нескольких семейств графиков пропускная способность дается явной формулой.
Пропускная способность графа путей P n на n вершинах равна 1, а для полного графа K m мы имеем. Для полного двудольного графа K m , n ,
- , предполагая
что было доказано Хваталем. [3] Как частный случай этой формулы, звездный граф на k + 1 вершинах имеет пропускную способность.
Для графа гиперкуба на вершин, ширина полосы была определена Харпером (1966) как
Хваталова показала [4], что ширина полосы графа с квадратной сеткой m × n , то есть декартово произведение двух графов путей на а также вершин, равно min { m , n }.
Границы
Пропускная способность графа может быть ограничена с точки зрения различных других параметров графа. Например, обозначая χ ( G ) хроматическое число группы G ,
обозначая диаметр группы G через diam ( G ) , выполняются следующие неравенства: [5]
где количество вершин в .
Если граф G имеет пропускную способность k , то его ширина пути не больше k ( Kaplan & Shamir 1996 ), а его глубина дерева не больше k log ( n / k ) ( Gruber 2012 ). Напротив, как отмечалось в предыдущем разделе, звездный граф S k , структурно очень простой пример дерева , имеет сравнительно большую пропускную способность. Заметим , что pathwidth из S к 1, и его дерево-глубина 2.
Некоторые семейства графов ограниченной степени имеют сублинейную ширину полосы: Чанг (1988) доказал, что если T - дерево максимальной степени не выше ∆, то
В более общем смысле, для плоских графов с ограниченной максимальной степенью не выше ∆ выполняется аналогичная оценка (см. Böttcher et al. 2010 ):
Расчет пропускной способности
И невзвешенная, и взвешенная версии являются частными случаями квадратичной задачи о назначении узких мест . Проблема с пропускной способностью NP-сложна даже для некоторых особых случаев. [6] Что касается существования эффективных алгоритмов аппроксимации , известно, что полосу пропускания NP-трудно аппроксимировать в пределах любой константы, и это справедливо даже тогда, когда входные графы ограничены деревьями гусениц с максимальной длиной волоса 2 ( Dubey, Feige & Унгер 2010 ). Для случая плотных графов алгоритм 3-аппроксимации был разработан Karpinski, Wirtgen & Zelikovsky (1997) . С другой стороны, известен ряд полиномиально разрешимых частных случаев. [2] эвристический алгоритм для получения линейных макетов графика низкой пропускной способности является алгоритмом Cuthill-Макка . Быстрый многоуровневый алгоритм вычисления пропускной способности графа был предложен в [7].
Приложения
Интерес к этой проблеме исходит из некоторых прикладных областей.
Одной из областей является обработка разреженных матриц / полосных матриц , и общие алгоритмы из этой области, такие как алгоритм Катхилла – Макки , могут применяться для поиска приближенных решений проблемы ширины полосы графа.
Еще одна область применения - автоматизация электронного проектирования . В стандартной методологии проектирования ячеек , как правило, стандартные ячейки имеют одинаковую высоту, а их размещение организовано в несколько рядов. В этом контексте проблема полосы пропускания графа моделирует проблему размещения набора стандартных ячеек в одной строке с целью минимизировать максимальную задержку распространения (которая, как предполагается, пропорциональна длине провода).
Смотрите также
- Pathwidth , другая проблема NP-полной оптимизации, включающая линейные схемы графов.
Рекомендации
- ^ ( Чинн и др., 1982 )
- ^ a b «Как справиться с NP-трудностью проблемы пропускной способности графа», Уриэль Фейдж, Лекционные заметки по информатике , том 1851, 2000, стр. 129-145, ‹См. Tfd› doi : 10.1007 / 3-540-44985 -X_2
- ↑ Замечание по проблеме Харари. В. Хватал, Чехословацкий математический журнал 20 (1): 109–111, 1970. http://dml.cz/dmlcz/100949
- ^ Оптимальная маркировка продукта двух путей. Я. Хваталова, Дискретная математика 11 , 249–253, 1975.
- ^ Чинн и др. 1982 г.
- ^ Garey-Джонсон: GT40
- ^ Илья Сафро и Дорит Рон и Ачи Брандт (2008). «Многоуровневые алгоритмы для задач линейного упорядочения». ACM Journal of Experimental Algorithmics . 13 : 1.4–1.20. DOI : 10.1145 / 1412228.1412232 .
- Böttcher, J .; Pruessmann, КП; Тараз, А .; Вюрфль, А. (2010). «Полоса пропускания, расширение, ширина дерева, разделители и универсальность для графов с ограниченной степенью». Европейский журнал комбинаторики . 31 : 1217–1227. arXiv : 0910.3014 . DOI : 10.1016 / j.ejc.2009.10.010 .
- Чинн, ПЗ ; Chvátalová, J .; Дьюдни, AK ; Гиббс, NE (1982). «Проблема пропускной способности для графиков и матриц - обзор». Журнал теории графов . 6 : 223–254. DOI : 10.1002 / jgt.3190060302 .
- Chung, Fan RK (1988), «Маркировка графиков», в Beineke, Lowell W .; Уилсон, Робин Дж. (Ред.), Избранные темы теории графов (PDF) , Academic Press, стр. 151–168, ISBN 978-0-12-086203-0
- Dubey, C .; Feige, U .; Унгер, В. (2010). «Результаты жесткости для приближения ширины полосы пропускания». Журнал компьютерных и системных наук . 77 : 62–90. DOI : 10.1016 / j.jcss.2010.06.006 .
- Garey, MR ; Джонсон, Д.С. (1979). Компьютеры и непоколебимость: руководство по теории NP-полноты . Нью-Йорк: WH Freeman. ISBN 0-7167-1045-5.
- Грубер, Герман (2012), «Сбалансированные разделители, ширина дерева и ранг цикла», журнал комбинаторики , 3 (4): 669–682, arXiv : 1012.1344 , doi : 10.4310 / joc.2012.v3.n4.a5
- Харпер, Л. (1966). «Оптимальные нумерации и изопериметрические задачи на графах» . Журнал комбинаторной теории . 1 : 385–393. DOI : 10.1016 / S0021-9800 (66) 80059-5 .
- Каплан, Хаим; Шамир, Рон (1996), "Pathwidth, пропускная способность, а также проблемы завершения в соответствующие графы интервалов с малыми кликами", SIAM журнал по вычислениям , 25 (3): 540-561, DOI : 10,1137 / s0097539793258143
- Карпинский, Марек; Виртген, Юрген; Зеликовский, Александр (1997). "Алгоритм аппроксимации проблемы пропускной способности на плотных графах" . Электронный коллоквиум по вычислительной сложности . 4 (17).
Внешние ссылки
- Проблема минимальной пропускной способности , в: Пьерлуиджи Крещенци и Вигго Канн (ред.), Сборник проблем оптимизации NP. Доступ 26 мая 2010 г.