Упрощение графа / решетки

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

Ввод - это ориентированный граф кратчайших путей, который представляет собой ограниченную решетку, частично упорядоченный набор с минимальным и максимальным элементом.

Определить следующий узел N ( n) узла n как набора узлов b, для которых a предыдущий узел P (n) . Расширить определения на множествах, N (S) объединение N (n) для n в S, аналогично для P (S).

Легко делать разные разрезы в списке множества узлов L, N (L), N (N (L)), ... где для каждой соседней пары наборов A N (A) = B означает отсутствие разделов:

A = A_1 union A_2
B = B_1 union B_2
with B_i = N(A_i), A_i = P(B_i) for i=1,2.

С помощью этого свойства создайте новую решетку с отображением:

• подрешетка в один узел
• , если верхнее разделение является найдено, чем создать ребра (число мощности разбиения).

Проще говоря, алгоритм для отображения решетка -> решетка таков:

A = {minimum node}
new_node = [A]
1:
while A, N(A) don't have partitions
  append N(A) to new_node
  A = N(A)
for each partition $B_i$
  last_new_node = new_node
  create new_node = [B_i]
  create edge last_new_node to new_node
  go to 1
At the end fix maximum node in new lattice if needed

Этот алгоритм можно вызывать повторно для новых решеток. Меня беспокоит:

• Есть ли гарантия для достижения одноузловой решетки?
• Есть ли какая-то мера количества итераций для достижения одноузловой решетки? Мне кажется, что граница - это диаметр входного графа.

Я ценю ссылку на любую подобную структуру данных.

Tnx

Предпосылки:

У меня возникла идея использовать проблему запрета сети с максимальным потоком в материалах, над которыми я работал. Я думал о версии запрета вершин, где заданное количество вершин можно удалить из сети, чтобы минимизировать максимальный поток. Сеть, над которой я работал, была очень правильным плоским ориентированным графом (плоскость разделена на шестиугольники, каждая вершина соединена с 6 вершинами). Я хотел отрезать (запретить) только кратчайшие пути от источника до стока . Для этого я использовал упрощение ориентированного графа, ребро (a, b) находится в упрощенном графе, если оно находится на кратчайшем пути от a к сток . Если веса ребер положительны, то упрощенный ориентированный граф является решетчатым. Это то, что я назвал «ориентированным графом кратчайших путей».

Я хотел иметь хорошие разрезы вершин (параллельность, распространение, ...), что проще для (очень структурированной) решетки.

Собственные разрезы являются ' волны », например, один хороший разрез C также дает N (C) , что приятно. Поэтому я попытался упростить решетку с помощью описанных выше операций. Я попытался описать 2 подмножества вершин, которые интересны для разрезов и используются при отображении: - волна - параллельный набор узлов. Если C - одна волна, то N (C) - другая. - полоса - серия волн без пересечения с другими полосами. C, N (C), N (N (C)) .

  B1--C1--D1 ...
 / \ / \ / 
A   X   X  
 \ / \ / \ 
  B2--C2--D2

Waves: {A}, {B1,B2}, {C1,C2}, {D1,D2}
Stripe is made of these 4 waves.

Отображение отображает полосу от начальной решетки к узлу новой решетки. Узлы в новой решетке соединяются, если они имеют общую волну. Направление края - от полосы, которая разделяет последнюю волну, к полосе, которая разделяет первую волну.

Поскольку отображение создает новую решетку с такими же свойствами, процедуру можно повторять до тех пор, пока не будет решетка с одним узлом. Это можно показать, потому что диаметр решетки уменьшается, по крайней мере, на 1 с каждой итерацией. Это связано с тем, что минимальный узел M и N (M) находятся в одной полосе, и это уменьшает диаметр решетки.

Теперь выполнение или поиск разрезов является рекурсивной задачей, начните с предпоследняя решетка только с одним узлом, и сделайте разрез по одной целой волне или по соседним волнам лестничным способом. Для узлов в разрезе возьмите подрешетку, которая отображается в ней, и сделайте разрез на этой подрешетке. То же самое происходит до достижения начальной решетки.

Эта структура является своего рода сжатием решетки. Думаю, его можно использовать для поиска разрезов динамической решетки.

В моем случае я не использую его из-за некоторых других ограничений проекта. Я решил начальную проблему очень просто с помощью всего нескольких строк кода, но я не понимал, что это можно сделать так раньше: -)