mirskontsa: (draft) EPPDC, дизайн алгоритма

PPDC: алгоритм

EPPDC: деконструкция алгоритма.

Какие есть важные моменты:

PPDC можно построить для любого связного графа, через итеративное добавление рёбер, причём рёбра можно добавлять в любом порядке, причём внутри алгоритма они добавляются ориентированно и есть 2 порядка добавления ориентированных рёбер, и можно выбрать любой из них.

Возможно, что в EPPDC в каждый пункт придётся внести изменения.

Мы будем исходить из гипотезы, что для любого связного графа можно также построить и 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
...

mirskontsa