graph Đạo với indegree tối đa của một đỉnh

Question

Tôi đã cố gắng để nhìn vào vài ứng dụng của dòng chảy mạng khi tôi đi qua vấn đề này:

Chúng tôi bắt đầu với một đồ thị có hướng, G = (V,E). Chúng tôi cần thêm các cạnh khác vào biểu đồ sao cho chúng tôi có \forall u,v \in V, e = (u -> v) or e = (v -> u) but not both. tức là chúng tôi muốn thêm các cạnh khác vào biểu đồ để mỗi cặp đỉnh trong biểu đồ được kết nối với nhau (với cạnh ngoài hoặc cạnh đến nhưng không được cả hai). Vì vậy, tổng cộng chúng ta sẽ có các cạnh |V||V-1|/2. Trong khi chúng tôi xây dựng biểu đồ này, chúng tôi cần đảm bảo rằng sự không đồng ý của một đỉnh đã cho, giả sử w là mức tối đa trong tất cả các đỉnh của biểu đồ (nếu có thể, được đưa ra biểu đồ gốc). Lưu ý rằng chúng tôi không thể thay đổi hướng của các cạnh trong biểu đồ gốc.

Tôi đang cố giải quyết bằng lưu lượng mạng bằng cách tạo mạng không có đỉnh w (và với 2 các đỉnh mới cho nguồn, s và chìm, t). Nhưng tôi không chắc chắn làm thế nào để thể hiện năng lực và hướng dòng chảy trong biểu đồ mới để đơn giản hóa vấn đề với lưu lượng mạng để tìm các hướng cạnh trong biểu đồ. Có lẽ những gì tôi đang làm là sai, nhưng tôi chỉ viết nếu ai đó có thể nhận được một gợi ý từ nó.

Answer 1

Khi tấn công loại sự cố này, tôi có xu hướng viết xuống một chương trình toán học và sau đó xoa bóp nó. Rõ ràng, chúng ta nên định hướng tất cả các cạnh thiếu liên quan đến w về phía w. Gọi d là kết quả của độ w. Đối với tất cả các i, j riêng biệt, hãy để x_{ij} = 1 nếu arc i-> j xuất hiện trong dung dịch và để x_{ij} = 0 nếu arc j-> i xuất hiện.

forall j. sum_i x_{ij} <= k 
forall i <> j. x_{ij} = 1 - x_{ji} 
forall i <> j. x_{ij} in {0, 1} 

Viết lại để sử dụng x_{ij} chỉ khi tôi < j.

(*) forall j. sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) <= k 
forall i < j. x_{ij} in {0, 1} 

Bây giờ (*) bắt đầu giống với ràng buộc bảo tồn, vì mỗi biến xuất hiện một lần tiêu cực và một lần tích cực. Hãy thay đổi sự bất bình đẳng thành một sự bình đẳng.

(*) forall j. x_{si} + sum_{i<j} x_{ij} + sum_{i>j} (1-x_{ji}) = k 
       ^^^^^^           ^
forall i < j. x_{ij} in {0, 1} 
forall i. x_{si} >= 0 
^^^^^^^^^^^^^^^^^^^^^ 

Chúng tôi gần như tất cả các cách để một LP flow - chúng ta chỉ cần để làm sạch ra hằng 1 và k. Tôi sẽ cho phép bạn xử lý phần còn lại (nó liên quan đến việc giới thiệu t).