Dinicのアルゴリズム

ディニッツと呼ぶ。ディニックではないらしい。

グラフ$$G:=(V,E,c)$$に対して、最大流問題を解いて最大フロー$$f$$を求めるアルゴリズム

$$\mathrm{O}(|E||V|^2)$$？

事前定義

トポロジカルソート

DAGの頂点列のうち、全ての有向辺に関して始点が終点よりも先行して現れる系列を求めるアルゴリズム

深さ優先探索(後行順)をして得られる系列の逆順がちょうどこれにあたる。

DFS(後行順)のラベル付の性質による

子孫が祖先よりも先に探索される。

from コード理論

平行調

長調(全全半全全全半)の音程は、自然短音階(全半全全半全全)の第三音程を始点としたものと等しい。

つまり、自然短音階の第3音からスタートすると、長調になる。

つまり、メジャースケールの音を、本来の始点から低い方へ3度移動した音を始点としたものは、ナチュラルマイナースケールとなる。