Lát cắt (lý thuyết đồ thị)

Trong lý thuyết đồ thị, một lát cắt là một cách phân chia tập hợp các đỉnh của một đồ thị thành hai tập hợp con không giao nhau. Tập hợp cắt của lát cắt là tập hợp các cạnh có hai đầu nằm ở hai tập hợp con khác nhau. Một cạnh của đồ thị là bị cắt nếu nó nằm trong tập hợp cắt.

Trong một đồ thị vô hướng không trọng số, kích thước của một lát cắt chính là số cạnh bị cắt. Trong đồ thị có trọng số, kích thước hay trọng số của lát cắt là tổng trọng số các cạnh bị cắt.

Trong một đồ thị luồng, một lát cắt s-t là một lát cắt trong đó đỉnh phát và đỉnh thu nằm ở hai tập hợp con khác nhau, và tập hợp cắt chỉ gồm các cung từ tập hợp con chứa đỉnh phát tới tập hợp con chứa đỉnh thu. Khả năng thông qua của một lát cắt s-t được định nghĩa là tổng khả năng thông qua của các cung trong tập hợp cắt.

Khái niệm lát cắt của một đồ thị cũng được dùng để chỉ tập hợp cắt thay vì phân chia của tập hợp đỉnh.

Định nghĩa

Một lát cắt ${\displaystyle C=(S,T)}$ là một cách phân chia tập hợp các đỉnh ${\displaystyle V}$ của đồ thị ${\displaystyle G=(V,E)}$.

Một lát cắt s-t ${\displaystyle C=(S,T)}$ của đồ thị ${\displaystyle N=(V,E)}$ là một cách phân chia ${\displaystyle N}$ sao cho ${\displaystyle s\in S}$ và ${\displaystyle t\in T}$, trong đó ${\displaystyle s}$ và ${\displaystyle t}$ được gọi là đỉnh phát và đỉnh thu của ${\displaystyle N}$.

Tập hợp cắt của lát cắt ${\displaystyle C=(S,T)}$ là tập hợp ${\displaystyle \{(u,v)\in E|u\in S,v\in T\}}$.

Kích thước của lát cắt ${\displaystyle C=(S,T)}$ trong đồ thị không trọng số là số cạnh trong tập hợp cắt. Trong đồ thị có trọng số, kích thước của lát cắt là tổng trọng số các cạnh trong tập hợp cắt.

Lát cắt nhỏ nhất

Một lát cắt nhỏ nhất.

Bài chi tiết: Lát cắt nhỏ nhất

Một lát cắt là nhỏ nhất nếu kích thước của nó không lớn hơn kích thước bất kì lát cắt nào khác. Ví dụ bên phải là một lát cắt nhỏ nhất: kích thước của nó là 2, và không có lát cắt nào có kích thước 1 vì đồ thị không có cầu.

Định lý luồng cực đại lát cắt cực tiểu chứng minh rằng luồng cực đại của một đồ thị luồng đúng bằng tổng khả năng thông qua của lát cắt nhỏ nhất chia cắt đỉnh phát và đỉnh thu. Có nhiều thuật toán thời gian đa thức để giải bài toán tìm luồng cực đại và lát cắt nhỏ nhất, chẳng hạn như thuật toán Edmonds-Karp.

Lát cắt lớn nhất

Một lát cắt lớn nhất.

Bài chi tiết: Lát cắt lớn nhất

Một lát cắt là lớn nhất nếu kích thước của nó không nhỏ hơn kích thước bất kì lát cắt nào khác. Ví dụ bên phải là một lát cắt lớn nhất: kích thước của nó là 5, và không có lát cắt nào có kích thước bằng |E| vì đồ thị này không phải là đồ thị hai phía (tồn tại chu trình lẻ).

Trong trường hợp tổng quát, việc tìm lát cắt lớn nhất đòi hỏi nhiều thời gian tính toán. Bài toán này là một trong 21 bài toán NP-đầy đủ của Karp. Hơn thế nữa, ngay cả việc tính xấp xỉ lát cắt lớn nhất với tỉ lệ lớn hơn 16/17 cũng là NP-khó.^[1][2]

Ghi chú là hai bài toán tìm lát cắt nhỏ nhất và lớn nhất không phải là các bài toán đối ngẫu theo nghĩa của quy hoạch tuyến tính, mặc dù ta thu được bài toán kia từ bài toán này bằng việc đổi hàm mục tiêu từ min sang max. Bài toán tìm luồng cực đại là bài toán đối ngẫu của bài toán tìm lát cắt nhỏ nhất.

Lát cắt thưa nhất

Bài toán tìm lát cắt thưa nhất yêu cầu chia các đỉnh thành hai phần sao cho tỉ lệ giữa số cạnh bị cắt và số đỉnh trong phần nhỏ hơn là nhỏ nhất có thể. Hàm mục tiêu này để tìm lát cắt có ít cạnh và phân chia tập hợp đỉnh càng đều càng tốt. Bài toán này là NP-khó, và thuật toán xấp xỉ tốt nhất hiện nay của Arora, Rao & Vazirani (2009) có tỉ lệ xấp xỉ ${\displaystyle O({\sqrt {\log n}})}$.

Xem thêm

• Liên thông (lý thuyết đồ thị)

Ghi chú

1. Håstad (2001)
2. Trevisan và đồng nghiệp (2000)

Tham khảo

• 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, ISSN 0004-5411
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001). Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. tr. 563, 655, 1043. ISBN 0-262-03293-7.
• Michael R. Garey và David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.2: ND16, pg.210.
• 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
• Håstad, Johan (2001), “Some optimal inapproximability results”, Journal of the ACM, 48 (4): 798–859, doi:10.1145/502090.502098
• R. M. Karp, Reducibility among combinatorial problems, in R. E. Miller and J. W. Thacher (eds.), Complexity of Computer Computation, Plenum Press, New York, 85-103 (1972)
• Khot, S.; Kindler, G.; Mossel, E.; O’Donnell, R. (2004), “Optimal inapproximability results for MAX-CUT and other two-variable CSPs?”, Proceedings of the 45th IEEE Symposium on Foundations of Computer Science (PDF), tr. 146–154
• Meira, Luis A. A. “Semidefinite Programming Based Algorithms for the Sparsest Cut Problem” (PDF). Truy cập ngày 6 tháng 9 năm 2011.
• Trevisan, Luca; Sorkin, Gregory; Sudan, Madhu; Williamson, David (2000), “Gadgets, Approximation, and Linear Programming”, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science: 617–626.
• Vijay V. Vazirani (2004). Approximation Algorithms. Springer. tr. 97–98. ISBN 3-540-65367-8.