前回の続き．なぁ漂識，音ゲーはどうした？音ゲーマーが音ゲーやらなかったら，音ゲーマーじゃないだろ！…いやまぁ，気になったことがあったらたまにはそっちに手出しちゃうこともあるでしょ～♪そんな感じのアレです，というわけでやっていきます．
読書中の独り言，脳内を書き殴っていくスタイルで，内容や式の紹介は魅力を感じたり，ここで俺が書かなきゃ俺は死ぬ！と思わない限りは省略していきます．気になる方は是非本書を手に取ってください．薬はやってません．
一章の内容
ネットワーク符号化の概念や，従来の符号化との比較を行っている．
hydroyourseason.hatenablog.com
二章
ネットワーク符号化の理論化を進めていくうえで必要になる道具を紹介している．
有限体
二元体GF(2)の拡大体と，拡大体上での和積に関する話が書いてある．特に今更確認することはないかな…．
ネットワークの最大流問題
表記が"流"になったり，"flow..."になったり大変ね！𝑶𝑹𝑩𝑰𝑻𝑨𝑳𝑰𝑪...
誰にも見えるはずがない。
人も流れ、時も流れ、周りも環境も流れ、自分自身流されてるのに、
速いのか遅いのかもわからない。
でもそれこそが全ての証だから、その行き先に価値なんてない。
ニコニコにはこんなmadがある．超 越 世 界．2KBさんのmadは他にも面白いものがあるので，暇があったら覗いてみよう．
それはさておき．流れ*1は，ネットワークの多品種flow...問題を考えるために，前提知識を積んどこうね！って感じ．福運積もう！*2この記事，大丈夫か？
最大流最小カット定理
何これ？必殺技？つよそう．自分は次のページで概念を理解しました．
Wikipediaではなくニコニコ大百科を引用してしまい，すいません．ニコ厨なので…．しかし，分かりやすい．とりあえず，何らかのグラフが与えられたとき，そのグラフのカットの容量の最小値は，最大流であるという主張が，最大流最小カット定理なのだそう．では，どうやったら最大流あるいは，容量を最小にするようなカットを得られるかが問題になってくるが，本書では最大流を求めるアルゴリズムとしてフォード-ファルカーソン法が紹介されている．
最大流を求めるアルゴリズム:フォード-ファルカーソン法
can't afford to buy a Ford... (システム英単語，1998)
名前でいじるのはよくない．これを実装できたら二章は大体把握したと言えるでしょう．とりあえず，
- ネットワークとフローの定義，性質を理解して
- それらをプログラム上で表現し，
- アルゴリズムを実現する．
ことにしようかね．
ネットワークとフロー
…．TeXなんかで書いて，真面目か？爆ﾜﾗ🤣
歪対称性はネットワーク上の流れを定義し，容量制限は名前の通り，あるリンク上を通過できる情報量はリンクの容量を超えないという性質を反映している．フロー保存則は，中継ノード*3に流入するフローの総量とそのノードが流出するフローの総量は等しいことを示している．もうちょっと詳しく知りたかったら，wikipediaを覗こう．風呂もフローも似たもんやねｗ
最大流問題
フローの流量とは，ソースノード，つまりネットワークの開始地点から一度に流す情報量のこと．ネットワーク上で情報を詰まることなく流せる最大のフローの流量を求めるのが，最大流問題．例を考えよう．たとえば，v1をソースノード，v6をシンクノードとする次のようなネットワークが存在したとする．
このネットワークに対して，次のようにフローを定義すると，これは最大流問題の制約条件を満たしている．
上二つのネットワークを見比べると，各リンク上のフローはリンク容量を超えることがなく，中継ノードでの流入量と流出量は保存されている．このときのフローの流量は8であるが，これは最大だろうか？それを考えるのが最大流問題．
カット，カット容量，最小カット
ワラキアの夜*4ではない．余談はさておき，カットとは何か？それは，ノード集合を排反に分割したときに消滅するリンクの部分集合で定義される．そして，カットの容量は，カットに含まれるリンクがもつ容量の総和で定義される．また，カット容量を最小にするようなカットを最小カットという．最小カットとフローの流量の最大値が一致する，というの最大流最小カット定理の主張やよ．
カットに関してもう一つ．カットに含まれるリンク上のフローの総和のことを，カットを横切るフロー(flow across the cut)という．任意のフローに対して，任意のカットを横切るフローじゃフローの流量に等しい．証明は易しい．これは，どこでネットワークを分断しても，切り口から流れ出る量は，ソースノードに流し込んだ量に一致する，ということを言っている．
フォード-ファルカーソン法
以下の記事が参考になるかもしれません．
私が日頃から作っているMathematicaは，最大流を計算してくれる関数が存在するので，そちらでズルをしてしまいました．こういうことをしているからコードが書けなくなる…．
