431 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 05:10:12.09 ID:6P8PW2pA
>>430 そのインド人の本は、アルゴリズムの正当性のまともな説明がありません。
計算量の評価についてもまともな説明がありmせん。
セジウィックのAlgorithms 4th Editionはいい本ですが、計算量の評価については
まともな説明がないように思います。
432 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 05:17:01.98 ID:6P8PW2pA
D40
T をグラフ G の全域木とする。
C を G のサイクルとする。
AB を C および T に含まれる辺とする。
このとき、 T から AB を除去し、辺 UV を追加したときに、
依然として G の全域木であるような辺 UV が C の中に
含まれることを示せ。
433 名前:デフォルトの名無しさん[] 投稿日:2017/06/28(水) 06:24:05.46 ID:6P8PW2pA
>>432 T は木であるからサイクルを含まない。
よって、 C には T に含まれないような辺が少なくとも一つは存在する。
T は全域木であるから、そのような辺の両端点を結ぶ T の辺のみからなる(一意的な)パスが存在する。
仮に、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちがすべて AB を含まない
と仮定すると、 A から B への T の辺のみからなるパスで辺 AB を含まないようなものが存在することになる。
A, B という A から B へのパスは、辺 AB を含み T の辺のみからなる。よって、 A から B への T の辺のみから
なるパスが2つ以上存在することになるが、これは木の性質に反する。
よって、 T に含まれないような C の辺たちの両端点を結ぶ T の辺のみからなるパスたちの中には、 AB を含む
ようなものが存在する。そのようなパスを U, …, A, B, …, V とする。 T から AB を除去し、辺 UV を追加し
たときにできる部分グラフは明らかに T と同じ数の辺をもち、依然として連結なままである。点の数が v で
辺の数が v - 1 であるような連結なグラフは木であるから、そうような部分グラフは木である。