サイクルランク

グラフ理論において、有向グラフのサイクルランクは、エガンとビュキ(Eggan 1963)によって初めて提案された有向グラフの接続性尺度である。直感的には、この概念は、有向非巡回グラフ(DAG) のサイクルランクが 0 であるのに対し、各頂点に自己ループを持つn次完全有向グラフのサイクルランクはn であるという意味で、有向グラフが DAG にどれだけ近いかを測定する。有向グラフのサイクルランクは、無向グラフのツリー深さや正規言語のスター高さと密接に関連している。また、疎行列計算 (Bodlaender ら 1995 を参照) や論理 (Rossman 2008) にも使用されている。

有向グラフG  = ( V ,  E )のサイクルランクr ( G )は次のように帰納的に定義されます。

• Gが非巡回の場合、r ( G ) = 0です。
• Gが強く連結でEが空でない場合、

${\displaystyle r(G)=1+\min _{v\in V}r(Gv),\,}$ここで、⁠ ⁠ は頂点${\displaystyle Gv}$vと、 vで始まるまたは終わるすべての辺を削除した結果の有向グラフです。

• Gが強く連結されていない場合、r ( G ) はGのすべての強く連結された成分の中で最大のサイクルランクに等しくなります。

無向グラフのツリーの深さは、強い接続性と強い接続性コンポーネントの代わりに無向接続性と接続性コンポーネントを使用するという、非常によく似た定義を持ちます。

サイクルランクは、正規言語のスター高さの文脈でEggan (1963)によって導入されました。これは、1980年代に開発され始め、疎行列計算に適用された無向木の深さの一般化として、 (Eisenstat & Liu 2005)によって再発見されました(Schreiber 1982)。

有向非巡回グラフのサイクルランクは 0 ですが、各頂点に自己ループを持つn 位の完全有向グラフのサイクルランクはnです。これらとは別に、他のいくつかの有向グラフのサイクルランクがわかっています。対称なエッジ関係を持ち自己ループを持たないn位の無向パスはサイクルランクを持ちます(McNaughton 1969)。有向-トーラス、つまり長さmとnの 2 つの有向回路の直積では、 m ≠ nに対しておよび が成り立ちます (Eggan 1963、Gruber & Holzer 2008)。 ${\displaystyle P_{n}}$${\displaystyle \lfloor \log n\rfloor }$${\displaystyle (m\times n)}$${\displaystyle T_{m,n}}$${\displaystyle r(T_{n,n})=n}$${\displaystyle r(T_{m,n})=\min\{m,n\}+1}$

サイクルランクの計算は計算上困難です。Gruber (2012) は、最大出次数が 2 以下のスパース有向グラフの場合でも、対応する決定問題が NP 完全であることを証明しています。プラス面としては、最大出次数が 2 以下の有向グラフでは 1 時間で解決でき、一般的な有向グラフでも 1 時間で解決できます。近似比 の近似アルゴリズムがあります。 ${\displaystyle O(1.9129^{n})}$${\displaystyle O^{*}(2^{n})}$${\displaystyle O((\log n)^{\frac {3}{2}})}$

サイクルランクの最初の応用は、形式言語理論において、正規言語のスター高さを研究するために行われた。Eggan (1963) は、正規表現、有限オートマトン、有向グラフの理論の関係を確立した。その後、この関係はEggan の定理として知られるようになった。Sakarovitch (2009) を参照。オートマトン理論では、ε 移動を伴う非決定性有限オートマトン(ε-NFA) は、 5 組( Q、Σ、δ、q ₀、F ) として定義され、次の要素で構成される。

• 有限の状態集合Q
• 入力シンボルの有限集合Σ
• ラベル付けされたエッジδの集合は遷移関係Q × (Σ ∪{ε}) × Qと呼ばれます。ここで ε は空の単語を表します。
• 初期状態q ₀ ∈ Q​
• 状態F ⊆ Qを受け入れる状態として区別される状態Fの集合。

単語w ∈ Σ ^*が ε-NFA によって受け入れられるのは、δからのエッジを使用して初期状態q _0からF内の最終状態への有向パスが存在し、そのパスに沿って訪問されたすべてのラベルを連結すると単語wが得られる場合です。オートマトンによって受け入れられるΣ ^*上のすべての単語の集合は、オートマトンAによって受け入れられる言語です。

状態集合Qを持つ非決定性有限オートマトンAの有向グラフ特性について話すとき、その遷移関係によって誘導される頂点集合Qを持つ有向グラフを自然に扱います。ここで、定理は次のように述べられます。

エガンの定理: 正規言語Lのスターの高さは、 Lを受け入れるε 移動を持つすべての非決定性有限オートマトンの中で最小のサイクルランクに等しくなります。

この定理の証明は、Eggan (1963) によって与えられ、最近では Sakarovitch (2009) によって与えられています。

この概念のもう 1 つの応用は、疎行列の計算、つまりネストされた分解を使用して(対称) 行列のコレスキー分解を並列に計算することです。与えられた疎行列Mは、行列の非ゼロ要素がGの辺と 1 対 1 で対応するような方法で、n頂点の対称有向グラフGの隣接行列として解釈できます。有向グラフGのサイクル ランクが最大でkの場合、プロセッサを備えた並列コンピュータでMのコレスキー分解を最大でkステップで計算できます(Dereniowski & Kubale 2004)。 ${\displaystyle (n\times n)}$${\displaystyle n}$

• サーキットランク