Диджойн
В математике диджойн — это подмножество ребер ориентированного графа , обладающее свойством, заключающимся в том, что стягивание каждого ребра в диджойне приводит к сильно связному графу . Эквивалентно, диджойн — это подмножество ребер, которое для каждого dicut включает в себя хотя бы одно ребро, пересекающее dicut. Здесь дирез — это разбиение вершин на два подмножества так, что каждое ребро, имеющее концы в обоих подмножествах, направлено из первого подмножества во второе.
Гипотеза Вудалла , нерешенная проблема в этой области, утверждает, что в любом ориентированном графе минимальное количество ребер в дивизионе (невзвешенное минимальное замыкание) равно максимальному количеству непересекающихся дисоединений, которые можно найти в графе (упаковке дисоединений). . [1] [2] Дробно-взвешенная версия гипотезы, выдвинутая Джеком Эдмондсом и Риком Джайлсом, была опровергнута Александром Шрийвером . [3] [4] [1]
Теорема Луккези-Янгера утверждает, что минимальный размер диджойна в любом заданном ориентированном графе равен максимальному количеству непересекающихся двучленов, которые можно найти в графе. [5] [6] Минимальное весовое соединение во взвешенном графе можно найти за полиномиальное время : [7] и является частным случаем задачи субмодулярного течения . [8]
В плоских графах дисоединения и наборы дуг обратной связи являются двойственными понятиями. Двойственный граф ориентированного графа, вложенного в плоскость, — это граф с вершиной для каждой грани данного графа и двойственным ребром между двумя двойственными вершинами, когда соответствующие две грани разделены ребром. Каждое двойное ребро пересекает одно из исходных ребер графа, повернутое на 90° по часовой стрелке. Набор дуг обратной связи — это подмножество ребер, включающее хотя бы одно ребро из каждого направленного цикла. Для диджойна в данном графе соответствующий набор ребер образует направленный разрез в двойственном графе, и наоборот. [9] Эта связь между этими двумя проблемами позволяет эффективно решать проблему множества дуг обратной связи для плоских графов, хотя она NP-трудна . для других типов графов [7]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б Абди, Ахмад; Корнюжоль, Жерар ; Златин, Майкл (2022), Об упаковке дисоединений в орграфах и взвешенных орграфах , arXiv : 2202.00392
- ^ Вудалл, Д.Р. (1978), «Системы Менгера и Кенига», в Алави, Юсеф; Лик, Дон Р. (ред.), Теория и приложения графов (Proc. Internat. Conf., Western Mich. Univ., Каламазу, Мичиган, 1976) , Конспекты лекций по математике, том. 642, Берлин: Springer, стр. 620–635, doi : 10.1007/BFb0070416 , MR 0499529.
- ^ Эдмондс, Джек ; Джайлс, Рик (1977), «Отношение мин-макс для субмодулярных функций на графах», Исследования по целочисленному программированию (Proc. Workshop, Бонн, 1975) , Анналы дискретной математики, том. 1, Северная Голландия, Амстердам, стр. 185–204, MR 0460169.
- ^ Шрийвер, А. (1980), «Контрпример к гипотезе Эдмондса и Джайлза» (PDF) , Discrete Mathematics , 32 (2): 213–215, doi : 10.1016/0012-365X(80)90057-6 , MR 0592858
- ^ Ловас, Ласло (1976), «О двух минимаксных теоремах в графе», Журнал комбинаторной теории , серия B, 21 (2): 96–103, doi : 10.1016/0095-8956(76)90049-6 , MR 0427138
- ^ Луккези, CL; Янгер, Д.Х. (1978), «Теорема о минимаксе для ориентированных графов», Журнал Лондонского математического общества , вторая серия, 17 (3): 369–374, doi : 10.1112/jlms/s2-17.3.369 , MR 0500618
- ^ Перейти обратно: а б Франк, Андраш (1981), «Как сделать орграф сильно связным», Combinatorica , 1 (2): 145–153, doi : 10.1007/BF02579270 , MR 0625547 , S2CID 27825518
- ^ Габоу, Гарольд Н. (1993), «Структура алгоритмов масштабирования стоимости для задач субмодульного потока», Труды 34-го ежегодного симпозиума по основам компьютерных наук (FOCS), Пало-Альто, Калифорния, США, 3-5 ноября 1993 г. , IEEE Computer Society, стр. 449–458, doi : 10.1109/SFCS.1993.366842.
- ^ Габоу, Гарольд Н. (1995), «Центроиды, представления и субмодулярные потоки», Journal of Algorithms , 18 (3): 586–628, doi : 10.1006/jagm.1995.1022 , MR 1334365