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

Эти алгоритмы Клейтмана-Ван две разных алгоритмы теории графов , решающие проблему реализации орграфа , то есть вопрос , если существует для конечного списка неотрицательных целых пар в простой ориентированный граф , таким образом, что его степень последовательность именно этот список. При положительном ответе список пар целых чисел называется орграфическим . Оба алгоритма создают специальное решение, если оно существует, или доказывают, что нельзя найти положительный ответ. Эти конструкции основаны на рекурсивных алгоритмах . Клейтман и Ван представили эти алгоритмы в 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}$

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

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

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

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