データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上
下
前
次
1-
新
87
: 2022/10/17(月)16:05
ID:BBjAlznw(1/2)
AA×
[
240
|
320
|
480
|600|
100%
|
GIF
|
べ
|
ﾚｽ栞
|
ﾚｽ消
]
87: [] 2022/10/17(月) 16:05:05.43 ID:BBjAlznw 命題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 は上の有向閉路には含まれないからこれは矛盾である。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/87
命題 始点 から各頂点へ最短路が存在すると仮定するこのとき を根とする 有向全域木 が存在して における から頂点 への有向路は から 頂点 への最短路となっている 証明 始点 から各頂点 への最短路の枝集合を とし とおく 定理と命題より は単純有向路としてよい の要素数がちょうど であれば これは有向全域木であり各頂点への最短路を含む一方 の要素数が 以上の場合は 以下の手順で最短路を繰り返し修正することにより所望の有向全域木を求めることができる の要素数が 以上と仮定するこのときある頂点 が存在して の中には に向かう枝がつ以上ある に向かう枝がつ以上あることの証明ですがどのような証明が典型的なものと考えられますか？ 証明 を無向グラフと考えたとき は連結であり だから無向閉路が存在する の作り方から に向かう枝は存在しないから はこの無向閉路上にはない 仮に上の が存在しないと仮定する を 上の無向閉路上の任意の頂点とする の定義により の中には へ向かう枝が存在するが 仮定によりそのような枝は唯一つしか存在しないゆえにこの無向閉路を有向グラフとして考えた とき有向閉路である の作り方から から への有向路が存在する ところが は上の有向閉路には含まれないからこれは矛盾である
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 18 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
ぬこの手
ぬこTOP
0.045s