ランク（グラフ理論）

数学の一分野であるグラフ理論では、無向グラフのランクには2 つの無関係な定義があります。nをグラフの 頂点の数とします。

• グラフの行列理論では、無向グラフの階数r は、その隣接行列の階数として定義されます。

同様に、グラフのヌル性はその隣接行列のヌル性であり、 n − rに等しくなります。

• グラフのマトロイド理論では、無向グラフのランクはn − cと定義され、c はグラフの接続要素の数です。 ^[1]同様に、グラフのランクは、グラフに関連付けられた有向接続行列のランクです。^[2]

同様に、グラフのヌル性は、その有向接続行列のヌル性であり、式m − n + cで与えられます。ここで、nとc は上記のとおりで、m はグラフ内の辺の数です。ヌル性は、グラフの最初のベッチ数に等しくなります。ランクとヌル性の合計が辺の数です。

サンプルのグラフとマトリックス:

（4つの辺e1～e4に対応）：

この例では、列ベクトルが線形独立であるため、行列の行列理論ランクは 4 です。

• サーキットランク
• サイクルランク
• ヌル性（グラフ理論）

• 陳偉凱（1976）、応用グラフ理論、ノースホランド出版社、ISBN 0-7204-2371-6。
• Hedetniemi, ST, Jacobs, DP, Laskar, R. (1989)「グラフのランクに関する不等式」Journal of Combinatorial Mathematics and Combinatorial Computing、第6巻、pp. 173–176。
• Bevis, Jean H.、Blount, Kevin K.、Davis, George J.、Domke, Gayla S.、Miller, Valerie A. (1997)「頂点追加後のグラフのランク」線形代数とその応用、第265巻、pp. 55–69。