브리지 (그래프 이론)

정점이 16개이고 브리지가 6개 있는 그래프(빨간색으로 강조 표시)

브리지 가장자리가 없는 비방향 연결 그래프

그래프 이론에서 브리지, isthmus,^[1] 컷 에지 또는 컷 아크는 그래프의 삭제로 그래프의 연결된 구성요소 수가 증가하는 그래프의 가장자리 입니다.마찬가지로, 가장자리가 어떤 사이클에 포함되지 않은 경우에만 브리지가 된다.연결된 그래프의 경우 브리지가 절단을 고유하게 결정할 수 있다.그래프는 다리가 없으면 다리가 없거나 이스트무스가 없다고 한다.

이 교량의 유형은 그래프 이론에서 "교량"의 관련 없는 의미와 구별되어야 하며, 그래프의 나머지 부분 집합으로 분리된 하위 그래프. 그래프 이론 용어 § 브리지 참조.

나무와 숲

가장자리를 추가하면 주기가 생성되기 때문에 노드가 $n$ $n개인$ 그래프에는 최대 $n-1$ - $n-1$ 1 {\ $displaystyle n-1$ }개의 $n-1$ $n-1$ 브리지가 포함될 수 있다.정확히 $n-1$ - $n-1$ $n-1$ 개의 $n-1$ 다리가 있는 그래프는 정확히 나무이고, 모든 가장자리가 브릿지인 그래프는 정확히 숲이다.

모든 비방향 그래프에서, 두 개의 가장자리 분리 경로가 서로 연결될 때마다 두 꼭지점이 서로 관련되는 정점에 따라 정점에는 동등성 관계가 있다. (모든 꼭지점은 두 개의 길이 영점 경로를 통해 그 자체와 관련되는데, 이는 동일하지만 그럼에도 불구하고 가장자리 분리된다.)이 관계의 동등성 클래스를 2-엣지 연결 구성요소라고 하며, 그래프의 브리지는 정확히 끝점이 서로 다른 구성요소에 속하는 가장자리들이다.그래프의 브릿지 블록 트리는 모든 비종교 구성요소에 대한 꼭지점과 모든 브리지에 대한 가장자리가 있다.^[2]

정점 연결에 대한 관계

브리지는 다른 정점 쌍 사이의 모든 경로에 속하는 정점인 관절 정점의 개념과 밀접하게 관련되어 있다.브리지의 두 끝점은 1도가 없는 한 관절 정점이다. 단, 다리 이외의 가장자리는 두 개의 관절 정점을 끝점으로 가질 수도 있다.브리지가 없는 그래프는 2-엣지 연결 그래프와 유사하게, 굴절 정점이 없는 그래프는 2-버텍스 연결이다.

입방형 그래프에서 모든 절단 정점은 적어도 하나의 브리지의 끝점이다.

브리지리스 그래프

브리지리스 그래프(bridgeless graph)는 브리지가 없는 그래프를 말한다.등가조건은 그래프의 각 연결된 성분은 오픈 이어 분해, ^[3]각 연결된 성분은 2-엣지 연결 또는 (로빈스의 정리) 모든 연결된 성분은 강한 방향을 갖는 것이다.^[3]

브리지와 관련된 중요한 개방적 문제는 Symour와 Szekeres(1978년과 1979년 독립적으로)로 인한 사이클 이중 커버 추측으로, 모든 브리지 없는 그래프는 각 에지를 정확히 두 번 포함하는 단순 사이클의 다중 집합을 인정한다고 명시한다.^[4]

타르잔의 다리 찾기 알고리즘

그래프에서 다리를 찾기 위한 최초의 선형 시간 알고리즘은 1974년 로버트 타르잔에 의해 설명되었다.^[5]다음과 같은 단계를 수행한다.

$G$ $G$ 의 스패닝 포리스트 찾기
스패닝 포리스트에서 $F$ 루트 $포리스트$ F $F$ 생성
사전 $F$ $F$ 에서포리스트 F {\ $displaystyle$ F}을(를 $)$ 트래버스하고 노드 번호를 지정하십시오.포리스트의 상위 노드는 이제 하위 노드보다 숫자가 낮다.
사전 순서(예약 번호를 사용하여 각 노드를 나타냄)의 $v$ 각 노드 $v$ $v$ 에 대해 다음을 수행하십시오.
- 이 노드의 숲 후손 $ND(v)$ $ND(v)$ $ND(v)$ ) $ND(v)$ 을(를) 계산하여 해당 자식 후손의 합계에 하나를 추가하십시오.
- $L(v)$ L (v ) {\displaystyle L(v)}, 마지막 에지를 제외한 모든 에지가 $v$ $v$ 에 루트인 하위 트리 내에 있는 경로로 $v$ $v$ $v$ 에서 도달할 수 있는 가장 낮은 사전 주문 $레이블$ $v$ 이것은 $v$ $v$ 의 $L(w)$ 순서 라벨 $v$ $v$ $v$ 의 $L(w)$ 하위 노드에서 L $L(w)$ ( $L(w)$ ) $L(w)$ 의 $v$ 값 $및$ F $F$ 에 속하지 않는 가장자리별로 $v$ v ${\displaystystyle v}$ 에서 도달할 수 있는 노드의 사전 순서 라벨로 구성된 세트의 최소값이다 $F$
- 마찬가지로 마지막 에지를 제외한 모든 에지가 $v$ $v$ 에 루트된 하위 트리 내에 있는 경로로 도달할 수 있는 가장 높은 사전 주문 레이블인 $H(v)$ $H(v)$ 을 계산하십시오 $v$ 이것은 $v$ $v$ 의 사전 순서 라벨 $v$ v $v$ 의 $H(w)$ 노드에서 H $H(w)$ ( $H(w)$ ) $H(w)$ 값 및 $v$ $F$ $F$ 에 속하지 않는 가장자리별로 $v$ $v$ ${\displaystyle$ v $}$ 에서 도달할 수 있는 사전 순서 라벨로 구성된 세트의 최대값이다 $F$
- 상위 $노드$ v $v$ 이 $w$ $v$ 가) 있는 각 $노드$ w ${\displaystyle$ $w}$ 에 대해 $L(w)=w$ $L(w)=w$ = w $(w)$ = $L(w)=w$ (w $)$ = $H(w)<w+ND(w)$ (w) $H(w)<w+ND(w)$ + $H(w)<w+ND(w)$ $H(w)<w+ND(w)$ ${\displaystyle$ $H$ $(w)<w+ND(w)}$ 인 $L(w)=w$ 경우 $}$ 에서 $}$ 까지의 $v$ 에지는 브리지가 $w$ $된다$ .

