我正在尝试基于一组关键顶点将网络分成一个或多个部分。 我有代码来解决我的问题（至少对我感兴趣的情况是这样），但为了确保正确性，我正在寻找我所做的事情在图论中的名称，甚至是等效算法或过程的参考资料。
输入网络是具有单个源和汇顶点的有向图。结果分区必须具有与原始图相同的属性（有向图，单个源顶点，单个汇顶点），并且还要求每个分区只能有两个关键集合中的顶点，并且它们必须是初始和终止顶点。
编辑
如果源和汇是相同的顶点，则结果子图将包含一个循环。 现有代码可用于检测和删除此类循环。
结束编辑
在这种情况下，图表值得千言万语。 我已经绘制了一个简单的图形，彩色顶点表示关键顶点，虚线是图的分区。
输入网络是具有单个源和汇顶点的有向图。结果分区必须具有与原始图相同的属性（有向图，单个源顶点，单个汇顶点），并且还要求每个分区只能有两个关键集合中的顶点，并且它们必须是初始和终止顶点。
编辑
如果源和汇是相同的顶点，则结果子图将包含一个循环。 现有代码可用于检测和删除此类循环。
结束编辑
在这种情况下，图表值得千言万语。 我已经绘制了一个简单的图形，彩色顶点表示关键顶点，虚线是图的分区。
def graphTraversal(graph,srcid,endids):
'''
Given a graph, start a traversal from srcid, stopping search
along a branch any time a vertex is in endids.
Return the visited subgraph
'''
closed = set()
open = set([srcid])
while len(open) != 0:
i = open.pop()
for j in graph.succ(i):
if (i,j) not in closed:
if j not in endids:
open.add(j)
closed.add( (i,j) )
return = graphFromList(closed)
def findAllValidPartitions(graph,srcids):
res = []
for n in srcids:
g2 = graphTraversal(graph,n,t)
g2rev = reverseEdgesInGraph(g2)
for s in srcids:
g3 = graphTraversal(g2rev ,s,t)
g3rev = reverseEdgesInGraph(g3)
g3rev = removeCycles(g3rev,s)
if len(g3rev .E) > 0:
res.append(g3rev)
return res