Говорят
В математике дивизия — это разбиение вершин ориентированного графа на два подмножества так, что каждое ребро, имеющее концы в обоих подмножествах, направлено от первого подмножества ко второму. Каждый сильно связный компонент графа должен полностью содержаться в одном из двух подмножеств, поэтому в сильно связном графе нет нетривиальных двучленов. [1]
Второе из двух подмножеств в dicut, подмножество вершин без ребер, выходящих из подмножества, называется замыканием. Проблема замыкания — это алгоритмическая задача поиска разреза в ориентированном графе, взвешенном по ребрам, общий вес которого как можно больше. Ее можно решить за полиномиальное время . [2]
В плоских графах директы и циклы являются двойственными понятиями. Двойственный граф ориентированного графа, вложенного в плоскость, — это граф с вершиной для каждой грани данного графа и двойственным ребром между двумя двойственными вершинами, когда соответствующие две грани разделены ребром. Каждое двойное ребро пересекает одно из исходных ребер графа, повернутое на 90° по часовой стрелке. Для двуразреза в данном графе двойственные ребра, пересекающие дивизию, образуют направленный цикл в двойственном графе, и наоборот. [3]
Диджойн ; можно определить как набор ребер, пересекающий все двуразрезы когда ребра дисоединения сжимаются, в результате получается сильно связный граф. Гипотеза Вудалла , нерешенная проблема в этой области, утверждает, что в любом ориентированном графе минимальное количество ребер в дивизионе (невзвешенное минимальное замыкание) равно максимальному количеству непересекающихся дисоединений, которые можно найти в графе (упаковке дисоединений). . [1] [4] Дробно-взвешенная версия гипотезы, выдвинутая Джеком Эдмондсом и Риком Джайлсом, была опровергнута Александром Шрийвером . [5] [6] [1] С другой стороны, теорема Луккези-Янгера утверждает, что минимальный размер диджойна равен максимальному количеству непересекающихся двучленов, которые можно найти в данном графе. [7] [8]
Ссылки
[ редактировать ]- ^ Перейти обратно: а б с Абди, Ахмад; Корнюжоль, Жерар ; Златин, Майкл (2022), Об упаковке дисоединений в орграфах и взвешенных орграфах , arXiv : 2202.00392
- ^ Ахуджа, Равиндра К .; Маньянти, Томас Л .; Орлин, Джеймс Б. (1993), «19.2 Замыкание графа с максимальным весом», Сетевые потоки , Энглвуд Клиффс, Нью-Джерси: Prentice Hall Inc., стр. 719–724, ISBN 0-13-617549-Х , МР 1205775 .
- ^ Ной, Марк (2001), «Ациклические и полностью циклические ориентации в плоских графах», American Mathematical Monthly , 108 (1): 66–68, doi : 10.2307/2695680 , JSTOR 2695680 , MR 1857074 .
- ^ Вудалл, Д.Р. (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), «Контрпример к гипотезе Эдмондса и Джайлза», 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