輪講：アルゴリズムデザイン（第2回）
月曜の輪講のメモです。第1回はこちら↓
輪講：アルゴリズムデザイン（第1回）
今回は、前回証明できなかったところの証明(アルゴリズム4.1、4.2、4.3)と、最小全域木の証明までです。（〜p136）
アルゴリズム4.1 区間スケジューリング
問題
それぞれ開始時間s(i)と終了時間f(i)がある、n個の要求集合{1,2,...,n}に対し、できるだけ多くの要求を処理できるようにスケジューリングをします。
アルゴリズム
f(i)が最小の要求から順に処理します。処理した要求の集合をAとします。
証明
証明することは、以下の二つです。
（4.1）Aに含まれる要求は、どの二つも同時に処理されることはない（共存可能）である。
（4.3）Aは最適解である。
まず、(4.1)共存可能について。この証明は本では省略されています。アルゴリズムでは要求iを選択してAに加えたあと、iと同時期に処理しなければならない要求を、解となる集合Aの候補から除いています。そのため共存関係になることはありません。
次に、(4.3)について。最適解である要求集合をOとします。本当はA=Oを示したいのですが、最適解Oはパターンが複数考えられるため、Oで処理する要求数とAの要求数が等しいこと（|O|=|A|）を示します。そのために、最適解Oが受理した要求を処理した順番にO={j_1,j_2,...,j_m}、同様にAも処理した順にA={i_1,i_2,...,i_k}とします。これに対し、r ≦ kに対してf(i_r) ≦ f(j_r)が成り立ちます（命題（4.2））。命題（4.2）はrに関する帰納法で証明しました。
（4.3）は、背理法を用いて証明します。「Aより多くの要求を含む最適な集合Oが存在する、つまりk < m となるOが存在する」を仮定し、これを命題（4.2）を用いて棄却しました。
アルゴリズム4.2 区間分割アルゴリズム
問題
それぞれ開始時間s(i)と終了時間f(i)があるn個の要求集合{1,2,...,n}に対し、同時に処理している要求数dができる限り少なくなるようにスケジューリングをします。（どの要求がどの資源で処理されているのかを、ラベル{1,2,...,d}を付与します。）
アルゴリズム
開始時刻時刻s(i)が早い順番に探索します。要求iについては、時刻s(i)の時点で処理されているどの要求も持っていないラベルを付けます。
アルゴリズム4.3 遅延最小化スケジューリング
問題
要求iに対し、期限d_iがある要求集合全てのスケジューリングを考えます。求めたいスケジュールは、期限内に終わらなかった要求（要求の終了時刻f(i) > d_iの要求）の遅延時間、(f(i)-d_i)が最も長いものが、最小となるスケジュールです。
アルゴリズム
要求の期限d_iを早い順にソートし、その順番で要求に応えていきます。
最小全点木問題（最小全域木問題）
問題
グラフGを入力。Gの全頂点集合Vを含み、かつ連結であり、辺の重さの総和が最小となる部分グラフを求めます。求められる結果は木であり、最小全域木と呼ばれます。
