사이비숲

그래프 이론에서 사이비 포리스트는 연결된 모든 구성요소가 최대 한 사이클을 갖는 비방향 그래프다^[1].즉, 연속된 에지의 두 사이클이 서로 정점을 공유하지 않고 연속된 에지의 경로에 의해 두 사이클이 서로 연결되지 않도록 정점 쌍을 연결하는 정점과 에지의 시스템이다.가성애는 연결된 사이비 숲이다.

그 이름은 더 흔히 연구되는 나무와 숲에 비유하여 정당화된다.(나무는 사이클이 없는 연결된 그래프, 숲은 나무의 분리된 결합이다.)가보우와 타르잔은^[2] 사이비숲의 연구를 단치히가 1963년 펴낸 선형 프로그래밍에 관한 책으로 돌렸는데, 이 책에서는 특정 네트워크 흐름 문제의 해결에서 사이비숲이 생겨난다.^[3]사이비 포리스트는 또한 함수의 그래프 이론적 모델을 형성하고 몇 가지 알고리즘적인 문제에서 발생한다.사이비 포리스트는 희소성 그래프로서, 그들의 가장자리 수는 정점 수 측면에서 선형적으로 경계된다(사실, 정점이 있는 만큼의 가장자리를 가지고 있다). 그리고 그들의 매트로이드 구조는 숲과 사이비 포리스트의 조합으로서 희소성 그래프의 여러 다른 패밀리를 분해할 수 있게 한다."pseudo forest"라는 이름은 피카르트와 케이란느(1982)에서 유래했다.

정의 및 구조

우리는 각 가장자리의 끝점으로 두 개의 꼭지점(일치될 수 있음)이 있는 정점과 가장자리의 집합으로 비방향 그래프를 정의한다.즉, 여러 에지(끝점 쌍이 동일한 에지)와 루프(두 끝점이 동일한 에지)를 허용한다.^[1]그래프의 하위 그래프는 가장자리 부분 집합의 각 에지가 정점 부분 집합에 양쪽 끝점을 가지도록 정점과 가장자리의 하위 집합에 의해 형성된 그래프다.비방향 그래프의 연결된 구성요소는 주어진 단일 시작 꼭지점에서 가장자리를 따라가면 도달할 수 있는 정점과 가장자리로 구성된 서브그래프다.그래프는 모든 정점 또는 가장자리가 다른 모든 정점 또는 가장자리에서 도달할 수 있는 경우 연결된다.비방향 그래프의 사이클은 각 정점이 정확히 두 모서리에 부딪히거나 루프인 연결된 서브그래프다.^[4]

사이비 포리스트는 연결된 각 구성요소가 최대 한 사이클을 포함하는 비방향 그래프다.^[5]마찬가지로, 연결된 각 성분에 정점 이상의 에지가 없는 비방향 그래프다.^[6]주기가 없는 성분은 나무일 뿐, 그 안에 주기가 한 번 있는 성분은 1-트리 또는 외순환 그래프라고 한다.즉, 1-트리는 정확히 하나의 사이클을 포함하는 연결된 그래프다.하나의 연결된 구성요소가 있는 사이비숲(보통 필자가 1-나무라고 정의하지만, 일부 필자가 유사수리를 1-나무로 정의함)은 나무나 1-나무 중 하나이며, 일반적으로 유사수림에는 모두 나무나 1-트리가 있는 한 여러 개의 연결된 구성요소가 있을 수 있다.

1-트리에서 그 주기의 가장자리 중 하나를 제거하면 그 결과는 나무다.이 과정을 반대로 하면, 만약 어떤 사람이 정점 두 개를 새로운 가장자리로 연결하여 트리를 증가시키면, 그 결과는 1-트리가 된다; 추가된 가장자리의 두 끝점을 연결하는 트리의 경로는 추가된 가장자리와 함께 1-트리의 고유한 순환을 형성한다.정점 중 하나를 새로 추가한 정점에 연결하는 가장자리를 추가하여 1-트리를 증가시키면 결과는 다시 1-트리가 되며, 1-트리를 구성하는 다른 방법은 단일 사이클로 시작한 다음 이 증가 작업을 여러 번 반복하는 것이다.어떤 1-나무의 가장자리는 두 개의 서브그래프로 독특한 방법으로 분할할 수 있는데, 하나는 사이클이고 다른 하나는 숲인데, 숲의 각 나무가 사이클의 꼭지점을 정확히 한 개씩 포함하고 있다.^[7]

더 구체적인 유형의 사이비 숲도 연구되었다.

