사이클 순위

관련 항목
그래프 연결
연결성 대수연결성 사이클 순위 순위(그래프 이론) SPQR 트리 St-연결성 K-연결성증명서 픽셀 연결 정점 분리기 강하게 연결된 구성 요소 바이콘넥트 그래프 브릿지
v t

그래프 이론에서 지시된 그래프의 사이클 순위는 에그간과 부치가 먼저 제안한 디그라프 연결 수단이다(Eggan 1963).직관적으로 이 개념은 DAG가 사이클 랭킹 0을 갖는 반면, 각 꼭지점에 자체 루프가 있는 순서의 완전한 digraph는 사이클 랭크 n을 갖는다는 점에서 digraph가 방향된 acyclick graph(DAG)에 얼마나 가까운지를 측정한다.지시된 그래프의 사이클 순위는 방향하지 않은 그래프의 트리 깊이와 정규 언어의 별 높이와 밀접한 관련이 있다.또한 희박한 매트릭스 연산(Bodlaender et al. 1995 참조)과 논리(Rosman 2008)에서도 사용법을 발견했다.

정의

digraph G = (V, E)의 사이클 랭크 r(G)은 다음과 같이 귀납적으로 정의된다.

• G가 반복적인 경우, r(G) = 0.
• G가 강하게 연결되어 있고 E가 비어 있지 않으면

${\displaystyle \mathrm{r}}$( ${\displaystyle G}$)${\displaystyle }$= 1${\displaystyle }$+ ${\displaystyle \underset{}{v}}$ ${\displaystyle \underset{}{\in }}$ V ${\displaystyle \underset{}{}}$( G${\displaystyle }$- ${\displaystyle v}$)${\displaystyle }$, ${\$ r$(G)=1+\min _{v\in V}r($$G-v$$)\,},$ $여기$서 G -$v는$꼭지점 v와 v에서 시작되거나 끝나는 모든 가장자리의 삭제로 인한 디그라피이다$.$

• G가 강하게 연결되지 않은 경우, r(G)은 G의 모든 강하게 연결된 구성요소 중 최대 사이클 순위와 동일하다.

비방향 그래프의 트리 깊이는 강한 연결성과 강하게 연결된 구성 요소 대신 비방향 연결성과 연결된 구성 요소를 사용하여 매우 유사한 정의를 가지고 있다.

역사

사이클 랭크는 에그간(1963년)이 정규 언어의 별 높이라는 맥락에서 도입했다.1980년대부터 개발되어 희박한 매트릭스 연산(Schreiber 1982년)에 적용되었던 비방향 트리 깊이의 일반화로서 (Eisenstat & Luu 2005)에 의해 재발견되었다.

예

