Tô màu đồ thị

Giới thiệu về máy tính này

Máy tính Tô màu đồ thị tìm sắc số χ(G) — số màu ít nhất cần để tô các đỉnh của đồ thị sao cho không có cạnh nào nối hai đỉnh cùng màu — và hiển thị một cách tô màu tối ưu. Nhập số đỉnh và danh sách cạnh; công cụ tính chính xác χ bằng tìm kiếm nhánh cận, cho biết bậc lớn nhất Δ và clique lớn nhất ω (một cận dưới của χ), đánh dấu đồ thị hai phía và đồ thị đầy đủ, rồi vẽ đồ thị đã tô màu. Hữu ích cho lập lịch, cấp phát thanh ghi, tô màu bản đồ và nghiên cứu sắc số.

Cách tô màu đồ thị

1. Nhập số đỉnh; các đỉnh được đánh số từ 1 đến n.
2. Liệt kê các cạnh dưới dạng cặp như 1-2, 2-3 — mỗi kết nối một cặp.
3. Đọc sắc số χ(G) và màu được gán cho từng đỉnh.
4. So sánh χ với clique lớn nhất ω để hiểu vì sao cần chừng ấy màu, hoặc tải một ví dụ có sẵn để khám phá.

Ví dụ thường gặp

• Một tam giác (K₃) cần 3 màu — mọi cặp đỉnh của nó đều kề nhau.
• Chu trình chẵn là đồ thị hai phía và chỉ cần 2 màu; chu trình lẻ như C₅ cần 3 màu.
• Đồ thị đầy đủ Kₙ cần đúng n màu.
• Một clique lớn nhất cỡ ω buộc phải dùng ít nhất ω màu, nên χ(G) ≥ ω.
• Đồ thị Grötzsch cần 4 màu dù không chứa tam giác nào, nên χ có thể lớn hơn số clique.