TODO: my notion page https://www.notion.so/PPDC-construction-50e4c555f0444468955b924c14c37013
PPDC: алгоритм
EPPDC: деконструкция алгоритма.
Какие есть важные моменты:
- PPDC можно построить для любого связного графа, через итеративное добавление рёбер, причём рёбра можно добавлять в любом порядке, причём внутри алгоритма они добавляются ориентированно и есть 2 порядка добавления ориентированных рёбер, и можно выбрать любой из них.
Мы будем исходить из гипотезы, что для любого связного графа можно также построить и EPPDC.
Какие возможны изменения по сравнению с PPDC:
- С практической точки зрения, если мы хотим перебрать как можно больше графов, PPDC можно строить начиная с дерева и заканчивая полным графом, добавляя рёбра по одному, в случайном порядке. Возможно, что для EPPDC такая схема не подходит, и придётся каждый раз фиксировать граф который мы хотим построить, и мб наилучший порядок добавления рёбер.
- Но это всё очень сильно усложняет схему алгоритма, например, непонятно, как выбрать хороший порядок добавления рёбер. Поэтому временно мы не будем рассматривать модификации в алгоритме, будем считать, что EPPDC можно построить при любом порядке выбора рёбер.
- Ещё возможный нюанс - это выбор порядка ориентирования ребра. Если ребро (a,b), то либо мы добавляем сначала (a,b), потом (b,a); либо сначала (b,a), а потом (a,b). Кажется, что в идеале было бы хорошо, если б мы могли добавить ребро в любом порядке
- Дальше мы пытаемся добавить неориентированное ребро (a,b). Сначала добавляем a-->b, потом b-->a
- Добавление ребра a-->b означает, что мы хотим удлинить какой-то из путей, который заканчивается в a, до пути, который заканчивается в b
- При добавлении ребра a-->b в каждой вершине начинается и заканчивается по 2 пути
- При добавлении ребра b-->a в вершине b находится 3 конца путей, а в вершине a только 1
- ...