지시된 아크리크 그래프의 사이클 순위는 0인 반면, 각 꼭지점에 자기루프가 있는 n 순서의 완전한 digram은 n 사이클 순위를 가진다. 이와 별도로 몇 개의 다른 digrams: n 순서의 비방향 경로 ${\displaystyle P_{}}$ n ${\$의 사이클$$ 순위는 대칭 가장자리 관계를 가지며 자체 루프가 없는 것으로 알려져 있다.${\displaystyle \lfloor }$ ${\displaystyle \log }$ ${\displaystyle n}$ ${\displaystyle \rfloor }$ ${\displaystyle \lfloor \log n\rfloor }($McNaughton 1969)For the directed ${\displaystyle (m\times n)}$-torus ${\displaystyle T_{m,n}}$, i.e., the cartesian product of two directed circuits of lengths m and n, we have ${\displaystyle r(T_{n,n})=n}$ and ${\displaystyle r(T_{m,n})=\min\{m,n\}+1}$ form ≠ n (Eggan 1963, 그루버 & 홀저 2008).

사이클 순위 계산

사이클 순위를 계산하는 것은 계산적으로 어렵다: 그루버(2012년)는 최대 2도의 희박한 디그라프에서도 해당 의사결정 문제가 NP-완전하다는 것을 증명한다.긍정적인 측면에서는 최대 2도인 디그그래프의 시간$$ $O{\displaystyle }$(1${\displaystyle {\mathrm{.}}^{9129n}}$ )${\displaystyle O(1.$${\displaystyle {9129}^{}}$$^{n}},$ 일반 디그그래프의 시간$$ $O{\displaystyle {}^{}}$ time (${\displaystyle {}^{}{\mathrm{}}^{}}$ ) ${\displaystyle O^{*}(2^{n})}$에서 문제를 해결할 수 있다.근사비 $O{\displaystyle }$(${\displaystyle }$( ( ${\displaystyle \log }$ ${\displaystyle n}$ ${\displaystyle {}^{}}$ ${\displaystyle {\frac{3}{}}^{}}$ ${\displaystyle 2^{}}$) ${\displaystyle O((\log n)^{\frac{3}{2}})}$의 근사 알고리즘이 있다$.$

적용들

정규 언어의 별 높이

사이클 등급의 첫 적용은 정규 언어의 별 높이를 연구하기 위한 형식 언어 이론이었다.Eggan(1963년)은 정규식, 유한 자동식, 지시된 그래프 이론 간의 관계를 설정했다.이후 몇 년 동안 이 관계는 에그간의 정리인 cf로 알려지게 되었다.사카로비치(2009년).automata 이론에서, mo-moves (ε-NFA)를 가진 비결정론적 유한 자동화는 다음과 같이 구성된 5-투플 (Q, δ, Δ, q₀, F)로 정의된다.

• 상태 Q의 유한 집합
• 입력 기호 symbols의 유한 집합
• 라벨이 부착된 가장자리 Δ(전환 관계)의 집합:Q × ( ( × {{{}) × Q. 여기서 ε은 빈말을 나타낸다.
• 초기 상태₀ Q ∈ Q
• 일련의 주들 F 수용 주들 F states Q.

Δ의^* 가장자리를 사용하여 F의 초기 상태 q에서₀ 최종 최종 상태까지의 지시 경로가 존재하는 경우, 경로를 따라 방문한 모든 라벨의 결합이 w를 산출하는 경우 w라는 단어가 ε-NFA에 의해 승인된다.자동자가 받아들인 σ에 대한^* 모든 단어 집합은 자동자 A가 받아들인 언어다.

상태가 Q로 설정된 비결정적 유한 자동자 A의 디그그래프 특성을 말할 때, 우리는 자연스럽게 디그그래프의 전환 관계에 의해 유도된 정점 세트 Q를 가진 디그그래프를 다룬다.이제 그 정리는 다음과 같이 명시되어 있다.

에그간의 정리:정규 언어 L의 항성 높이는 모든 비결정적 유한 자동자 사이의 최소 사이클 순위와 같으며, with-모브는 L을 수용한다.

이 정리의 증명서는 에그간(1963년)이, 최근에는 사카로비치(2009년)가 제시한다.

희소성 행렬 계산에서의 연쇄 인자화

이 개념의 또 다른 적용은 희박한 행렬 계산에 있다. 즉, 내포된 해부를 사용하여 (대칭) 행렬의 숄스키 인자화를 병렬로 계산한다.주어진 희소성$({\displaystyle n}$ ${\displaystyle \times }$ ${\displaystyle n}$) ${\displaystyle(n\times n)}$ -매트릭스$$ M은 행렬의 0이 아닌 항목이 G의 가장자리와 일대일 일치하도록 n 꼭지점에 있는 일부 대칭 디그라프 G의 인접 행렬로 해석될 수 있다. 디그라프 G의 사이클 순위가 최대 k인 경우, 추어스키 인자화(Cholesky factorization).M은 $n{\displaystyle }$ ${\displaystyle n}$ 프로세서가$$ 장착된 병렬 컴퓨터에서 최대 k 단계로 계산할 수 있다(Dereniowski & Kubale 2004).

참고 항목

• 회로 순위

참조