接続行列
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/07 14:03 UTC 版)
数学において、接続行列（せつぞくぎょうれつ、英: Incidence matrix）は、2つのオブジェクトクラス間の関係を示す行列である。1つ目のクラスをX、2つ目をYとすると、接続行列は、Xのそれぞれの要素について1つの行を、Yのそれぞれの要素について1つの列を持つ。行xおよび列y中の成分はxおよびyが関連（この文脈においてincidentと呼ばれる）しているならば1であり、関連していないならば0である。以下に示すように変種が存在する。
グラフ理論
接続行列はグラフ理論において頻繁に使われる。
無向グラフと有向グラフ
グラフ理論において無向グラフは2種類の接続行列、非向き付け (unoriented) 接続行列と向き付け (oriented) 接続行列を持つ。
無向グラフの「非向き付け接続行列」（または単に「接続行列」）はn × m行列Bである（nおよびmはそれぞれ頂点および辺の数）。頂点viと辺ejが接続しているならばBi,j = 1、それ以外は0である。
例えば、右に示す無向グラフの接続行列は4つの行（4つの頂点1–4に対応）と4つの列（4つの辺e1–e4に対応）から構成される行列である
|
= |
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/09/13 00:05 UTC 版) M e v = { 1 , if v = i − 1 , if v = j 0 , otherwise . {\displaystyle M_{ev}=\left\{{\begin{array}{rl}1,&{\text{if }}v=i\\-1,&{\text{if }}v=j\\0,&{\text{otherwise}}.\end{array}}\right.} によって与えられる辺e（頂点iとjを連結している; i > j）と頂点vについて要素Mevを持つ | e | × | v | {\textstyle |e|\times |v|} 有向接続行列Mを定義する。 次に、ラプラシアン行列Lは L = M T M , {\displaystyle L=M^{\textsf {T}}M\,,} を満たす（ M T {\textstyle M^{\textsf {T}}} はMの転置行列）。 ここで、単位ノルム固有値ベクトル v i {\textstyle \mathbf {v} _{i}} および対応する固有値 λ i {\textstyle \lambda _{i}} を使った L {\textstyle L} の固有値分解を考える。 λ i = v i T L v i = v i T M T M v i = ( M v i ) T ( M v i ) {\displaystyle {\begin{aligned}\lambda _{i}&=\mathbf {v} _{i}^{\textsf {T}}L\mathbf {v} _{i}\\&=\mathbf {v} _{i}^{\textsf {T}}M^{\textsf {T}}M\mathbf {v} _{i}\\&=\left(M\mathbf {v} _{i}\right)^{\textsf {T}}\left(M\mathbf {v} _{i}\right)\\\end{aligned}}} λ i {\textstyle \lambda _{i}} はベクトル M v i {\textstyle M\mathbf {v} _{i}} とそれ自身の内積として書くことができるため、これは λ i ≥ 0 {\textstyle \lambda _{i}\geq 0} であり、したがって L {\textstyle L} の固有値は全て非負であることを示す。 ※この「接続行列」の解説は、「ラプラシアン行列」の解説の一部です。 辞書ショートカット カテゴリ一覧 すべての辞書の索引
接続行列のページの著作権
ビジネス｜業界用語｜コンピュータ｜電車｜自動車・バイク｜船｜工学｜建築・不動産｜学問 ©2025 GRAS Group, Inc.RSS
|
