연결(그래프 이론)

Connectivity (graph theory)
이 그래프는 왼쪽 회색 영역의 오른쪽 노드를 제거하면 연결이 끊어집니다.
이 그래프는 점선 모서리를 제거하면 연결이 끊어집니다.

연결(Connectivity)은 수학과 컴퓨터 과학에서 그래프 이론의 기본 개념 중 하나로, 나머지 노드를 두 개 이상의 고립된 부분 그래프로 분리하기 위해 제거해야 하는 최소 수의 요소(노드 또는 에지)를 요구합니다.[1] 네트워크 흐름 문제 이론과 밀접한 관련이 있습니다. 그래프의 연결성은 네트워크로서의 복원력의 중요한 척도입니다.

연결된 정점 및 그래프

정점이 0이면 이 그래프는 연결이 끊어집니다. 그래프의 나머지 부분이 연결되어 있습니다.

무향 그래프 G에서 두 꼭짓점 u와 v는 G가 u에서 v로의 경로를 포함한다면 연결되어 있다고 합니다. 그렇지 않으면 연결 해제라고 합니다. 두 꼭짓점이 길이 1의 경로(즉, 하나의 간선의 끝점)로 추가로 연결되어 있으면 이 꼭짓점을 인접이라고 합니다.

그래프의 모든 정점 쌍이 연결되어 있으면 그래프가 연결된다고 합니다. 이는 모든 정점 쌍 사이에 경로가 있음을 의미합니다. 연결되지 않은 방향 없는 그래프를 연결 해제라고 합니다. 따라서 G에 두 개의 정점이 존재하면 방향이 없는 그래프 G는 연결이 끊어지므로 G에 있는 어떤 경로도 이러한 정점을 끝점으로 갖지 않습니다. 꼭짓점이 하나만 있는 그래프가 연결되어 있습니다. 두 개 이상의 정점이 있는 모서리가 없는 그래프는 연결이 끊어집니다.

모든 방향 에지를 방향 에지가 아닌 것으로 대체하면 연결된(방향이 없는) 그래프가 생성되는 경우 방향 그래프가 약하게 연결되어 있다고 합니다. 모든 정점 u, v에 대하여 u에서 v로 향하는 지시 경로 또는 v에서 u로 향하는 지시 경로를 포함하는 경우에는 일방적으로 연결되거나 일방적으로 연결됩니다(반연결이라고도 함).[2] 모든 정점 u, v에 대하여 u에서 v로 향하는 지시 경로 및 v에서 u로 향하는 지시 경로를 포함하는 경우에는 강하게 연결되거나 단순히 강하게 연결됩니다.

구성요소 및 절단

연결된 구성요소는 무방향 그래프의 최대 연결 부분 그래프입니다. 각 꼭짓점은 각 모서리와 마찬가지로 정확히 하나의 연결된 구성 요소에 속합니다. 그래프가 연결된 구성 요소가 정확히 하나인 경우에만 연결됩니다.

강한 성분은 방향 그래프의 최대 강하게 연결된 부분 그래프입니다.

연결된 그래프 G의 꼭짓점 절단 또는 분리 집합은 G를 분리하는 꼭짓점 집합입니다. 정점 연결 κ(G)(여기서 G는 완전한 그래프가 아닙니다)는 최소 정점 절단의 크기입니다. 그래프의 정점 연결도가 k 이상이면 k-정점 연결 또는 k-연결이라고 합니다.

더 정확하게 말하면, 모든 그래프 G(완전하거나 그렇지 않음)는 적어도 k+1개의 정점을 포함하지만 제거가 그래프를 단절시키는 k -1개의 정점 집합을 포함하지 않으면 k-정점 연결이라고 하며, κ(G)는 G가 k-연결된 가장 큰 k로 정의됩니다. 특히, K로 표시된 n개의 정점을 갖는 완전 그래프는 정점 절단이 전혀 없지만 κ(K) = n-1입니다.

