2017-10-28

ぱらぱらめくる『Graphs and Matrices』2 Incidence Matrix

2.1 ランク
- 有向グラフGのn個のノードと、m個のエッジ。nxm行列で、エッジの始点と終点とを1,-1で表したもの、それがIncidence matrix Q(G)
- Q(G)の列和はゼロ、行ベクトルは線形非独立
- 連結グラフのランクはn-1、k個の連結グラフの集合ならランクはn-k
- k個の連結グラフが、ノード数n1,...,nkであるとき、グラフ全体のIncidence matrixは、行・列をうまく並べることで、ni-1ランクの行列を対角に並べたものとできる
- サイクルの無いグラフであるであるのは、列ベクトルが線形独立であることとiffの関係
2.2 Minors
- グラフのIncidence matrix Q(G)は totally unimodularである。ただし、totally unimodularとは、行列の正方部分行列のすべてのdeterminantが0,1,-1のいずれかであること
- グラフが木のとき、Q(G)のオーダーn-1の部分行列のすべてがnonsingular
- nxn行列Aの中に、pxqのゼロ行列があり、pxq >= n+1 ならdet A = 0
- Incidence matrixの部分行列はグラフのincidence matrixとは限らない。incidence matrixの部分行列が表すのはグラフの部分構造なので、substructureと呼ぶ。エッジは含まれるがそれに対応する２ノードの片方しか含まれない、とかそういう感じ
2.3 Path matrix
- パスに含まれないエッジは0、含まれるエッジには、パスの向きとエッジの向きとの関係に応じて1,-1を付与する
- 木はn個のノード、n-1本のエッジからなるから、木グラフのIncidence matrixはn x (n-1)
- 今、第n番目のノードをルートノードとしたときに、1,...,(n-1)のノードのそれぞれからn番ノードへのpathに応じた0,1,-1で表したパスをとり、それを列ベクトルとした行列*1 を考える。これがpath matrix $Pn$ 。Q(G)はn x (n-1)行列だが、この第n行を取り除いた $Q(G)_n$ を考えると、 $Q(G)_n^{-1} = Pn$ だという。
2.4 Integer generalized inverses
- 整数行列のgeneralized inverseは、整数行列と限らないが、ある条件を満たすと、g-inverseの中に整数行列が含まれる
- 正方整数行列は、determinantが1か-1のとき、unimodularと呼ばれるが、unimodularな整数正方行列がnonsingularなとき、逆行列は整数行列である
  - determinantとadjointの関係 ( $A^{-1} = \frac{1}{detA} (a_{ij})$ 、ただし $a_{ij} = (-1)^{i+j} detA(i|j)$ )から

> m <- matrix(c(2,1,3,2),2,2)
> m
     [,1] [,2]
[1,]    2    3
[2,]    1    2
> det(m)
[1] 1
> solve(m)
     [,1] [,2]
[1,]    2   -3
[2,]   -1    2

- m x n 整数行列をm x m unimodular 行列とn x n unimodular 行列とで、ランク分の対角正整数行列とをサンドイッチした積に分解できる
- グラフ関連の行列では、要素が整数たるべし、ということが多いので、それを分解したりするときに、整数行列の範囲で処理できるのがよい。それを満足する特徴としてunimodularなどの性質とリンクして理解する必要がある
- Moore-Penrose inverseの整数
2.6 無向グラフのIncidence matrix (成分が0,1)
- サイクルグラフの場合、頂点数が偶数ならIncidence matrixのdeterminant=0、奇数なら2
- 連結グラフのとき、二部グラフならランクはn-1、そうでなければn
- Substructureを考えると、ゼロ行、ゼロ列があるとき、それは、そのstructureに孤立ノード、両端ノードが含まれていないエッジが存在することに対応する
2.7 Matchings in bipartite graphs
- この無向グラフのIndicence matrixはTotally unimodularである

*1:n-1) x (n-1