图论切割宽度
Graph Theory Cutwidth
有人可以向我解释什么是区间图的切割宽度并给我一个例子吗？
我找到了这个定义，但我不明白：
The cutwidth of a graph G is equal to the minimum cost of an ordering of its vertices.
你的定义有点不完整：
您还应该包括与图形排序相关的成本的定义。在您可能引用的定义中，此成本定义如下：
对于任何节点集S，相应的成本c'(S)由从任何节点出发的边数给出S 中的节点 到 S
之外的任何节点
据此，排序成本 v_1, ..., v_n 定义为所有子集的最大成本 v_1, ..., v_i 其中 i = 1, ..., n - 1
根据前面的定义，这意味着你取从低阶节点到高阶节点的最大边数，这里你可以任意选择低阶和高阶之间的'cut'。
那么切割宽度就是节点最优排序的成本（即节点排序成本最低）。
当我们将其应用于区间图时，即 nodes 是区间并且 edges 表示这些区间之间的交点的图，子集的成本 c'(S) 是区间 外部 S 与区间 内部 S.
从这里可以看出，区间图的切割宽度是区间最优排序的成本，使得高阶区间与低阶区间相交的次数最少。
很遗憾，对于给定的区间图，我无法为您提供确切的计算规则，但我会给您举一个小例子：
取区间 [0,4],[0,1],[2,3],[1.5,2.5],[3.5,5] 得到下图：
无论间隔如何排序，如果您选择了4循环[0,4]，[0,1.9]，[1.5,2.5]，[2,3]中的两个间隔在前在你的顺序中，循环中的其他两个间隔将与前两个间隔至少有两个交点，这意味着切割宽度是 至少 2.
同时，[0,1.9],[1.5,2.5],[2,3],[0,4],[3.5,5] 的排序为您节省了 2,2,2,1 for i = 1,2,3,4, 所以这个图的切割宽度是 最多 2.
综合这些结果，可以看出图形的切割宽度为2。
或许可以将这种切割宽度的上限和下限推广到所有区间图，但目前我无法为您提供该问题的完整解决方案。
有人可以向我解释什么是区间图的切割宽度并给我一个例子吗？
我找到了这个定义，但我不明白：
The cutwidth of a graph G is equal to the minimum cost of an ordering of its vertices.
你的定义有点不完整： 您还应该包括与图形排序相关的成本的定义。在您可能引用的定义中，此成本定义如下：
对于任何节点集S，相应的成本c'(S)由从任何节点出发的边数给出S 中的节点 到 S
之外的任何节点据此，排序成本 v_1, ..., v_n 定义为所有子集的最大成本 v_1, ..., v_i 其中 i = 1, ..., n - 1
根据前面的定义，这意味着你取从低阶节点到高阶节点的最大边数，这里你可以任意选择低阶和高阶之间的'cut'。
那么切割宽度就是节点最优排序的成本（即节点排序成本最低）。
当我们将其应用于区间图时，即 nodes 是区间并且 edges 表示这些区间之间的交点的图，子集的成本 c'(S) 是区间 外部 S 与区间 内部 S.
从这里可以看出，区间图的切割宽度是区间最优排序的成本，使得高阶区间与低阶区间相交的次数最少。
很遗憾，对于给定的区间图，我无法为您提供确切的计算规则，但我会给您举一个小例子：
取区间 [0,4],[0,1],[2,3],[1.5,2.5],[3.5,5] 得到下图：
无论间隔如何排序，如果您选择了4循环[0,4]，[0,1.9]，[1.5,2.5]，[2,3]中的两个间隔在前在你的顺序中，循环中的其他两个间隔将与前两个间隔至少有两个交点，这意味着切割宽度是 至少 2.
同时，[0,1.9],[1.5,2.5],[2,3],[0,4],[3.5,5] 的排序为您节省了 2,2,2,1 for i = 1,2,3,4, 所以这个图的切割宽度是 最多 2.
综合这些结果，可以看出图形的切割宽度为2。
或许可以将这种切割宽度的上限和下限推广到所有区间图，但目前我无法为您提供该问题的完整解决方案。