图形/点阵简化

Question

我正在研究图切割算法的数据结构.问题是在最短路径上进行不同的切割.我制作了数据结构,我不确定属性.

输入是最短路径的有向图,它是有界点阵,有最小和最大元素的部分有序集.

将节点n的下一个节点N(n)定义为一组节点b,其中a <b且没有c,其中<c <b.类似地定义前一节点P(n).扩展集合的定义,N(n)对于S中的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个顶点).我想剪(停职)只从最短路径source来sink.为了使我使用有向图的(a,b)简化,如果在最短路径上,则边缘在简化图a中sink.如果边缘权重为正,则简化的有向图是格子.这就是我所说的"最短路径的有向图".

我希望顶点切割很好(平行,传播,...),更容易(非常结构化)晶格.

原生切割是'波浪',例如,一个很好的切割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)相同的条带,并且减少了晶格直径.

现在,执行或搜索剪切是递归任务,从最后一个只有一个节点的格子一开始,并在楼梯方式上在一个整波或相邻波上切割.对于切割中的节点,采用映射在其中的子网格,并在该子网格上进行切割.完成相同直到达到初始晶格.

这种结构在晶格压缩上是某种形式.我认为它可以用于动态格子切割搜索.

在我的情况下,我没有使用它,因为一些其他项目限制.我只用几行代码解决了初始问题非常简单,但我没有意识到它可以像以前那样完成:-)

Answer 1

是否有保证达到单节点晶格？

如果我正确理解你的伪代码,则不:它带有n节点线性顺序到n节点线性顺序.

我会将您的代码描述为接受部分顺序并找到一个系列并行的部分顺序,它有一个合理的"忠实"嵌入.

如果你只是想在平面图中找到最大流/最小切割,那么就有一个O(n log n)算法.