Bài tập Lập trình về đồ thị - 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 thì được file graph.pdf với nội dung như Hình 1. Tài liệu về ngôn ngữ DOT:. Tài liệu Drawing graphs with dot có thể download tại link dưới đây: https://www.graphviz.org/pdf/dotguide.pdf 1 25 4 1 2 3 Hình 1. Đồ thị được tô màu của ví dụ trước