최대 사이비 포리스트라고도 불리는 1-포리스트는 그래프의 일부 성분이 다중 사이클을 포함하지 않으면 더 이상 가장자리를 추가할 수 없는 사이비 포리스트다.사이비 포리스트가 그 구성 요소 중 하나로 트리를 포함하는 경우, 1-포리스트가 될 수 없다. 그 이유는 해당 트리 내에서 두 정점을 연결하는 가장자리 또는 단일 주기를 형성하는 가장자리 또는 해당 트리를 다른 구성 요소에 연결하는 가장자리를 추가할 수 있기 때문이다.그러므로 1-숲은 정확히 모든 성분이 1-나무인 사이비숲이다.

비방향 그래프 G의 스패닝 사이비 포리스트는 G의 모든 정점을 가진 G의 사이비 포리스트 서브그래프다.이러한 사이비숲은 어떤 가장자리도 가질 필요가 없는데, 예를 들어 모든 정점이 G이고 가장자리가 없는 서브그래프는 사이비숲(이들 구성 요소는 하나의 꼭지점으로 구성된 나무)이기 때문이다.

G의 최대 사이비숲은 G의 어떤 더 큰 사이비숲 안에 들어 있지 않은 G의 사이비숲 하위그래프다. G의 최대 사이비숲은 항상 스패닝 사이비숲이지만 반대로는 아니다.G가 나무인 연결된 구성요소가 없다면 그 최대 사이비숲은 1 숲이지만, G가 트리 구성요소를 가지고 있다면 그 최대 사이비숲은 1 숲이 아니다.정확히 말하면, 그래프 G에서 최대 사이비숲은 G의 모든 트리 성분과 G의 나머지 정점을 덮고 있는 하나 이상의 분리된 1-tree로 구성된다.

지시된 사이비 포리스트

이러한 정의의 버전은 지시된 그래프에도 사용된다.방향 그래프는 비방향 그래프와 마찬가지로 정점과 가장자리로 구성되지만 각 가장자리는 끝점 중 하나에서 다른 끝점으로 방향 지정된다.지시된 사이비 포리스트는 각 꼭지점이 최대 하나의 나가는 가장자리, 즉 최대 하나의 바깥쪽 가장자리를 갖는 지시된 그래프다.지시된 1-포리스트(가장 일반적으로 기능적 그래프(아래 참조)로 불리며, 때로는 최대 지시의 사이비포리스트)는 각 정점이 정확히 1을 초과하는 지시된 그래프다.^[8]D가 지시된 사이비숲이라면 D의 각 가장자리에서 방향을 제거하여 형성된 비방향 그래프는 비방향 사이비숲이다.

가장자리 수

n 정점 집합의 모든 사이비 포리스트에는 최대 n개의 가장자리가 있으며, n 정점 집합의 모든 최대 사이비 포리스트에는 정확히 n개의 가장자리가 있다.반대로, 그래프 G가 그 정점의 모든 부분 집합 S에 대해 S의 유도 하위 그래프에 있는 가장자리 수는 S의 정점의 최대 정점의 수인 경우, G는 사이비 포리스트다. 1-tree는 정점과 가장자리가 동일한 연결 그래프로 정의할 수 있다.^[2]

개별 그래프에서 그래프 패밀리로 이동하면, 그래프 패밀리가 패밀리에 있는 그래프의 모든 하위 그래프가 패밀리에 있고, 패밀리의 모든 그래프가 정점만큼 많은 가장자리를 갖는 속성을 가지고 있다면, 패밀리는 사이비 포리스트만 포함한다.예를 들어, 철갑상어의 모든 하위 그래프(모든 가장자리 쌍이 하나의 교차점을 갖도록 그린 그래프)도 철갑상어이므로, 철갑상어마다 정점만큼의 가장자리를 가지고 있다는 콘웨이의 추측도 철갑상어마다 사이비 숲이라고 말하는 것처럼 다시 풀 수 있다.좀 더 정확한 특성화는 만약 추측이 사실이라면, 트라클은 정확히 4Vertex 사이클이 없고 최대 1개의 홀수 사이클이 있는 사이비 숲이라는 것이다.^[9]

