循環数
このグラフは、2 つのエッジ (たとえば、エッジ 1–2 と 2–3) を削除することでツリーにすることができるため、循環数r = 2を持ちますが、いずれか 1 つのエッジを削除すると、グラフにサイクルが残ります。

数学の一分野であるグラフ理論において、無向グラフの循環数、回路ランク、サイクルランク、コランク、またはヌル度は、グラフのすべてのサイクルを破壊してグラフをツリーまたはフォレストにするためにグラフから削除する必要があるエッジの最小数です。

この概念はグスタフ・キルヒホフによって導入され、サイクロマティック数と名付けられました。[ 1 ] [ 2 ]

式

グラフのサイクマティック数は、グラフ内の独立サイクルの数、サイクル基底のサイズに等しい。有向グラフの対応するフィードバックアーク集合問題とは異なり、サイクマティック数rは次の式を用いて簡単に計算できる。 ここで、 eは与えられたグラフの辺の数、vは頂点の数、cは連結成分の数である。 [ 3 ]r＝e−v+c、{\displaystyle r=e-v+c,}

貪欲アルゴリズムを使用するか、スパニング フォレストを補完することによって、すべてのサイクルを効率的に破る最小サイズのエッジ セットを構築することが可能です。

サイクロマティック数は、代数グラフ理論においてはグラフのサイクル空間の次元として、マトロイド理論においてはグラフマトロイドの双対階数として、そして位相幾何学においてはグラフから導かれる位相空間のベッティ数の一つとして説明することができる。これは、グラフの耳分解における耳の数を数え、ほぼ木におけるパラメータ化された複雑性の基礎を形成し、ソフトウェアメトリクスにおいてはコードの サイクロマティック複雑性の定義の一部として適用されてきた。

ハイパーグラフの場合

ハイパーグラフのサイクマティック数は、そのレヴィグラフから導出できます。レヴィグラフは、同じサイクマティック数を持ちますが、単純グラフに縮約されます。これは です。 ここで、 gは次数和（およびレヴィグラフの辺の数）、eは与えられたハイパーグラフのハイパーエッジの数、vは頂点の数、cは連結成分の数です。 r＝グラム−（v+e）+c、{\displaystyle r=g-(v+e)+c,}

ハイパーグラフの次数和は、すべての頂点の次数の合計であり、単純グラフでは2 e 、 k -一様ハイパーグラフではkeに減少します。この式は頂点と辺の間で対称であり、ハイパーグラフとその双対ハイパーグラフが同じサイクロマティック数を持つことを示しています。

マトロイドランクと最小フィードバックエッジセットの構築

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

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

独立サイクルの数

代数的グラフ理論において、サイクロマティック数はのサイクル空間の次元でもある。直感的には、サイクロマティック数はグラフ内の独立したサイクルの数を数えるという意味で説明できる。サイクルの集合が独立であるとは、サイクルの1つを他のサイクルのサブセットの対称差として形成することが不可能な場合を指す。[ 3 ]G{\displaystyle G}

この独立閉路の数は、位相幾何学の一分野であるホモロジー理論を用いて説明することもできる。任意のグラフG は、 1 次元単体複体の例として見ることができる。単体複体は、各グラフの辺を線分で表し、これらの線分を端点で互いに接着することによって形成される位相空間の一種である。サイクロマティック数は、この複体の最初の (整数)ホモロジー群の階数である。 [ 5 ] この位相的なつながりのため、グラフGのサイクロマティック数は、 Gの最初のベッティ数とも呼ばれる。[ 6 ]より一般的には、同様に定義される任意の位相空間の最初のベッティ数は、空間内の独立閉路の数を数える。 r＝ランク⁡[H1（G、Z）]。{\displaystyle r=\operatorname {rank} \left[H_{1}(G,\mathbb {Z} )\right].}

アプリケーション

メッシュ係数

平面グラフのサイクマティック数の変形は、同じ頂点集合を持つ任意の平面グラフの最大のサイクマティック数で割ることによって正規化され、メッシュ化係数と呼ばれる。m辺n頂点の連結平面グラフの場合、メッシュ化係数は式[ 7 ]で計算できる。

メートル−n+12n−5。{\displaystyle {\frac {m-n+1}{2n-5}}.}

ここで、式の分子は与えられたグラフのサイクマティック数であり、分母はn頂点平面グラフの最大のサイクマティック数である。メッシュ度係数は、木構造の場合0、最大平面グラフの場合1の範囲をとる。 メートル−n+1{\displaystyle m-n+1}2n−5{\displaystyle 2n-5}

耳の分解

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

ほぼ木

循環数を持つグラフは、 r-ほぼ木とも呼ばれます。これは、グラフを木や森にするため には、 r本の辺だけを削除すればよいためです。1-ほぼ木は近似木であり、連結近似木は擬似木、つまり各頂点を根とする（おそらく自明な）木を持つ閉路です。[ 9 ]r{\displaystyle r}

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

有向グラフへの一般化