두 개의 정점 u와 v에 대해 절단된 정점은 그래프에서 제거하면 u와 v가 분리되는 정점 집합입니다. 로컬 연결 κ(u, v)는 u와 v를 구분하는 가장 작은 정점 컷의 크기입니다. 로컬 연결은 방향이 없는 그래프, 즉 κ(u, v) = κ(v, u)에 대해 대칭입니다. 또한 완전한 그래프를 제외하고 κ(G)는 모든 인접하지 않은 정점 u, v 쌍에 대한 κ(u, v)의 최소값과 같습니다.

2-연결은 쌍연결, 3-연결은 쌍연결이라고도 합니다. 연결되어 있지만 2 연결되어 있지 않은 그래프 G를 분리 가능이라고 부르기도 합니다.

에지에 대해서도 유사한 개념을 정의할 수 있습니다. 특정한 단일 간선을 절단하면 그래프가 단절되는 단순한 경우를 브리지라고 합니다. 보다 일반적으로, G의 모서리 절단은 제거하면 그래프가 단절되는 모서리 집합입니다. 에지 연결 λ(G)는 가장 작은 에지 절단의 크기이고, 두 정점 u, v의 로컬 에지 연결 λ(u, v)은 u와 v를 연결하는 가장 작은 에지 절단의 크기입니다. 다시 로컬 에지 연결은 대칭입니다. 그래프의 에지 연결이 k 이상이면 k-edge-connected라고 합니다.

그래프의 연결 정도가 최소인 경우 그래프가 최대로 연결된다고 합니다. 그래프의 에지 연결 정도가 최소인 경우, 그래프는 최대 에지 연결이라고 합니다.[3]

초연결 및 초연결

그래프는 최소 정점 절단마다 정점이 분리되는 경우 초연결 또는 초κ이라고 합니다. 각 최소 정점 절단의 삭제가 정확히 두 개의 성분을 생성하는 경우 그래프는 초연결 또는 초κ이라고 합니다. 그 중 하나는 고립된 정점입니다. 최소 꼭지점 절단이 그래프를 정확히 두 성분으로 분리하는 경우 그래프는 반초연결 또는 반초초κ입니다.

더 정확하게는 모든 최소 정점 컷이 하나의 (최소 차수) 정점과 인접한 정점으로 구성되는 경우 G 연결 그래프를 초연결 또는 초 κ라고 합니다. 모든 최소 에지 절단이 일부 (최소 차수) 정점에 결합된 에지로 구성되는 경우 G 연결 그래프는 초 에지 연결 또는 초 λ이라고 합니다.

만약 X가 임의의 정점 u ∉ X의 근방 N(u)를 포함하지 않는다면 G의 절단 집합 X를 자명하지 않은 절단 집합이라고 합니다. 그렇다면 G의 초연결 κ1은 다음과 같습니다.

