ﾚｽ書き込み

ｽﾚへ戻る 写 ﾚｽ栞 ﾚｽ消

---

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4

PC,ｽﾏﾎ,PHSは ULA べっかんこ 公式(ｽﾏﾎ) 公式(PC) で書き込んでください｡

名前
ﾒｰﾙ
引用切替：ﾚｽｱﾝｶｰのみ
>>87 > 命題2.4： > 始点 s から各頂点へ最短路が存在すると仮定する。このとき、 s を根とする > 有向全域木 T が存在して、 T における s から頂点 v への有向路は、 s から > 頂点 v への最短路となっている。 > > 証明： > 始点 s から各頂点 v への最短路（の枝集合）を P_v とし、 T = ∪_{v ∈ V} P_v とおく。 > 定理2.3と命題2.2より、 P_v は単純有向路としてよい。 T の要素数がちょうど n - 1 であれば、 > これは有向全域木であり、各頂点への最短路を含む。一方、 T の要素数が n 以上の場合は、 > 以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。 > T の要素数が n 以上と仮定する。このとき、ある頂点 v_* ∈ V - {s} が存在して、 T の中には > v_* に向かう枝が2つ以上ある。 > … > > v_* に向かう枝が2つ以上あることの証明ですが、どのような証明が典型的なものと考えられますか？ > > 証明： > T を無向グラフと考えたとき、 T は連結であり、 #T = n だから無向閉路が存在する。 > T の作り方から s に向かう枝は存在しないから、 s はこの無向閉路上にはない。 > 仮に、上の v_* が存在しないと仮定する。 > v を 上の無向閉路上の任意の頂点とする。 T の定義により、 T の中には v へ向かう枝が存在するが、 > 仮定により、そのような枝は唯一つしか存在しない。ゆえに、この無向閉路を有向グラフとして考えた > とき、有向閉路である。 > > T の作り方から、 s から v への有向路が存在する。 > ところが、 s は上の有向閉路には含まれないからこれは矛盾である。
ﾛｰｶﾙﾙｰﾙ SETTING.TXT

---

他の携帯ﾌﾞﾗｳｻﾞのﾚｽ書き込みﾌｫｰﾑはこちら｡書き込み設定で書き込みｻｲﾄの設定ができます｡
・ULA
・べっかんこ(身代わりの術)
・べっかんこ(通常)
・公式(ｽﾏﾎ)
・公式(PC)[PC,ｽﾏﾎ,PHS可]

---

書き込み設定(板別)で板別の名前とﾒｰﾙを設定できます｡

---

ﾒﾓ帳

(0/65535文字)

---

上下板覧索設栞歴

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.016s