성분(그래프 이론)

그래프 이론에서, 비방향 그래프의 구성 요소는 연결된 하위 그래프로서, 더 큰 연결된 하위 그래프의 일부가 아니다. 어떤 그래프의 구성 요소들은 그것의 꼭지점을 분리 세트로 분할하고, 그러한 세트의 유도 하위 그래프들이다. 그 자체로 연결된 그래프는 정확히 하나의 성분을 가지고 있는데, 전체 그래프로 구성되어 있다. 구성요소를 연결 구성요소라고도 한다.

주어진 그래프에 있는 성분들의 수는 매트로이드, 위상학적 공간, 행렬의 불변성과 밀접한 관련이 있는 중요한 그래프 불변성이다. 랜덤 그래프에서 빈번하게 발생하는 현상은 거대 성분의 발생률로, 다른 성분보다 유의하게 큰 한 성분의 발생률과 과대산출 임계값은 거대 성분의 존재와 그렇지 않은 가장자리 확률이다.

그래프의 구성요소는 선형 시간 내에 구성할 수 있으며, 문제의 특별한 경우인 연결 구성요소 라벨링은 영상 분석의 기본 기법이다. 동적 연결 알고리즘은 가장자리가 그래프에 삽입되거나 삭제될 때 변경당 짧은 시간 내에 구성요소를 유지한다. 계산 복잡성 이론에서 연결된 구성요소는 공간 복잡성이 제한된 알고리즘을 연구하기 위해 사용되어 왔으며, 비선형 시간 알고리즘은 구성요소의 수를 정확하게 추정할 수 있다.

정의 및 예제

주어진 비방향 그래프의 구성요소는 더 큰 연결된 하위 그래프의 일부가 아닌 연결된 하위 그래프로 정의될 수 있다. 그래프의 모든$$ 꼭지점 $v{\displaystyle }$ ${\displaystyle v}$은(는) 그래프의 구성 요소 중 하나에 속하며, $v{\displaystyle }$ ${\displaystyle v}$에서 도달할 수 있는 정점 집합의 유도 하위 그래프일 수 있다$.$^[1] 모든 그래프는 그 구성 요소의 분리 결합이다.^[2] 예를 들어, 첫 번째 그림에 표시된 그래프는 세 가지 구성요소를 가지고 있다. 이 일반적인 규칙의 추가적인 예는 다음과 같은 특수한 경우를 포함한다.

• 빈 그래프에서 각 꼭지점은 하나의 꼭지점과 0개의 가장자리가 있는 성분을 형성한다.^[3] 보다 일반적으로 이 유형의 성분은 모든 그래프에서 분리된 정점에 대해 형성된다.^[4]
• 연결된 그래프에는 정확히 하나의 성분, 즉 전체 그래프가 있다.^[4]
• 숲에서 모든 구성 요소는 나무다.^[5]
• 군집 그래프에서 모든 성분은 최대 정벌이다. 이러한 그래프는 임의의 비방향 그래프의 전이적 폐쇄로 제작될 수 있으며, 이 경우 전이적 폐쇄를 찾는 것은 연결된 구성 요소를 식별하는 동등한 공식이다.^[6]

성분을 정의하는 또 다른 방법에는 그래프의 정점에 정의된 동등성 관계의 동등성 클래스가 포함된다. 방향 지정되지 않은 $그래프$에서$$u {\$displaystyle$u$$$\}$에서$$v {\$displaystyle v}$까지의 경로가 있거나 동등하게 걷기(정점과 가장자리를 반복할 수 있는 경로)에서 $꼭지점$ v ${\$$displaystyle u}$에 도달할 수 있다. 도달 가능성은 다음과 같은 동등성 관계다.

• 그것은 반사적이다: 어떤 꼭지점에서 그 자체로 길이 0의 사소한 경로가 있다.
• 대칭: $u{\displaystyle }$ ${\displaystyle u}$에서 $v{\displaystyle }$ ${\displaystyle v}$까지의 경로가 있는 경우$,$ 역순으로 동일한 에지가 $v{\displaystyle }$ ${\displaystyle v}$에서 $u{\displaystyle }$ ${\displaystyle u}$까지의 경로를 형성한다$.$
• transitive: $u{\displaystyle }$ ${\displaystyle u}$에서 $v{\displaystyle }$ ${\displaystyle v}$까지의 경로와$$ v ${\displaystyle v}$에서 w ${\displaystyle w}$까지의 경로가 있는 경우$,$ 두 경로를 함께 연결하여 $u{\displaystyle }$ ${\displaystyle u}$에서 $w{\displaystyle }$ ${\displaystystyle w}$로 이동할 수 있다$.$