Streinu와 Theran은^[10] 사이비 포리스트를 정의하는 sparsity 조건을 일반화한다: 그들은 정점을 가진 모든 비어있지 않은 서브그래프가 최대 kn - l 엣지를 가지고 있고 (k,l)-sparse이고 정확히 kn - l 엣지를 가지고 있다면 그래프를 (k,l)-sparse로 정의한다.따라서 사이비 포리스트는 (1,0)-파스 그래프, 최대 사이비 포리스트는 (1,0)-밀착 그래프다.다른 몇 개의 중요한 그래프 패밀리는 k와 l의 다른 값에서 정의될 수 있으며, l ≤ k 때 (k,l)-sparse 그래프는 l 포리스트와 k - l 사이비 포리스트의 가장자리 분리 결합으로 형성된 그래프로 특징지어질 수 있다.^[11]

거의 모든 희박한 무작위 그래프는 사이비 포리스트다.^[12]즉, c가 0 < c < 1/2을 가진 상수이고, p_c(n)가 cn 에지가 있는 n-vertex 그래프 중에서 무작위로 균일하게 선택하는 확률이라면, P_c(n)는 큰 n에 대한 한계에 있는 하나를 선택하는 경향이 있다.단, c > 1/2의 경우 cn 에지가 있는 거의 모든 랜덤 그래프는 외발성(外發性)이 아닌 큰 성분을 가지고 있다.

열거

그래프는 자체 루프가 없고 엔드포인트가 같은 다중 에지가 없는 경우 단순하다.정점이 n개 표시된 단순 1-tree의 수는^[13]