サイクルランクは、有向グラフにおけるサイクルの入れ子レベルを測る不変量です。サイクルランクは、サイクロマティック数（無向グラフの木の深さの定義に密接に関連）よりも複雑な定義を持ち、計算がより困難です。有向グラフにおいてサイクロマティック数に関連するもう一つの問題は、最小フィードバックアーク集合、つまり、削除することですべての有向サイクルが破壊される最小の辺集合です。サイクルランクと最小フィードバックアーク集合はどちらも計算が NP困難です。

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

計算化学

化学およびケミノフォーマティクスの分野では、分子グラフのサイクロマティック数（最小の環の最小集合内の環の数）はフレジャック数と呼ばれることもあります。[ 12 ] [ 13 ] [ 14 ]

パラメータ化された複雑さ

グラフ上の計算問題の中には、一般にNP困難であるものもありますが、循環数が小さいグラフでは多項式時間で解くことができます。例としては、経路再構成問題が挙げられます。[ 15 ]

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

参考文献

  1. ^ピーター・ロバート・コティウガ（2010年）「ラウル・ボットの数学的遺産を祝う」アメリカ数学会、p. 20、ISBN 978-0-8218-8381-5
  2. ^ Per Hage (1996)、「島のネットワーク：オセアニアにおけるコミュニケーション、親族関係、分類構造」、ケンブリッジ大学出版局、p. 48、ISBN 978-0-521-55232-5
  3. ^ a bベルジュ、クロード（2001年）「サイクロマティック数」、グラフ理論、クーリエ・ドーバー出版、pp.  27– 30、ISBN 9780486419756。
  4. ^ベルジュ、クロード（1976年）、グラフとハイパーグラフ、ノースホランド数学図書館、第6巻、エルゼビア、p.477、ISBN 9780720424539。
  5. ^セール、ジャン＝ピエール（2003）、Trees、Springer Monographs in Mathematics、Springer、p. 23、ISBN 9783540442370。
  6. ^グレゴリー・ベルコライコ、ピーター・クックメント（2013年）、量子グラフ入門、アメリカ数学会、p.4、ISBN 978-0-8218-9211-4
  7. ^ Buhl, J.; Gautrais, J.; Sole, RV; Kuntz, P.; Valverde, S.; Deneubourg, JL; Theraulaz, G. (2004)「アリの回廊ネットワークにおける効率性と堅牢性」、The European Physical Journal B、42 (1)、Springer-Verlag: 123– 129、Bibcode : 2004EPJB...42..123B、doi : 10.1140/epjb/e2004-00364-9。
  8. ^ Whitney, H. (1932)、「非分離グラフと平面グラフ」、アメリカ数学会誌、34 (2): 339– 362、doi : 10.2307/1989545、JSTOR 1989545、PMC 1076008、PMID 16587624   特に定理18（耳分解と回路ランクの関係）と定理19（耳分解の存在について）を参照してください。
  9. ^ Brualdi, Richard A. (2006),組み合わせ行列クラス, 数学とその応用百科事典, 第108巻, Cambridge: Cambridge University Press , p.  349 , ISBN 0-521-86565-4、Zbl  1106.05001
  10. ^コッパースミス、ドン；ヴィシュキン、ウジ（1985）、「'almost trees'におけるNP困難問題の解決：頂点被覆」、離散応用数学、10（1）：27–45、doi：10.1016/0166-218X（85）90057-5、Zbl 0573.68017 。
  11. ^フィアラ、イジー;クロクス、トン。 Kratochvíl、Jan (2001)、「Fixed-parameter complexity of λ-labelings」、離散応用数学、113 (1): 59–72、doi : 10.1016/S0166-218X(00)00387-5、Zbl 0982.05085 。
  12. ^ May, John W.; Steinbeck, Christoph (2014)、「化学開発キットのための効率的なリング認識」、Journal of Cheminformatics、6 (3): 3、doi : 10.1186/1758-2946-6-3、PMC 3922685、PMID 24479757  
  13. ^ Downs, GM; Gillet, VJ; Holliday, JD; Lynch, MF (1989)、「化学グラフのためのリング認識アルゴリズムのレビュー」、J. Chem. Inf. Comput. Sci.、29 (3): 172– 187、doi : 10.1021/ci00063a007
  14. ^ Frerejacque、Marcel (1939)、「No. 108-Condensation d'une moleculeorganique」[有機分子の凝縮]、Bull.社会チム。神父様、5 : 1008 – 1011
  15. ^ Demaine, Erik D. ; Eppstein, David ; Hesterberg, Adam; Jain, Kshitij; Lubiw, Anna ; Uehara, Ryuhei; Uno, Yushi (2019)、「Reconfiguring Undirected Paths」、Friggstad, Zachary; Sack, Jörg-Rüdiger ; Salavatipour, Mohammad R. (eds.)、Algorithms and Data Structures – 16th International Symposium、WADS 2019、エドモントン、AB、カナダ、2019 年 8 月 5 ～ 7 日、議事録、Lecture Notes in Computer Science、vol. 11646、シュプリンガー、pp.  353– 365、arXiv : 1905.00518、doi : 10.1007/978-3-030-24766-9_26、ISBN 978-3-030-24765-2
「 https://en.wikipedia.org/w/index.php?title=Cyclomatic_number&oldid=1323644880」より取得