3

問題は、頂点に割り当てられた数（色）の合計が最小になるように、木の頂点を自然数で色付けすることです。

それを行うための色の数は限られていますか？

4

5 に答える 5

3

それには3色で十分だと思います。それを証明する方法は？

そうではありません。根付いた木を代数的に次のように記述します。V1ノードツリーです。は、とのルートからルートまでのエッジでE(t1, t2)構成され、ルートをルートとするツリーです。次のツリーでは、最小値156を達成するために4色が必要です。t1t2t1t2t2t3

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

いくつかの実験に基づいて、私は、この構造が一般化され、したがって、すべての木の最小値を達成するのに固定数の色では不十分であることを証明できると推測します。

定理すべてのd≥k≥3について、次の帰納的に構築されたツリーT（d、k）は少なくともk色を必要とします。T（d、1）は1頂点ツリーです。i> 1の場合、T（d、i）は、T（d、i-1）の各頂点にd枚の葉が付いたツリーです。

kの帰納法による証明。基本ケースk=3は、基本的に、最適化のために3色が必要な例です。k> 3の場合、k-1色のみを使用するT（d、k）の色付けを検討してください。色kを使用して改善する方法を示します。内部頂点の色が1の場合、その色をkに変更し、隣接する葉のd> k-1の色を1に変更することで改善します。間隔頂点の色が1でなく、葉の色が1以外の場合。葉を1に変更します。まだ改善していない場合は、すべての葉の色が1で、すべての間隔の頂点の色が1より大きいです。すべての葉を削除してラベルをデクリメントすると、T（d、k-1）の色になります。 、誘導仮説によって改善することができます。

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

結果：

> color 3 t3
[157,158,163]
> color 4 t3
[157,158,159,156]
于 2012-05-03T13:39:36.503 に答える
2

まず、どの木でも2色で十分です。それを証明するために、ツリーをレベルごとに別の色で着色することができます。

第二に、レベルごとの着色は、2色の唯一の有効な方法です。それはレベルでの誘導によって証明することができます。ルートノードの色を修正します。次に、すべての子が異なる色、子の子（最初の色など）を持つ必要があります。

第3に、最適な色を選択するには、2つの可能なレイアウトを確認します。ルートノードに色0がある場合と、色がある場合1です。

于 2012-05-03T12:37:30.020 に答える
0

ツリーの場合、使用できる色は2つだけです。1つは深さが奇数のノード用で、もう1つは深さが偶数のノード用です。

編集：私は問題を理解していなかったので、前の答えは間違っていました。

ウォブルで示されているように、必要な色の数に制限はありません。

于 2012-05-03T12:39:30.763 に答える
0

n個のノードを持つツリーの合計を最小化する色の数はO（logn）として制限されます

これは、1989年の論文http://dl.acm.org/citation.cfm?id=75430でE.Kubickaによって取り上げられました。

于 2015-01-24T08:29:49.853 に答える
-1

ツリーを2色{0,1}で着色するだけで十分ですが、複雑さはO（n）になります。

ツリーを3色{0,1,2}で着色するだけで十分ですが、複雑さはO（log *（n））になります。

今質問はlog*（n）とは何ですか

log *（n）- 「反復対数」として知られる「logStarn」

簡単に言えば、log *（n）= log（log（log（.....（log *（n））））と仮定できます。

log *（n）は非常に強力です。

例：

1） Log *（n）= 5ここで、n=宇宙の原子番号

2）ユークリッド最小全域木を知っている点のセットのドロネー三角形分割を見つける：ランダム化されたO（n log * n）時間。

于 2014-05-03T20:39:03.300 に答える