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

Алгоритмы Клейтмана –Вана — это два различных алгоритма в теории графов, решающих проблему реализации орграфа , то есть вопрос, существует ли для конечного списка неотрицательных целочисленных пар простой ориентированный граф, такой, что его последовательность степеней — это в точности этот список. Для положительного ответа список целочисленных пар называется диграфическим . Оба алгоритма строят специальное решение, если оно существует, или доказывают, что нельзя найти положительный ответ. Эти построения основаны на рекурсивных алгоритмах . Клейтман и Ванг ^[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}),\dots ,(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_{ я},v_{b_{i}+1})}$${\displaystyle S}$${\displaystyle S'}$${\displaystyle S}$

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

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

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

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