잘라내기(그래프 이론)

Cut (graph theory)

그래프 이론에서 절단은 그래프의 꼭지점을 두 개의 분리된 부분 [1]집합으로 나눈 것입니다.모든 절단에 따라 파티션의 각 하위 집합에 끝점이 하나씩 있는 가장자리 세트인 절단 세트가 결정됩니다.이 가장자리들은 절단 부위를 가로지른다고 한다.연결된 그래프에서 각 컷 세트는 고유한 컷을 결정하며, 경우에 따라 컷은 정점 파티션이 아닌 컷 세트로 식별됩니다.

흐름 네트워크에서 s-t 컷은 선원과 싱크가 서로 다른 서브셋에 있어야 하는 컷이며, 그 컷 세트는 선원 측에서 싱크 측으로 가는 가장자리만으로 구성됩니다.s-t 절단 용량은 절단 세트의 각 모서리 용량 합계로 정의됩니다.

정의.

절단 C = (S,T)는 그래프 G = (V,E)의 V를 2개의 부분 집합 S 및 T로 분할한 것이다.절단 C = (S,T)의 컷 세트는 한쪽 끝점이 S에 있고 다른 한쪽 끝점이 T에 있는 에지의 세트 {(u,v) e E s S, v t T}이다.s와 t가 그래프 G의 꼭지점일 경우 s-t 컷은 s가 세트 S에 속하고 t가 세트 T에 속하는 컷입니다.

무가중 무방향 그래프에서 절단 크기 또는 가중치는 절단된 모서리와 교차하는 모서리 수입니다.가중 그래프에서 값 또는 가중치는 절단된 모서리의 가중치 합계에 의해 정의됩니다.

본드는 적절한 서브셋으로 다른 컷셋이 없는 컷셋입니다.

최소 컷

최소 컷.
주요 기사:최소 컷

절단 크기 또는 중량이 다른 절단 크기보다 크지 않은 경우 절단은 최소입니다.오른쪽 그림은 최소 컷을 나타내고 있습니다.이 컷의 사이즈는 2이며 그래프는 브릿지리스이기 때문에 사이즈1의 컷은 없습니다.

max-flow min-cut 정리는 최대 네트워크 흐름과 소스와 싱크를 분리하는 최소 컷의 컷 에지 가중치의 합계가 같다는 것을 증명합니다.최소 컷 문제를 해결하기 위한 다항 시간 방법, 특히 에드먼즈-카르프 [2]알고리즘이 있습니다.

최대 컷

최대 컷
주요 기사: 최대 컷

절단 크기가 다른 절단 크기보다 작지 않은 경우 최대 절단입니다.오른쪽 그림은 최대 절단을 보여줍니다. 절단의 크기는 5이며 그래프가 양분하지 않기 때문에 크기 6 또는 E(가장자리 수)의 절단은 없습니다(홀수 주기가 있음).

일반적으로 최대 컷을 찾는 것은 계산상 어렵습니다.[3]최대 컷 문제는 Karp의 21개의 NP 완전 [4]문제 중 하나입니다.max-cut 문제도 APX-hard이며, 이는 P [5]= NP가 아닌 한 다항식 시간 근사 스킴이 없음을 의미한다.단, 반무한 [6]프로그래밍을 사용하여 일정한 근사비 내에서 근사할 수 있다.

min-cut과 max-cut은 선형 프로그래밍 측면에서 이중 문제가 아닙니다. 그러나 목표 함수에서 min-cut을 max로 변경하여 한 문제에서 다른 문제로 전환됩니다.max-flow 문제는 min-cut [7]문제의 듀얼입니다.

가장 희박한 컷

가장 드문 절단 문제는 절단된 부분의 가장자리 수를 파티션의 작은 절반에 있는 정점 수로 나눈 비율을 최소화하기 위해 정점을 양분하는 것입니다.이 목적 함수는 희박한(절단과 교차하는 가장자리가 거의 없음) 솔루션과 균형 잡힌(분할에 가까운) 솔루션을 선호합니다.이 문제는 NP-hard로 알려져 있으며, 가장 잘 알려진 근사 알고리즘은O(' n입니다.이는 Arora, Rao 및 Vazirani(2009)[8]에 의한 것입니다.

공간 절약

무방향 그래프의 모든 절단 세트의 패밀리를 그래프의 절단 공간이라고 합니다.이것은 2개의 컷 세트의 대칭 차이를 벡터 덧셈 연산으로서 산술 모듈로 2의 2요소 유한장 위에 벡터 공간을 형성하고, [9][10]사이클 공간의 직교 보체이다.그래프의 가장자리에 양의 가중치가 주어지는 경우, 절단 공간의 최소 가중치 기준은 그래프와 동일한 정점 집합의 Gomory-Hu [11]트리라고 불리는 트리로 설명할 수 있습니다.이 트리의 각 가장자리는 원본 그래프 내의 결합과 관련지어지며, 2개의 노드 s와 t 사이의 최소 절단은 트리 내의 s에서 t까지의 경로에 관련된 노드 중 최소 중량 결합이다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ "NetworkX 2.6.2 documentation". networkx.algorithms.cuts.cut_size. Retrieved 2021-12-10. A cut is a partition of the nodes of a graph into two sets. The cut size is the sum of the weights of the edges “between” the two sets of nodes.
  2. ^ 를 클릭합니다Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, p. 563,655,1043, ISBN 0-262-03293-7.
  3. ^ 를 클릭합니다Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, A2.2: ND16, p. 210, ISBN 0-7167-1045-5.
  4. ^ 를 클릭합니다Karp, R. M. (1972), "Reducibility among combinatorial problems", in Miller, R. E.; Thacher, J. W. (eds.), Complexity of Computer Computation, New York: Plenum Press, pp. 85–103.
  5. ^ 를 클릭합니다Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R. (2004), "Optimal inapproximability results for MAX-CUT and other two-variable CSPs?" (PDF), Proceedings of the 45th IEEE Symposium on Foundations of Computer Science, pp. 146–154.
  6. ^ 를 클릭합니다Goemans, M. X.; Williamson, D. P. (1995), "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming", Journal of the ACM, 42 (6): 1115–1145, doi:10.1145/227683.227684.
  7. ^ 를 클릭합니다Vazirani, Vijay V. (2004), Approximation Algorithms, Springer, pp. 97–98, ISBN 3-540-65367-8.
  8. ^ 를 클릭합니다Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009), "Expander flows, geometric embeddings and graph partitioning", J. ACM, ACM, 56 (2): 1–37, doi:10.1145/1502793.1502794.
  9. ^ 를 클릭합니다Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN 9781584885054.
  10. ^ 를 클릭합니다Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
  11. ^ 를 클릭합니다Korte, B. H.; Vygen, Jens (2008), "8.6 Gomory–Hu Trees", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21, Springer, pp. 180–186, ISBN 978-3-540-71844-4.