1443673
Lát cắt (lý thuyết đồ thị)
https://vi.wikipedia.org/wiki?curid=1443673
Title: Lát cắt (lý thuyết đồ thị)
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ỉ formula_15.