Из Википедии, бесплатной энциклопедии
  (Перенаправлено из Branchwidth )
Перейти к навигации Перейти к поиску
Разбиение ветвей сеточного графа с указанием электронного разделения. Разделение, декомпозиция и граф имеют ширину три.

В теории графов , А ветвь-разложения из неориентированного графа G является иерархической кластеризацией ребер G , представленных в некорневом бинарном дереве T с краями G , как его листьев. Удаление любого ребра из T разбивает ребра G на два подграфа, а ширина разложения равна максимальному количеству общих вершин любой пары подграфов, сформированных таким образом. Branchwidth из G является минимальной шириной любой ветви-разложений G .

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

Определения [ править ]

Некорневое бинарное дерево является связным неориентированным графом без циклов , в которых каждый узел , не имеет листьев ровно три соседей. Разложение по ветвям может быть представлено двоичным деревом T без корня вместе с биекцией между листьями T и ребрами данного графа G  = ( V , E ). Если e - любое ребро дерева T , то удаление e из T разбивает его на два поддерева T 1 и T 2 . Это разбиение Tв поддеревьев индуцирует разбиение ребер , связанных с листьями Т на два подграфа G 1 и G 2 из G . Это разбиение G на два подграфа называется е-разделением .

Ширина e-разделения - это количество вершин графа G , инцидентных как ребру E 1, так и ребру E 2 ; то есть это количество вершин, общих для двух подграфов G 1 и G 2 . Ширина разложения ветвей - это максимальная ширина любого из его электронных разделений. Branchwidth из G является минимальной шириной ответвления-разложений G .

Отношение к ширине дерева [ править ]

Разбиения по ветвям графов тесно связаны с разложениями по деревьям , а ширина ветвей тесно связана с шириной дерева : эти две величины всегда находятся в пределах постоянного множителя друг друга. В частности, в статье, в которой они ввели ширину ветвления, Нил Робертсон и Пол Сеймур [1] показали, что для графа G с шириной дерева k и шириной ветвления b > 1

Ширина резьбы [ править ]

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

Алгоритмы ширины ветвей обычно сводятся к задаче эквивалентной ширины резьбы. В частности, ширина резьбы среднего графа плоского графа ровно в два раза превышает ширину ветвления исходного графа. [2]

Алгоритмы и сложность [ править ]

Это NP-полной , чтобы определить , является ли граф G имеет ветвь-разложение ширины на большей к , когда G и K оба рассматривают как входы к проблеме. [2] Однако графы с шириной ветвления не более k образуют второстепенное замкнутое семейство графов , [3] из которого следует, что вычисление ширины ветвления является управляемым с фиксированным параметром : существует алгоритм для вычисления оптимальных разложений ветвей, выполнение которого Время на графиках ширины ветвления k для любой фиксированной константы k линейно зависит от размера входного графа. [4]

Для плоских графов ширина ветвления может быть вычислена точно за полиномиальное время. Это в отличие от ширины дерева, для которой сложность плоских графов является хорошо известной открытой проблемой. [5] Первоначальный алгоритм плоской ширины ветвления, разработанный Полом Сеймуром и Робином Томасом , занимал время O ( n 2 ) на графах с n вершинами, а их алгоритм построения разложения ветвей этой ширины занимал время O ( n 4 ). [2] Это было позже ускорено до O ( n 3 ). [6]

Как и в случае с древовидной шириной, ширина ветвления может использоваться в качестве основы алгоритмов динамического программирования для многих NP-сложных задач оптимизации, используя количество времени, которое экспоненциально зависит от ширины входного графа или матроида. [7] Например, Кук и Сеймур (2003) применяют динамическое программирование на основе ширины ветвей к проблеме слияния нескольких частичных решений задачи коммивояжера в единое глобальное решение путем формирования разреженного графа из объединения частичных решений, использование эвристики спектральной кластеризации, чтобы найти хорошее разложение по ветвям этого графа, и применение динамического программирования к разложению. Фомин и Тиликос (2006) утверждают, что ширина ветвления работает лучше, чем ширина дерева, при разработке алгоритмов с фиксированными параметрами на плоских графах по нескольким причинам: ширина ветки может быть более жестко ограничена функцией интересующего параметра, чем границы ширины дерева, она может быть вычислена точно в полиномиальное время, а не просто в приближении, и алгоритм его вычисления не имеет больших скрытых констант.

