Đồ thị tách cực là gì và làm thế nào để nhận biết?

Đồ thị tách cực là đồ thị vô hướng có tập đỉnh phân hoạch thành một clique (đồ thị con đầy đủ) và một tập độc lập. Có thể nhận biết đồ thị tách cực trong thời gian tuyến tính bằng cách kiểm tra đẳng thức tổng dãy bậc đỉnh của Hammer-Simeone.

Đồ thị con cấm của đồ thị tách cực gồm những loại nào?

Theo định lý Foldes-Hammer (1977), một đồ thị là đồ thị tách cực khi và chỉ khi nó không chứa đồ thị con cảm ứng đẳng cấu với 2K2 (hai cạnh rời nhau), C4 (chu trình 4 đỉnh) hoặc C5 (chu trình 5 đỉnh).

Tại sao đồ thị tách cực lại quan trọng trong lý thuyết thuật toán?

Nhiều bài toán tối ưu NP-khó trên đồ thị tổng quát như Tìm Clique lớn nhất, Tập độc lập lớn nhất, Tô màu đồ thị và Phủ đỉnh đều trở nên giải được trong thời gian đa thức hoặc tuyến tính trên đồ thị tách cực.

Đồ thị tách cực là gì? Định nghĩa, định lý Foldes-Hammer và thuật toán

Đồ thị tách cực là loại đồ thị đơn vô hướng mà tập hợp đỉnh của nó có thể được phân hoạch thành hai tập hợp con rời nhau: một tập hợp tạo thành một đồ thị đầy đủ (clique) và tập hợp còn lại tạo thành một tập hợp độc lập (independent set). Cấu trúc đặc thù này mang lại cho đồ thị tách cực nhiều tính chất đại số và tổ hợp độc đáo, là giao điểm quan trọng giữa lớp đồ thị dây cung (chordal graphs) và đồ thị bù dây cung (co-chordal graphs) trong lý thuyết đồ thị thuật toán và khoa học máy tính lý thuyết.

Định nghĩa hình thức và tính chất cấu trúc

Cho đồ thị đơn vô hướng $G = (V, E)$ với tập đỉnh $V$ và tập cạnh $E$ . Đồ thị $G$ được gọi là đồ thị tách cực (split graph) nếu tồn tại một phân hoạch $V = K \cup I$ với $K \cap I = \emptyset$ sao cho:

Đồ thị con cảm ứng trên $K$ là một đồ thị đầy đủ (clique), nghĩa là với mọi cặp đỉnh $u, v \in K$ phân biệt, luôn tồn tại cạnh $(u, v) \in E$ .
Đồ thị con cảm ứng trên $I$ là một tập hợp độc lập (independent set), nghĩa là không tồn tại bất kỳ cạnh nào nối hai đỉnh thuộc $I$ (với mọi $x, y \in I$ , $(x, y) otin E$ ).

Một tính chất đối ngẫu quan trọng của đồ thị tách cực là tính tự bù (self-complementary duality): đồ thị bù $\overline{G}$ của một đồ thị tách cực $G$ cũng là một đồ thị tách cực. Trong đồ thị bù $\overline{G}$ , tập đỉnh $K$ trở thành tập độc lập và tập đỉnh $I$ trở thành clique đầy đủ (Golumbic, 1980).

Định lý đặc trưng Foldes-Hammer về đồ thị con cấm

Vào năm 1977, hai nhà toán học Stéphane Földes và Peter L. Hammer đã chứng minh định lý nền tảng xác lập điều kiện cần và đủ cho đồ thị tách cực dựa trên tập các đồ thị con cảm ứng cấm (forbidden induced subgraphs) (Foldes & Hammer, 1977):

Đồ thị con cảm ứng cấm	Ký hiệu	Cấu trúc hình học	Ý nghĩa đối với phân hoạch Split
Cặp cạnh rời nhau	$2K_2$	Gồm 4 đỉnh tạo thành 2 cạnh độc lập không chung đỉnh và không có cạnh chéo nối giữa chúng.	Vi phạm tính chất clique của tập $K$ hoặc tạo cạnh nội bộ trong tập độc lập $I$ .
Chu trình độ dài 4	$C_4$	Chu trình 4 đỉnh liên tiếp không có đường chéo nối tắt.	Ngăn cản việc phân tách 4 đỉnh thành clique và tập độc lập rời nhau.
Chu trình độ dài 5	$C_5$	Chu trình ngũ giác 5 đỉnh không có đường chéo.	Là đồ thị tự bù nhỏ nhất không thể phân hoạch thành clique và tập độc lập.

