非平面グラフに最小全域木はありますか? プリム アルゴリズムと三角形の不等式について読みましたが、グラフが三角形の不等式を満たしていませんか?
1 に答える
1
ここでプリムのアルゴリズムについて読んだ正しさの証明では、三角形の不等式は一度も使用されませんでした。したがって、プリムのアルゴリズムは非メトリック グラフ (三角形の不等式を満たさないもの) に対しても有効である必要があります。したがって、プリムのアルゴリズムを適用して、接続された重み付き無向グラフの MST を見つけることができます。
于 2013-06-11T06:06:23.210 に答える