2

我有一个特定类型的平面图，我发现搜索一种可以合法地为其顶点着色的算法很有趣。关于这种类型的图表，它非常简单和酷：

考虑任何具有n>2个顶点和k个叶子的树T。让我们将G(T)表示为由T构造的图，该图通过将其叶连接到k -cycle 以使G(T)是平面的方式。

我想出的问题是用3种颜色为G(T)着色。显然，作为平面图的G(T)是4可着色的，但我认为（没有证据）由于其简单性，它几乎总是3可着色的。几乎总是意味着只有当T是一颗星星并且只有奇数个叶子时，G(T)才是4可着色的。

我正在寻找一些算法，或者也许可以证明我的假设可以很容易地转化为算法。我将非常感谢任何帮助和提示。

如果我不够清楚，我会举一个例子：

令 T 为一棵树，其边 E(T) = { {1,2}, {2,3}, {2,4}, {4,5} } 然后 E(G(T)) =集合：E(T) 和 { {1,5}, {5,3}, {3,1} }，因为我们将叶子 1,5,3 连接成一个循环。

4

1 回答 1

0 
local Edges_of_Tree = {{1,2}, {2,3}, {2,4}, {4,5}}
local Cycle_of_Leaves = {1,5,3}

local color1 = 'Red'
local color2 = 'Green'
local color3 = 'Blue'

local vert = {}     
local vert_arr = {}  

local function add_edge(v1, v2)
   assert(v1 ~= v2)
   if not vert[v1] then
      vert[v1] = {deg = 0, adj = {}}
      table.insert(vert_arr, v1)
   end
   vert[v1].deg = vert[v1].deg + 1
   assert(not vert[v1].adj[v2], 'multiple edges between '..v1..' and '..v2)
   vert[v1].adj[v2] = true
end

for _, edge in ipairs(Edges_of_Tree) do
   local v1, v2 = unpack(edge)
   add_edge(v1, v2)
   add_edge(v2, v1)
end

table.sort(vert_arr)

local leaf_ctr = 0
local root
for v, vv in pairs(vert) do
   if vv.deg == 1 then
      leaf_ctr = leaf_ctr + 1
   else
      root = v
   end
end
assert(#vert_arr > leaf_ctr + 1, 'tree is a star')
assert(leaf_ctr == #Cycle_of_Leaves, 'invalid Cycle_of_Leaves')
for _, v in ipairs(Cycle_of_Leaves) do
   assert(vert[v] and vert[v].deg == 1 and vert[v].color == nil, 
      'invalid Cycle_of_Leaves')
   vert[v].color = false
end

local function recursive_paint_inodes(v, color, prev_v)
   assert(vert[v].color == nil, 'a cycle in tree found')
   vert[v].color = color
   local next_color = (color1..color2):gsub(color, '')
   for next_v in pairs(vert[v].adj) do
      if next_v ~= prev_v and vert[next_v].deg > 1 then
         recursive_paint_inodes(next_v, next_color, v)
      end
   end
end
recursive_paint_inodes(root, color1)

local front
for i = 1, leaf_ctr do
   local vv = vert[Cycle_of_Leaves[i]]
   vv.next = Cycle_of_Leaves[i % leaf_ctr + 1]
   vv.prev = Cycle_of_Leaves[(i - 2) % leaf_ctr + 1]
   local parent = next(vv.adj)
   if parent ~= next(vert[vv.prev].adj) then
      assert(not vert[parent].conn_to_leaf, 'graph is non-planar')
      vert[parent].conn_to_leaf = true
      front = Cycle_of_Leaves[i]
   end
end

vert[next(vert[vert[front].prev].adj)].color = color3
vert[front].color = color3

local tricolor = color1..color2..color3
local leaf = front
for i = 1, leaf_ctr - 1 do
   local prev_color = vert[leaf].color
   leaf = vert[leaf].next
   local parent_color = vert[next(vert[leaf].adj)].color
   local enabled_colors = tricolor:gsub(prev_color, ''):gsub(parent_color, '')
   vert[leaf].color = enabled_colors:match(color1)
      or enabled_colors:match(color2) or color3
end

for _, v in ipairs(vert_arr) do
   print(v..' '..vert[v].color)
end

这段代码是用Lua 编写的。
你可以在那里测试它。

于 2013-04-20T22:18:27.040 回答