이 관계의 동등성 클래스는 그래프의 정점을 분리 집합으로 분할하고, 모두 서로 도달할 수 있는 정점의 부분 집합으로 분할하며, 이러한 부분 집합 중 어떤 부분 집합 외부에 도달 가능한 추가 쌍은 없다. 각 꼭지점은 정확히 하나의 등가 등급에 속한다. 그런 다음 구성요소는 이러한 동등성 등급 각각에 의해 형성된 유도 하위 그래프들이다.^[7] 또는 일부 소스는 구성요소를 유도하는 하위 그래프가 아니라 정점의 등가 등급인 정점 집합으로 정의한다.^[8]

지시된 그래프의^[9] 강하게 연결된 구성 요소와 리디렉션되지 않은 그래프의 상호연결된 구성 요소를 포함하여, 보다 진보된 형태의 그래프 연결을 위한 구성 요소를 정의하기 위해 동등성 클래스를 포함하는 유사한 정의가 사용되어 왔다.^[10]

성분수

지정된 그래프의 구성 요소 수를 사용하여 스패닝 포리스트의 에지 수를 계산할 수 있다. 즉, $정점$이 n ${\displaystyle$ n$}개$ 및 $c{\displaystyle }$ ${\displaystyle c}$개$$ 구성 요소가 있는 그래프에서 모든 스패닝 포리스트에는 정확히 $n{\displaystyle }$ -${\displaystyle c}$ ${\displaysty n-c}$개의 에지가$$ 있다. 이 숫자 $n{\displaystyle }$ -${\displaystyle c}$ ${\displaystyle n-c}$은 그래프의 모토이드-이론적 순위 및 그래픽 모토이드의 순위다. 이중 cographic matroid의 순위는 그래프의 회로 순위와 같으며, 모든 주기를 중단하기 위해 그래프에서 제거해야 하는 최소 에지 수와 같다. $m{\displaystyle }$ ${\displaystyle m}$ 에지$$, n ${\displaystyle n}$ 꼭지점$$ 및 $c{\displaystyle }$ ${\displaystyle c}$ 구성요소가$$ 있는 그래프에서 회로 순위는 $m{\displaystyle }$- ${\displaystyle n}$+ ${\displaystyle c}$ ${\displaystyle m-n+c}$이다$.$^[11]

그래프는 3차원 유클리드 공간에서 정점을 일반 위치에 놓고 가장자리를 선 세그먼트로 표시함으로써 위상학적 공간으로서 다방면으로 해석될 수 있다.^[12] 그래프의 성분은 이러한 해석을 통해 해당 공간의 위상학적으로 연결된 성분의 수로 일반화할 수 있다. 연결된 성분의 수가 중요한 위상적 불변수인 공간의 제로트 베티 수인 것처럼, 그래프의 성분의 수는 중요한 그래프 불변수로서 위상적 그래프 이론에서는 그래프의 제로트 베티 수로 해석할 수 있다.^[3]

그래프 이론에서도 같은 수가 다른 방법으로 발생한다. 대수 그래프 이론에서 이것은 그래프의 라플라크 행렬의 고유값으로서 0의 다중성과 동일하다.^[13] 또한 그래프의 색다형 다항식의 첫 번째 0이 아닌 계수의 지수로, 전체 그래프의 색다형 다항식을 성분 다항식의 산물로 얻을 수 있다.^[14] 성분의 수는 완벽한 일치를^[15] 갖는 그래프를 특징짓는 투테 정리 및 최대 일치의 크기에 대한 관련 투테-베르게 공식과 그래프 강도의 정의에서 핵심적인 역할을 한다.^[16][17]

알고리즘

너비 우선 검색 또는 깊이 우선 검색을 사용하여 선형 시간(그래프의 꼭지점과 가장자리 수 측면에서)으로 그래프의 구성요소를 계산하는 것이 간단하다. 두 경우 모두 특정 꼭지점 $v{\displaystyle }$ ${\displaystyle v}$에서 시작하는 검색에서 $v{\displaystyle }$ ${\displaystyle v}($더 이상 포함 안 함)을 포함하는 전체 구성 요소를 찾은 후$$ 반환하십시오. 그래프의 모든 구성요소를 찾으려면 정점을 반복하고, 새로운 너비를 먼저 시작하거나, 루프가 이전에 찾은 구성요소에 포함되지 않은 정점에 도달할 때마다 깊이 첫 번째 검색을 시작하십시오. 홉크로프트와 타르잔(1973)은 본질적으로 이 알고리즘을 설명하고, 그 시점에서 이미 "잘 알려진"^[18] 알고리즘이라고 기술한다.

