회로 순위

그래프 이론에서 수학의 한 가지, 회로 순위, 사이클 수, 사이클 순위 또는 비방향 그래프의 무효는 모든 사이클을 깨기 위해 그래프에서 제거해야 하는 최소 에지 수로서 나무나 숲으로 만든다.그래프의 독립 사이클 수(사이클 기준의 크기)와 같다.지시된 그래프에 대한 해당 피드백 아크 세트 문제와 달리, 회로 순위 r은 다음 공식을 사용하여 쉽게 계산된다.

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

여기서 m은 주어진 그래프에서 가장자리 수, n은 꼭지점 수, c는 연결된 구성요소의 수입니다.^[1] 또한 탐욕스러운 알고리즘을 사용하거나 스패닝 포리스트를 보완하여 모든 사이클을 효율적으로 파괴하는 최소 크기의 에지 세트를 구축할 수 있다.

회로 순위는 그래프의 주기 공간의 치수로서 대수 그래프 이론, 그래픽 매트로이드의 코랭크로서의 매트로이드 이론, 그래프에서 파생된 위상학적 공간의 베티 수치의 하나로서 위상 측면에서 설명할 수 있다.그것은 그래프의 귀 분해에 있는 귀를 세고, 거의 트리의 파라미터화된 복잡성의 기초를 형성하며, 코드 조각의 사이클로매틱 복잡성의 정의의 일부로서 소프트웨어 메트릭스에 적용되었다.사이클로메틱 넘버라는 이름으로 구스타프 키르흐호프가 도입했다.^[2][3]

매트로이드 순위 및 최소 피드백 에지 세트 구성

그래프 G의 회로 순위는 Matroid 이론을 G의 그래픽 매트로이드의 코랭크로 사용하여 설명할 수 있다.^[4] 이는 매트로이드의 탐욕스러운 특성을 이용하여 각 단계에서 적어도 하나의 남은 그래프의 사이클에 속하는 에지를 선택하는 탐욕스러운 알고리즘을 사용하여 모든 사이클을 깨는 최소의 에지 집합을 찾을 수 있다는 것을 의미한다.

또는 G의 스패닝 포리스트를 구성하고 스패닝 포리스트에 속하지 않는 보완적인 에지 세트를 선택하여 모든 사이클을 파괴하는 최소 에지 집합을 찾을 수 있다.

독립 사이클 수

대수 그래프 이론에서 회로 순위는 $G{\displaystyle }$ ${\displaystyle G}$의 사이클 공간의 차원이라고도$$할 수 있다. 직관적으로 이것은 회로 순위는 그래프에서 독립 사이클의 수를 세는 것을 의미하는데, 여기서 사이클의 집합은 대칭 di로서 사이클 중 하나를 형성할 수 없는 경우에는 독립적이다.다른 일부에 대한 ^[1]추론

이러한 독립 사이클의 카운트는 위상의 한 분야인 호몰로지 이론을 사용하여 설명할 수도 있다.모든 그래프 G는 1차원 단순화 복합체의 예로 볼 수 있는데, 이는 각 그래프 가장자리를 선 세그먼트별로 나타내고 선 세그먼트를 그 끝점에 함께 붙임으로써 형성된 위상학적 공간의 한 유형이다.사이클로메틱 수는 이 콤플렉스의 첫 번째 (정수) 호몰로지 그룹의 순위다.^[5]

$\왼쪽[왼쪽]H_{1}(G,\mathb {Z} )\right].}$

이러한 위상학적 연결 때문에 그래프 G의 사이클로메틱 수는 G의 첫 번째 베티 번호라고도 불린다.^[6] 보다 일반적으로 위상학적 공간의 첫 번째 베티 번호는 동일한 방법으로 정의되며, 공간 내 독립 사이클 수를 카운트한다.

적용들

메쉬드 계수

동일한 꼭지점이 설정된 평면 그래프의 가능한 최대 회로 등급으로 나누어 정규화된 평면 그래프의 회로 등급의 변형을 중간 계수라고 한다.m 에지와 n 정점이 있는 연결된 평면 그래프의 경우, 중상도 계수는 공식으로^[7] 계산할 수 있다.

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

