6.2.14
定理6.2.14．行列 \(A \in M_n\) に対して、\(A\) が SC 性を持つことと、有向グラフ \(\mathcal{G}(A)\) が強連結であることは同値である。
演習．前記定理を証明せよ。
演習．有向グラフ \(\mathcal{G}\) の各ノードのペアが少なくとも1つのサイクルに属している場合、なぜ \(\mathcal{G}\) が強連結であるか説明せよ。行列
\begin{bmatrix}
0 & 1 & 0\\
1 & 0 & 1\\
0 & 1 & 0
\end{bmatrix}
を考え、逆の含意の反例を示せ。
有向グラフにおいて、与えられた2つのノード間に複数の有向経路が存在する場合がある。しかし、異なる長さを持つ2つの経路は本質的に異ならない場合もある。経路の途中で同じノードを2回訪れる場合、最初と2回目の訪問の間にある中間の弧をすべて削除することで（サイクルを含む部分グラフを削除する）、経路の長さを短縮できる。この操作により端点は変わらない。
行列解析の総本山
[行列解析]総本山
行列解析の総本山。行列解析の内容を網羅的かつ体系的に整理しています。線形代数の学習を一通り終えた方が、次のステップとして取り組むのに最適です。行列に関する不等式を研究するには、行列解析の知識が欠かせません。
am-gm.com
2025.08.05
コメント