Обобщение на матроиды [ править ]

Также возможно определить понятие разложения по ветвям для матроидов, которое обобщает разложения по ветвям графов. [8] Разложение по ветвям матроида - это иерархическая кластеризация элементов матроида, представленная в виде бинарного дерева без корня с элементами матроида на его листьях. Электронной разделение может быть определено таким же образом , как и для графиков, а также приводит к разбиению множества М из матроидных элементов на два подмножества A и B . Если ρ обозначает ранговую функцию матроида, то ширина e-разделения определяется как ρ ( A ) + ρ ( B ) - ρ ( M ) + 1, аналогично определяются ширина разложения и ветвь матроида. Ширина ветвления графа и ширина ветвления соответствующего графического матроида могут различаться: например, трехреберный граф путей и трехреберная звезда имеют разные ширины ветвления, 2 и 1 соответственно, но оба они индуцируют один и тот же графический матроид с шириной ветвления. 1. [9] Однако для графов, которые не являются деревьями, ширина ветвления графа равна ширине ветвления связанного с ним графического матроида. [10] Ширина ветвления матроида равна ширине ветвления его двойственного матроида., и, в частности, это означает, что ширина ветвления любого плоского графа, не являющегося деревом, равна ширине ветвления его двойственного. [9]

Branchwidth является важным компонентом попыток распространить теорию графов несовершеннолетних к матроидным несовершеннолетним : хотя древесная ширина также может быть обобщена на матроиды, [11] и играет большую роль , чем branchwidth в теории графов миноров, branchwidth имеет более удобные свойства в настройка матроида. [12] Робертсон и Сеймур предположили, что матроиды, представимые над любым конкретным конечным полем , хорошо квазиупорядочены , аналогично теореме Робертсона – Сеймура для графов, но до сих пор это было доказано только для матроидов с ограниченной шириной ветвления. [13]Кроме того, если минорно-замкнутое семейство матроидов, представимых над конечным полем, не включает графические матроиды всех планарных графов, то существует постоянная граница на ширину ветвления матроидов в семействе, обобщая аналогичные результаты для минорно-замкнутого графа. семьи. [14]

Для любой фиксированной константы k матроиды с шириной ветвления не более k могут быть распознаны за полиномиальное время с помощью алгоритма, который имеет доступ к матроиду через оракул независимости . [15]

Запрещенные несовершеннолетние [ править ]

Четыре запрещенных минора для графов с шириной ветвления три.

По теореме Робертсона – Сеймура графы с шириной ветвления k можно охарактеризовать конечным набором запрещенных миноров . Графики ширины разветвления 0 являются сопоставлениями ; минимальные запрещенные миноры - это двухреберный граф путей и треугольный граф (или двухреберный цикл, если рассматриваются мультиграфы, а не простые графы). [16] Графики ширины ветвления 1 - это графики, в которых каждый компонент связности представляет собой звезду ; минимальные запрещенные миноры для ширины ветвления 1 - это треугольный граф (или двухреберный цикл, если рассматриваются мультиграфы, а не простые графы) и трехреберный граф путей. [16]Графики ширины ветвления 2 - это графы, в которых каждый двусвязный компонент является последовательно-параллельным графом ; единственный минимальный запрещенный минор - это полный граф K 4 на четырех вершинах. [16] Граф имеет ширину ветвления три тогда и только тогда, когда он имеет ширину дерева три и не имеет графа куба в качестве второстепенного; следовательно, четыре минимальных запрещенных минора являются тремя из четырех запрещенных миноров для трех ширины дерева (граф октаэдра , полный граф K 5 и граф Вагнера ) вместе с графом куба. [17]

