Обратная связь набор дуг

Ребра, которые попадают во все циклы в графе

Разбиение ориентированного графа на минимальный набор дуг обратной связи (красные пунктирные ребра) и максимальный ациклический подграф (синие сплошные ребра)

В теории графов и графовых алгоритмах набор дуг обратной связи или набор ребер обратной связи в ориентированном графе — это подмножество ребер графа, которое содержит по крайней мере одно ребро из каждого цикла в графе. Удаление этих ребер из графа разрывает все циклы, создавая ациклический подграф данного графа, часто называемый направленным ациклическим графом . Набор дуг обратной связи с наименьшим количеством возможных ребер является минимальным набором дуг обратной связи , и его удаление оставляет максимальный ациклический подграф ; также используются взвешенные версии этих задач оптимизации . Если набор дуг обратной связи минимален, что означает, что удаление любого ребра из него создает подмножество, которое не является набором дуг обратной связи, то он обладает дополнительным свойством: обращение всех его ребер, а не их удаление, создает направленный ациклический граф.

Наборы дуг обратной связи применяются в анализе цепей, химической инженерии , разрешении тупиковых ситуаций , ранжированном голосовании , ранжировании участников спортивных мероприятий, математической психологии , этологии и рисовании графов . Нахождение минимальных наборов дуг обратной связи и максимальных ациклических подграфов является NP-трудной задачей ; ее можно решить точно за экспоненциальное время или за фиксированное параметрически разрешимое время. За полиномиальное время минимальный набор дуг обратной связи можно аппроксимировать с точностью до полилогарифмического аппроксимационного отношения , а максимальные ациклические подграфы можно аппроксимировать с точностью до постоянного множителя. Оба варианта трудно аппроксимировать ближе, чем некоторый постоянный множитель, что является результатом неаппроксимируемости , который может быть усилен в рамках гипотезы уникальных игр . Для турнирных графов минимальный набор дуг обратной связи можно аппроксимировать точнее, а для планарных графов обе задачи можно решить точно за полиномиальное время.

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

Приложения

Результаты мужского пляжного волейбола на Олимпийских играх 2016 года , группа F, и рейтинг минимального количества неудач для этих результатов. Стрелки направлены от проигравшего к победителю каждого матча и окрашены в синий цвет, когда результат соответствует рейтингу, и в красный цвет для неудачи, когда результат не соответствует рейтингу. При таком рейтинге только один матч является неудачей, тот, в котором США обыграли QAT. Фактический рейтинг, используемый на Олимпийских играх, отличался тем, что ESP ставился выше QAT по коэффициенту сетов, в результате чего их матч был оценен как еще один неудачный. ^[1]

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

• В спортивных соревнованиях с круговой системой результаты каждой игры можно записать, направив ребро от проигравшего к победителю каждой игры. Нахождение минимальной дуги обратной связи, установленной в результирующем графе, переворачивание ее ребер и топологическое упорядочение, дает рейтинг всех участников. Среди всех различных способов выбора рейтинга он минимизирует общее количество неудач, игр, в которых участник с более низким рейтингом побеждает участника с более высоким рейтингом. ^{[2] [3] [4]} Во многих видах спорта используются более простые методы для систем рейтинга групповых турниров, основанные на очках, присужденных за каждую игру; ^[5] эти методы могут обеспечить постоянное приближение к рейтингу с минимальными неудачами. ^[6]
• В приматологии и, в более общем плане , в этологии иерархии доминирования часто определяются путем поиска порядка с наименьшим количеством изменений в наблюдаемом поведении доминирования, что является еще одной формой задачи о минимальном наборе дуг обратной связи. ^{[7] [8] [9]}
• В математической психологии представляет интерес определение ранжирования субъектами наборов объектов в соответствии с заданным критерием, таким как их предпочтения или их восприятие размера, на основе попарных сравнений между всеми парами объектов. Минимальный набор дуг обратной связи в турнирном графе обеспечивает ранжирование, которое не согласуется с минимальным количеством парных результатов. ^{[2] [10]} В качестве альтернативы, если эти сравнения приводят к независимым вероятностям для каждого парного упорядочения, то оценка максимального правдоподобия общего ранжирования может быть получена путем преобразования этих вероятностей в логарифмические правдоподобия и нахождения набора дуг обратной связи с минимальным весом в результирующем турнире. ^{[2] [3]}
• Такое же упорядочение по принципу максимального правдоподобия может быть использовано для сериализации , проблемы в статистике и разведочном анализе данных по размещению элементов в линейном порядке, в случаях, когда доступны данные, которые обеспечивают попарные сравнения между элементами. ^{[3] [11] [12]}
• В рейтинговом голосовании метод Кемени –Янга можно описать как поиск порядка, который минимизирует сумму, по парам кандидатов, числа избирателей, которые предпочитают противоположный порядок для этой пары. ^[13] Это можно сформулировать и решить как задачу набора дуг обратной связи с минимальным весом, в которой вершины представляют кандидатов, ребра направлены так, чтобы представлять победителя каждого соревнования лицом к лицу, а стоимость каждого ребра представляет собой число избирателей, которые будут недовольны, если дать более высокий рейтинг проигравшему в состязании лицом к лицу. ^[14]

