Проблема двусторонней реализации

Проблема двудольной реализации является классической проблемой решения в теории графов , разделе комбинаторики . Даны две конечные последовательности $(a_{1},\dots ,a_{n})$ и $(b_{1},\dots ,b_{m})$ натуральных чисел с $m\leq n$, проблема состоит в том, существует ли помеченный простой двудольный граф такой, что $(a_{1},\dots ,a_{n}),(b_{1},\dots ,b_{m})$ — последовательность степеней этого двудольного графа.

Решения

Задача относится к классу P. сложности Это можно доказать с помощью теоремы Гейла–Райзера , т. е. необходимо проверить правильность $n$ неравенства.

Другие обозначения

Проблему также можно сформулировать в терминах матриц ноль-единица . Связь можно увидеть, если осознать, что каждый двудольный граф имеет матрицу двусмежности , где суммы столбцов и суммы строк соответствуют $(a_{1},\ldots ,a_{n})$ и $(b_{1},\ldots ,b_{m})$. Тогда проблема часто обозначается матрицами 0-1 для заданных сумм строк и столбцов . В классической литературе проблема иногда ставилась в контексте таблиц сопряженности с помощью таблиц сопряженности с заданными маргинальными значениями . Третья формулировка основана на последовательностях степеней простых ориентированных графов с не более чем одной петлей на вершину. В этом случае матрица интерпретируется как матрица смежности такого ориентированного графа. Когда пары неотрицательных целых чисел (( a ₁ , b ₁ ), ..., ( a _n , b _n )) являются парами входящей и исходящей степени помеченного ориентированного графа с не более чем одной петлей на вершину?

Связанные проблемы

Подобные задачи описывают степеней последовательности простых графов и простых ориентированных графов . Первая проблема — это так называемая проблема реализации графа . Вторая известна как проблема реализации орграфа . Проблема двудольной реализации эквивалентна вопросу, существует ли помеченный двудольный подграф полного двудольного графа с заданной последовательностью степеней. требует Задача Хичкока наличия такого подграфа, минимизирующего сумму затрат на каждом ребре, заданных для полного двудольного графа. Дальнейшим обобщением является проблема f-фактора для двудольных графов , т. е. для данного двудольного графа ищется подграф, обладающий определенной последовательностью степеней. Задача равномерной выборки двудольного графа до последовательности фиксированной степени заключается в построении решения проблемы двудольной реализации с дополнительным ограничением, согласно которому каждое такое решение приходит с одинаковой вероятностью. показала, что эта проблема возникает в FPTAS для обычных последовательностей. Кэтрин Гринхилл (для правильных двудольных графов с запрещенным 1-множителем ) и для полурегулярных последовательностей Эрдёша и др. Общая проблема до сих пор не решена.

Ссылки

• Гейл, Д. (1957). «Теорема о потоках в сетях» . Пасифик Дж. Математика . 7 (2): 1073–1082. дои : 10.2140/pjm.1957.7.1073 .
• Райзер, HJ (1963). Комбинаторная математика . Джон Уайли и сыновья .
• Гринхилл, Кэтрин (2011). «Полиномиальная оценка времени смешивания цепи Маркова для выборки регулярных ориентированных графов» . Электронный журнал комбинаторики . 18 (1): 234. arXiv : 1105.0457 . Бибкод : 2011arXiv1105.0457G . дои : 10.37236/721 . S2CID   11309590 .
• Эрдеш, Польша; Поцелуй, СЗ; Миклош, И.; Соукуп, Лайош (2015). «Приблизительный подсчет графических реализаций» . ПЛОС ОДИН . 10 (7): e0131300. arXiv : 1301.7523 . Бибкод : 2015PLoSO..1031300E . дои : 10.1371/journal.pone.0131300 . ПМЦ   4498913 . ПМИД   26161994 .
• Эрдеш, Петер Л.; Кирай, Золтан; Миклош, Иштван (май 2013 г.). «О расстояниях обмена различных реализаций графической последовательности степеней» (PDF) . Комбинаторика, теория вероятностей и вычисления . 22 (3): 366–383. дои : 10.1017/S0963548313000096 . S2CID   5643528 .