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  là một cách phân chia tập hợp các đỉnh  của đồ thị .

 Một lát cắt s-t  của đồ thị  là một cách phân chia  sao cho  và , trong đó  và  được gọi là đỉnh phát và đỉnh thu của .

 Tập hợp cắt của lát cắt  là tập hợp .

Kích thước của lát cắ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 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à 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ó.

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  có tỉ lệ xấp xỉ .

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

Ghi chú

Tham khảo

 A2.2: ND16, pg.210.

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)

.

Thể loại:Lý thuyết đồ thị
Thể loại:Tối ưu hóa tổ hợp