ぱらぱらめくる『Graphs and Matrices』大雑把なまとめ

  • グラフはノードとエッジでできており、それにIDを振ると色々な行列が出来る
  • 行列は正方行列と非正方行列とがある
    • 非正方行列の代表はIncidence matrix(ノードとエッジの関係を表した行列)
    • 正方行列はノードxノードの行列があり、いろいろある
  • グラフの特徴を現した行列では、すべての要素の順番を入れ替えても変わらない性質が大事である。なぜなら、ノードは相互に対等であるから
  • したがって、グラフの特徴を現した行列におけるそのような性質を問題にする。そのような性質はトレースと行列式固有値と固有空間
  • 非正方行列の場合には一般化逆行列を考える
  • グラフを表す行列としてこの本では以下を考える
    • Incidence Matrix
    • Adjacency Matrix
    • Laplacian Matrix
    • Distance Matrix
    • Resistance Matrix