無効性（グラフ理論）

数学の分野であるグラフ理論におけるグラフの無効性は、無関係な 2 つの数のいずれかを意味します。グラフにn 個の頂点とm個の辺がある場合、次のようになります。

• グラフの行列理論では、グラフのヌル性はグラフの隣接行列 A のヌル性です。A のヌル性は n − rで与えられ、 rは隣接行列の階数です。このヌル性は隣接行列のスペクトルにおける固有値0の多重度に等しくなります。Cvetkovič と Gutman (1972)、Cheng と Liu (2007)、および Gutman と Borovićanin (2011) を参照してください。
• マトロイド理論では、グラフの無効性は、グラフに関連付けられた有向接続行列 Mの無効性です。 Mの無効性はm − n + cで与えられます。ここで、c はグラフの要素数、n − c は有向接続行列の階数です。この名前はほとんど使用されません。この数は、グラフのサイクル階数、サイクロマティック数、または回路階数としてよく知られています。これは、グラフの共グラフマトロイドの階数に等しくなります。また、これは、 L = D − Aと定義されるグラフのラプラシアン行列の無効性と等しく、ここでD は頂点次数の対角行列です。ラプラシアン無効性は、 L = M M ^T ( M自身の転置)であるため、サイクル階数に等しくなります。

• ランク（グラフ理論）

• Bo Cheng と Bolian Liu (2007)、「グラフのヌル性について」、 Electronic Journal of Linear Algebra、vol. 16、article 5、pp. 60–67。
• Dragoš M. Cvetkovič および Ivan M. Gutman (1972)、2 部グラフのスペクトルにおける数値ゼロの代数的多重度。Matematički Vesnik (ベオグラード)、vol. 9、141–150ページ。
• Ivan Gutman および Bojana Borovićanin (2011)、「グラフの無効性: 最新の調査」、 Zbornik Radova (Beograd)、第 14 巻、第 22 号 (グラフ スペクトルのアプリケーションに関する選択されたトピック)、pp. 137–154。