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

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

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 - 暇つぶし2ch■コピペモード
□スレを通常表示
□オプションモード
□このｽﾚｯﾄﾞのURL
■項目テキスト

85:デフォルトの名無しさん
 22/09/26 20:52:32.58 Sp/QOOjd.net
英語だけどイラスト付きで分かりやすく書いてある 
https://medium.com/enjoy-algorithm/lower-bound-of-comparison-sorting-c3e2225e3419

86:デフォルトの名無しさん
 22/09/26 21:50:30.08 cqAm7B1L.net
>>85 
ありがとうございました。

87:デフォルトの名無しさん
 22/10/17 16:05:05.43 BBjAlznw.net
命題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 は上の有向閉路には含まれないからこれは矛盾である。

次ページ