Định lý phát biểu rằng: Một đồ thị đơn vô hướng $G$ là một đồ thị tách cực khi và chỉ khi $G$ không chứa bất kỳ đồ thị con cảm ứng nào đồng hình với $2K_2$ , $C_4$ , hoặc $C_5$ .

Đặc trưng theo dãy bậc đỉnh và thuật toán nhận dạng tuyến tính

Hammer và Simeone (1981) đã đưa ra một tiêu chuẩn nhận dạng đại số cực kỳ hiệu quả dựa trên dãy bậc của đồ thị. Giả sử các đỉnh của $G$ có bậc được sắp xếp giảm dần:

d_1 \ge d_2 \ge \dots \ge d_n

Gọi $m$ là chỉ số lớn nhất thỏa mãn bất đẳng thức $d_m \ge m - 1$ . Đồ thị $G$ là đồ thị tách cực khi và chỉ khi phương trình cân bằng bậc sau đây được thỏa mãn chính xác:

\sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i

Nếu phương trình trên thỏa mãn, kích thước của clique lớn nhất trong $G$ bằng $m$ hoặc $m+1$ . Tiêu chuẩn này cho phép xây dựng thuật toán nhận dạng đồ thị tách cực với độ phức tạp thời gian tuyến tính $O(|V| + |E|)$ bằng cách đếm bậc đỉnh bằng sắp xếp theo cơ số (counting sort) và kiểm tra đẳng thức tổng bậc (McDiarmid & Yolov, 2015).

Vị trí trong phân cấp họ đồ thị hoàn hảo

Đồ thị tách cực thuộc lớp đồ thị hoàn hảo (perfect graphs) và có mối liên hệ chặt chẽ với các họ đồ thị quan trọng khác:

Giao điểm giữa Chordal và Co-chordal: Một đồ thị là đồ thị tách cực khi và chỉ khi cả $G$ và đồ thị bù $\overline{G}$ đều là đồ thị dây cung (chordal graphs). Điều này có nghĩa là $ext{Split} = ext{Chordal} \cap ext{Co-Chordal}$ .
Đồ thị khoảng (Interval graphs): Giao của đồ thị khoảng và đồ thị tách cực tạo nên lớp đồ thị tách cực khoảng (interval split graphs), xuất hiện nhiều trong bài toán lập lịch tài nguyên.
Đồ thị ngưỡng (Threshold graphs): Đồ thị ngưỡng là trường hợp đặc biệt của đồ thị tách cực, trong đó các đỉnh trong tập độc lập $I$ có lân cận trong $K$ được bao hàm lẫn nhau theo quan hệ thứ tự tuyến tính.

Độ phức tạp tính toán và các bài toán tối ưu trên Split Graphs

Trong khi các bài toán kinh điển như Clique lớn nhất (Maximum Clique), Tập độc lập lớn nhất (Maximum Independent Set), Tô màu đồ thị (Graph Coloring) và Phủ đỉnh nhỏ nhất (Minimum Vertex Cover) đều là các bài toán NP-khó (NP-hard) trên lớp đồ thị tổng quát, chúng đều có thể được giải quyết trong thời gian đa thức (polynomial time) hoặc tuyến tính trên đồ thị tách cực:

Bài toán Clique lớn nhất: Kích thước clique lớn nhất $\omega(G)$ được xác định ngay qua giá trị $m$ của dãy bậc đỉnh trong thời gian $O(|V|)$ .
Bài toán Tập độc lập lớn nhất: Tập độc lập lớn nhất lpha(G) có kích thước bằng $|V| - m$ và được tìm thấy trực tiếp từ phần hoạch bù.
Bài toán Sắc số (Chromatic Number): Vì đồ thị tách cực là đồ thị hoàn hảo, sắc số $\chi(G)$ luôn bằng đúng kích thước clique lớn nhất $\omega(G)$ .

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

Đồ thị tách cực có nhiều ứng dụng thiết thực trong thiết kế hệ thống và giải thuật:

Mô hình hóa mạng truyền thông phân cấp: Cấu trúc clique mô tả mạng lưới lõi (core backbone network) với các bộ định tuyến tốc độ cao kết nối đầy đủ, trong khi tập độc lập mô tả các trạm đầu cuối (access edge nodes) chỉ kết nối vào mạng lõi mà không kết nối trực tiếp với nhau.
Phân tích mạng lưới sinh học và tin sinh học: Phân cụm các protein trung tâm (hub proteins) có tương tác tương hỗ dày đặc liên kết với các protein vệ tinh chuyên biệt.
Tối ưu hóa lập lịch và quản lý bộ nhớ đệm: Lập lịch thực thi các tiến trình song song chia sẻ tài nguyên tính toán độc quyền trong các hệ thống tính toán hiệu năng cao.