컴퓨터 이미지 분석의 기본 기법인 커넥티드 컴포넌트 라벨링은 그래프의 이미지 및 성분 분석에서 그래프를 구성하는 것을 포함한다. 정점은 관심 대상 또는 영상에 묘사된 객체의 일부로 선택되는 영상의 픽셀 부분집합이다. 가장자리는 인접 픽셀을 연결하며, 인접 픽셀은 Von Neumann 근방에 따라 직교로 정의되거나 Moore 근방에 따라 직교 및 대각선으로 정의된다. 이 그래프의 연결된 구성 요소를 식별하고 이를 개체로 표시하면 이미지의 해당 부분에서 더 많은 구조를 찾거나 어떤 종류의 물체를 묘사하는지 식별할 수 있다. 이 분야의 연구자들은 이러한 유형의 그래프에 특화된 여러 가지 성분 탐색 알고리즘을 개발하여 폭 우선 또는 깊이 우선 검색에 의해 생성되는 보다 분산된 순서가 아닌 픽셀 순서로 처리할 수 있도록 하였다.^[19]

정점과 에지가 추가될 때 그래프의 구성요소를 동적으로 추적할 수 있는 효율적인 알고리즘도 있다. 정점의 파티션을 동등성 등급으로 추적하기 위해 분리된 데이터 구조를 사용하여 정점을 연결하는 가장자리가 추가될 때 두 클래스를 결합하여 교체한다. 이 알고리즘은 O(α(n)){\displaystyle O(\alpha(n))}작업에, 어디서, 한 꼭지점 폭포는 둘 다 작업을 구성 요소를 결정하는 vertices과 가장자리를 추가하며 O(α(n)){\displaystyle O(\alpha(n))}아주 느리게 재배가 매우 빠르게 성장하는 애커만 함수의 역은amortized 시간이 걸린다.[20] 이러한 종류의 증분 연결 알고리즘의 한 가지 적용은 최소 스패닝 트리에 대한 크러스칼의 알고리즘에 있다. 이 알고리즘은 길이별로 정렬된 순서에 따라 그래프에 가장자리를 추가하고 이전에 추가된 서브그래프의 서로 다른 두 구성 요소를 연결할 때만 최소 스패닝 트리에 가장자리를 포함한다.^[21] When both edge insertions and edge deletions are allowed, dynamic connectivity algorithms can still maintain the same information, in amortized time ${\displaystyle O(\log ^{2}n/\log \log n)}$ per change and time ${\displaystyle O(\log n/\log \log n)}$ per connectivity 쿼리 ^[22]또는 거의 로가리듬에 가까운 임의 예상 시간.^[23]

그래프의 구성요소는 수정 가능하기 보다는 읽기 액세스를 통해서만 접근 가능한 훨씬 큰 입력을 가진 로그 비트 수로 제한된 작동 메모리를 가진 튜링 기계의 힘을 연구하기 위해 계산 복잡성 이론에 사용되어 왔다. 이런 식으로 제한된 기계에 의해 해결될 수 있는 문제들은 복잡도 등급 L을 정의한다. 두 꼭지점이 동일한 구성요소에 속하는지 여부를 시험하는 의사결정 문제로 공식화되었을 때, 그리고 1982년에 관련 복잡도 등급인 SL이 로그-공간 축소 하에서 이 연결 문제와 그것과 동등한 다른 문제를 포함하도록 정의되었을 때, 이 모델에서 연결 구성요소가 발견될 수 있을지는 여러 해 동안 불분명했다.ctions.^[24] 마침내 2008년에 이 연결 문제가 로그 공간에서 해결될 수 있다는 것이 증명되었고, 따라서 SL = L.^[25]

