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

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

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

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

Позволять $S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))$ — конечный список неотрицательных целых чисел, находящихся в невозрастающем лексикографическом порядке , и пусть $(a_{i},b_{i})$ быть парой неотрицательных целых чисел с $b_{i}>0$. Список $S$ является диграфическим тогда и только тогда, когда конечный список $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}),\dots ,(a_{n},b_{n}))$ имеет пары неотрицательных целых чисел и является диграфическим.

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

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

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

Позволять $S=((a_{1},b_{1}),\dots ,(a_{n},b_{n}))$ — конечный список целых неотрицательных чисел таких, что $a_{1}\geq a_{2}\geq \cdots \geq a_{n}$ и пусть $(a_{i},b_{i})$ быть такой парой, что $(b_{i},a_{i})$ является максимальным относительно лексикографического порядка для всех пар $(b_{1},a_{1}),\dots ,(b_{n},a_{n})$. Список $S$ является диграфическим тогда и только тогда, когда конечный список $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}),\dots ,(a_{n},b_{n}))$ имеет пары неотрицательных целых чисел и является диграфическим.

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

См. также

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

Ссылки

• Клейтман, диджей; Ван, Д.Л. (1973), «Алгоритмы построения графов и орграфов с заданными валентностями и коэффициентами», Discrete Mathematics , 6 : 79–88, doi : 10.1016/0012-365x(73)90037-x