Đơn giản hóa quy trình làm việc của bạn: Tìm kiếm miniwebtool.
Thêm
Công cụ liên quan
Máy Tính Ma Trận KềMáy tính Đường đi Ngắn nhất DijkstraTrình xác thực dãy bậc đồ thịCông cụ Kiểm tra Đường đi HamiltonMáy tính Cây khung nhỏ nhấtCông Cụ Vẽ Đường Cong Tham SốMáy tính Nguyên lý Chuồng bồ câuTrình Kiểm Tra Đồ Thị PhẳngMáy Tính Sắp Xếp TopoMáy Tính Đỉnh và Trục Đối Xứng
Trang chủ > Toán học > Phép toán toán học nâng cao > Máy Tính Tô Màu Đồ Thị
 

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

Tìm sắc số và cách tô màu đỉnh hợp lệ cho bất kỳ đồ thị vô hướng nào. Nhập các cạnh hoặc danh sách kề để nhận số màu tối thiểu, phân bổ màu, lời giải từng bước bằng thuật toán DSATUR và sơ đồ đồ thị SVG tương tác.

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

⚡ Thử một ví dụ:

Chu trình 4 C₄ Tam giác K₃ Đầy đủ K₅ Ngũ giác C₅ Bánh xe W₆ Phân đôi K₃,₃ Mẫu danh sách kề Lập lịch thi
Định dạng cạnh: A-B hoặc A B, phân cách bằng dấu phẩy hoặc xuống dòng. Tối đa 60 đỉnh và 600 cạnh.
Tự động chọn quay lui chính xác cho đồ thị nhỏ và DSATUR cho đồ thị lớn.

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

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.

Định nghĩa sắc số
χ(G) = min { k : G chấp nhận một cách tô k-màu đúng }

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

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ụ:

A-B, B-C, C-D, D-A
A-C

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ụ:

A: B, C, D
B: A, D
C: A
D: A, B

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ị

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

Tham khảo nội dung, trang hoặc công cụ này như sau:

"Máy Tính Tô Màu Đồ Thị" tại https://MiniWebtool.com/vi/may-tinh-to-mau-o-thi/ từ MiniWebtool, https://MiniWebtool.com/

bởi đội ngũ miniwebtool. Cập nhật: 20 tháng 4, 2026

Có API dành cho developer: Chạy công cụ này từ ứng dụng, tự động hóa hoặc agent của bạn bằng một yêu cầu HTTP JSON. Xem tài liệu API

Bạn cũng có thể thử AI Giải Toán GPT của chúng tôi để giải quyết các vấn đề toán học của bạn thông qua câu hỏi và trả lời bằng ngôn ngữ tự nhiên.

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

Công cụ nổi bật:

