Máy Tính Tô Màu Đồ Thị

Giới thiệu về Máy Tính Tô Màu Đồ Thị

Máy Tính Tô Màu Đồ Thị tính toán sắc số χ(G) và tạo cách tô màu đỉnh hợp lệ cho bất kỳ đồ thị vô hướng nào. Hãy nhập đồ thị của bạn dưới dạng danh sách cạnh hoặc danh sách kề và công cụ sẽ trả về số lượng màu tối thiểu cần thiết sao cho không có hai đỉnh kề nhau nào có cùng màu, cùng với trực quan hóa SVG tương tác, dấu vết hoạt ảnh DSATUR và bảng phân tích chi tiết từng màu sắc được gán cho các đỉnh.

Tô màu đồ thị là gì?

Một cách tô màu đỉnh đúng của đồ thị G = (V, E) là việc gán màu cho mỗi đỉnh sao cho mọi cạnh đều có các điểm đầu mút khác màu nhau. Sắc số, ký hiệu là χ(G), là số màu nhỏ nhất mà đồ thị có thể được tô màu đúng. Việc tính toán χ(G) nói chung là bài toán NP-khó, nhưng nó có một lý thuyết toán học tuyệt đẹp và nhiều ứng dụng thực tế: lập lịch thi, phân bổ tần số vô tuyến, cấp phát thanh ghi trong trình biên dịch và định lý bốn màu nổi tiếng cho bản đồ phẳng.

Các định lý và cận quan trọng

• Cận tầm thường: 1 ≤ χ(G) ≤ |V| cho bất kỳ đồ thị nào.
• Cận dưới clique: χ(G) ≥ ω(G), trong đó ω(G) là kích thước của clique lớn nhất.
• Đặc điểm đồ thị phân đôi: χ(G) ≤ 2 khi và chỉ khi G không có chu trình lẻ (König).
• Định lý Brooks: χ(G) ≤ Δ(G), trừ khi G là đồ thị đầy đủ hoặc chu trình lẻ, trong trường hợp đó χ(G) = Δ(G) + 1. Ở đây Δ(G) là bậc tối đa.
• Định lý bốn màu: Mọi đồ thị phẳng đều có thể tô bằng 4 màu.
• Cận trên tham lam: Bất kỳ thuật toán tham lam nào cũng sử dụng tối đa Δ(G) + 1 màu.

Các thuật toán được sử dụng

DSATUR (Degree of Saturation)

Được giới thiệu bởi Daniel Brélaz vào năm 1979, DSATUR là một trong những heuristic thực tế mạnh nhất để tô màu đồ thị. Nó liên tục chọn đỉnh chưa tô màu có các láng giềng đã sử dụng nhiều màu sắc khác nhau nhất (độ bão hòa của nó), giải quyết các trường hợp bằng nhau dựa trên bậc của đỉnh, và gán cho nó màu nhỏ nhất chưa được các láng giềng sử dụng. DSATUR được chứng minh là tối ưu trên đồ thị phân đôi và trên nhiều họ đồ thị có cấu trúc, đồng thời tạo ra các cách tô màu chất lượng cao trong vài mili giây trên đồ thị có hàng trăm đỉnh.

Welsh-Powell

Thuật toán Welsh-Powell sắp xếp các đỉnh theo thứ tự bậc giảm dần và sau đó tô màu chúng một cách tham lam. Nó chạy trong thời gian O(|V|²) và đảm bảo sử dụng tối đa Δ(G) + 1 màu. Nó cực kỳ nhanh và thường là một ước tính sơ bộ tốt, mặc dù có thể bị DSATUR đánh bại trên các đồ thị có cấu trúc cục bộ thay đổi.

Tham lam (theo thứ tự đầu vào)

Thuật toán đơn giản nhất: đi qua các đỉnh theo thứ tự nhập vào và gán cho mỗi đỉnh màu nhỏ nhất chưa được láng giềng đã tô màu sử dụng. Kết quả phụ thuộc vào thứ tự đầu vào, nhưng thứ tự ngẫu nhiên cung cấp một mức cơ sở để bạn so sánh với các heuristic thông minh hơn.

Quay lui chính xác

Đối với các đồ thị nhỏ (tối đa khoảng 18 đỉnh), máy tính có thể tìm thấy sắc số thực sự bằng cách thử k = 2, 3, 4, ... và cố gắng tô k-màu cho đồ thị bằng kỹ thuật quay lui duyệt theo chiều sâu. Việc tìm kiếm sắp xếp các đỉnh theo bậc giảm dần và cắt tỉa khi không có màu nào khả dụng. Khi thuật toán chính xác thành công, kết quả sẽ được gắn nhãn "Chính xác".

Định dạng đầu vào

Danh sách cạnh

Viết mỗi cạnh dưới dạng hai nhãn đỉnh cách nhau bởi dấu gạch ngang, khoảng trắng hoặc mũi tên. Phân cách các cạnh bằng dấu phẩy hoặc xuống dòng. Nhãn đỉnh có thể là chữ cái, chữ số hoặc dấu gạch dưới. Ví dụ:

Danh sách kề

Viết mỗi đỉnh, một dấu hai chấm và danh sách các láng giềng của nó cách nhau bởi dấu phẩy. Ví dụ:

Các vòng lặp tự thân bị từ chối vì một đỉnh không thể được gán màu khác với chính nó. Các cạnh trùng lặp sẽ được loại bỏ một cách âm thầm và đồ thị được xử lý như một đồ thị vô hướng.

Cách sử dụng máy tính này

1. Chọn định dạng: Chuyển đổi giữa danh sách cạnh và danh sách kề bằng các nút radio.
2. Nhập đồ thị: Dán dữ liệu của bạn hoặc nhấp vào một trong các ví dụ nhanh (tam giác, đầy đủ K₅, bánh xe kiểu Petersen, phân đôi K₃,₃, lập lịch thi).
3. Chọn thuật toán: Để "Tự động" để có mặc định tốt nhất, hoặc bắt buộc sử dụng Welsh-Powell, tham lam, DSATUR, hoặc quay lui chính xác.
4. Nhấp "Tô Màu Đồ Thị": Sắc số, danh sách phân bổ màu, SVG tương tác với các nút có thể kéo và dấu vết từng bước hoạt ảnh sẽ xuất hiện bên dưới.
5. Khám phá: Nhấn Phát để xem thuật toán tô màu từng đỉnh, kéo các nút để sắp xếp lại bố cục và sử dụng Lùi / Tiếp để xem qua dấu vết một cách thủ công.

Ứng dụng thực tế của tô màu đồ thị

Lập lịch thi

Coi mỗi bài thi là một đỉnh và vẽ một cạnh giữa các bài thi có chung ít nhất một sinh viên. Một cách tô màu đúng với k màu sẽ tạo ra một lịch thi với k khung giờ sao cho không có sinh viên nào bị trùng lịch. Sắc số chính là số khung giờ tối thiểu cần thiết.

Phân bổ tần số vô tuyến

Các máy phát trong phạm vi nhiễu của nhau phải phát sóng trên các tần số khác nhau. Sắc số của đồ thị nhiễu là số lượng tần số tối thiểu cần dùng.

Cấp phát thanh ghi

Trong trình biên dịch, phạm vi sống của các biến là các đỉnh; hai phạm vi sống chồng chéo về thời gian nghĩa là có một cạnh giữa chúng. Một cách tô k-màu gán các biến cho k thanh ghi CPU mà không bị xung đột.

Tô màu bản đồ

Các quốc gia có chung biên giới phải nhận các màu khác nhau. Định lý bốn màu (Appel-Haken, 1976) chứng minh rằng bốn màu luôn đủ cho bất kỳ bản đồ phẳng nào.

Sudoku và giải đố ràng buộc

Một bảng Sudoku hoàn chỉnh là một cách tô 9-màu của một đồ thị có 81 đỉnh (ô) và các cạnh kết nối các ô trong cùng một hàng, cột hoặc ô 3×3. Tô màu đồ thị là cốt lõi toán học của nhiều trò chơi giải đố thỏa mãn ràng buộc.

Các trường hợp đặc biệt thú vị

• Đồ thị đầy đủ K_n: χ(K_n) = n. Mọi cặp đỉnh đều kề nhau, nên tất cả màu sắc phải khác nhau.
• Chu trình C_n: χ(C_n) = 2 nếu n chẵn, 3 nếu n lẻ.
• Cây: Bất kỳ cây nào có ≥ 2 đỉnh đều có χ = 2 (cây là đồ thị phân đôi).
• Đồ thị phân đôi: χ = 2 nếu đồ thị có ít nhất một cạnh.
• Đồ thị Petersen: Một đồ thị 3-regular nổi tiếng với χ = 3.
• Đồ thị bánh xe W_n: Một đỉnh trung tâm nối với một chu trình n đỉnh. χ = 3 nếu n chẵn, 4 nếu n lẻ.

Câu hỏi thường gặp

Sắc số của một đồ thị là gì?

Sắc số χ(G) là số màu nhỏ nhất cần để tô màu các đỉnh của đồ thị sao cho không có hai đỉnh kề nhau nào cùng màu. Đồ thị phân đôi có sắc số tối đa là 2; đồ thị có tam giác có sắc số ít nhất là 3; và theo định lý Brooks, sắc số không bao giờ vượt quá bậc tối đa, ngoại trừ đồ thị đầy đủ và chu trình lẻ.

Máy tính này sử dụng thuật toán nào?

Với đồ thị nhỏ, máy tính chạy tìm kiếm quay lui chính xác. Với đồ thị lớn, nó dùng heuristic DSATUR để tô màu các đỉnh dựa trên độ bão hòa màu của láng giềng. Bạn cũng có thể chọn Welsh-Powell hoặc tham lam.