Другое раннее применение наборов дуг обратной связи касалось проектирования последовательных логических схем, в которых сигналы могут распространяться циклами по схеме вместо того, чтобы всегда прогрессировать от входов к выходам. В таких схемах минимальный набор дуг обратной связи характеризует количество точек, в которых необходимо усиление, чтобы сигналы могли распространяться без потери информации. ^[15] В синхронных схемах , сделанных из асинхронных компонентов, синхронизация может быть достигнута путем размещения тактируемых вентилей на краях набора дуг обратной связи. ^[16] Кроме того, разрезание схемы на наборе дуг обратной связи сводит оставшуюся схему к комбинационной логике , упрощая ее анализ, а размер набора дуг обратной связи контролирует, сколько дополнительного анализа необходимо для понимания поведения схемы через разрез. ^[15] Аналогично, в технологической схеме процесса в химической инженерии разрыв краев диаграммы технологического потока на наборе дуг обратной связи и угадывание или попытка всех возможностей для значений на этих краях позволяет проанализировать остальную часть процесса систематическим образом из-за его ацикличности. В этом приложении идея разрыва краёв таким образом называется «разрыванием». ^[17]

В послойном рисовании графа вершины заданного ориентированного графа разбиваются на упорядоченную последовательность подмножеств (слои рисунка), и каждое подмножество размещается вдоль горизонтальной линии этого рисунка, с ребрами, простирающимися вверх и вниз между этими слоями. В этом типе рисунка желательно, чтобы большинство или все ребра были ориентированы последовательно вниз, а не смешивали восходящие и нисходящие ребра, чтобы отношения достижимости на рисунке были более визуально очевидны. Это достигается путем нахождения минимального или минимального набора дуг обратной связи, обращения ребер в этом наборе и последующего выбора разбиения на слои таким образом, чтобы это соответствовало топологическому порядку результирующего ациклического графа. ^{[18] [19]} Наборы дуг обратной связи также использовались для другой подзадачи послойного рисования графа, упорядочивания вершин в последовательных парах слоев. ^[20]

При разрешении тупиковых ситуаций в операционных системах проблема удаления наименьшего числа зависимостей для выхода из тупиковой ситуации может быть смоделирована как задача поиска минимального набора дуг обратной связи. ^{[21] [22]} Однако из-за вычислительной сложности поиска этого набора и необходимости обеспечения скорости в компонентах операционной системы в этом приложении часто используются эвристики, а не точные алгоритмы. ^[22]

Алгоритмы

Эквивалентности

Минимальный набор дуг обратной связи и максимальный ациклический подграф эквивалентны для целей точной оптимизации, поскольку один является дополнительным набором другого. Однако для параметризованной сложности и аппроксимации они различаются, поскольку анализ, используемый для этих видов алгоритмов, зависит от размера решения, а не только от размера входного графа, а минимальный набор дуг обратной связи и максимальный ациклический подграф имеют разные размеры. ^[23]

Набор дуг обратной связи данного графа совпадает с набором вершин обратной связи направленного линейного графа . Здесь набор вершин обратной связи определяется аналогично набору дуг обратной связи как подмножество вершин графа, удаление которых устранит все циклы. Линейный граф направленного графа имеет вершину для каждого ребра и ребро для каждого двухреберного пути в . В другом направлении минимальный набор вершин обратной связи данного графа может быть получен из решения задачи минимального набора дуг обратной связи на графе, полученном путем разбиения каждой вершины на две вершины, одну для входящих ребер и одну для исходящих ребер. Эти преобразования позволяют преобразовывать точные алгоритмы для наборов дуг обратной связи и для наборов вершин обратной связи друг в друга с соответствующим переводом их границ сложности. Однако это преобразование не сохраняет качество аппроксимации для задачи максимального ациклического подграфа. ^{[21] [24]} ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$

Ориентированный граф с тремя сильно связанными компонентами , самый правый из которых может быть разделен в вершине сочленения на два двусвязных компонента , каждый из которых является циклом из двух вершин. Задача набора дуг обратной связи может быть решена отдельно в каждом сильно связанном компоненте и в каждом двусвязном компоненте сильно связанного компонента. ${\displaystyle d}$

Как в точных, так и в приближенных решениях задачи набора дуг обратной связи достаточно решить по отдельности каждый сильно связанный компонент заданного графа и разбить эти сильно связанные компоненты еще дальше до их двусвязных компонентов , разделив их в вершинах сочленения. Выбор решения в любой из этих подзадач не влияет на другие, и ребра, которые не появляются ни в одном из этих компонентов, бесполезны для включения в набор дуг обратной связи. ^[25] Когда один из этих компонентов может быть разделен на два несвязных подграфа путем удаления двух вершин, применяется более сложная декомпозиция, позволяющая разбить задачу на подзадачи, полученные из трехсвязных компонентов ее сильно связанных компонентов. ^[26]

Точный

Один из способов найти минимальный набор дуг обратной связи — это поиск упорядочения вершин таким образом, чтобы как можно меньше ребер были направлены от более поздних вершин к более ранним вершинам в упорядочении. ^[27] Поиск всех перестановок графа с -вершинами занял бы время , но метод динамического программирования, основанный на алгоритме Хелда–Карпа, может найти оптимальную перестановку за время , также используя экспоненциальное количество пространства. ^{[28] [29]} Алгоритм «разделяй и властвуй» , который проверяет все разбиения вершин на два равных подмножества и рекурсирует внутри каждого подмножества, может решить задачу за время , используя полиномиальное пространство . ^[29] ${\displaystyle n}$ ${\displaystyle O(n!)}$ ${\displaystyle O(n2^{n})}$ ${\displaystyle O(4^{n}/{\sqrt {n}})}$