κ1(G) = min{ X : X는 trivial이 아닌 절단 집합입니다.

사소한 에지 컷과 에지 초연결 λ1(G)은 유사하게 정의됩니다.

멩거 정리

주 기사: 멩거 정리

그래프에서 연결성에 대한 가장 중요한 사실 중 하나는 정점 사이의 독립적인 경로의 수를 기준으로 그래프의 연결성과 에지-연결성을 특징으로 하는 멩거 정리입니다.

u와 v가 그래프 G의 정점인 경우, u와 v 사이의 경로 집합을 독립적이라고 합니다. 만약 두 경로 중 어느 것도 하나의 정점을 공유하지 않는다면(u와 v 자신을 제외하고). 마찬가지로 컬렉션에서 두 경로가 에지를 공유하지 않으면 에지 독립적입니다. u와 v 사이의 상호 독립적인 경로의 수는 κ'(u, v)로, u와 v 사이의 상호 에지 독립적인 경로의 수는 λ'(u, v)로 표기합니다.

멩거 정리는 서로 다른 정점 u, v에 대하여 λ(u, v)는 λ'(u, v)와 같으며, u가 v에 인접하지 않으면 κ(u, v)는 κ'(u, v)와 같음을 주장합니다. 이 사실은 실제로 최대 흐름 최소 절단 정리의 특별한 경우입니다.

계산적 측면

그래프에서 두 개의 정점이 연결되어 있는지 여부를 결정하는 문제는 너비 우선 검색과 같은 검색 알고리즘을 사용하여 효율적으로 해결할 수 있습니다. 좀 더 일반적으로 그래프가 연결되었는지(예를 들어, 서로소 집합 데이터 구조를 사용하여) 계산적으로 판단하거나 연결된 구성 요소의 수를 세는 것이 쉽습니다. 간단한 알고리즘은 다음과 같이 의사 코드로 작성될 수 있습니다.

  1. 그래프의 임의의 노드에서 시작, G
  2. 도달한 모든 노드를 세면서 깊이 우선 검색 또는 너비 우선 검색을 사용하여 해당 노드에서 진행합니다.
  3. 그래프가 완전히 통과되면 계수된 노드 수가 G의 노드 수와 같으면 그래프가 연결되고 그렇지 않으면 연결이 끊어집니다.

멩거 정리에 의해, 연결된 그래프 G의 임의의 두 꼭짓점 u와 v에 대하여, 수 κ(u, v)와 λ(u, v)는 max-flow min-cut 알고리즘을 사용하여 효율적으로 결정될 수 있습니다. 그러면 G의 연결성과 에지 연결성은 각각 κ(u, v)과 λ(u, v)의 최소값으로 계산될 수 있습니다.

계산 복잡도 이론에서 SL은 그래프에서 두 꼭짓점이 연결되어 있는지 여부를 결정하는 문제로 축소 가능한 문제의 클래스로 2004년 Omer Reingold에 의해 L과 동일함이 증명되었습니다.[9] 따라서 O(log n) 공간에서 무방향 그래프 연결을 해결할 수 있습니다.

베르누이 랜덤 그래프가 연결되어 있을 확률을 계산하는 문제를 네트워크 신뢰도라고 하며, 주어진 두 꼭짓점이 연결되어 있는지 여부를 계산하는 문제를 ST 신뢰도 문제라고 합니다. 둘 다 #P-hard입니다.[10]

연결된 그래프 수

주 기사: 그래프 열거

n개의 노드가 있는 별개의 연결된 라벨이 붙은 그래프의 수는 On-Line Encyclopedia of Integer Sequences에서 시퀀스 A001187로 표로 표시됩니다. 처음 몇 개의 중요하지 않은 항은

4개의 노드로 연결된 그래프의 수와 영상
n 그래프
1 1
2 1
3 4
4 38
5 728
6 26704
7 1866256
8 251548592

예

  • 단절된 그래프의 정점 및 에지 연결은 모두 0입니다.
  • 1-연결성은 최소 2개의 정점을 가진 그래프에 대한 연결성과 같습니다.
  • n개의 정점에 대한 완전한 그래프는 n - 1과 같은 간선 연결성을 갖습니다. n개의 정점에 대한 다른 모든 단순한 그래프는 엄격하게 더 작은 간선 연결성을 갖습니다.
  • 트리에서 서로 다른 두 정점 사이의 로컬 에지 연결은 1입니다.

연결 제한

  • 그래프의 정점 연결은 간선 연결보다 작거나 같습니다. That is, κ(G) ≤ λ(G).
  • 최소 차수의 정점에 연결된 모든 간선을 제거하면 해당 정점과 나머지 그래프의 연결이 끊어지기 때문에 정점이 2개 이상인 그래프의 간선 연결은 그래프의 최소 차수보다 작거나 같습니다.[1]
  • d도의 정점 천이 그래프의 경우, 2(d + 1)/3 ≤ κ(G) ≤ λ(G) = d가 있습니다.
  • d ≤ 4인 정점 전이 그래프 또는 d의 최소 케일리 그래프 또는 d의 대칭 그래프의 경우 두 종류의 연결은 κ(G) = λ(G) = d입니다.

기타속성

  • 연결은 그래프 동형화에 의해 보존됩니다.
  • G가 연결되어 있으면 그 선 그래프 L(G)도 연결되어 있습니다.
  • 그래프 G가 강하게 연결된 방향이 있는 경우에만 2-edge 연결됩니다.
  • 발린스키의 정리는 k차원 볼록 폴리톱의 폴리톱 그래프(1-스켈레톤)가 k-정점 연결 그래프라는 것을 말합니다.[13] 임의의 3-정점으로 연결된 평면 그래프는 다지선 그래프(Steinitz theorem)라는 Steinitz의 이전 정리는 부분적인 역방향을 제공합니다.
  • G. A. Dirac의 정리에 따르면, 만약 어떤 그래프가 k개의 ≥ 2에 대하여 k개의 정점을 연결한다면, 그래프의 모든 k개의 정점에 대하여 집합의 모든 정점을 통과하는 순환이 있습니다. k = 2일 때는 그 반대가 참입니다.

참고 항목

참고문헌

  1. ^ a b Diestel, R. (2005). "Graph Theory, Electronic Edition". p. 12.
  2. ^ 11장: 디그래프: 디그래프에 대한 이중성의 원리: 정의
  3. ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 335. ISBN 978-1-58488-090-5.
  4. ^ Liu, Qinghai; Zhang, Zhao (2010-03-01). "The existence and upper bound for two types of restricted connectivity". Discrete Applied Mathematics. 158 (5): 516–521. doi:10.1016/j.dam.2009.10.017.
  5. ^ Gross, Jonathan L.; Yellen, Jay (2004). Handbook of graph theory. CRC Press. p. 338. ISBN 978-1-58488-090-5.
  6. ^ Balbuena, Camino; Carmona, Angeles (2001-10-01). "On the connectivity and superconnectivity of bipartite digraphs and graphs". Ars Combinatorica. 61: 3–22. CiteSeerX 10.1.1.101.1458.
  7. ^ Gibbons, A. (1985). Algorithmic Graph Theory. Cambridge University Press.
  8. ^ Nagamochi, H.; Ibaraki, T. (2008). Algorithmic Aspects of Graph Connectivity. Cambridge University Press.
  9. ^ Reingold, Omer (2008). "Undirected connectivity in log-space". Journal of the ACM. 55 (4): 1–24. doi:10.1145/1391289.1391291. S2CID 207168478.
  10. ^ Provan, J. Scott; Ball, Michael O. (1983). "The complexity of counting cuts and of computing the probability that a graph is connected". SIAM Journal on Computing. 12 (4): 777–788. doi:10.1137/0212053. MR 0721012..
  11. ^ Godsil, C.; Royle, G. (2001). Algebraic Graph Theory. Springer Verlag.
  12. ^ Babai, L. (1996). Automorphism groups, isomorphism, reconstruction. Technical Report TR-94-10. University of Chicago. Archived from the original on 2010-06-11. 조합학 핸드북 27장.
  13. ^ Balinski, M. L. (1961). "On the graph structure of convex polyhedra in n-space". Pacific Journal of Mathematics. 11 (2): 431–434. doi:10.2140/pjm.1961.11.431.
  14. ^ Dirac, Gabriel Andrew (1960). "In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen". Mathematische Nachrichten. 22 (1–2): 61–85. doi:10.1002/mana.19600220107. MR 0121311..
  15. ^ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). "A generalization of Dirac's theorem on cycles through k vertices in k-connected graphs". Discrete Mathematics. 307 (7–8): 878–884. doi:10.1016/j.disc.2005.11.052. MR 2297171..