0

これは質問です、私はこれが宿題の質問であることを認めます、私は答えを探していませんが、むしろ私が正しい方向に進んでいるかどうか、そして私が親切に正しい方向に私を向けていないかどうかを知りたいです。

質問：重み付きグラフの2つのエッジに同じ重みがない場合、頂点vに付随する重みが最小のエッジがすべての最小全域木（MST）に含まれることを示します。

私の答え：頂点（V）と重み付きグラフ（G）が与えられた場合、∃（存在する）とエッジ（E）がVに関連付けられていることに注意してください。これは、最も重みの少ないエッジです。同じ最小重みのエッジを持つ2つの異なる頂点があることに注意してください。これは私たちにとって問題ではありません。頂点の1つが最小全域木に含まれている場合、もう1つは問題になります。MSTの構築を開始した場合、MSTを取得するには、エッジが最小の頂点の1つ（または両方）を含める必要があるため、ある場合には、重みが最小のエッジをMSTに含める必要があります（ MSTは、ルートからすべての頂点への最短経路を見つける必要があると述べています）

私の答えが正しいかどうかはわかりませんが、それで十分であることをどのように証明できると思いますか？

4

2 に答える 2

2

あなたの証明は有効ではありません、そしてその理由はあなたの証明に多くの不正確な声明といくつかの虚偽があるからです。たとえば、「MSTの定義では、ルートからすべての頂点への最小パスを見つける必要がある」と述べていますが、MSTの定義では、最小重みのスパニングツリーであるとしています。

「エッジが最小の頂点」がMSTに含まれている必要があるという事実を使用しますが、すべての頂点がMSTに表示されるため（スパニングツリーの定義から）、関連性を確認するのは困難です。

証明を書くスキルは、あなたの言語で非常に正確であり、証明したものに続く論理的なステップを作成することです（または、よく知られている定理を適用している場合は、良い引用です）。使用している専門用語の正確な定義（ここでは、おそらく「最小」と「スパン」と「ツリー」）を理解して使用することが非常に重要です。

この証明については、キースが言うように、矛盾して証明を試みたいと思います。つまり、最小の重みのエッジを含まないスパニングツリーがある場合は、より低い重みのスパニングツリーを見つけることができます。おそらく、最初にスパニングツリーに必要なエッジの数と、その数のエッジを持つグラフ内のすべてのツリーがスパニングツリーである必要があるかどうかを証明するのに役立ちます。証明で必要になるため、ツリーの定義も明確にする必要があります。エッジを含まないスパニングツリーを取得し、何らかの方法で変更して、重みが小さく、まだ残っていることを示します。スパニングツリー。

于 2011-11-28T07:08:46.520 に答える
1

それは私には証拠のようには聞こえません。あなたは、頂点が含まれるという考えから、エッジが含まれている必要があることを証明することなく、エッジが含まれるという考えに飛躍しているようです。あなたはおそらく矛盾による証明の線に沿って何かをもっと考えるべきです。

于 2011-11-28T06:09:25.543 に答える