В параметризованной сложности время алгоритмов измеряется не только с точки зрения размера входного графа, но и с точки зрения отдельного параметра графа. В частности, для задачи минимального набора дуг обратной связи так называемым натуральным параметром является размер минимального набора дуг обратной связи. На графах с вершинами, с натуральным параметром , задача набора дуг обратной связи может быть решена за время , путем преобразования ее в эквивалентную задачу набора вершин обратной связи и применения параметризованного алгоритма набора вершин обратной связи. Поскольку показатель степени в этом алгоритме является константой , независимой от , этот алгоритм называется трактуемым с фиксированным параметром. ^[30] ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle O(n^{4}4^{k}k^{3}k!)}$ ${\displaystyle n}$ ${\displaystyle 4}$ ${\displaystyle k}$

Также были изучены другие параметры, помимо натурального параметра. Алгоритм с фиксированными параметрами, использующий динамическое программирование, может найти минимальные наборы дуг обратной связи за время , ${\displaystyle O(2^{r}m^{4}\log m)}$ где — ранг схемы базового неориентированного графа. Ранг схемы — это неориентированный аналог набора дуг обратной связи, минимальное количество ребер, которые необходимо удалить из связного графа, чтобы свести его к остовному дереву ; его гораздо проще вычислить, чем минимальный набор дуг обратной связи. ^[24] Для графов с древовидной шириной динамическое программирование на древовидной декомпозиции графа может найти минимальный набор дуг обратной связи за время, полиномиальное по размеру графа и экспоненциальное по . Согласно гипотезе экспоненциального времени , лучшей зависимости от не существует. ^[31] ${\displaystyle r}$ ${\displaystyle t}$ ${\displaystyle O(t\log t)}$ ${\displaystyle t}$

Вместо минимизации размера набора дуг обратной связи исследователи также рассматривали минимизацию максимального количества ребер, удаленных из любой вершины. Этот вариант задачи может быть решен за линейное время . ^[32] Все минимальные наборы дуг обратной связи могут быть перечислены алгоритмом с полиномиальной задержкой на набор. ^[33]

Приблизительно

Нерешенная задача по математике :

Имеет ли задача набора дуг обратной связи алгоритм аппроксимации с постоянным коэффициентом аппроксимации?

(еще нерешенные проблемы по математике)

Самый известный полиномиальный алгоритм аппроксимации для набора дуг обратной связи имеет непостоянное отношение аппроксимации . Это означает, что размер набора дуг обратной связи, который он находит, не превышает этого коэффициента, превышающего оптимум. ^[21] Определение того, имеет ли набор дуг обратной связи алгоритм аппроксимации с постоянным отношением или необходимо непостоянное отношение, остается открытой проблемой. ^[34] ${\displaystyle O(\log n\log \log n)}$

Задача о максимальном ациклическом подграфе имеет простой алгоритм аппроксимации, который достигает коэффициента аппроксимации : ${\displaystyle {\tfrac {1}{2}}}$

• Зафиксировать произвольный порядок вершин
• Разобьем ребра на два ациклических подграфа, один из которых будет состоять из ребер, направленных в соответствии с порядком, а другой — из ребер, направленных в противоположном направлении порядку.
• Верните больший из двух подграфов.

Это можно улучшить, используя жадный алгоритм для выбора порядка. Этот алгоритм находит и удаляет вершину, числа входящих и исходящих ребер которой максимально удалены друг от друга, рекурсивно упорядочивает оставшийся граф, а затем помещает удаленную вершину в один конец полученного порядка. Для графов с ребрами и вершинами это создает ациклический подграф с ребрами за линейное время, давая отношение аппроксимации . [ ^35] Другой, более сложный, алгоритм аппроксимации с полиномиальным временем применяется к графам с максимальной степенью и находит ациклический подграф с ребрами, давая отношение аппроксимации вида . [ ^{36] [37]} Когда , отношение аппроксимации может быть достигнуто. ^[38] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m/2+n/6}$ ${\displaystyle {\tfrac {1}{2}}+\Omega (n/m)}$ ${\displaystyle \Delta }$ ${\displaystyle m/2+\Omega (m/{\sqrt {\Delta }})}$ ${\displaystyle {\tfrac {1}{2}}+\Omega (1/{\sqrt {\Delta }})}$ ${\displaystyle \Delta =3}$ ${\displaystyle 8/9}$

Ограниченные входы

В ориентированных планарных графах задача набора дуг обратной связи является двойственной к задаче сжатия набора ребер (дисоединения ) , чтобы сделать полученный граф сильно связным . ^[39] Эта двойственная задача полиномиально разрешима, ^[40] и, следовательно, планарная задача минимального набора дуг обратной связи также является разрешимой. ^{[41] [40]} Она может быть решена за время . ^[42] ${\displaystyle O(n^{5/2}\log n)}$ Взвешенная версия задачи может быть решена за время , ^[39] ${\displaystyle O(n^{3})}$ или, когда веса являются положительными целыми числами, которые не превышают число , за ${\displaystyle N}$ время . [ ^42] ${\displaystyle O(n^{5/2}\log nN)}$ Эти планарные алгоритмы могут быть расширены на графы, которые не имеют графа полезности в качестве минора графа , используя тот факт, что трисвязные компоненты этих графов являются либо планарными, либо имеют ограниченный размер. ^[26] Планарные графы также были обобщены другим способом до класса ориентированных графов, называемых слабо ациклическими орграфами , определяемыми целочисленностью определенного многогранника , связанного с их наборами дуг обратной связи . Каждый плоский ориентированный граф слабо ацикличен в этом смысле, и задача набора дуг обратной связи может быть решена за полиномиальное время для всех слабо ациклических орграфов. ^[43] ${\displaystyle K_{3,3}}$

