Chỉ số chọn lựa (choice number hay list chromatic number) của đồ thị là gì?

Chỉ số chọn lựa ký hiệu là ch(G), là số nguyên k nhỏ nhất sao cho với mọi phép gán danh sách màu có kích thước k cho mỗi đỉnh, đồ thị G luôn tồn tại một phép tô màu danh sách hợp lệ.

Mối quan hệ giữa sắc số (chromatic number) và chỉ số chọn lựa của đồ thị là gì?

Chỉ số chọn lựa luôn lớn hơn hoặc bằng sắc số của đồ thị: ch(G) >= chi(G); đặc biệt có những đồ thị mà hiệu số ch(G) - chi(G) có thể lớn tùy ý (ví dụ đồ thị hai phía đầy đủ K_{n,n}).

Định lý Thomassen năm 1994 đã chứng minh điều gì nổi bật về tô màu danh sách?

Carsten Thomassen đã chứng minh một kết quả kinh điển: mọi đồ thị phẳng đều có chỉ số chọn lựa không vượt quá 5 (mọi đồ thị phẳng đều 5-list-colorable).

Tô màu danh sách đỉnh tô màu danh sách là gì? Định nghĩa và

Tô màu danh sách đỉnh tô màu danh sách (List coloring / Vertex list coloring) là một bài toán tổng quát hóa quan trọng và kinh điển của bài toán tô màu đồ thị chuẩn tắc trong lý thuyết đồ thị và toán học tổ hợp, trong đó mỗi đỉnh của đồ thị được gán một tập hợp các màu khả dĩ ban đầu (gọi là danh sách màu hay list), và mục tiêu là tìm kiếm một phép gán màu hợp lệ sao cho mỗi đỉnh nhận một màu thuộc danh sách riêng của nó và không có hai đỉnh kề nhau nào nhận cùng một màu.

Lịch sử hình thành và nguồn gốc lý thuyết

Bài toán tô màu danh sách được hai nhà toán học lỗi lạc người Nga Vadim G. Vizing độc lập đề xuất vào năm 1976 và sau đó được Paul Erdős, Arthur L. Rubin cùng Herbert A. Taylor công bố chính thức vào năm 1979 trong một bài báo kinh điển trên tập san toán học. Động lực ban đầu của lý thuyết xuất phát từ nhu cầu giải quyết các bài toán thực tiễn về phân bổ tần số vô tuyến và lập lịch trình thời gian biểu trong điều kiện các ràng buộc về tài nguyên tại từng vị trí hoặc tác vụ là không đồng nhất.

Trong bài toán tô màu đỉnh truyền thống, tất cả các đỉnh đều được quyền chọn từ cùng một tập hợp màu chung {1, 2, ..., k}. Tuy nhiên, trong thực tế, mỗi nút mạng hoặc mỗi tác vụ thường chỉ có thể tiếp cận một số kênh tần số hoặc khe thời gian nhất định do giới hạn phần cứng hoặc nhiễu cục bộ. Khái niệm tô màu danh sách ra đời để phản ánh chính xác cấu trúc ràng buộc dị thể này, mở ra một hướng nghiên cứu tổ hợp đồ sộ kéo dài suốt nửa thế kỷ qua.

Định nghĩa toán học và các đại lượng đặc trưng

Cho một đồ thị đơn vô hướng G = (V, E). Một phép gán danh sách màu L là một ánh xạ gán cho mỗi đỉnh v thuộc V một tập hợp hữu hạn các màu L(v). Một phép tô màu L hợp lệ (proper L-coloring) là một hàm c: V -> Union_{v in V} L(v) thỏa mãn đồng thời hai điều kiện:

Với mọi đỉnh v thuộc V: c(v) thuộc L(v) (màu của đỉnh thuộc danh sách cho phép của đỉnh đó).
Với mọi cạnh e = (u, v) thuộc E: c(u) khác c(v) (hai đỉnh kề nhau không bao giờ cùng màu).

Nếu đồ thị G tồn tại một phép tô màu L hợp lệ, ta nói G là L-colorable (có thể tô màu theo danh sách L). Đồ thị G được gọi là k-list-colorable (hoặc k-choosable) nếu với mọi phép gán danh sách L thỏa mãn |L(v)| >= k với mọi v thuộc V, G luôn tồn tại ít nhất một phép tô màu L hợp lệ.

