Chương trình C ++ để triển khai Định lý Vizing

Định lý của Vizing tuyên bố rằng chỉ số màu của đồ thị đơn giản có thể là maxdegree hoặc maxdegree + 1. Ở đây, chỉ số màu có nghĩa là màu tối đa cần thiết để tô màu cho các cạnh của biểu đồ.

Đây là một chương trình C ++ để triển khai Định lý Vizing.

Thuật toán

 Begin Lấy số lượng đỉnh và cạnh làm đầu vào. Lấy cặp đỉnh cho các cạnh. function EdgeColor ():Tô màu cho các cạnh của đồ thị. 1) Gán màu cho cạnh hiện tại là c, tức là ban đầu. 2) Nếu bất kỳ cạnh nào trong cùng một màu bị chiếm, hãy loại bỏ màu này và chuyển sang gắn cờ lại và thử với màu tiếp theo. 
 Ví dụ 
 
 #include  using namespace std; void EdgeColor (int ed [] [3], int e) {int i, c, j; for (i =0; i > n; cout <<"Nhập số cạnh của đồ thị:"; cin>> e; int ed [e] [3], deg [n + 1] ={0}; for (i =0; i > ed [i] [0]; cout <<"\ n (2):"; cin>> ed [i] [1]; // tính tung độ của từng đỉnh ed [i] [2] =-1; deg [ed [i] [0]] ++; deg [ed [i] [1]] ++; } // tìm ra độ lớn nhất. for (i =1; i <=n; i ++) {if (max  
 Đầu ra 
 
 Nhập số đỉnh của đồ thị:4 Nhập số cạnh của đồ thị:3 Nhập cặp đỉnh cho cạnh 1N (1):1N (2):2 Nhập cặp đỉnh cho cạnh 2N (1):3N ( 2):2 Nhập cặp đỉnh cho cạnh 3N (1):4N (2):1A Theo định lý Vizing, đồ thị này có thể sử dụng tối đa 3 màu để tạo ra màu cạnh hợp lệ. Màu của cạnh giữa đỉnh N (1):1 và N (2):2 là:màu 1. Màu của cạnh giữa đỉnh N (1):3 và N (2):2 là:màu2. Màu của cạnh giữa đỉnh N (1):4 và N (2):1 là:color2.