CODEWITHSUNDEEP
algorithmgraphtree
a-z
a-z

Reputation: 1664

coloring tree with minimum sum of colors

The problem is to color tree vertices with natural numbers such that sum of numbers(colors) assigned to vertices be minimum.

Is number of colors to do that bounded?

Upvotes: 3

Views: 3627

Answers (4)

Shubhorup Biswas
Shubhorup Biswas

Reputation: 11

Number of colours to minimise sum for a tree with n nodes is bounded as O(logn)

This was covered by E. Kubicka in her 1989 paper http://dl.acm.org/citation.cfm?id=75430

Upvotes: 0

Thomash
Thomash

Reputation: 6379

For a tree, you can use only 2 colors : one for for nodes with odd depth and a second color for nodes with even depth.

EDIT: The previous answer was wrong because I didn't understand the problem.

As shown by Wobble, the number of colors needed is not bounded.

Upvotes: 0

Skiminok
Skiminok

Reputation: 2871

First, 2 colors is enough for any tree. To prove that, you can just color the tree level by level in alternate colors.

Second, coloring level by level is the only valid method of 2-coloring. It can be proved by induction on the levels. Fix the color of the root node. Then all its children should have the different color, children of the children — first color, and so on.

Third, to choose the optimal coloring, just check the two possible layouts: when the root node has the color 0, and when it has the color 1, respectively.

Upvotes: 2

wobble
wobble

Reputation: 66

I think 3 colors are enough to do that. How to prove it?

It's not. Describe a rooted tree algebraically as follows. V is a one-node tree. E(t1, t2) is a tree consisting of t1 and t2 and an edge from t1's root to t2's root, rooted at t2's root. The following tree t3 requires four colors to attain the minimum, 156.

t3 = E(t2, E(t2, E(t2, E(t2, t2))))
t2 = E(t1, E(t1, E(t1, E(t1, t1))))
t1 = E(t0, E(t0, E(t0, E(t0, t0))))
t0 = V

Based on some experimentation, I would conjecture can prove that this construction generalizes and thus that no fixed number of colors suffices to attain the minimum for all trees.

Theorem For all d ≥ k ≥ 3, the following inductively constructed tree T(d, k) requires at least k colors. T(d, 1) is the one-vertex tree. For i > 1, T(d, i) is the tree with d leaves attached to each vertex of T(d, i - 1).

Proof By induction on k. The base case k = 3 is essentially your example where 3 colors are necessary for optimality. For k > 3, consider a coloring of T(d, k) that uses only k - 1 colors. We show how to use color k to improve it. If some internal vertex has color 1, then we improve by changing its color to k and changing the colors of its d > k - 1 adjacent leaves to 1. If no interval vertex has color 1, and some leaf has color other than 1, change the leaf to 1. If we haven't improved yet, all leaves have color 1 and all interval vertices have color > 1. Removing all the leaves and decrementing the labels, we have a coloring of T(d, k - 1), which we can improve by inductive hypothesis.

data Tree = V | E Tree Tree
    deriving (Eq, Show)

otherMinimums [x, y] = [y, x]
otherMinimums (x:xs) = minimum xs : map (min x) (otherMinimums xs)

color m V = [1..m]
color m (E t1 t2) = let
    c1 = color m t1
    c2 = color m t2 in
    zipWith (+) (otherMinimums c1) c2

t3 = E t2 $ E t2 $ E t2 $ E t2 $ t2
t2 = E t1 $ E t1 $ E t1 $ E t1 $ t1
t1 = E t0 $ E t0 $ E t0 $ E t0 $ t0
t0 = V

Results:

> color 3 t3
[157,158,163]
> color 4 t3
[157,158,159,156]

Upvotes: 3

Related Questions