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

Проблема двудольной реализации - это классическая проблема решения в теории графов , раздел комбинаторики . Учитывая две конечные последовательности и натуральные числа, задача спрашивает, существует ли помеченный простой двудольный граф , который является последовательностью степеней этого двудольного графа.${\ Displaystyle (а_ {1}, \ точки, а_ {п})}$${\ displaystyle (b_ {1}, \ dots, b_ {n})}$${\ displaystyle (a_ {1}, \ dots, a_ {n}), (b_ {1}, \ dots, b_ {n})}$

Решения [ править ]

Проблема относится к классу сложности P . Это можно доказать с помощью теоремы Гейла – Райзера , т. Е. Нужно проверить правильность неравенств.${\ displaystyle n}$

Другие обозначения [ править ]

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

Связанные проблемы [ править ]

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

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

• Гейл, Д. (1957). «Теорема о потоках в сетях» . Pacific J. Math . 7 (2): 1073–1082. DOI : 10,2140 / pjm.1957.7.1073 .
• Райзер, HJ (1963). Комбинаторная математика . Джон Вили и сыновья .
• Гринхилл, Кэтрин (2011). «Полиномиальная оценка времени перемешивания цепи Маркова для выборки регулярных ориентированных графов» . Электронный журнал комбинаторики . 18 (1): 234. arXiv : 1105.0457 . Bibcode : 2011arXiv1105.0457G .
• Erdős, PL; Поцелуй, СЗ; Miklós, I .; Соукуп, Лайош (2015). «Приблизительный подсчет графических реализаций». PLOS ONE . 10 (7): e0131300. arXiv : 1301,7523 . Bibcode : 2015PLoSO..1031300E . DOI : 10.1371 / journal.pone.0131300 .