私は来週のクラステストの改訂のために私の本のすべての演習を行っています、そして私はこのサブグラフの質問について本当に混乱しています。
現在、私の考えでは、最小スパニングツリーGがすでに存在するため、その最小スパニングツリーにサブノードが存在するため、G'が存在する必要があると考えています。状態に関する限り、私は少し途方に暮れています。
グラフX'は、X'のノードセットとエッジセットがそれぞれXのノードセットとエッジセットのサブセットである場合、グラフXのサブグラフです。Gの最小全域木として（V、T）を持ち、G'=（V'、E'）をGの接続された部分グラフとします。
（a）（V'、E'∩T）がG'の最小全域木の部分グラフであることを証明します。
（b）（V'、E'∩T）はどのような条件下でG'の最小全域木ですか？あなたの主張を証明してください。
前もって感謝します！
(a) コメントで述べたように (V', E' ∩ T) には複数のコンポーネントが含まれる場合があります。一般に、G' の最小全域木にはより多くのエッジが必要になります。問題は、E' ∩ T で既に与えられている、使用されないエッジがあるかどうかです。したがって、この問題は、E' ∩ T ⊂ T' となる G' の最小全域木 (V', T') の存在として言い換えることができます。
Kruskal のアルゴリズムを使用した証明を次に示します。そしてその正しさの証明。Kruskal のアルゴリズムにおける重みによるエッジの列挙は決定論的ではありません。エッジは重みでソートされますが、重みが等しいエッジの列挙は非決定論的です。しかし、すべてのスパニング ツリーには、最小スパニング ツリー (V,T) を生成するエッジの単調な列挙があります。E_x を重み x のすべてのエッジのセットとします。順序付けの場合、E_x ∩ T のすべてのエッジが E_x \ T のエッジの前に来るように、任意の順序を選択します。E_x ∩ T のエッジは、それらが検査されるクラスカルのアルゴリズムのステップでサイクルを形成しません。究極の最小スパニング ツリー。順序はサイクルの非存在を変更しないため、それらがどの順序で表示されるかは問題ではありません。次に、 E_x \ T のすべてのエッジは、サイクルを形成するため破棄されます。
次のステップでは、与えられた G の最小全域木を生成する順序付けを使用して、G' に対してクラスカルのアルゴリズムを再度実行します。この木を (V', T') と呼びます。ここで重要な特性は、これを行うと、E' ∩ T のすべてのエッジが他のエッジの前に追加されることです。逆に、いくつかのエッジ t ∈ E' ∩ T が G' の実行で棄却されると仮定します。これは、循環を形成するためです。これは、(V,T) の計算時にエッジ t が最初に接続された 2 つのコンポーネント間の接続が、一部のチェーン C によって既に形成されていることを意味します。もしそうなら、その同じチェーンは元の実行でそれらのコンポーネントを接続していたでしょうが、そうではありませんでした. ここで、進行中のツリーに E_x ∩ T のエッジを追加した直後の時点での G' 上のクラスカルのアルゴリズムの状態を考えてみましょう。クラスカルの何か
(b) この部分は、主に (a) の結果、つまり、エッジ セット E' ∩ T が、クラスカルのアルゴリズムの実行のある時点で常に有効な状態であるという観察結果です。したがって、アルゴリズムがその時点で終了した場合、つまりエッジのセットが使い果たされた場合、E' ∩ T はまさに最小全域木のエッジです。この状態でアルゴリズムが終了することが条件なので、(V', E' ∩ T) が接続されるとクラスカルのアルゴリズムは終了し、(V', E' ∩ T) は最小全域木になります。逆に、(V', E' ∩ T) が最小全域木である場合、必ず連結されます。
(a) のために
質問がよくわかりません...説明していただけますか？
(b)の場合
ならそうだと思う
for every e=(u,v)in T if u in V'and v in V'thene in E
(V′,E′∩T)の最小スパニング ツリーが得られG'ます。
コズ：
eているがに含まe=(u,v)れていないものがあるT 場合、
はまったく接続されていません。それは確かにのスパニングツリーになることはできませんu in V'v in V'in E'(V′,E′∩T)G'(V′,E′∩T)がありG'、それG'が であるとしましょうTg。より少ないコストでのスパニング ツリーT'を構築できます 。結果のグラフは のスパニング ツリー( のエッジの数が同じで接続されているため) であり、 よりもコストが低くなります。が の最小全域木であることは既にわかっているため、このようなことはあり得ません。GTe=(u,v) , u in V' and v in V' and e in TTe=(u,v) , u in V' and v in V' and e in TgGTTTT私はせっかちな人のために非公式のtl;drバージョンを提供します:)eh9は賞金に値します
a-Tが持つ可能性のあるすべてのエッジとの交差によって形成されるv'のスパニングツリーが存在します。E'∩Tは必然的にこれのサブセットです
b-条件は（V'、E'∩T）が接続されているときです。E'の非最小エッジとサイクルはTとの交点によって破棄され、残りの最小連結グラフはMSTです。
部分 'a' は、最小スパニング ツリー ( など(V,T)) が実際に最小であるという観察からほとんどすぐに続きます。以下は、証明の一部のスケッチです。
最小で(V′,E′∩T)はない矛盾を仮定します。これはe in E′∩T、接続性を維持しながら削除できるものがあることを意味します。これは、 も T から削除できることを意味しますが、は最小eであるため、明らかに削除できません。T
パート 'b' については、lavin がまともな解決策を提供してくれたと思います。これが役立つことを願っています。