Luận văn Bài toán ghép cặp và ứng dụng

Tóm tắt Luận văn Bài toán ghép cặp và ứng dụng: ...ậy gọi là ủồ thị ủối ngẫu của bản ủồ. Như vậy mọi bản ủồ trờn mặt phẳng ủều cú ủồ thị ủối ngẫu phẳng. 1.3. BẬC, NỬA BẬC VÀO, NỬA BẬC RA 1.3.1 Định nghĩa bậc, nửa bậc vào, nửa bậc ra: 9 • Bậc: Cho ủồ thị G = (V, E). Bậc của ủỉnh v V∈ là tổng số cạnh liờn thuộc với nú và ký hiệu là d(v)....E,c) với nguồn a và ủớch z, f = { fij│( i, j)∈ G } là luồng trờn mạng G, (S,T) là lỏt cắt của G. Khi ủú, khả năng thụng qua của lỏt cắt (S,T) khụng nhỏ hơn giỏ trị của luồng f, tức là C(S, T) ≥ v(f) Định lý 2.3 Cho mạng G với nguồn a và ủớch z, f = { fij│( i, j)∈ G } là luồng trờn mạng ...chất (i) 18 CHƯƠNG 3 ỨNG DỤNG CỦA BÀI TOÁN GHẫP CẶP 3.1 BÀI TOÁN PHÂN CễNG CễNG VIỆC 3.1.1 Phỏt biểu bài toỏn Trong 1 cụng ty, cú n người cụng nhõn x1, x2, …, xn và n cụng việc y1, y2,…,yn. Mỗi người cụng nhõn là cú thể làm ủược 1 hoặc nhiều hơn một việc. Tỡm ủiều kiện ủể tất cả c...