여기서 공식의$$ 분자 $m{\displaystyle }$- ${\displaystyle \mathrm{n}}$+ ${\displaystyle 1}$ ${\displaystyle m-n+1$}은$($는) 주어진 그래프의 회로 등급이며, 분모 ${\displaystyle \mathrm{2n}}$- ${\displaystyle 5}$ ${\displaystyle 2n-5}$은 n-vertex 평면 그래프의 가능한 최대 회로 등급이다$$.중혼도 계수는 나무의 경우 0과 최대 평면 그래프의 경우 1이다.

귀 분해

회로 순위는 그래프의 귀 분해, 그래프 가장자리의 분할에서 많은 그래프 알고리즘에서 유용한 경로 및 사이클의 귀 수를 제어한다.특히 그래프는 오픈 이어 분해된 경우에만 2Vertex 연결된다.이것은 서브그래프의 순서인데, 여기서 첫 번째 서브그래프는 단순한 사이클이고, 나머지 서브그래프는 모두 단순한 경로로, 각 경로는 이전의 서브그래프에 속하는 정점에서 시작하고 끝나며, 경로의 각 내부 꼭지점이 그 경로에서 처음으로 나타난다.회로 순위 $r{\displaystyle }$ ${\displaystyle r}$이(가) 있는 모든 양극 연결 그래프에서 모든 열린 귀 분해에는 $정확히{\displaystyle }$ r ${\displaystyle$ r$}개$의 귀가$$ 있다$.$^[8]

거의 나무

$나무$나 숲으로 만들려면 그래프에서 r 가장자리만 제거하면 되기 때문에 자전거 번호 r ${\displaystyle r}$이 있는 그래프를 r-almost-tree라고도 한다$$.거의 1-알짜리는 거의 나무다. 즉, 가까운 나무는 유사수목이며, 각각의 꼭지점에 뿌리를 두고 있는 (아마도 사소한) 나무가 순환한다.^[9]

몇몇 저자들은 $r{\displaystyle }$ ${\displaystyle r}$에 의해 매개변수화된 r-near-tree의 그래프 알고리즘의 매개변수화된 복잡성을 연구했다$.$^[10][11]

지시된 그래프에 대한 일반화

사이클 순위는 그래프에서 사이클의 내포 수준을 측정하는 지시된 그래프의 불변량이다.회로 순위(비방향 그래프의 트리 깊이 정의와 밀접하게 관련됨)보다 정의가 복잡하고 계산이 더 어렵다.회로 등급과 관련된 지시된 그래프의 또 다른 문제는 최소 피드백 호 세트, 제거로 모든 지시된 사이클이 중단되는 가장자리 집합이다.사이클 순위와 최소 피드백 호 세트 모두 계산하기 어려운 NP이다.

또한 가장자리의 방향을 무시하고 기본 비방향 그래프의 회로 순위를 계산하여 지시된 그래프의 단순한 불변성을 계산할 수도 있다.이 원칙은 컴퓨터 코드 조각이 얼마나 복잡한지 추정하기 위한 소프트웨어 메트릭인 사이클로믹 복잡성의 정의의 기초를 형성한다.

계산화학

화학 및 척수학 분야에서 분자 그래프의 회로 순위(가장 작은 고리의 가장 작은 집합에 있는 고리의 수)를 프레자크 숫자로 부르기도 한다.^[12][13][14]

매개 변수화된 복잡성

그래프의 일부 계산 문제는 일반적으로 NP-hard이지만 회로 순위가 작은 그래프의 경우 다항식 시간으로 해결할 수 있다.예를 들어 경로 재구성 문제가 있다.^[15]

관련개념

그래프에서 사물을 삭제하는 관점에서 정의된 다른 숫자는 다음과 같다.

• 에지 연결 - 그래프의 연결을 끊기 위해 삭제할 최소 에지 수;
• 일치 사전 폐합 - 완벽한 일치의 존재를 방지하기 위해 삭제할 최소 에지 수
• 피드백 정점 설정 번호 - 그래프를 반복하기 위해 삭제할 최소 정점 수
• 피드백 호 세트 - 지시된 그래프에서 삭제할 최소 호 수, 반복적으로 만들기 위해.

참조