Bài tập Lập trình - Bài 2: Tô màu đồ thị
Bài tập lập trình 2: Tô màu đồ thị
Bạn đã biết trong bài giảng:
Định lý 1. Cho G là đồ thị với mọi đỉnh đều có bậc ≤ k. Nếu G không chính quy, vậy thì χ(G) ≤ k.
Chứng minh của mệnh đề này cho chúng ta cách xây dựng thứ tự các đỉnh để thuật toán tham
lam tô màu đỉnh dùng không quá k màu (cho đồ thị không chính quy). Bài tập này yêu cầu bạn
cài đặt thuật toán này.
Nhiệm vụ: Nhập đồ thị từ bàn phím dưới dạng danh sách cạnh. Đưa ra màn hình một cách tô
màu đồ thị dùng
• Không nhiều hơn k màu nếu G không chính quy.
• Không nhiều hơn k + 1 màu nếu G chính quy.
Dữ liệu vào: Từ file dothi.txt trong đó
• Dòng đầu tiên ghi hai số nguyên n và m là số đỉnh và số cạnh của đồ thị;
• Ở m dòng tiếp theo, mỗi dòng ghi hai số nguyên tương ứng với một cạnh của đồ thị.
Dữ liệu ra: file dothitomau.dot biểu diễn đồ thị ở dạng ngôn ngữ DOT với các đỉnh đã được tô
màu.
Ví dụ:
Dữ liệu vào
Dữ liệu ra
4 5
1 2
2 3
3 4
4 1
1 5
graph dothi
{
5 [fillcolor=red, style=filled];
4 [fillcolor=red, style=filled];
1 [fillcolor=green, style=filled];
3 [fillcolor=green, style=filled];
2 [fillcolor=red, style=filled];
1 -- 2;
2 -- 3;
3 -- 4;
4 -- 1;
1 -- 5;
}
Với dữ liệu ra dothitomau.dot, ta biên dịch với chương trình graphviz:
dot -Tpdf dothitomau.dot -o graph.pdf
1
2 trang
17740
Free
Bạn đang xem tài liệu "Bài tập Lập trình - Bài 2: Tô màu đồ thị", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_tap_lap_trinh_bai_2_to_mau_do_thi.pdf
rgb.txt- test.dot