체인 분해로 교량 탐색

매우 간단한 교량 탐색 알고리즘은^[6] 연쇄 분해를 사용한다.체인 분해는 그래프의 모든 브리지를 계산할 수 있을 뿐만 아니라 G의 모든 절단 정점(및 G의 블록 컷 트리)을 판독할 수 있게 해 2-에지 및 2-버텍스 연결성 테스트(선형 시간 3-에지 및 3-버텍스 연결성 테스트로 확장)를 위한 일반적인 프레임워크를 제공한다.

체인 분해는 G의 DFS-트리 T에 따라 특별한 귀 분해이며 매우 간단하게 계산할 수 있다: 모든 꼭지점을 방문하지 않은 것으로 표시하도록 하라.오름차순 DFS 번호 1...n의 각 꼭지점 v에 대해, v에 문제가 있는 모든 백지(즉, DFS 트리에 없는 모든 가장자리)를 트래버스하고 방문으로 표시된 첫 번째 꼭지점에서 정지하는 트리-에지의 경로를 다시 따라 T의 루트로 돌아간다.그러한 통과 중에 모든 통과 정점은 방문한 것으로 표시된다.따라서, 통과는 늦어도 v에서 정지하고 v로 시작하는 방향 경로나 사이클 중 하나를 형성한다; 우리는 이 경로를 체인이라고 부른다.이 절차에 의해 발견된 ith 체인을 C라고_i 한다.C=C₁, C₂, ...는 G의 연쇄 분해다.

그러면 다음과 같은 특성화를 통해 G의 모든 교량을 포함하여 C에서 G의 여러 특성을 효율적으로 읽을 수 있다.^[6] C는 단순한 연결 그래프 G=(V,E)의 연쇄 분해로 한다.

G는 C 파티션 E의 체인이 있는 경우에만 2-엣지로 연결된다.
G의 엣지 e는 만약 e가 C의 어떤 체인에 포함되어 있지 않다면 그리고 오직 한 경우에 브리지다.
G가 2엣지 연결이라면 C는 귀 분해다.
G가 최소 도 2를 가지고 있고 C가₁ C에서 유일한 사이클인 경우에만 G가 2-Vertex로 연결된다.
2개의 가장자리가 연결된 그래프 G의 꼭지점 v는 C - C에서₁ 주기의 첫 번째 꼭지점인 경우에만 절단된 꼭지점이다.
G가 2-베르텍스 연결이라면 C는 오픈 이어 분해다.

참고 항목

메모들

^ Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR 1633290.
^ Westbrook, Jeffery; Tarjan, Robert E. (1992), "Maintaining bridge-connected and biconnected components on-line", Algorithmica, 7 (5–6): 433–464, doi:10.1007/BF01758773, MR 1154584.
^ ^a ^b Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly, 46: 281–283, doi:10.2307/2303897, hdl:10338.dmlcz/101517.
^ Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1.
^ Tarjan, R. Endre (1974), "A note on finding the bridges of a graph", Information Processing Letters, 2 (6): 160–161, doi:10.1016/0020-0190(74)90003-9, MR 0349483.
^ ^a ^b Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, arXiv:1209.0700, doi:10.1016/j.ipl.2013.01.016.

[1] Bollobás, Béla (1998), Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, New York: Springer-Verlag, p. 6, doi:10.1007/978-1-4612-0619-4, ISBN 0-387-98488-7, MR 1633290.

[2] Westbrook, Jeffery; Tarjan, Robert E. (1992), "Maintaining bridge-connected and biconnected components on-line", Algorithmica, 7 (5–6): 433–464, doi:10.1007/BF01758773, MR 1154584.

[robbins39-3] Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly, 46: 281–283, doi:10.2307/2303897, hdl:10338.dmlcz/101517.

[4] Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1.

[5] Tarjan, R. Endre (1974), "A note on finding the bridges of a graph", Information Processing Letters, 2 (6): 160–161, doi:10.1016/0020-0190(74)90003-9, MR 0349483.

[Schmidt-6] Schmidt, Jens M. (2013), "A Simple Test on 2-Vertex- and 2-Edge-Connectivity", Information Processing Letters, 113 (7): 241–244, arXiv:1209.0700, doi:10.1016/j.ipl.2013.01.016.

[1]

[2]

[3]

[4]

[5]

[6]

Search