Сокращаемые потоковые графы — это еще один класс направленных графов, на которых проблема набора дуг обратной связи может быть решена за полиномиальное время. Эти графы описывают поток управления в структурированных программах для многих языков программирования. Хотя структурированные программы часто производят планарные направленные потоковые графы, определение сводимости не требует, чтобы граф был планарным. ^[44]

Когда задача минимального набора дуг обратной связи ограничена турнирами , она имеет схему аппроксимации с полиномиальным временем , которая обобщается до взвешенной версии задачи. ^[45] Также известен субэкспоненциальный параметризованный алгоритм для взвешенных наборов дуг обратной связи на турнирах. ^[14] Задача максимального ациклического подграфа для плотных графов также имеет схему аппроксимации с полиномиальным временем. Ее основные идеи заключаются в применении рандомизированного округления к линейно-программируемой релаксации задачи и в дерандомизации полученного алгоритма с использованием обходов на графах-расширителях . ^{[34] [46]}

Твёрдость

NP-твердость

Редукция NP -полноты Карпа и Лоулера от вершинного покрытия большого желтого графа до минимального набора дуг обратной связи в малом синем графе расширяет каждую желтую вершину до двух смежных вершин синего графа, а каждое неориентированное желтое ребро — до двух противоположно направленных ребер. Минимальное вершинное покрытие (верхняя левая и нижняя правая желтые вершины) соответствует красному минимальному набору дуг обратной связи.

Чтобы применить теорию NP-полноты к минимальному набору дуг обратной связи, необходимо изменить задачу с задачи оптимизации (сколько ребер можно удалить, чтобы разорвать все циклы) на эквивалентную версию решения с ответом «да» или «нет» (возможно ли удалить ребра). Таким образом, версия решения задачи набора дуг обратной связи принимает в качестве входных данных как ориентированный граф, так и число . Она спрашивает, можно ли разорвать все циклы, удалив не более ребер, или, что эквивалентно, существует ли ациклический подграф с не менее чем ребрами. Эта задача является NP-полной , что подразумевает, что ни она, ни задача оптимизации не должны иметь полиномиальных алгоритмов. Это была одна из 21 исходной NP-полной задачи Ричарда М. Карпа ; ее NP-полнота была доказана Карпом и Юджином Лоулером , показав, что входные данные для другой сложной задачи, задачи покрытия вершин , могут быть преобразованы («сокращены») в эквивалентные входные данные для задачи решения набора дуг обратной связи. ^{[47] [48]} ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle |E(G)|-k}$

Некоторые NP-полные проблемы могут стать проще, если их входные данные ограничены особыми случаями. Но для самого важного особого случая проблемы набора дуг обратной связи, случая турниров, проблема остается NP-полной. ^{[49] [50]}

Неприблизимость

Класс сложности APX определяется как состоящий из задач оптимизации, имеющих полиномиальный алгоритм аппроксимации, который достигает постоянного коэффициента аппроксимации . Хотя такие аппроксимации неизвестны для задачи набора дуг обратной связи, известно, что задача является APX-трудной , что означает, что точные аппроксимации для нее могут быть использованы для достижения аналогичных точных аппроксимаций для всех других задач в APX. Как следствие ее доказательства сложности, если только P = NP , она не имеет полиномиального коэффициента аппроксимации времени лучше 1,3606. Это тот же самый порог для сложности аппроксимации, который известен для покрытия вершин, и доказательство использует редукцию Карпа–Лоулера от покрытия вершин до набора дуг обратной связи, что сохраняет качество аппроксимаций. ^{[34] [51] [52] [53]} С помощью другого сокращения задача максимального ациклического подграфа также является APX-трудной и NP-трудной для аппроксимации с точностью до множителя 65/66 от оптимального. ^[38]

Трудность аппроксимации этих задач также изучалась при недоказанных предположениях о вычислительной сложности , которые являются стандартными в теории вычислительной сложности, но сильнее, чем P ≠ NP. Если гипотеза уникальных игр верна, то задачу минимального набора дуг обратной связи трудно аппроксимировать за полиномиальное время с точностью до любого постоянного множителя, а задачу максимального набора дуг обратной связи трудно аппроксимировать с точностью до множителя , для ${\displaystyle {\tfrac {1}{2}}+\varepsilon }$ каждого . ^[54] Помимо полиномиального времени для алгоритмов аппроксимации, если гипотеза экспоненциального времени верна, то для каждого минимального набора дуг обратной связи не существует ${\displaystyle \varepsilon >0}$ аппроксимации с точностью до множителя , который можно вычислить за субэкспоненциальное время . ^[55] ${\displaystyle \varepsilon >0}$ ${\displaystyle {\tfrac {7}{6}}-\varepsilon }$ ${\displaystyle O(2^{n^{1-\varepsilon }})}$

Теория

В плоских ориентированных графах задача набора дуг обратной связи подчиняется теореме минимума-максимума : минимальный размер набора дуг обратной связи равен максимальному числу непересекающихся по ребрам направленных циклов, которые можно найти в графе. ^{[41] [56]} Это неверно для некоторых других графов; например, на первой иллюстрации показана направленная версия неплоского графа , в которой минимальный размер набора дуг обратной связи равен двум, тогда как максимальное число непересекающихся по ребрам направленных циклов равно только одному. ${\displaystyle K_{3,3}}$