Запрещенные миноры также изучались для ширины ветвления матроида, несмотря на отсутствие в этом случае полного аналога теоремы Робертсона – Сеймура. Матроид имеет ширину ветвления, равную единице, тогда и только тогда, когда каждый элемент является циклом или кольцом, поэтому единственный минимальный запрещенный минор - это однородный матроид U (2,3), графический матроид треугольного графа. Матроид имеет ширину ветвления два тогда и только тогда, когда он является графическим матроидом графа с шириной ветвления два, поэтому его минимальные запрещенные второстепенные элементы являются графическим матроидом K 4.и неграфический матроид U (2,4). Матроиды с шириной ветвления три не являются хорошо квазиупорядоченными без дополнительного предположения о представимости над конечным полем, но, тем не менее, матроиды с любой конечной границей их ширины ветвления имеют конечное число минимальных запрещенных миноров, каждый из которых имеет ряд элементов, не более чем экспоненциально зависит от ширины ветки. [18]

Заметки [ править ]

  1. ↑ Робертсон и Сеймур, 1991 , теорема 5.1, с. 168.
  2. ^ a b c Сеймур и Томас (1994) .
  3. ↑ Робертсон и Сеймур (1991) , теорема 4.1, стр. 164.
  4. ^ Bodlaender & Thilikos (1997) . Fomin, Mazoit & Todinca (2009) описывают алгоритм с улучшенной зависимостью от k , (2 √ 3 ) k , за счет увеличения зависимости от числа вершин с линейной до квадратичной.
  5. Перейти ↑ Kao, Ming-Yang, ed. (2008), «Ширина графов», Энциклопедия алгоритмов , Springer, стр. 969, ISBN 9780387307701, Другая давняя открытая проблема , есть ли полиномиальный алгоритм для вычисления древесной ширины плоских графов.
  6. ^ Гу и Тамаки (2008) .
  7. ^ Хикс (2000) ; Глинены (2003) .
  8. ↑ Робертсон и Сеймур, 1991 . Раздел 12, «Клубки и матроиды», стр. 188–190.
  9. ^ a b Mazoit & Thomassé (2007) .
  10. ^ Mazoit & Thomasse (2007) ; Хикс и МакМюррей (2007) .
  11. ^ Hliněný & Whittle (2006) .
  12. ^ Geelen, Gerards & Виттл (2006) .
  13. ^ Гилен, Джерардс и Уиттл (2002) ; Гилен, Джерардс и Уиттл (2006) .
  14. ^ Гилен, Джерардс и Уиттл (2006) ; Гилен, Джерардс и Уиттл (2007) .
  15. ^ Oum & Seymour (2007) .
  16. ^ a b c Робертсон и Сеймур (1991) , теорема 4.2, с. 165.
  17. ^ Bodlaender & Thilikos (1999) . Четвертый запрещенный минор для ширины дерева три, пятиугольная призма, имеет кубический граф как минор, поэтому он не является минимальным для ширины ветви три.
  18. ^ Холл и др. (2002) ; Geelen et al. (2003) .

