関係は

私は、次の質問を証明するために助けを探しています：< = 3、は（1）があることを証明 それぞれの学位を持つn個の頂点を持つ無向木与えられたが削除すると、頂点の数が2つのツリー（最大2 * n/3）を持つエッジが存在します。 （2）は、上記のツリーでこのようなエッジを見つける線形アルゴリズムを提案します。関係は

出典

2017-02-21 user3857787

ツリーが3つの頂点だけを子として持つルート（合計4つ）の場合は、（1）を満たしますか？ –

@ ShihabShahriar（2 * n/3）項が切り上げられた場合、おそらく問題はありません。 – Gassa

@ShihabShahriarはい、あなたの例では、それらのエッジの除去は満足するでしょう。 – user3857787

任意のルートを選択してください。各サブツリーのサイズを計算するためにポストオーダートラバーサルを行います。少なくとも兄弟と同じ大きさのサブツリーを持つ子を経由してルートから降順にすると、（n-1）/ 3と2（n-1）/ 3 + 1の排他的なサイズのサブツリーが見つかりますマイナス1を2で割って減少しています）。親の端を切り離す。

出典

2017-02-21 15:51:22

問題は、最初の条件が真である必要はありません。（私は思う） –

@ ShihabShahriarもっと具体的にする必要があるだろう。 –

答えて

関連する問題