Каждый турнирный граф имеет гамильтонов путь , и гамильтоновы пути соответствуют один к одному с минимальными наборами дуг обратной связи, не пересекающимися с соответствующим путем. Гамильтонов путь для набора дуг обратной связи находится путем обращения его дуг и нахождения топологического порядка полученного ациклического турнира. Каждая последовательная пара порядка должна быть не пересекающейся с наборами дуг обратной связи, потому что в противном случае можно было бы найти меньший набор дуг обратной связи, обращая эту пару. Следовательно, этот порядок дает путь через дуги исходного турнира, покрывающий все вершины. Наоборот, из любого гамильтонова пути набор ребер, которые соединяют более поздние вершины в пути с более ранними, образует набор дуг обратной связи. Он минимален, потому что каждое из его ребер принадлежит циклу с ребрами гамильтонова пути, который не пересекается со всеми другими такими циклами. ^[57] В турнире может быть так, что минимальный набор дуг обратной связи и максимальный ациклический подграф оба близки к половине ребер. Точнее, каждый турнирный граф имеет набор дуг обратной связи размера , а некоторые турниры требуют размера . ^[58] Для почти всех турниров размер составляет не менее . ^[59] Каждый направленный ациклический граф может быть встроен как подграф большего турнирного графа таким образом, что является уникальным минимальным набором дуг обратной связи турнира. Размер этого турнира был определен как «реверсивное число» , и среди направленных ациклических графов с тем же числом вершин он является наибольшим, когда сам является (ациклическим) турниром. ^{[60] [61]} ${\displaystyle {\tbinom {n}{2}}/2-\Omega (n^{3/2})}$ ${\displaystyle {\tbinom {n}{2}}/2-O(n^{3/2})}$ ${\displaystyle {\tbinom {n}{2}}/2-1.73n^{3/2}}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle D}$

Направленный граф имеет эйлеров цикл всякий раз, когда он сильно связан и каждая вершина имеет равное количество входящих и исходящих ребер. Для такого графа с ребрами и вершинами размер минимального набора дуг обратной связи всегда не менее . Существует бесконечно много эйлеровых направленных графов, для которых эта граница узка. ^[62] Если направленный граф имеет вершины, не более трех ребер на вершину, то он имеет набор дуг обратной связи не более чем из ребер, и некоторые графы требуют именно этого количества. Если направленный граф имеет ребра, не более четырех ребер на вершину, то он имеет набор дуг обратной связи не более чем из ребер, и некоторые графы требуют именно этого количества. ^[63] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle (m^{2}+mn)/2n^{2}}$ ${\displaystyle n}$ ${\displaystyle n/3}$ ${\displaystyle m}$ ${\displaystyle m/3}$

Ссылки