Ссылки [ править ]

  • Bodlaender, Hans L .; Тиликос, Димитриос М. (1997), "Конструктивные алгоритмы с линейным временем для определения ширины ветвления", Proc. 24 - й международный коллоквиум автоматного, языки и программирование (ICALP '97) , Lecture Notes в области компьютерных наук, 1256 , Springer-Verlag, стр 627-637,. Дои : 10.1007 / 3-540-63165-8_217 , ЛВП : 2117/96447.
  • Bodlaender, Hans L .; Thilikos, Димитриос М. (1999), "Графы с branchwidth не более трех", журнал алгоритмов , 32 (2): 167-194, DOI : 10,1006 / jagm.1999.1011.
  • Кук, Уильям; Сеймур, Пол Д. (2003), «Слияние туров посредством разложения ветвей» (PDF) , INFORMS Journal on Computing , 15 (3): 233–248, doi : 10.1287 / ijoc.15.3.233.16078.
  • Фомин, Федор В .; Тиликос, Димитриос М. (2006), «Доминирующие множества в плоских графах: ширина ветвления и экспоненциальное ускорение», SIAM Journal on Computing , 36 (2): 281, doi : 10,1137 / S0097539702419649.
  • Фомин, Федор В .; Мазуа, Фредерик; Todinca, Йоан (2009), "Вычисление branchwidth с помощью эффективных триангуляции и блоков" , Дискретный прикладной математики , 157 (12): 2726-2736, DOI : 10.1016 / j.dam.2008.08.009.
  • Гилен, Джим ; Джерардс, Берт; Робертсон, Нил ; Уиттл, Джефф (2003), «Об исключенных минорах для матроидов с шириной ветвления k », Журнал комбинаторной теории, серия B , 88 (2): 261–265, DOI : 10.1016 / S0095-8956 (02) 00046 -1.
  • Гилен, Джим ; Джерардс, Берт; Виттл, Geoff (2002), "Отделение ширина и хорошо квази-упорядочение в матроидах и графиках", Журнал комбинаторной теории, серии B , 84 (2): 270-290, DOI : 10,1006 / jctb.2001.2082.
  • Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2006), "К теории структуры матриц и матроидов" (PDF) , Proc. Международный конгресс математиков , III , стр. 827–842..
  • Гилен, Джим ; Джерардс, Берт; Уиттл, Джефф (2007), «Исключение плоского графа из GF ( q ) -представимых матроидов» (PDF) , Журнал комбинаторной теории, серия B , 97 (6): 971–998, doi : 10.1016 / j.jctb. 2007.02.005 , архивировано из оригинала (PDF) 24.09.2010 CS1 maint: обескураженный параметр ( ссылка ).
  • Гу, Цянь-Пин; Тамаки, Хисао (июль 2008 г.), "Оптимальные ветви разложение плоских графов в O ( п 3 ) время", ACM Сделки по алгоритмам , 4 (3): 30: 1-30: 13, DOI : 10,1145 / 1367064,1367070.
  • Холл, Рианнон; Оксли, Джеймс ; Семпл, Чарльз; Уиттл, Джефф (2002), «О матроидах ширины ветки три», Журнал комбинаторной теории, серия B , 86 (1): 148–171, DOI : 10.1006 / jctb.2002.2120.
  • Хикс, Илья В. (2000), Разбиения ветвей и их приложения , Ph.D. диссертация, Университет Райса, архивировано из оригинала 16 июля 2011 г. , извлечено 06 июля 2010 г..
  • Хикс, Илья В .; Мак - Мюррей, Нолан Б., младший (2007), "О branchwidth графов и их цикл матроиды", Журнал комбинаторной теории, серии B , 97 (5): 681-692, DOI : 10.1016 / j.jctb.2006.12. 007.
  • Hliněný, Петр (2003), "О свойствах матроидов, определяемых в логике MSO", Proc. 28-й Международный симпозиум по математическим основам информатики (MFCS '03) , Lecture Notes in Computer Science, 2747 , Springer-Verlag, pp. 470–479, doi : 10.1007 / 978-3-540-45138-9 \ _41
  • Глинены, Петр; Уиттл, Джефф (2006), "Matroid tree-width" (PDF) , European Journal of Combinatorics , 27 (7): 1117–1128, doi : 10.1016 / j.ejc.2006.06.005 , заархивировано из оригинала (PDF) 06 марта 2012 г. , дата обращения 06 июля 2010..
    • Дополнение и исправление: Hliněný, Petr; Уиттл, Джефф (2009), «Дополнение к ширине дерева матроидов», Европейский журнал комбинаторики , 30 (4): 1036–1044, DOI : 10.1016 / j.ejc.2008.09.028.
  • Мазуа, Фредерик; Томассе, Стефан (2007), «Разветвление графических матроидов», в Хилтоне, Энтони; Талбот, Джон (ред.), Surveys in Combinatorics 2007 (PDF) , Серия лекций Лондонского математического общества, 346 , Cambridge University Press, стр. 275.
  • Оум, Санг-ил ; Сеймура, Пол (2007), "Проверка ветвь ширина", Журнал комбинаторной теории , Series B, 97 (3): 385-393, DOI : 10.1016 / j.jctb.2006.06.006 , МР  2305892.
  • Робертсон, Нил ; Сеймура, Пол Д. (1991), "Graph несовершеннолетнего X. Препятствие к разложению дерева.", Журнал комбинаторной теории , 52 (2): 153-190, DOI : 10.1016 / 0095-8956 (91) 90061-N.
  • Сеймур, Пол Д .; Томас, Робин (1994), "маршрутизации вызовов и крысолов", Combinatorica , 14 (2): 217-241, DOI : 10.1007 / BF01215352.