Алгоритмы Клейтмана – Ванга - Kleitman–Wang algorithms

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

Алгоритм Клейтмана – Ванга (произвольный выбор пар)

Алгоритм основан на следующей теореме.

Позволять ${ displaystyle S = ((a_ {1}, b_ {1}), dots, (a_ {n}, b_ {n}))}$ конечный список неотрицательных целых чисел, который находится в невозрастающий лексикографический порядок и разреши ${ displaystyle (a_ {i}, b_ {i})}$ - пара неотрицательных целых чисел с ${ displaystyle b_ {i}> 0}$. Список ${ displaystyle S}$ диграфично тогда и только тогда, когда конечное список ${ displaystyle S '= ((a_ {1} -1, b_ {1}), dots, (a_ {b_ {i} -1} -1, b_ {b_ {i} -1}), (a_ {b_ {i}}, 0), (a_ {b_ {i} +1}, b_ {b_ {i} +1}), (a_ {b_ {i} +2}, b_ {b_ {i} + 2}), точки, (a_ {n}, b_ {n}))}$ имеет неотрицательные пары целых чисел и является диграфическим.

Обратите внимание, что пара ${ displaystyle (a_ {i}, b_ {i})}$ произвольно, за исключением пар ${ displaystyle (a_ {j}, 0)}$. Если данный список ${ displaystyle S}$ диграфичен, то теорема будет применяться не более чем ${ displaystyle n}$ установка времени на каждом следующем шаге ${ Displaystyle S: = S '}$. Этот процесс заканчивается, когда весь список ${ displaystyle S '}$ состоит из ${ displaystyle (0,0)}$ пары. На каждом шаге алгоритма строится дуги орграфа с вершинами ${ displaystyle v_ {1}, dots, v_ {n}}$, т.е. если можно сократить список ${ displaystyle S}$ к ${ displaystyle S '}$, затем добавляем дуги ${ displaystyle (v_ {i}, v_ {1}), (v_ {i}, v_ {2}), dots, (v_ {i}, v_ {b_ {i} -1}), (v_ { i}, v_ {b_ {i} +1})}$. Когда список ${ displaystyle S}$ не может быть сведен к списку ${ displaystyle S '}$ неотрицательных целочисленных пар на любом этапе этого подхода теорема доказывает, что список ${ displaystyle S}$ с самого начала не является диграфическим.

Алгоритм Клейтмана – Ванга (максимальный выбор пары)

Алгоритм основан на следующей теореме.

Позволять ${ displaystyle S = ((a_ {1}, b_ {1}), dots, (a_ {n}, b_ {n}))}$ - конечный список неотрицательных целых чисел такой, что ${ Displaystyle а_ {1} geq а_ {2} geq cdots geq а_ {п}}$ и разреши ${ displaystyle (a_ {i}, b_ {i})}$ быть парой, такой что ${ displaystyle (b_ {i}, a_ {i})}$ максимальна по лексикографический порядок под всеми парами ${ displaystyle (b_ {1}, a_ {1}), dots, (b_ {n}, a_ {n})}$. Список ${ displaystyle S}$ диграфично тогда и только тогда, когда конечный список ${ displaystyle S '= ((a_ {1} -1, b_ {1}), cdots, (a_ {b_ {i} -1} -1, b_ {b_ {i} -1}), (a_ {b_ {i}}, 0), (a_ {b_ {i} +1}, b_ {b_ {i} +1}), (a_ {b_ {i} +2}, b_ {b_ {i} + 2}), точки, (a_ {n}, b_ {n}))}$ имеет неотрицательные пары целых чисел и является диграфическим.

Обратите внимание, что список ${ displaystyle S}$ не должны располагаться в лексикографическом порядке, как в первой версии. Если данный список ${ displaystyle S}$ диграфично, то теорема будет применяться не более чем ${ displaystyle n}$ раз, устанавливая на каждом следующем шаге ${ Displaystyle S: = S '}$. Этот процесс заканчивается, когда весь список ${ displaystyle S '}$ состоит из ${ displaystyle (0,0)}$ пары. На каждом шаге алгоритма строится дуги орграфа с вершинами ${ displaystyle v_ {1}, dots, v_ {n}}$, т.е. если можно сократить список ${ displaystyle S}$ к ${ displaystyle S '}$, то добавляются дуги ${ displaystyle (v_ {i}, v_ {1}), (v_ {i}, v_ {2}), dots, (v_ {i}, v_ {b_ {i} -1}), (v_ { i}, v_ {b_ {i} +1})}$. Когда список ${ displaystyle S}$ не может быть сведен к списку ${ displaystyle S '}$ неотрицательных целочисленных пар на любом этапе этого подхода теорема доказывает, что список ${ displaystyle S}$ с самого начала не является диграфическим.

Смотрите также

• Теорема Фулкерсона – Чена – Ансти

Рекомендации

• Kleitman, D. J .; Ван, Д. Л. (1973), "Алгоритмы построения графов и орграфов с заданными валентностями и факторами", Дискретная математика, 6: 79–88, Дои:10.1016 / 0012-365x (73) 90037-x