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 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ỉ formula _ 15 Xem thêm BULLET Liên_thông lý_thuyết đồ_thị Tham_khảo BULLET A2 2 ND16 pg 210 BULLET 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
Lát cắt ( lý_thuyết đồ_thị )