在线性时间内查找 k-coloring（k = 2/3）图

Question

问题：

给定一个图 G = (V,E) G 的 k-coloring 是顶点的标签，颜色为 c_1, c_2, ..., c_k 这样对于每条边 (u,v)，u 的颜色与 v 的颜色不同。

一个。给出一个线性时间算法，为一棵树找到一个二次着色。

乙。考虑用两种颜色给一棵树上色，这样你就有了最大数量的彩色节点 c_1。证明你的（a）部分的算法，可能稍作修改，就可以用来解决这个问题。要准确。

摄氏度。显示树 T 的示例，它最多可以有 j 个节点在 2 色中着色 c_1，但 T 可以有 j' > j 个节点在 3 色中着色 c_1。尝试找到这种树T的最小例子。

D.给出一个线性时间动态规划算法，该算法为一棵树创建 3 着色，使得最大数量的节点被着色 c_1。证明你的答案。

我有：

A 和 B 看起来很简单，但我在 C 和 D 上很吃力

一个。这看起来很简单，运行 DFS，但是修改它所以如果它

遇到一个未着色的节点color it c1 and its children c2,
遇到有色节点颜色child与相反颜色
如果它试图“翻转”child 的颜色，那么 return 不可能有 k-coloring

这只是 DFS，所以运行在 O(V+E)

编辑：由于这是一棵树，您可以在随机节点上调用 BFS，在 BFS 中交替使用颜色

乙。由于这是二元首选（即 c1 或 c2），并且所有选择都遵循首选，我们可以简单地计算出第一个节点 c1 或 c2 的着色效果更好。我们可以通过在上述算法中添加一个计数器来计算 c1 节点的数量。运行算法两次，一次是从c1开始，然后是c2，比较两者的c1节点数，然后挑出c1节点多的图

摄氏度。摆弄了一段时间，找不到一个，更不用说最小的了

编辑：1-3、2-3、3-4、4-5、4-6 描述者Bing Wang 在这里工作

D.不知道。我假设您将不得不使用修改后的 DFS 使其运行处于线性状态，但除此之外我非常不确定。我可以想出一些方法来暴力破解它，但没有任何方法运行是线性的。

编辑：对此仍然感到困惑

Answer 1

c: 1-3, 2-3, 3-4, 4-5,4-6。这棵树可以在双色的每种颜色中有 3 个节点。但是，如果您将节点 #3/#4 着色为其他两种颜色（三色），则可以有 4 个相同颜色的节点。通过遍历所有可能性，您应该很容易证明没有更小的答案。

D: 遍历树，例如DFS。每个节点需要保持所有 3 种颜色的 c_1 计数。当你处理第一个节点时，那将是 (1,0,0) - 相当容易计数。将节点添加到访问后，尝试所有 3 种颜色，每种颜色将与连接节点的 2 种颜色兼容，从中选择较大的一种，依此类推，构建当前节点的 3 个值。

E=[(1,3),(2,3),(3,4),(4,5),(4,6)]
V={v:set() for e in E for v in e}
[None if V[e[0]].add(e[1]) else V[e[1]].add(e[0]) for e in E]
serialized={}
def traverse(c):
    serialized[c]=V[c]
    [traverse(n) for n in V[c] if n not in serialized]
    
traverse(E[0][0])
visited=set()
for k,v in reversed(serialized.items()):
    filtered=v.intersection(visited)
    visited.add(k)
    m=[1+sum(max([V[child][1],V[child][2]]) for child in filtered)
        ,sum(max([V[child][0],V[child][2]]) for child in filtered)
        ,sum(max([V[child][0],V[child][1]]) for child in filtered)]
    V[k]=m
print(max(V[k]))

Answer 2

一个。选择任何顶点并将其着色为 c1。运行 BFS 从那里开始。奇数距离的所有东西都得到 c2，偶数距离的东西得到 c1。

乙。只有两种着色，它们的区别仅在于将 c1 换成 c2。运行 (A) 并在需要时交换。

C.想象一下 A 和 B 是相连的，A 和 B 一样有许多其他邻居都是叶子。有 2 种颜色，你可以获得比 A 或 B 的大小多一个给定颜色，但是有 3 个你可以给两个给 A 和 B 涂上不同的颜色，并给所有的叶子涂上相同的颜色。叶子的数量取决于 j 和 j' 输入。如果我们找到 j 和 j' 的可能最小值，则给每两片树叶。然后你可以有四个 c1 叶子，A c2 和 B c3，而不是最多 3 个只有两种颜色。

在线性时间内查找 k-coloring（k = 2/3）图

Finding k-coloring (with k = 2/3) graph in linear time

algorithm

dynamic

dynamic-programming

undirected-graph