Tôi nên nhập đồ thị như thế nào?

Dùng chế độ danh sách cạnh (ví dụ: A-B) hoặc danh sách kề (ví dụ: A: B, C). Các vòng lặp tự thân không được chấp nhận.

Tại sao DSATUR không phải lúc nào cũng tìm thấy sắc số thực sự?

Vì đây là bài toán NP-khó. DSATUR là một heuristic mạnh và thường cho kết quả tối ưu, nhưng đôi khi có thể dùng nhiều màu hơn cần thiết. Máy tính cung cấp thêm cận dưới từ clique để bạn đánh giá độ chính xác.

Ứng dụng thực tế là gì?

Lập lịch thi, phân bổ tần số vô tuyến, cấp phát thanh ghi CPU, tô màu bản đồ, giải Sudoku và phân công công việc.

Sắc số có luôn bằng clique lớn nhất không?

Không. Clique lớn nhất là cận dưới. Chúng bằng nhau trong đồ thị hoàn hảo, nhưng trong đồ thị tổng quát (như đồ thị Mycielski), sắc số có thể lớn hơn nhiều so với chỉ số clique.

Đồ thị lớn nhất mà máy tính này xử lý được là bao nhiêu?

Máy tính hỗ trợ tối đa 60 đỉnh và 600 cạnh. Với thuật toán chính xác, đồ thị trên 18 đỉnh có thể tự động chuyển sang DSATUR để tránh xử lý quá chậm.

Đọc thêm

• Tô màu đồ thị — Wikipedia
• Thuật toán DSATUR — Wikipedia
• Đa thức sắc số — Wikipedia
• Định lý bốn màu — Wikipedia
• Định lý Brooks — Wikipedia

Các công cụ liên quan khác:

Phép toán toán học nâng cao:

• Máy Tính Antilog
• Máy tính hàm Beta
• Máy tính hệ số nhị thức
• Máy tính phân phối xác suất nhị thức
• Máy tính Bitwise
• Máy tính Định lý Giới hạn Trung tâm
• Máy tính kết hợp
• Máy tính hàm lỗi bổ sung
• Máy tính số phức
• Máy tính Entropy
• Máy tính chức năng lỗi
• Máy tính giảm dần theo cấp số nhân
• Máy tính tăng trưởng theo cấp số nhân
• Máy tính Tích phân Lũy thừa
• máy-tính-số-mũ-độ-chính-xác-cao Nổi bật
• Máy tính giai thừa Nổi bật
• Máy tính Hàm Gamma
• Máy tính tỷ lệ vàng
• Máy tính Nửa đời
• Máy tính phần trăm tăng trưởng
• Máy tính hoán vị
• Máy tính Phân phối Poisson
• Máy tính căn bậc của đa thức với các bước chi tiết
• Máy tính xác suất
• Máy tính phân bố xác suất
• Máy tính Tỷ lệ
• Máy tính công thức bậc hai
• Máy Tính Khoa Học Nổi bật
• Máy tính ký hiệu khoa học
• Máy Tính Chữ Số Có Nghĩa Mới
• Máy tính tổng khối
• Máy tính tổng các số liên tiếp
• Máy tính Tổng Bình phương
• Công cụ tạo bảng chân trị Mới
• Máy tính lý thuyết tập hợp Mới
• Công cụ tạo Biểu đồ Venn (3 Tập hợp) Mới
• Máy tính Định lý Số dư Trung Quốc Mới
• Máy tính Hàm Phi Euler Mới
• Máy tính Thuật toán Euclid Mở rộng Mới
• Máy tính Nghịch đảo Nhân theo Mô-đun Mới
• Máy tính Phân số liên tục Mới
• Máy tính Đường đi Ngắn nhất Dijkstra Mới
• Máy tính Cây khung nhỏ nhất Mới
• Trình xác thực dãy bậc đồ thị Mới
• Máy tính Hoán vị lệch (Giai thừa phụ) Mới
• Máy tính số Stirling Mới
• Máy tính Nguyên lý Chuồng bồ câu Mới
• Máy tính Phân phối Dừng Chuỗi Markov Mới
• Máy Tính Làm Tròn Mới
• Máy Tính Phân Phối Nhị Thức Âm Mới
• Máy tính Hoán vị Có lặp Mới
• Máy Tính Lũy Thừa Modular Mới
• Máy Tính Căn Nguyên Thủy Mới
• Công Cụ Rút Gọn Đại Số Boolean Mới
• Công cụ Giải Bản đồ Karnaugh (K-Map) Mới
• Máy Tính Tô Màu Đồ Thị Mới
• Máy Tính Sắp Xếp Topo Mới
• Máy Tính Ma Trận Kề Mới
• Máy tính Bao hàm - Loại trừ Mới
• Công cụ Giải Quy hoạch Tuyến tính Mới
• Trình Giải Bài Toán Người Du Hành (TSP) Mới
• Công cụ Kiểm tra Đường đi Hamilton Mới