どのようにグラフを2縮退するか?

私は、「カラフルなグラフモチーフ」から「2縮退シュタイナーツリー」にPPT(多項式時間短縮)を示さなければなりません。入力グラフは2縮退でなければならないが、ここでは通常のグラフG(つまり、基本的にはカラフルグラフモチーフのインスタンス)である。だから、Gを2縮退グラフG
‘に変換する方法は?

ベストアンサー

すべてのエッジを2つのエッジのパスで置き換えます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です