サーキットランク

数学の一分野であるグラフ理論において、無向グラフの回路ランク、サイクロマティック数、サイクルランク、またはヌル性は、グラフのサイクルをすべて破壊してグラフをツリーまたはフォレストにするためにグラフから削除する必要があるエッジの最小数です。これは、グラフ内の独立したサイクルの数（サイクル基底のサイズ）に等しいです。有向グラフの対応するフィードバックアークセット問題とは異なり、回路ランクrは次の式を使用して簡単に計算できます。

${\displaystyle r=m-n+c}$、

ここで、mは与えられたグラフの辺の数、nは頂点の数、cは連結成分の数である。 ^[1]また、貪欲アルゴリズムを使用するか、スパニングフォレストを補完することによって、すべてのサイクルを効率的に破る最小サイズの辺のセットを構築することも可能です。

回路ランクは、代数グラフ理論ではグラフのサイクル空間の次元として、マトロイド理論ではグラフィックマトロイドのコランクとして、位相ではグラフから導出される位相空間のベッティ数の1つとして説明できる。これは、グラフの耳分解における耳の数を数え、ほぼ木におけるパラメータ化された複雑さの基礎を形成し、コードのサイクロマティック複雑度の定義の一部としてソフトウェアメトリクスに適用されてきた。サイクロマティック数という名前で、この概念はグスタフ・キルヒホフによって導入された。^{[2] [3]}

グラフGの回路ランクは、マトロイド理論を使用して、 Gのグラフィックマトロイドのコランクとして記述できます。^{[4]マトロイドの貪欲特性を使用すると、これは、各ステップで残りのグラフの少なくとも1つのサイクルに属するエッジを選択する}貪欲アルゴリズムを使用して、すべてのサイクルを破るエッジの最小セットを見つけることができることを意味します。

あるいは、 Gのスパニング フォレストを構築し、スパニング フォレストに属さないエッジの 補完セットを選択することで、すべてのサイクルを破るエッジの最小セットを見つけることができます。

代数的グラフ理論では、回路ランクは のサイクル空間の次元でもあります。直感的には、これは回路ランクがグラフ内の独立したサイクルの数を数えることを意味すると説明できます。サイクルのコレクションが独立しているとは、サイクルの1つを他のサイクルのサブセットの対称差として形成できない場合のことです。^[1]${\displaystyle G}$

この独立閉路の数は、位相幾何学の一分野であるホモロジー理論を用いて説明することもできる。任意のグラフGは、 1次元 単体複体の例として見ることができる。単体複体は、各グラフの辺を線分で表し、これらの線分を端点で互いに接着することによって形成される位相空間の一種である。サイクロマティック数は、この複体の最初の（整数）ホモロジー群の階数である。 ^[5]

${\displaystyle r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right].}$

この位相的なつながりのため、グラフGのサイクロマティック数はGの第一ベッティ数とも呼ばれます。^[6]より一般的には、同様に定義される任意の位相空間の第一ベッティ数は、その空間内の独立したサイクルの数を数えます。

平面グラフの回路ランクの変形は、同じ頂点セットを持つ任意の平面グラフの最大可能な回路ランクで割ることによって正規化され、メッシュ係数と呼ばれます。m辺n頂点の接続された平面グラフの場合、メッシュ係数は式^[7]で計算できます。

${\displaystyle {\frac {m-n+1}{2n-5}}.}$

ここで、式の分子は与えられたグラフの回路ランクであり、分母はn頂点平面グラフの可能な最大回路ランクです。メッシュ係数は、ツリーの場合は 0 から最大平面グラフの場合は 1 までの範囲になります。 ${\displaystyle m-n+1}$${\displaystyle 2n-5}$

回路ランクは、グラフの耳分解における耳の数を制御します。耳分解とは、グラフの辺をパスとサイクルに分割したもので、多くのグラフアルゴリズムで役立ちます。特に、グラフが2 頂点連結であるためには、開いた耳分解が必要です。これは、最初のサブグラフが単純なサイクルで、残りのサブグラフがすべて単純なパスで、各パスが前のサブグラフに属する頂点で始まり、終わり、パスの各内部頂点がそのパスで初めて現れるようなサブグラフのシーケンスです。回路ランクが の任意の 2 連結グラフでは、すべての開いた耳分解にちょうど 個の耳があります。^[8]${\displaystyle r}$${\displaystyle r}$

サイクロマティック数を持つグラフは、r個の辺だけを削除すれば木や森になるので、 rほぼ木とも呼ばれる。1 ほぼ木は近似木である。連結近似木は擬似木であり、各頂点に根を持つ（おそらく自明な）木を持つサイクルである。^[9]${\displaystyle r}$

いくつかの著者は、 r近傍木上のグラフアルゴリズムのパラメータ化された複雑性を研究しており、パラメータ化されている。^{[10] [11]}${\displaystyle r}$

サイクルランクは、グラフ内のサイクルのネストレベルを測定する有向グラフの不変量です。回路ランクよりも複雑な定義があり (無向グラフのツリーの深さの定義に密接に関連しています)、計算がより困難です。回路ランクに関連する有向グラフのもう 1 つの問題は、最小フィードバックアークセットです。これは、削除するとすべての有向サイクルが破壊されるエッジの最小セットです。サイクルランクと最小フィードバックアークセットはどちらも計算が NP 困難です。

エッジの方向を無視し、基礎となる無向グラフの回路ランクを計算することで、有向グラフのより単純な不変量を計算することも可能です。この原理は、コンピュータ コードの複雑さを推定するソフトウェア メトリック である循環的複雑度の定義の基礎となります。

化学や化学情報学の分野では、分子グラフの回路ランク（最小の環の最小集合内の環の数）はフレジャック数と呼ばれることもあります。^{[12] [13] [14]}

グラフ上の計算問題の中には一般にNP困難であるものもありますが、回路ランクが小さいグラフの場合は多項式時間で解くことができます。例としてはパス再構成問題があります。 ^[15]

グラフから何かを削除するという観点から定義された他の数値は次のとおりです。

• エッジの接続性- グラフを切断するために削除するエッジの最小数。
• マッチング排除-完全なマッチングの存在を防ぐために削除するエッジの最小数。
• フィードバック頂点セット数 - グラフを非循環にするために削除する頂点の最小数。
• フィードバック アーク セット- 有向グラフを非循環にするために、有向グラフから削除するアークの最小数。