Chỉ số chọn lựa (Choice number hay List chromatic number): Ký hiệu là ch(G) hoặc chi_L(G), là số nguyên dương k nhỏ nhất sao cho G là k-choosable. Nói cách khác, nếu mỗi đỉnh được cấp một danh sách gồm ít nhất ch(G) màu bất kỳ, ta luôn luôn tìm được một phương án tô màu hợp lệ bất kể các danh sách màu giữa các đỉnh trùng lặp hay phân tách nhau ra sao.

Mối quan hệ giữa Sắc số và Chỉ số chọn lựa

Mối tương quan giữa sắc số truyền thống chi(G) (chromatic number) và chỉ số chọn lựa ch(G) là một trong những chủ đề hấp dẫn nhất của toán học tổ hợp. Rõ ràng rằng, nếu ta gán cho mọi đỉnh cùng một danh sách màu chung có kích thước k = chi(G), đồ thị sẽ tô màu được. Do đó, bất đẳng thức cơ bản luôn luôn đúng là:

ch(G) >= chi(G)

Tuy nhiên, sự khác biệt lớn nhất giữa hai đại lượng này nằm ở chỗ: hiệu số ch(G) - chi(G) có thể lớn tùy ý! Một ví dụ kinh điển được Erdős, Rubin và Taylor chỉ ra là đồ thị hai phía đầy đủ K_{n,n}. Ta biết rằng sắc số của mọi đồ thị hai phía đều bằng 2 (chi(K_{n,n}) = 2 với mọi n >= 1). Thế nhưng, khi n tăng lên, chỉ số chọn lựa ch(K_{n,n}) tăng vô hạn theo hàm logarit của n: ch(K_{n,n}) = Theta(log n). Cụ thể, với K_{3,3}, sắc số chỉ bằng 2 nhưng chỉ số chọn lựa bằng 3.

Các định lý kinh điển và bước đột phá của Thomassen

Lý thuyết tô màu danh sách ghi dấu ấn bằng nhiều định lý sâu sắc trong cấu trúc đồ thị:

Định lý Galvin (1995): Fred Galvin đã chứng minh giả thuyết Dinitz nổi tiếng về bảng vuông Latinh bằng cách chứng minh rằng: Đối với mọi đồ thị hai phía đa cạnh G, chỉ số chọn lựa cạnh (list chromatic index) bằng đúng sắc số cạnh (chromatic index): ch'(G) = chi'(G) = Delta(G), trong đó Delta(G) là bậc cực đại của đồ thị.
Định lý Thomassen về đồ thị phẳng (1994): Carsten Thomassen đã tạo nên một kỳ tích toán học khi công bố một chứng minh ngắn gọn và tuyệt đẹp chỉ trong hai trang giấy, khẳng định rằng: Mọi đồ thị phẳng đều 5-choosable (ch(G) <= 5 với mọi đồ thị phẳng G). Điều này giải quyết trọn vẹn một bài toán mở lâu năm.
Đồ thị phẳng không 4-choosable của Voigt (1993): Margit Voigt đã phát hiện ra một đồ thị phẳng có 238 đỉnh nhưng không 4-choosable, chứng minh rằng không thể hạ chỉ số chọn lựa của lớp đồ thị phẳng từ 5 xuống 4, mặc dù Định lý Bốn Màu khẳng định sắc số truyền thống của đồ thị phẳng luôn <= 4.

Độ phức tạp tính toán và thuật toán

Về mặt lý thuyết độ phức tạp tính toán, bài toán quyết định xem một đồ thị tổng quát có k-choosable hay không là một bài toán cực kỳ khó. Trong khi bài toán 2-coloring truyền thống có thể giải được trong thời gian đa thức (kiểm tra đồ thị hai phía bằng BFS/DFS), bài toán 2-list-coloring cũng có thể giải được trong thời gian đa thức nhờ chuyển đổi về bài toán 2-SAT.

Tuy nhiên, với k >= 3, bài toán kiểm tra xem một đồ thị có k-list-colorable với một tập danh sách cho trước hay không là bài toán NP-đầy đủ (NP-complete). Thậm chí bài toán kiểm tra xem ch(G) <= k hay không còn nằm ở bậc cao hơn trong phân cấp đa thức: nó là bài toán Pi_2^P-đầy đủ đối với k >= 3. Các thuật toán hiện đại dựa trên Phương pháp Đa thức Alon-Tarsi (Alon-Tarsi polynomial method) và Lý thuyết Tổ hợp Đại số (Combinatorial Nullstellensatz) là những công cụ đại số mạnh mẽ hàng đầu được sử dụng để chứng minh tính khả tô danh sách của các họ đồ thị đối xứng cao.

Ứng dụng thực tiễn trong khoa học máy tính và viễn thông

