5 Cycles and Cuts ぱらぱらめくる『Graphs and Matrices』

• Incidence matrix Qのnull spaceをcycle subspace、Q^Tのnull space を cut subspaceと呼ぶ
  • edgeのセットをうまく取り出して足し合わせると、キャンセルアウトするのがcycleなので、incidence matrixのcolumnsの線形和でゼロベクトルができれば、その線形和を表すベクトルはサイクルに相当する。cutはそのノードとエッジの取り換え版
• 5.1, 5.2 Fundamental cycle, fundamental cut, fundamental matrices
  • グラフにspanning treeをとり、そのtreeでのノード間パスを取る。それにtreeに含まれないエッジを渡すとサイクルができるが、それがfundamental cycle
  • グラフのspanning treeからエッジを１つ取り除くとノードが2群にcutされる。これがfundamental cut
  • fundamental cycles, cutsと関係する行列: fundamental matrices。木のエッジを行に、グラフ全体のエッジを列にとる