Máy tính tuổiTrình Trích Xuất Ảnh từ VideoTrình tạo bài tây ngẫu nhiênmáy-tính-số-mũ-độ-chính-xác-caoCông cụ Mã hóa Caesar⏱️ Máy Tính GiờCông cụ chuyển đổi kg sang lbsCông cụ đếm hàngMáy tính thương và số dưTra cứu ID người dùng FacebookTra cứu ID người dùng InstagramTrình tạo chuỗi ngẫu nhiênMáy tính Phân tích Thừa số Nguyên tố🖱️ Bộ Đếm ClickBộ chuyển đổi thập phân sang nhị phânTrình Tạo Mã MorseCông cụ đổi Pound sang KilogramTrình nhân hóa văn bản AIMáy tính phân số tối giảnCông cụ chuyển đổi chữ số La MãBộ Chuyển Đổi Số Sang ChữĐảo ngược văn bảnTrình Luyện Toán NhẩmBộ chuyển đổi hệ cơ sốMáy tính giảm giá phần trămMáy tính Kiểm tra Chia hếtĐổ xúc xắcTrình tạo nhánh giải đấu ngẫu nhiênMáy tính thời gianMáy tính ngày trong năm - Hôm nay là ngày thứ mấy trong nămCông cụ chuyển đổi nhị phân sang thập phân📅 Máy tính ngàyMáy tính căn bậc haiMáy tính chuyển đổi phân số sang số thập phân🔍 Kiểm tra Đạo vănCông Cụ Vẽ Đồ Thị Hệ Bất Phương TrìnhXóa dấu cáchThống kê Kênh YouTubeGhép VideoSắp xếp sốMáy tính nhị phânMáy tính thập phân sang phân sốTrình tạo tên ngẫu nhiênĐây có phải là Số Nguyên Tố?Máy Giải Phương Trình Bậc BaBộ chọn bình luận YouTubeBộ chuyển đổi Thập phân sang Thập lục phânCông cụ xáo trộn chữ cáiTrình trích xuất âm thanhTrình tạo oẳn tù tìBộ chuyển đổi Nhị phân sang HexTrình phát hiện nội dung AICông cụ tạo nhóm ngẫu nhiênMáy tính HEXSắp xếp theo thứ tự bảng chữ cái📷 OCR Chuyển Ảnh Thành Văn BảnMáy tính Cạnh huyềnBộ chuyển đổi Feet và Inch sang CmBộ lặp MP3Máy tính Ước số chung lớn nhấtBộ chuyển đổi HEXBộ chuyển đổi FPSCon số may mắn của tôi là gì?Máy tính So sánh Phân sốCân Bằng Phương Trình Hóa HọcCông cụ chia ảnhSo sánh hai chuỗiTạo Ô ChữCông cụ loại bỏ dấu câu trực tuyếnTrình chuyển đổi SRT sang TXTTrình tạo mê cungMáy Tính Số TuầnMáy tính Cung Mặt trời, Mặt trăng & Cung mọc 🌞🌙✨tra-cứu-địa-chỉ-MACMáy tính hoàng hôn và bình minhMáy Tính Bộ Chia Điện ÁpCông cụ chuyển đổi kPa sang psiBộ Chia Âm ThanhLịch Sao Thủy Nghịch HànhMáy tính Độ dốc và CấpCông cụ chuyển đổi cm sang feet và inchMáy tính Tích phânTrình tạo thẻ tín dụng ngẫu nhiênCông cụ chuyển đổi psi sang kPa⏰ Đồng Hồ Báo Thức Trực TuyếnTrình tạo địa chỉ giả ngẫu nhiênMáy tính GFRTrình tạo ngày sinh ngẫu nhiênMáy tính trung bình mẫu⏱️ Bộ Đếm Ngược Thời GianChuyển đổi Số thành Phân sốMáy tính Tuổi thọ Trung bìnhTạo và giải SudokuBộ chuyển đổi Hex sang RGBMáy Tính Giờ Làm ViệcMáy Tính Độ Lệch Chuẩn Tương ĐốiTạo Trò Chơi Tìm TừCông Cụ Rút Gọn Đại Số BooleanTrình tạo ngày ngẫu nhiênCông cụ ước tính thu nhập YouTubeCông cụ chuyển đổi Phần trăm sang PPMMáy tính giai thừaTrình tạo chữ cái ngẫu nhiênTrình tạo siêu năng lực ngẫu nhiênMáy Tính Chu Vi Hình ElipĐiều chỉnh tốc độ videoBộ chuyển đổi địa chỉ IP sang nhị phân💧 Máy Tính Điểm SươngChuyển đổi CSV sang JSONCông cụ chuyển đổi thời gian phân sốCông cụ vẽ đồ thị hàm sốLịch trăng non và trăng trònMáy Tính Điểm SốMáy tính TổngBộ chuyển đổi hex sang thập phânMáy tính Tuổi thaiCông cụ chuyển đổi cURL sang JSONCông cụ chuyển đổi hỗn số thành phân sốDanh sách các số nguyên tốMáy tính ModuloMáy tính SinMáy tính thâm hụt caloTrình nén VideoTrình tạo thời gian ngẫu nhiênTung đồng xu📈 Công Cụ Tạo Biểu Đồ ĐườngBảng mã ASCIIBộ Chuyển Đổi Nhị PhânChuyển Đổi Mã Màu Mọi Định Dạng⏱️ Đồng Hồ Bấm Giờ Trực TuyếnMáy tính arctanMáy tính Pha Mặt TrăngCông cụ chuyển đổi hệ thập lục phân sang nhị phân🌡️ Máy Tính Chỉ Số NhiệtMáy tính tanMáy tính định lý PythagoreCông cụ tính điểm trung bình GPAMáy tính Cầu thangMáy tính Giá trị Niên kim trong Tương laiBộ Giải Mã Mã Morse🌐 Chuyển đổi Múi giờBộ Chuyển Đổi Thời Gian Sang Thập PhânCông cụ chuyển đổi Radian sang ĐộHẹn Giờ Học PomodoroMáy Giải Phương Trình Bậc BốnMáy tính bước chân sang khoảng cách🌬️ Máy tính Chỉ số Gió lạnhMáy Tính Giá Trị Tuyệt ĐốiMáy tính BSAMáy tính Natri hiệu chuẩnTrình tạo số nguyên ngẫu nhiênBộ chuyển đổi RGB sang HexCông cụ Tìm Quy luật Dãy sốMáy tính Hằng số Lò xoMáy tính nhânMáy tính One Rep Max (1RM)Trình tải hình thu nhỏ YouTubeTrình Tạo Đoạn Văn Ngẫu NhiênTrình tạo số thập phân ngẫu nhiênXoay VideoChuyển đổi Thời gian SRTCông cụ Giải Bản đồ Karnaugh (K-Map)Công cụ Mã hóa AtbashBộ chia videoDanh sách năm nhuậnMáy tính Hàm Phi EulerMáy tính ĐiệnNgười chọn ngẫu nhiênThêm văn bản vào hình ảnhCông cụ Mã hóa VigenèreKiểm Tra Số Chẵn Hay Số LẻMáy tính diện tích hình trònMáy tính tương hợp tình yêun chữ số đầu tiên của piTrình Mô Phỏng Cổng LogicTrình tạo IMEI Ngẫu nhiênTrình tạo JSON ngẫu nhiênTrình tạo mã vạchTrình tạo thẻ BingoMáy tính Strike Rate CricketMáy tính Net Run RateMáy Tính Tỷ Lệ K/DMáy Tính Xếp Hạng EloMáy tính phục hồi nhịp timMáy Tính Thời Gian Đi Bộ Đường DàiMáy tính Pace Chèo thuyềnMáy Tính Hiệu Suất Chạy Theo TuổiMáy tính FTP và Vùng Công suấtMáy Tính Beep TestMáy tính Điểm ACFTMáy tính Wilks & DOTSMáy tính Offset Bánh xeTra cứu Chỉ số Tải trọng & Xếp hạng Tốc độ LốpMáy tính Chi phí Mỗi DặmMáy Tính Mua Lại Hợp Đồng ThuêMáy Tính Pha Trộn OctanMáy Tính Pha Nhớt Xăng 2 ThìMáy Tính Dung Tích Động CơMáy Tính Ghế Sofa Qua CửaMáy Tính Dây CủiMáy Tính CADR Máy Lọc Không KhíMáy Tính Kích Thước Máy Hút ẨmMáy Tính Kích Thước Quạt TrầnMáy Tính Kích Thước Rèm CửaMáy Tính Kích Thước ThảmMáy tính chiều cao treo tranhMáy Tính Chiều Cao Lắp Đặt TVMáy Tính Kích Thước TVMáy Tính Thể Tích và Bạt Lót HồMáy Tính Muối Hồ BộiMáy Tính Thể Tích Hồ BơiMáy Tính Kích Thước Máy Nước NóngMáy Tính Nhựa EpoxyMáy Tính Khoảng Cách Con Tiện Lan CanMáy Tính Len Chân Tường và Nẹp Trang TríMáy Tính Ốp TườngMáy Tính Sơn Phủ Sàn GỗMáy Tính Hạt Giống CỏMáy Tính Cỏ NềnMáy Tính Nhựa ĐườngMáy Tính Yard KhốiMáy Tính Chiều Dài AntenMáy Tính Độ Lấp Đầy Ống Lót DâyMáy Tính Tụ Điện Nối Tiếp và Song SongMáy Tính Cảm KhángMáy Tính Chiếu Sáng PhòngMáy Tính Lux Sang LumenMáy Chuyển Đổi Lumen Sang WattMáy Tính Công Suất Máy Phát ĐiệnCông Cụ Chuyển Đổi mAh Sang WhMáy Tính Công Suất 3 PhaMáy Tính kVAMáy Tính Ampe Sang WattMáy Tính Watt Sang AmpeMáy Tính Điện Trở Nối TiếpMáy Tính Lực Ma SátMáy Tính Mặt Phẳng NghiêngMáy tính Lợi thế Cơ họcMáy tính Tốc độ Âm thanhMáy Tính Tốc Độ SóngMáy tính Lực nổiMáy tính Vận tốc Tới hạnMáy tính Bước sóng de BroglieMáy tính năng lượng photonMáy Tính E=mc²Máy Tính Giãn Nở Thời GianMáy tính Định luật thứ ba của KeplerMáy tính Vận tốc ThoátMáy Tính Lực Hấp DẫnMáy tính Định luật Beer-LambertMáy Tính Phương Trình NernstMáy tính Áp suất Thẩm thấuMáy Tính Độ Tăng Điểm SôiMáy Tính Độ Giảm Điểm Đông BăngMáy Tính Thành Phần Phần TrămMáy Tính Nồng Độ Đương LượngMáy tính Nồng độ MolanBộ Chuyển Đổi pKa Sang KaMáy tính Henderson-HasselbalchMáy Tính Sản Lượng Lý ThuyếtMáy tính Chất phản ứng Giới hạnMáy tính Cấu hình ElectronBảng tuần hoàn tương tácTrình Tạo Giáo Án AITrình tạo Câu đố AITrình tạo trích dẫn (APA/MLA/Chicago)Máy Tính Phần Trăm Điểm DanhMáy Tính Điểm APMáy Tính Điểm ACTMáy Tính Điểm SATChuyển đổi Phần trăm sang CGPATrình chuyển đổi CGPA sang phần trămCông Cụ Chấm Điểm Dễ Dàng (EZ Grader)Máy tính Chi phí Nuôi conMáy Tính Lượng Sữa Cho BéMáy Tính Kích Cỡ TãTrình Tạo Tên Em BéCông Cụ Dự Đoán Màu Mắt Em BéMáy Tính Phân Vị BMI Cho Trẻ EmCông Cụ Dự Đoán Chiều Cao Của TrẻMáy Tính Thời Gian Tăng Gấp Đôi hCGMáy tính ngày dự sinh IVFMáy tính làm tổ của phôiCông cụ dự đoán giới tính kiểu Trung QuốcCông cụ định dạng ngày ISO 8601Trình Chuyển Đổi Ngày JulianNap CalculatorWorld ClockBộ chuyển đổi Ngày sang Chữ số La MãĐếm Ngược Đến Khi Nghỉ HưuMáy Tính Cai NghiệnMáy Tính Nửa Sinh NhậtMáy Tính Ngày Kỷ NiệmMáy Tính Chia Tiền BoaMáy Tính ROI Email MarketingMáy tính Chi phí trên Mỗi Khách hàng Tiềm năngMáy Tính Vốn Lưu ĐộngTrình tạo nhân vật RPG ngẫu nhiên