Lý thuyết tô màu danh sách có phạm vi ứng dụng rộng rãi trong các hệ thống phân tán và kỹ thuật thông tin:

Phân bổ phổ tần số trong mạng thông tin di động (Frequency Assignment Problem - FAP): Mỗi trạm phát sóng cơ sở (BTS) bị giới hạn bởi các dải băng tần khả dụng tại vùng địa lý đó do quy định pháp lý hoặc hạn chế giao thoa phần cứng. Việc mô hình hóa mạng lưới trạm phát dưới dạng đồ thị giao thoa và gán tần số theo danh sách khả dụng giúp tối đa hóa thông lượng mạng mà không gây can nhiễu đồng kênh.
Cấp phát thanh ghi trong trình biên dịch (Register Allocation in Compilers): Trong kỹ thuật tối ưu hóa mã máy, các biến tạm thời trong chương trình cần được gán vào các thanh ghi phần cứng (hardware registers) của CPU. Do một số thanh ghi chuyên biệt chỉ hỗ trợ các kiểu dữ liệu hoặc tập lệnh nhất định, bài toán cấp phát thanh ghi thực chất là bài toán tô màu danh sách đỉnh trên đồ thị xung đột biến (interference graph).
Lập lịch thi và phân công thời khóa biểu (Timetabling and Scheduling): Xếp lịch các môn thi hoặc ca làm việc của nhân sự với các ràng buộc về phòng ốc, ca trực và sự sẵn sàng của giảng viên/nhân viên, trong đó mỗi môn học chỉ có thể diễn ra tại một số khung giờ cụ thể.

Phương pháp đại số Alon-Tarsi và Tổ hợp Đa thức

Một trong những bước tiến lý thuyết sâu sắc nhất trong việc nghiên cứu tô màu danh sách là việc Noga Alon và Michael Tarsi đưa ra Định lý Alon-Tarsi (1992), thiết lập cầu nối tuyệt đẹp giữa tô màu danh sách và hướng đồ thị (graph orientations):

Giả sử D là một đồ thị có hướng nhận G làm đồ thị nền. Một hướng D được gọi là Eulerian nếu tại mọi đỉnh v, bậc vào bằng bậc ra (d_in(v) = d_out(v)). Alon và Tarsi đã chứng minh rằng: Nếu tồn tại một định hướng D của G sao cho số lượng đồ thị con Eulerian sinh bởi tập cạnh chẵn khác số lượng đồ thị con Eulerian sinh bởi tập cạnh lẻ, thì với mọi phép gán danh sách L thỏa mãn |L(v)| >= d_out(v) + 1 với mọi đỉnh v, đồ thị G luôn có thể tô màu danh sách L hợp lệ. Công cụ này bắt nguồn từ việc áp dụng Bổ đề Nullstellensatz Tổ hợp (Combinatorial Nullstellensatz) lên đa thức đồ thị (graph polynomial), cho phép các nhà toán học giải quyết hàng loạt bài toán tô màu danh sách phức tạp mà các phương pháp quy nạp tổ hợp truyền thống bất lực.

Bài toán tô màu danh sách cạnh và Giả thuyết List Coloring

Bên cạnh tô màu đỉnh, bài toán Tô màu danh sách cạnh (Edge list coloring) khảo sát việc gán màu cho các cạnh của đồ thị từ các danh sách màu khả dĩ tại mỗi cạnh. Chỉ số chọn lựa cạnh của đồ thị G, ký hiệu là ch'(G), là kích thước danh sách nhỏ nhất đảm bảo luôn tồn tại một phép tô màu cạnh hợp lệ (hai cạnh chung đỉnh không cùng màu).

Một trong những giả thuyết mở nổi tiếng và thách thức nhất trong lý thuyết đồ thị hiện đại là Giả thuyết List Coloring (List Coloring Conjecture), được đề xuất bởi nhiều nhà toán học độc lập vào đầu những năm 1980, phỏng đoán rằng: Đối với mọi đồ thị đơn G, chỉ số chọn lựa cạnh luôn luôn bằng đúng sắc số cạnh truyền thống: ch'(G) = chi'(G). Mặc dù giả thuyết này đã được Galvin chứng minh đúng cho lớp đồ thị hai phía vào năm 1995, bài toán đối với đồ thị tổng quát vẫn là một thách thức vĩ đại chưa có lời giải trọn vẹn, thúc đẩy nhiều thế hệ nhà toán học tiếp tục khám phá các kỹ thuật phân tích xác suất và cấu trúc cực hạn mới.