graph - 从图形中切分以找到将系统分解为不相交集的排列？

Question

假设一个无向系统，您想要在其排列中找出元素的图形，这些元素使系统不相交，使得每个集合都是最小的。该图有两个特殊节点：不能在元素中的 sink 和 source。

给定一些图 G=(V,E)，你如何在计算上找到最小割？

Answer 1

随意选择任何方法来计算从图形计算的 mincuts。我在下面列出了一个简单的例子，相关的研究、模型、存储方法、引理、定理——以及这个线程关注的关于可视化和计算的一些东西。简单示例之后的下一步是图形模型的参数化，然后是计算。

Python 和笛卡尔积的简单示例

假设一个 3x2x2 的图有 3 个平行，其中第一个分支有 3 个东西，第二个分支有 2 个东西，最后一个分支有 2 个东西。最小切割是{{1,4,6},{1,4,7},{1,5,6},{1,5,7},{2,4,6},{2,4, 7},{2,5,6},{2,5,7},{3,4,6},{3,4,7},{3,5,6},{3,5,7} }。

import itertools;

somelists = [
   [1, 2, 3],
   [4, 5],
   [6, 7]
]

print list(itertools.product(*somelists))

计算

• 一般问题如何分析稀疏邻接矩阵？但相关，因为图表通常是稀疏的。

• Graph Complement 对查找 mincuts 很有用：下面是 Mathematica 的试用版，但请注意，至少在 10.1 中发现 Mathematica中的一些错误与 mincut 和 VertexConnectivity 命令相关。

数学

• 【割计算代数中的图形参数化问题】割理想如树的割理想的Betti数

• 【简单图的硬图参数化问题】 固定顶点数和固定顶点割数的最小简单图生成集？

• mincuts 具有交叉标准、仙人掌存储方法和Graph Connectivity 论文 (2004)中概述的当前研究。

• 最小割的许多相关术语，例如顶点分离器、分叉器、顶点割、边割、图边界——此处概述的数学术语。

使用汇和源可视化串并图

• Tikz 包用于绘制具有许多串联并行的变量的串行并行图

• 优质材料包含Lauritzen Steffen 的“图形模型” 、 “R 的图形模型”和 Sturmfels 的代数几何材料。