${\displaystyle n\sum _{k=1}^{n}{\frac {(-1)^{k-1}}\sum _{n_{1}+\cdots +n_{k}=n}{n!}{n_{1}!\cdots n_{k}!}}{{\binom {{n_{1}:{2}}+\cdots +{\binom{n_{k}}{n}}}.}$

n 최대 300의 값은 온라인 정수 백과사전 OEIS: A057500 시퀀스에서 찾을 수 있다.

각 꼭지점에는 나가는 가장자리에 대해 가능한 끝점이 n개 있기 때문에 자체 루프를 허용하는 n 꼭지점의 최대 방향 사이비 포리스트 수는 n개다ⁿ.안드레 조이알은 이 사실을 최대의 지시된 사이비숲과 두 개의 구별된 노드를 가진 비방향 나무들 사이의 편차를 찾아냄으로써 n개의 노드에 있는 무방향 나무의 수가 n이라는^{n − 2} 케일리의 공식에 대한 객관적 증거를 제공하는데 이용했다.^[14]자가 루프를 허용하지 않을 경우 최대 유도 사이비 포리스트의 수는 대신(n - 1)이다.ⁿ

함수 그래프

지시된 사이비숲과 종말론은 어떤 의미에서 수학적으로 동등하다.정해진 X에서 그 자체(즉, X의 내형성)에 이르는 모든 함수 ƒ은 ((x) = y가 될 때마다 x에서 y까지의 에지를 갖는 지시된 사이비 포리스트를 정의하는 것으로 해석할 수 있다.결과 유도된 사이비 포리스트는 최대값이며, 일부 값 x에 ƒ(x) = x가 있을 때마다 자체 루프를 포함할 수 있다. 또는 자체 루프를 생략하면 최대값이 아닌 사이비 포리스트가 생성된다.다른 방향에서는 어떤 최대 지시 사이비숲이 ƒ(x)가 x에서 나가는 가장자리의 대상이 되는 함수 ƒ을 결정하고, 어떤 비 최대 지시 사이비숲도 자기루프를 첨가하여 최대화시킨 다음 같은 방법으로 함수로 변환할 수 있다.이러한 이유로, 최대 지시의 사이비 포리스트를 기능 그래프라고 부르기도 한다.^[2]기능 그래프로 기능을 보는 것은 기능-이론적 관점에서 쉽게 설명되지 않는 속성을 설명하는데 편리한 언어를 제공한다. 이 기법은 기능 그래프의 경로에 해당하는 반복적 기능과 관련된 문제에 특히 적용할 수 있다.

사이클 검출은 기능 그래프의 경로를 따라 그 안에서 사이클을 찾는 문제로서 암호학 및 계산 번호 이론에 응용하는 것으로, 정수 인자화를 위한 폴라드의 rho 알고리즘의 일부로서, 암호 해시함수의 충돌을 찾는 방법으로서 있다.이러한 애플리케이션에서 ƒ은 랜덤하게 동작할 것으로 예상된다. Flajolet과 Odlyzko는^[15] 무작위로 선택한 매핑에서 발생하는 기능 그래프의 그래프-이론적 속성을 연구한다.특히 생일 역설의 형태는 정점이 없는 무작위 기능 그래프에서 무작위로 선택한 꼭지점에서 시작하는 경로가 일반적으로 스스로 반복되어 O(점수) 단계 내에서 사이클을 형성한다는 것을 의미한다.코냐긴 외그래프 통계에 대한 분석적 및 계산적 진전을 이루었다.^[16]

마틴, 오들리즈코, 울프람은^[17] 세포 자동자의 역학을 모델링하는 사이비숲을 조사한다.그들이 상태 전이도라고 부르는 이러한 기능적 그래프는 자동화의 셀의 앙상블이 들어갈 수 있는 각각의 가능한 구성에 대해 하나의 꼭지점을 가지고 있으며, 자동화의 규칙에 따라 각 구성을 따르는 구성에 연결하는 가장자리를 가지고 있다.구성 요소의 수, 제한 주기의 길이, 제한 주기와 비 제한 상태를 연결하는 나무의 깊이 또는 도표의 대칭과 같은 이러한 도표 구조로부터 자동화의 특성을 유추할 수 있다.예를 들어, 들어오는 가장자리가 없는 정점은 에덴동산 패턴에 해당하고, 자기루프가 있는 정점은 정물화 패턴에 해당한다.

기능 그래프의 또 다른 초기 적용은 Steiner 3중 시스템을 연구하기 위해 사용되는 열차에 있다.^[18]3중 시스템의 열차는 각각의 가능한 3중 기호에 대한 꼭지점을 갖는 기능적 그래프로, 각각의 3중 pqr은 by에 의해 스튜에 매핑된다. 여기서 pqs, prt, qru는 각각 3중 시스템에 속하는 3중으로, pq, pr, qr을 포함하고 있다.열차는 계산하기에 다소 번거롭지만 트리플 시스템의 강력한 불변성인 것으로 나타났다.

2분자성모종

매트로이드(matroid)는 벡터 공간에서 선형 독립성의 특성을 본떠서 모델링된 특성을 만족시키는 방식으로, 특정 요소 집합이 독립적으로 정의되는 수학 구조다.매트로이드의 표준 예 중 하나는 그래프의 숲에서 독립된 집합이 모서리 집합인 그래픽 매트로이드다. 포리스트의 매트로이드 구조는 그래프의 최소 스패닝 트리를 계산하는 알고리즘에서 중요하다.유사하게, 우리는 사이비 숲에서 온 모계들을 정의할 수 있다.

모든 그래프 G = (V,E)에 대해, 우리는 G의 가장자리에 매트로이드를 정의할 수 있다. 이 매트로이드는 유사 포리스트를 형성하는 경우에만 독립적이다. 이 매트로이드는 G의 2분자 매트로이드(또는 자전거 매트로이드)로 알려져 있다.^[19][20]이 매트로이드의 가장 작은 종속 집합은 둘 이상의 주기를 가진 G의 최소 연결 서브그래프인데, 이러한 서브그래프를 자전거라고 부르기도 한다.자전거에는 세 가지 유형이 있다: 세 개의 내부 분리 경로로 연결된 두 개의 정점이 있고, 그림 8 그래프는 하나의 정점을 공유하는 두 개의 사이클로 구성되며, 수갑 그래프는 한 경로로 연결된 두 개의 분리 사이클로 구성된다.^[21]그래프는 자전거가 서브그래프로 포함되지 않은 경우에만 사이비숲이다.^[10]

금단의 미성년자

일부 가장자리를 수축하고 다른 가장자리를 삭제하여 사이비숲의 마이너를 형성하면 또 다른 사이비숲이 생긴다.따라서 사이비숲 가문은 미성년자 아래 폐쇄되고, 로버슨가는–세이모어 정리는 사이비 숲이 금지된 미성년자의 유한 집합의 관점에서 특징지어질 수 있다는 것을 암시하는데, 이는 바그너의 평면 그래프를 완전한 그래프₅ K도 아니고 완전한 양분 그래프 K도_3,3 미성년자로 가지고 있지 않은 그래프로 특징짓는 것과 유사하다.위에서 언급했듯이, 어떤non-pseudoforest 그래프가 서브 그래프로;아무거나 몸매가 쇠고랑을 채우다 8그래프가 나비 그래프(five-vertex 그림 8)을 형성하도록 깔고, 어떤 theta 그래프는 모든 non-pseudoforest는 butterfl가 포함된 다이아몬드 그래프(four-vertex theta 그래프)[22]을 만들기 위해 체결될 것 하청 받을 수 있는 handcuff 그림 8, 또는 세타 그래프가 포함되어 있습니다.이봐.단조로운 다이아몬드, 그리고 이것들은 단조로운 숲이 아닌 유일한 그래프들이다.따라서 그래프는 나비와 다이아몬드를 마이너로서 가지고 있지 않은 경우에만 사이비숲이다.다이아몬드만 금하고 나비는 금하지 않으면 결과적으로 더 큰 그래프 계열은 선인장 그래프와 여러 선인장 그래프의 분리 결합으로 구성된다.^[23]

좀 더 간단히 말하면, 자기 루프를 가진 다중 글씨를 고려한다면, 금지된 단조, 즉 두 개의 루프를 가진 꼭지점이 있을 뿐이다.

알고리즘

사이비 포리스트의 초기 알고리즘적 사용은 네트워크 심플렉스 알고리즘과 다른 유형의 상품들 간의 전환을 모델링하는 일반적인 흐름 문제에 그것의 적용을 포함한다.^[3][24]이러한 문제에서, 정점들이 각 상품들을 모델화하는 흐름 네트워크와 한 상품과 다른 상품들 사이의 허용 가능한 전환들을 모델화하는 가장자리 모델이 하나가 입력 네트워크로 주어진다.각 가장자리에는 용량(단위시간당 얼마만큼의 상품을 전환할 수 있는지), 흐름승수(상품간 전환율), 비용(비정확한 손실량 또는 마이너스일 경우 전환단위당 이익이 얼마나 발생하는지)이 표시된다.이 과제는 유량망의 각 가장자리를 통해 얼마만큼의 상품을 전환할지 결정하는 동시에, 비용이나 이윤을 최소화하기 위해, 용량 제약에 순응하고 어떤 종류의 상품도 사용되지 않는 것을 허용하지 않는 것이다.이러한 유형의 문제는 선형 프로그램으로 공식화할 수 있으며, 심플렉스 알고리즘을 사용하여 해결할 수 있다.이 알고리즘에서 발생하는 중간 해결책과 궁극적인 최적 해결책은 특수한 구조를 가지고 있다: 입력 네트워크의 각 가장자리는 가장자리의 부분집합을 제외하고 미사용되거나 전체 용량에 사용되며, 입력 네트워크의 스팬 사이비 포리스트를 형성하여 흐름 양이 0과 풀 사이에 있을 수 있다.l역량이 어플리케이션에서는 외발성 그래프를 증축수라고도 하고, 최대 사이비숲을 증축수림이라고도 한다.^[24]

최소 스패닝 사이비 포리스트 문제는 더 큰 에지 가중 그래프 G에서 최소 중량의 스패닝 사이비 포리스트를 찾는 것을 포함한다.사이비숲의 매트로이드 구조로 인해 최소 중량 최대 사이비숲은 최소 스패닝트리 문제와 유사한 탐욕스러운 알고리즘에 의해 발견될 수 있다.그러나 가보우와 타르잔은 이 경우 보다 효율적인 선형 시간 접근법을 발견했다.^[2]

그래프 G의 유사성(pseudarbority)은 가장자리가 분할될 수 있는 최소 사이비 숲의 수로서 수목성에 유추하여 정의된다. 동등하게, G의 가장자리가 (k,0)-파스인 최소 k 또는 G의 가장자리가 최대 k에서 바깥도로 지시된 그래프를 형성하도록 방향을 지정할 수 있는 최소 k이다.사이비숲의 매트로이드 구조로 인해, 의사보리성은 다항식 시간에 계산될 수 있다.^[25]

초당파의 각 면에 정점이 n개인 임의의 정점이 있는 임의의 정점 쌍에서² 각각 임의로 선택한 cn 에지가 있는 임의의 정점 그래프는 c가 완전히 1보다 작은 상수일 때마다 높은 확률을 가진 사이비 숲이다.이 사실은 뻐꾸기 해싱의 분석에 핵심적인 역할을 하는데, 키에서 결정된 위치에서 두 개의 해시 테이블 중 하나를 들여다봄으로써 키-값 쌍을 찾는 데이터 구조인, 즉 정점이 해시 테이블 위치에 해당하고 키 중 하나가 있을 수 있는 두 위치를 연결하는 "쿠쿠크 그래프"를 구성할 수 있다.뻐꾸기 해싱 알고리즘은 뻐꾸기 그래프가 사이비숲일 경우에만 모든 키의 위치를 찾는 데 성공한다.^[26]

사이비숲은 또한 그래프 컬러링과 관련된 문제들에 대한 병렬 알고리즘에서도 핵심적인 역할을 한다.^[27]

메모들

참조

외부 링크

• Weisstein, Eric W., "Unicyclic Graph", MathWorld