6.4.17.補題：前順序集合における極大要素の存在と有向グラフの非自明サイクル
補題 6.4.17
非空有限集合 \(S\) に前順序 \(R\) が定義されているとする。このとき、\(S\) は少なくとも1つの極大要素を含む。
証明：
集合の要素を任意の順序で \(s_1, s_2, \ldots, s_k\) と並べる。はじめに \(s = s_1\) とする。もし \(s_2 R s\) が成り立つなら \(s\) をそのままにし、そうでなければ \(s = s_2\) と置く。次に、もし \(s_3 R s\) が成り立つならそのままにし、そうでなければ \(s = s_3\) と置く。この操作を \(s_4, \ldots, s_k\) まで順に続ける。最終的に得られる \(s\) が極大要素である。■
次に、有向グラフ \(\Xi\) を考える。ノード \(P_i\) に対して、\(\Xi_{\text{out}}(P_i)\) を、\(P_i\) から長さ1の有向経路で到達できる、\(P_i\) とは異なるノードの集合と定義する。
\(\Xi\) が弱連結（weakly connected）であるならば、各ノード \(P_i \in \Xi\) に対して、\(\Xi_{\text{out}}(P_i)\) は空ではないことに注意する。
ここで、有向グラフ \(\Xi(A)\) における非自明な閉路（サイクル）の集合を \(C(A)\) と表す。
行列 (6.4.13) に対しては、\(C(A)\) は1つのサイクル \(\gamma = P_1P_2, P_2P_1\) からなる。 行列 (6.4.15) に対しては、長さ2の非自明サイクルが3つ存在する。 また、行列 (6.4.15a) に対しては、非自明サイクルが2つ存在し、そのうち1つは長さ2、もう1つは長さ3である。
行列解析の総本山
コメント