인접 목록으로 표시된 그래프에서, 정점에 대한 랜덤 액세스로, 최대 $most{\displaystyle }$ $[\displaystyle \varepsilon n$에서 하위 선형 $시간{\displaystyle }$ O ($$- 2 ${\displaystyle \log }$ ε${\displaystyle {\mathrm{\epsilon }}^{}}$ - 1 ${\displaystyle {}^{}}$에서$$가법($absolution$) $오차$를 얻을 일정한 확률로 연결된 성분의 수를 추정할 수 있다$.$$\log \varepsilon ^{-1}}$^[26].

랜덤 그래프

랜덤 그래프에서 성분의 크기는 랜덤 변수에 의해 제공되며, 이는 랜덤 그래프를 선택하는 방법에 대한 특정 모형에 따라 달라진다. Erdős-Rény-Gilbert 모델의 $G{\displaystyle }$ (${\displaystyle n}$,${\displaystyle p)}$ ${\displaystyle$ $G($$n,p)}$ 버전에서$$, 가장자리와 확률을 포함한 $확률$ p ${\displaystyp p}$과(와) 쌍을 연결하는 에지를 포함할지 여부를 각 꼭지 쌍에 대해 랜덤하고 독립적으로 $선택$하여$$n {\$displaystystyp$에 대한 그래프를 생성한다. ${\displaystyle 1}$$-$ p [\$displaystyle 1-p}$ 이 두 꼭지점을 연결하는 가장자리 없이 그대로 둔다.^[27] 이 모델의 연결은 $p{\displaystyle }$ ${\displaystyle p}$에 따라 달라지며, 서로 동작이 매우$$ 다른 $p{\displaystyle }$ ${\displaystyle p}$의 세 가지 범위가 있다. 아래 분석에서 모든 결과는 높은 확률로 발생하는데, 이는 결과의 $확률$이 n ${\displaystyle n}$의 충분히 큰 값에 대해 임의로 1에 가깝다는 것을 의미한다$.$ 분석은 임의로 0에 근접하도록 선택할 수 있지만 $n{\displaystyle }$ ${\displaystyle$ \varepsilon$}$의 선택에 의존해서는 안 되는 양의 상수인$$매개 변수 $\epsilon {\displaystyle }$ ${\displaystyle$ $n}$에 따라 달라진다$.$

임계 < (1 -)/ ${\displaystyle p<(1-\varepsilon )/n}$

$이{\displaystyle }$ p ${\displaystyle p}$ 범위에서 모든 구성요소는 단순하고 매우 작다$.$ 가장 큰 구성 요소의 크기는 ${\displaystyle {C\mathrm{}}_{}}$ 1${\displaystyle {}_{}}$= ${\displaystyle O}$( ${\displaystyle \mathrm{로그}}$ ${\displaystyle n}$) ${\displaystyle C_{1}$ = O$(\log$ n$)}$ 입니다$.$ 그래프는 사이비 숲이다. 그것의 구성 요소들의 대부분은 나무들이다: 주기가 있는 구성 요소들의 정점의 수는 $n{\displaystyle }$ ${\displaystyle n}$의 어떤 무한 함수보다 더 느리게 증가한다$.$ 고정된 크기의 모든 트리는 선형적으로 여러 번 발생한다.^[28]

임계 $p{\displaystyle }$= ${\displaystyle 1}$/ n ${\displaystyle p=1/n}$

${\displaystyle C{}_{}}$ ${\displaystyle {1\mathrm{}}_{}{}_{}}$= ${\displaystyle O({n\mathrm{}}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$/ 3${\displaystyle {}^{}}$) ${\displaystyle C_{1}$ $=O(n^{2/3})$를 가진 단일 거대 구성 요소가 있으며$,$ 나머지 구성 요소는 크기가 $O{\displaystyle (\mathrm{로그}}$ ${\displaystyle n}$) ${\displaystyle O(\log$ n$)}$과(으)로 작다$.$^[29]

초임계 >( + )/ ${\displaystyle$ p$>(1+\varepsilon )/n}$

The size of the giant component becomes linear, and for large values of ${\displaystyle p}$ approaches the whole graph: ${\displaystyle C_{1} \approx yn}$ where ${\displaystyle y=y(np)}$ is the positive solution to the equation ${\displaystyle e^{-pny}=1-y}$. Again, 남아있는 모든 구성 요소들은 작다.^[30]

무작위 그래프의 같은 모델에는 p{p\displaystyle}의 상당히 높은 문턱,<>(1− ε)(로그⁡ n)/n{\displaystyle p<,(1-\varepsilon)(n\log)/n}, 그리고 역치 값에 대해 단일 연결된 구성 요소, p. 아래 값에 대해 높은 확률로 복수의 연결된 구성 요소 존재할 것이다. >(1 )( )/ n ${\displaystyle p>(1+\varepsilon )(\log$ n$)/n$ 이 현상은 쿠폰 수집기의 문제와 밀접하게 관련되어 있다: 연결되기 위해서는 각 정점마다 적어도 하나의 가장자리에 충돌할 만큼 충분한 에지가 랜덤 그래프에 필요하다. 더 정확히 말하면, 무작위 에지가 그래프에 하나씩 추가되면 전체 그래프를 연결하는 첫 번째 에지가 마지막 절연 정점에 도달할 가능성이 높다.^[31]

그리드 그래프의 무작위 하위 그래프를 포함한 다양한 모델의 경우, 연결된 구성요소는 퍼콜레이션 이론에 의해 설명된다. 이 이론의 핵심 의문은 거대 성분(또는 무한 성분)이 존재하고 그렇지 않은 임계 확률인 과대산출 문턱의 존재다.^[32]

참조

외부 링크

• 방향 지정되지 않은 그래프에서 구성요소를 찾기 위한 MATLAB 코드, MATLAB 파일 교환.
• 연결된 구성 요소, Steven Skiena, Stony Brook 알고리즘 저장소