1. "Основная сетка – Мужчины", Рио-2016 , Fédération Internationale de Volleyball , заархивировано из оригинала 2016-12-23 , извлечено 2021-11-14
2. Хьюберт, Лоуренс (1976), «Сериация с использованием асимметричных мер близости», Британский журнал математической и статистической психологии , 29 (1): 32–52, doi :10.1111/j.2044-8317.1976.tb00701.x, MR  0429180
3. Ремейдж, Рассел-младший; Томпсон, WA-младший (1966), «Рейтинги парных сравнений с максимальным правдоподобием», Biometrika , 53 (1–2): 143–149, doi :10.1093/biomet/53.1-2.143, JSTOR  2334060, MR  0196854, PMID  5964054
4. Годдард, Стивен Т. (1983), «Рейтинг в турнирах и групповое принятие решений», Management Science , 29 (12): 1384–1392, doi :10.1287/mnsc.29.12.1384, MR  0809110; обратите внимание, что алгоритм, предложенный Годдардом для поиска рейтингов с минимальным количеством нарушений, неверен
5. Вазири, Бабак; Дабадгао, Шаунак; Йих, Юехверн; Морин, Томас Л. (январь 2018 г.), «Свойства методов спортивного ранжирования» (PDF) , Журнал Общества операционных исследований , 69 (5): 776–787, doi :10.1057/s41274-017-0266-8, S2CID  51887586
6. Копперсмит, Дон ; Флейшер, Лиза К.; Рурда, Атри (2010), «Упорядочение по взвешенному числу побед дает хороший рейтинг для взвешенных турниров», ACM Transactions on Algorithms , 6 (3): A55:1–A55:13, doi :10.1145/1798596.1798608, MR  2682624, S2CID  18416
7. Сейфарт, Роберт М. (ноябрь 1976 г.), «Социальные отношения среди взрослых самок бабуинов», Animal Behaviour , 24 (4): 917–938, doi :10.1016/s0003-3472(76)80022-x, S2CID  54284406
8. Эстеп, Д.К.; Кроуэлл-Дэвис, С.Л.; Эрл-Костелло, С.-А.; Бити, С.А. (январь 1993 г.), «Изменения в социальном поведении кобыл тяжеловозных лошадей (Equus caballus), совпадающие с выжеребкой», Applied Animal Behaviour Science , 35 (3): 199–213, doi :10.1016/0168-1591(93)90137-e
9. Эйкворт, Джордж К. (апрель 2019 г.), «Доминирование у таракана (Nauphoeta)», Insect Behavior , CRC Press, стр. 120–126, doi :10.1201/9780429049262-18, ISBN 978-0-429-04926-2, S2CID  203898549
10. Слейтер, Патрик (1961), «Несоответствия в графике парных сравнений», Biometrika , 48 (3–4): 303–312, doi :10.1093/biomet/48.3-4.303, JSTOR  2332752
11. Бранк, HD (1960), «Математические модели для ранжирования на основе парных сравнений», Журнал Американской статистической ассоциации , 55 (291): 503–520, doi : 10.2307/2281911, JSTOR  2281911, MR  0115242; опубликовано в предварительной форме как документ ASTIA № AD 206 573, ВВС США, Управление научных исследований, ноябрь 1958 г., hdl : 2027/mdp.39015095254010
12. Томпсон, WA Jr.; Ремейдж, Рассел Jr. (1964), «Ранжирование по парным сравнениям», Annals of Mathematical Statistics , 35 (2): 739–747, doi : 10.1214/aoms/1177703572 , JSTOR  2238526, MR  0161419
13. Кемени, Джон Г. (осень 1959 г.), «Математика без чисел», Daedalus , 88 (4): 577–591, JSTOR  20026529
14. Karpinski, Marek ; Schudy, Warren (2010), "Быстрые алгоритмы для турнира по набору дуг обратной связи, агрегации рангов Кемени и турнира по промежуточности", в Cheong, Otfried ; Chwa, Kyung-Yong; Park, Kunsoo (ред.), Алгоритмы и вычисления - 21-й международный симпозиум, ISAAC 2010, остров Чеджудо, Корея, 15-17 декабря 2010 г., Труды, часть I , Lecture Notes in Computer Science, т. 6506, Springer, стр. 3–14, arXiv : 1006.4396 , doi :10.1007/978-3-642-17517-6_3, ISBN 978-3-642-17516-9, S2CID  16512997
15. Unger, Stephen H. (26 апреля 1957 г.), Исследование асинхронных логических сетей обратной связи , Технические отчеты, т. 320, Массачусетский технологический институт, Исследовательская лаборатория электроники, hdl :1721.1/4763
16. Feehrer, John R.; Jordan, Harry F. (декабрь 1995 г.), «Размещение тактовых затворов в оптоэлектронных схемах с измерением времени пролета», Applied Optics , 34 (35): 8125–8136, Bibcode : 1995ApOpt..34.8125F, doi : 10.1364/ao.34.008125, PMID  21068927
17. Rosen, Edward M.; Henley, Ernest J. (лето 1968 г.), «Новая стехиометрия», Chemical Engineering Education , 2 (3): 120–125, архивировано из оригинала 2021-08-02 , извлечено 2021-08-02
18. Ди Баттиста, Джузеппе; Идс, Питер ; Тамассиа, Роберто ; Толлис, Иоаннис Г. (1998), «Слоистые рисунки орграфов», Рисование графов: алгоритмы визуализации графов , Prentice Hall , стр. 265–302, ISBN 978-0-13-301615-4
19. Бастерт, Оливер; Матушевски, Кристиан (2001), «Слоистые рисунки орграфов», в Кауфманн, Михаэль; Вагнер, Доротея (ред.), Рисование графов: методы и модели , Lecture Notes in Computer Science, т. 2025, Springer-Verlag, стр. 87–120, doi :10.1007/3-540-44969-8_5, ISBN 978-3-540-42062-0
20. Деметреску, Камил; Финокки, Ирен (2001), «Разрушьте «правильные» циклы и получите «лучший» рисунок», ACM Journal of Experimental Algorithmics , 6 : 171–182, MR  2027115
21. Even, G.; Naor, J .; Schieber, B .; Sudan, M. (1998), «Аппроксимация минимальных наборов обратной связи и мультиразрезов в ориентированных графах», Algorithmica , 20 (2): 151–174, doi :10.1007/PL00009191, MR  1484534, S2CID  2437790
22. Minoura, Toshimi (1982), «Повторный взгляд на избежание тупиковых ситуаций», Journal of the ACM , 29 (4): 1023–1048, doi : 10.1145/322344.322351 , MR  0674256, S2CID  5284738
23. Мишра, Соунака; Сикдар, Крипасиндху (2004), «Об аппроксимируемости линейного порядка и связанных с ним задачах NP-оптимизации на графах», Дискретная прикладная математика , 136 (2–3): 249–269, doi :10.1016/S0166-218X(03)00444-X, MR  2045215
24. Хехт, Майкл (2017), «Точные локализации наборов обратной связи», Теория вычислительных систем , 62 (5): 1048–1084, arXiv : 1702.07612 , doi : 10.1007/s00224-017-9777-6, S2CID  18394348
25. Парк, С.; Акерс, С.Б. (1992), «Эффективный метод поиска минимального набора дуг обратной связи в ориентированных графах», Труды Международного симпозиума IEEE 1992 года по схемам и системам (ISCAS '92) , т. 4, стр. 1863–1866, doi :10.1109/iscas.1992.230449, ISBN 0-7803-0593-0, S2CID  122603659
26. Nutov, Zeev; Penn, Michal (2000), «О целостности, устойчивости и составе дициклических упаковок и покрытий», Journal of Combinatori Optimization , 4 (2): 235–251, doi :10.1023/A:1009802905533, MR  1772828, S2CID  207632524
27. Younger, D. (1963), «Минимальные наборы дуг обратной связи для направленного графа», IEEE Transactions on Circuit Theory , 10 (2): 238–245, doi :10.1109/tct.1963.1082116
28. Лоулер, Э. (1964), «Комментарий к минимальным наборам дуг обратной связи», IEEE Transactions on Circuit Theory , 11 (2): 296–297, doi :10.1109/tct.1964.1082291
29. Bodlaender, Hans L .; Fomin, Fedor V.; Koster, Arie MCA; Kratsch, Dieter; Thilikos, Dimitrios M. (2012), "Заметка о точных алгоритмах для задач упорядочения вершин на графах", Теория вычислительных систем , 50 (3): 420–432, doi :10.1007/s00224-011-9312-0, hdl : 1956/4556 , MR  2885638, S2CID  9967521
30. Чэнь, Цзяньэр; Лю, Ян; Лу, Сунцзянь; О'Салливан, Барри; Разгон, Игорь (2008), «Алгоритм с фиксированными параметрами для задачи направленной обратной связи о множестве вершин», Журнал ACM , 55 (5): 1–19, doi :10.1145/1411509.1411511, S2CID  1547510
31. Бонами, Марте; Ковалик, Лукаш; Недерлоф, Йеспер; Пилипчук, Михал; Сокала, Аркадиуш; Врохна, Марцин (2018), «О направленном наборе вершин обратной связи, параметризованном шириной дерева», в Брандштедт, Андреас; Кёлер, Эккехард; Меер, Клаус (ред.), Графовые концепции в информатике - 44-й международный семинар, WG 2018, Котбус, Германия, 27-29 июня 2018 г., Труды , заметки лекций по информатике, т. 11159, Springer, стр. 65–78, arXiv : 1707.01470 , doi :10.1007/978-3-030-00256-5_6, ISBN 978-3-030-00255-8, S2CID  8008855
32. Лин, Лишин; Сахни, Сартай (1989), «Проблемы удаления справедливых границ», IEEE Transactions on Computers , 38 (5): 756–761, doi :10.1109/12.24280, MR  0994519
33. Швиковски, Бенно; Спекенмейер, Эвальд (2002), «О перечислении всех минимальных решений задач обратной связи», Дискретная прикладная математика , 117 (1–3): 253–265, doi : 10.1016/S0166-218X(00)00339-5 , MR  1881280
34. Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek ; Woeginger, Gerhard (2000), "Minimum Feedback Arc Set", Сборник задач оптимизации NP , архивировано из оригинала 29.07.2021 , извлечено 29.07.2021
35. Eades, Peter ; Lin, Xuemin; Smyth, WF (1993), «Быстрая и эффективная эвристика для задачи набора дуг обратной связи», Information Processing Letters , 47 (6): 319–323, doi :10.1016/0020-0190(93)90079-O, MR  1256786, архивировано из оригинала 22.10.2020 , извлечено 01.08.2021
36. Бергер, Бонни ; Шор, Питер В. (1997), «Жесткие границы для задачи максимального ациклического подграфа», Журнал алгоритмов , 25 (1): 1–18, doi :10.1006/jagm.1997.0864, ​​MR  1474592
37. Хассин, Рефаэль; Рубинштейн, Шломи (1994), «Приближения для задачи максимального ациклического подграфа», Information Processing Letters , 51 (3): 133–140, doi :10.1016/0020-0190(94)00086-7, MR  1290207
38. Newman, Alantha (июнь 2000 г.), Аппроксимация максимального ациклического подграфа (магистерская диссертация), Массачусетский технологический институт, hdl :1721.1/86548, как цитируют Гурусвами и др. (2011)
39. Gabow, Harold N. (1995), «Центроиды, представления и субмодулярные потоки», Журнал алгоритмов , 18 (3): 586–628, doi :10.1006/jagm.1995.1022, MR  1334365
40. Frank, András (1981), «Как сделать орграф сильно связанным», Combinatorica , 1 (2): 145–153, doi :10.1007/BF02579270, MR  0625547, S2CID  27825518
41. Lucchesi, CL; Younger, DH (1978), "Теорема о минимаксе для ориентированных графов", Журнал Лондонского математического общества , Вторая серия, 17 (3): 369–374, doi :10.1112/jlms/s2-17.3.369, MR  0500618
42. Gabow, Harold N. (1993), "Структура алгоритмов масштабирования стоимости для задач субмодулярного потока", 34-й ежегодный симпозиум по основам компьютерной науки, Пало-Альто, Калифорния, США, 3-5 ноября 1993 г. , IEEE Computer Society, стр. 449–458, doi :10.1109/SFCS.1993.366842, ISBN 0-8186-4370-6, MR  1328441, S2CID  32162097
43. Грётшель, Мартин ; Юнгер, Михаэль; Райнельт, Герхард (1985), «О ациклическом подграфовом политопе», Математическое программирование , 33 (1): 28–42, doi :10.1007/BF01582009, MR  0809747, S2CID  206798683
44. Рамачандран, Виджая (1988), «Поиск минимального набора дуг обратной связи в приводимых потоковых графах», Журнал алгоритмов , 9 (3): 299–313, doi :10.1016/0196-6774(88)90022-3, MR  0955140
45. Кеньон-Матье, Клэр ; Шуди, Уоррен (2007), «Как ранжировать с небольшим количеством ошибок: PTAS для дуги взвешенной обратной связи, установленной на турнирах», в Джонсон, Дэвид С.; Фейдж , Уриэль (ред.), Труды 39-го ежегодного симпозиума ACM по теории вычислений, Сан-Диего, Калифорния, США, 11-13 июня 2007 г. , стр. 95–103, doi : 10.1145/1250790.1250806, S2CID  9436948, ECCC  TR06-144; см. также расширенную версию автора. Архивировано 15.01.2009 на Wayback Machine
46. Арора, Санджив ; Фриз, Алан ; Каплан, Хаим (2002), «Новая процедура округления для задачи назначения с приложениями к проблемам размещения плотных графов», Математическое программирование , 92 (1): 1–36, doi :10.1007/s101070100271, MR  1892295, S2CID  3207086, заархивировано из оригинала 2021-08-03 , извлечено 2021-08-03
47. Карп, Ричард М. (1972), «Сводимость среди комбинаторных задач», Сложность компьютерных вычислений , Труды симпозиума. IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, Нью-Йорк: Пленум, стр. 85–103
48. Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), "A1.1: GT8", Компьютеры и неразрешимость: Руководство по теории NP-полноты , WH Freeman, стр. 192, ISBN 0-7167-1045-5
49. Алон, Нога (2006), «Рейтинговые турниры», SIAM Journal on Discrete Mathematics , 20 (1): 137–142, doi :10.1137/050623905, MR  2257251
50. Charbit, Pierre; Thomassé, Stéphan; Yeo, Anders (2007), «Проблема минимального набора дуг обратной связи является NP-трудной для турниров» (PDF) , Combinatorics, Probability and Computing , 16 (1): 1–4, doi :10.1017/S0963548306007887 (неактивен 1 ноября 2024 г.), MR  2282830, S2CID  36539840{{citation}}: CS1 maint: DOI неактивен по состоянию на ноябрь 2024 г. ( ссылка )
51. Ausiello, G .; D'Atri, A.; Protasi, M. (1980), "Структурно-сохраняющие сокращения среди задач выпуклой оптимизации", Журнал компьютерных и системных наук , 21 (1): 136–153, doi :10.1016/0022-0000(80)90046-X, MR  0589808
52. Канн, Вигго (1992), Об аппроксимируемости NP-полных задач оптимизации (PDF) (диссертация на соискание степени доктора философии), Кафедра численного анализа и вычислительной техники, Королевский технологический институт, Стокгольм, архивировано (PDF) из оригинала 29.12.2010 , извлечено 11.10.2007
53. Динур, Ирит ; Сафра, Самуэль (2005), «О сложности аппроксимации минимального покрытия вершин» (PDF) , Annals of Mathematics , 162 (1): 439–485, doi : 10.4007/annals.2005.162.439 , заархивировано (PDF) из оригинала 20 сентября 2009 г. , извлечено 29 июля 2021 г.; предварительная версия в Dinur, Irit ; Safra, Samuel (2002), "The important of being biased", в Reif, John H. (ed.), Proceedings of the 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada , стр. 33–42, doi :10.1145/509907.509915, ISBN 1-58113-495-9, S2CID  1235048
54. Guruswami, Venkatesan ; Håstad, Johan ; Manokaran, Rajsekar; Raghavendra, Prasad; Charikar, Moses (2011), «Beating the random ordering is hard: every ordering CSP is approximation resist» (PDF) , SIAM Journal on Computing , 40 (3): 878–914, doi :10.1137/090756144, MR  2823511, архивировано (PDF) из оригинала 2021-07-31 , извлечено 2021-07-31
55. Бонне, Эдуард; Пашос, Вангелис Т. (2018), «Разрежение и субэкспоненциальное приближение», Acta Informatica , 55 (1): 1–15, arXiv : 1402.2843 , doi : 10.1007/s00236-016-0281-2, MR  3757549, S2CID  3136275
56. Ловас, Ласло (1976), «О двух теоремах о минимаксе в графе», Журнал комбинаторной теории , Серия B, 21 (2): 96–103, doi : 10.1016/0095-8956(76)90049-6 , MR  0427138
57. Бар-Ной, Амоц; Наор, Джозеф (1990), «Сортировка, минимальные наборы обратной связи и пути Гамильтона в турнирах», SIAM Journal on Discrete Mathematics , 3 (1): 7–20, doi :10.1137/0403002, MR  1033709
58. Спенсер, Дж. (1980), «Оптимальное ранжирование неранжируемых турниров», Periodica Mathematica Hungarica , 11 (2): 131–144, doi :10.1007/BF02017965, MR  0573525, S2CID  119894999
59. Фернандес де ла Вега, В. (1983), «О максимальной мощности последовательного набора дуг в случайном турнире», Журнал комбинаторной теории , Серия B, 35 (3): 328–332, doi : 10.1016/0095-8956(83)90060-6 , MR  0735201
60. Бартелеми, Жан-Пьер; Юдри, Оливье; Айзек, Гарт; Робертс, Фред С.; Тесман, Барри (1995), «Обратное число орграфа», Discrete Applied Mathematics , 60 (1–3): 39–76, doi :10.1016/0166-218X(94)00042-C, MR  1339075
61. Айзек, Гарт; Нараян, Даррен А. (2004), «Классификация турниров, имеющих ациклический турнир в качестве минимального набора дуг обратной связи», Information Processing Letters , 92 (3): 107–111, doi :10.1016/j.ipl.2004.07.001, MR  2095357
62. Хуан, Хао; Ма, Цзе; Шапира, Асаф; Судаков, Бенни ; Юстер, Рафаэль (2013), «Большие наборы дуг обратной связи, подграфы с высокой минимальной степенью и длинные циклы в эйлеровых орграфах», Комбинаторика, вероятность и вычисления , 22 (6): 859–873, arXiv : 1202.2602 , doi : 10.1017/S0963548313000394, hdl : 20.500.11850/73894 , MR  3111546, S2CID  7967738
63. Ханауэр, Катрин; Бранденбург, Франц-Иосиф; Ауэр, Кристофер (2013), «Точные верхние границы для минимальных наборов дуг обратной связи регулярных графов», Брандштедт, Андреас; Янсен, Клаус; Райщук, Рюдигер (ред.), Теоретико-графовые концепции в информатике - 39-й международный семинар, WG 2013, Любек, Германия, 19–21 июня 2013 г., Переработанные статьи , Конспекты лекций по информатике, том. 8165, Springer, стр. 298–309, номер документа : 10.1007/978-3-642-45043-3_26, ISBN. 978-3-642-45042-6, МР  3139198