二部图中的最佳边着色
Optimal edge coloring in bipartite graphs
我遇到过以下问题：在二部图中找到最佳边着色。我知道贪婪着色算法有时不能 return 最佳颜色数。 'greedy coloring algorithm' 我的意思是：选择度数最高的第一个顶点，并在颜色 1...度数上为它的边着色，然后选择度数 <= 到前一个度数的顶点，并在第一个上为它的每个入射边着色可用编号（未被其邻居使用的最小编号），选择下一个顶点等。
但我引入了一个修改：第一个选择的顶点的边缘我按降序（度数...1）着色，而下一个顶点的边缘与之前一样在 1...度数上着色。这种修改导致了我提出的例子我有最佳数量的颜色。但我不太确定这是否总是一条规则。有人知道这个版本的边缘着色算法是否是最优的，或者谁能给出任何反例？
您可以将 "naive" 贪心算法的反例转化为 "sophisticated" 贪心算法的反例。只需将具有适当程度的虚拟节点插入 "absorb" 向后着色。人们总是可以在图中的任意部分制造一个度数 n 的新节点：只需在另一部分插入 n 个新节点，然后通过一条边将它们分别连接到所需的新节点。
由于所有按降序着色的节点都是新插入的，因此原始反例中的所有节点都按升序着色，因此获得与原始 "naive" 贪心算法中相同的颜色.由于最优着色至少与原始图的度数一样多，并且新插入的节点的度数都小于原始图的最大度数，因此新图不需要比原始图更多的颜色。因此，由 "sophisticated" 算法生成的着色——其颜色仍然比原始图形所需的颜色多——对于新图形来说并不是最佳选择。
例如，以下面评论中描述的图形为例，左侧有节点 B、C、D，右侧有 E、F、G、H。它有这些优势：
B connects to E, F, and G
C connects to E, F, and G
D connects to G and H
目前，我假设只有您触摸的第一个节点按降序着色。 （对于其他节点，甚至不清楚 "descending order" 可能意味着什么——从最大值下降？节点的度数可能不够高。）
因此，我们在左边插入一个新的节点A，在右边插入三个节点I、J、K；现在连接
A connects to I, J, and K
B connects to E, F, and G
C connects to E, F, and G
D connects to G and H
复杂的贪心算法因此会对 AI-3、AJ-2、AK-1 进行着色，然后在其余节点上像朴素的贪心算法一样进行处理。
我遇到过以下问题：在二部图中找到最佳边着色。我知道贪婪着色算法有时不能 return 最佳颜色数。 'greedy coloring algorithm' 我的意思是：选择度数最高的第一个顶点，并在颜色 1...度数上为它的边着色，然后选择度数 <= 到前一个度数的顶点，并在第一个上为它的每个入射边着色可用编号（未被其邻居使用的最小编号），选择下一个顶点等。
但我引入了一个修改：第一个选择的顶点的边缘我按降序（度数...1）着色，而下一个顶点的边缘与之前一样在 1...度数上着色。这种修改导致了我提出的例子我有最佳数量的颜色。但我不太确定这是否总是一条规则。有人知道这个版本的边缘着色算法是否是最优的，或者谁能给出任何反例？
您可以将 "naive" 贪心算法的反例转化为 "sophisticated" 贪心算法的反例。只需将具有适当程度的虚拟节点插入 "absorb" 向后着色。人们总是可以在图中的任意部分制造一个度数 n 的新节点：只需在另一部分插入 n 个新节点，然后通过一条边将它们分别连接到所需的新节点。
由于所有按降序着色的节点都是新插入的，因此原始反例中的所有节点都按升序着色，因此获得与原始 "naive" 贪心算法中相同的颜色.由于最优着色至少与原始图的度数一样多，并且新插入的节点的度数都小于原始图的最大度数，因此新图不需要比原始图更多的颜色。因此，由 "sophisticated" 算法生成的着色——其颜色仍然比原始图形所需的颜色多——对于新图形来说并不是最佳选择。
例如，以下面评论中描述的图形为例，左侧有节点 B、C、D，右侧有 E、F、G、H。它有这些优势：
B connects to E, F, and G
C connects to E, F, and G
D connects to G and H
目前，我假设只有您触摸的第一个节点按降序着色。 （对于其他节点，甚至不清楚 "descending order" 可能意味着什么——从最大值下降？节点的度数可能不够高。）
因此，我们在左边插入一个新的节点A，在右边插入三个节点I、J、K；现在连接
A connects to I, J, and K
B connects to E, F, and G
C connects to E, F, and G
D connects to G and H
复杂的贪心算法因此会对 AI-3、AJ-2、AK-1 进行着色，然后在其余节点上像朴素的贪心算法一样进行处理。