Đồ thị giao nhau (intersection graph) là gì?

Đồ thị giao nhau (intersection graph) là một đồ thị vô hướng biểu diễn quan hệ giao nhau giữa các tập hợp thuộc một họ tập hợp nhất định, trong đó mỗi đỉnh của đồ thị tương ứng với một tập hợp và hai đỉnh được nối với nhau bởi một cạnh khi và chỉ khi hai tập hợp tương ứng có phần giao khác rỗng. Khái niệm này đóng vai trò nền tảng trong lý thuyết đồ thị cấu trúc, toán học rời rạc và lý thuyết thuật toán, cung cấp cầu nối toán học quan trọng giữa các cấu trúc hình học hoặc tập hợp liên tục với các mô hình mạng rời rạc. Trong các giáo trình Toán rời rạc và Lý thuyết đồ thị tại Việt Nam, thuật ngữ đồ thị giao cũng được sử dụng phổ biến như một tên gọi tương đương, là mô hình cơ sở để biểu diễn các họ tập hợp có phần tử chung và ứng dụng trực tiếp vào nhiều bài toán phân bổ và lập lịch thực tế.

Khái niệm và mô hình toán học hình thức

Định nghĩa hình thức

Cho một họ hữu hạn các tập hợp ký hiệu là $\mathcal{F} = \{S_1, S_2, \dots, S_n\}$, trong đó mỗi $S_i$ là một tập con của một tập vũ trụ $U$. Đồ thị giao nhau của họ $\mathcal{F}$, thường được ký hiệu là $\Omega(\mathcal{F})$ hoặc $G = (V, E)$, là một đồ thị vô hướng đơn được xác định bởi hai thành phần:

• Tập đỉnh: $V = \{v_1, v_2, \dots, v_n\}$, trong đó mỗi đỉnh $v_i$ tương ứng một-đối-một với tập hợp $S_i \in \mathcal{F}$.
• Tập cạnh: $E = \{\{v_i, v_j\} \mid i \neq j \text{ và } S_i \cap S_j \neq \emptyset\}$. Nghĩa là hai đỉnh phân biệt $v_i$ và $v_j$ kề nhau khi và chỉ khi tập hợp $S_i$ và tập hợp $S_j$ chia sẻ ít nhất một phần tử chung.

Ngược lại, nếu cho trước một đồ thị vô hướng $G = (V, E)$, một biểu diễn giao (intersection representation) của $G$ là một ánh xạ gán mỗi đỉnh $v \in V$ với một tập hợp $S_v$ sao cho $\{u, v\} \in E \iff S_u \cap S_v \neq \emptyset$. Khi tập vũ trụ $U$ hoặc cấu trúc của các tập con $S_i$ bị ràng buộc theo các điều kiện topo hoặc hình học đặc thù, ta thu được các họ đồ thị con rất giàu tính chất.

Ví dụ minh họa cơ bản

Xem xét một họ gồm bốn tập hợp số nguyên cụ thể: $S_1 = \{1, 2\}$, $S_2 = \{2, 3\}$, $S_3 = \{3, 4\}$, và $S_4 = \{4, 1\}$. Đồ thị giao nhau của họ này có bốn đỉnh tương ứng $v_1, v_2, v_3, v_4$. Ta kiểm tra các cặp giao:

• $S_1 \cap S_2 = \{2\} \neq \emptyset$, do đó tồn tại cạnh $\{v_1, v_2\}$.
• $S_2 \cap S_3 = \{3\} \neq \emptyset$, do đó tồn tại cạnh $\{v_2, v_3\}$.
• $S_3 \cap S_4 = \{4\} \neq \emptyset$, do đó tồn tại cạnh $\{v_3, v_4\}$.
• $S_4 \cap S_1 = \{1\} \neq \emptyset$, do đó tồn tại cạnh $\{v_4, v_1\}$.
• Trong khi đó, $S_1 \cap S_3 = \emptyset$ và $S_2 \cap S_4 = \emptyset$, nên không có cạnh nối giữa các cặp đỉnh này.

Kết quả ta nhận được chính là một đồ thị chu trình gồm bốn đỉnh $C_4$. Ví dụ đơn giản này cho thấy cấu trúc liên thuộc của các tập hợp ban đầu quy định chính xác hình thái liên kết của đồ thị đích.

Lịch sử hình thành và các định lý nền tảng

Định lý phổ quát Marczewski (1945)

Câu hỏi tự nhiên đầu tiên xuất hiện trong nghiên cứu đồ thị giao nhau là: Liệu có đồ thị vô hướng nào không thể biểu diễn dưới dạng đồ thị giao nhau của một họ tập hợp hay không? Câu trả lời đã được nhà toán học Edward Szpilrajn-Marczewski khẳng định dứt khoát vào năm 1945 trong công trình công bố trên tạp chí Fundamenta Mathematicae. Định lý Szpilrajn-Marczewski (1945) chứng minh rằng:

Mọi đồ thị vô hướng hữu hạn đều là đồ thị giao nhau của một họ tập hợp hữu hạn nào đó.

Chứng minh của định lý này rất thanh lịch và mang tính kiến thiết trực tiếp: Với đồ thị $G = (V, E)$, ta chọn tập vũ trụ chính là tập các cạnh $U = E$. Với mỗi đỉnh $v \in V$, ta xây dựng tập hợp $S_v$ gồm tất cả các cạnh liên thuộc với đỉnh $v$, tức là $S_v = \{e \in E \mid v \in e\}$. Khi đó, hai đỉnh phân biệt $u$ và $v$ kề nhau khi và chỉ khi tồn tại cạnh $e = \{u, v\} \in E$, tức là $e \in S_u \cap S_v$, đồng nghĩa $S_u \cap S_v \neq \emptyset$. Như vậy, việc xem xét đồ thị giao nhau tổng quát trên các tập hợp tùy ý không tạo ra một lớp đồ thị hạn chế, mà là một phương thức biểu diễn tương đương cho toàn bộ thế giới đồ thị vô hướng.

Chỉ số giao và định lý Erdős-Goodman-Pósa (1966)

Bởi vì mọi đồ thị đều có thể biểu diễn dưới dạng đồ thị giao nhau, trọng tâm nghiên cứu chuyển sang bài toán tối ưu kích thước của tập vũ trụ $U$. Chỉ số giao (intersection number), ký hiệu là $\theta(G)$, là số lượng phần tử tối thiểu của một tập vũ trụ $U$ sao cho $G$ đẳng cấu với đồ thị giao nhau của một họ tập con của $U$.

Vào năm 1966, ba nhà toán học Paul Erdős, A. W. Goodman và Louis Pósa đã giải quyết trọn vẹn bài toán xác định cận trên của chỉ số giao cho đồ thị có $n$ đỉnh trên tạp chí Canadian Journal of Mathematics. Định lý Erdős-Goodman-Pósa (1966) thiết lập:

Với mọi đồ thị vô hướng $G$ có $n$ đỉnh với $n \ge 4$, chỉ số giao $\theta(G)$ thỏa mãn bất đẳng thức chặt chẽ:

Đẳng thức xảy ra khi và chỉ khi đồ thị $G$ là đồ thị phân đôi đầy đủ cân bằng, tức là đồ thị Turán hai phần gồm hai tập đỉnh có kích thước chênh lệch không quá một phần tử. Nghiên cứu của Erdős, Goodman và Pósa (1966) cũng chỉ ra mối quan hệ tương đương sâu sắc: chỉ số giao $\theta(G)$ bằng đúng số lượng clique (đồ thị con đầy đủ) tối thiểu cần thiết để phủ tất cả các cạnh của $G$, thường được gọi là bài toán phủ cạnh bằng clique (edge clique cover number).

Các lớp đồ thị giao nhau hình học và cấu trúc

Mặc dù trên tập hợp trừu tượng mọi đồ thị đều là đồ thị giao nhau, nhưng khi hạn chế không gian chứa các tập hợp hoặc đặt ra các đòi hỏi topo đặc biệt, các lớp đồ thị sinh ra sở hữu cấu trúc toán học vô cùng chặt chẽ. Chuyên khảo kinh điển của McKee và McMorris (1999) cũng như công trình tổng quan của Brandstädt, Le và Spinrad (1999) đã hệ thống hóa các lớp đồ thị giao nhau cốt lõi sau đây:

Đồ thị khoảng (Interval Graphs)

Đồ thị khoảng là đồ thị giao nhau của một họ các khoảng đóng trên trục số thực $\mathbb{R}$. Mỗi đỉnh $v_i$ tương ứng với một đoạn $I_i = [a_i, b_i]$, và hai đỉnh kề nhau khi hai đoạn có điểm chung. Đồ thị khoảng có các đặc trưng hình học nổi bật:

• Mọi đồ thị khoảng đều là đồ thị hoàn hảo (perfect graph) và là đồ thị dây cung.
• Đồ thị khoảng không chứa bất kỳ chu trình cảm ứng nào có độ dài lớn hơn ba (tính chất dây cung) và không chứa đồ thị hình ba nhánh (astroidal triple-free).
• Chúng mô hình hóa trực tiếp các bài toán giao thoa thời gian, nơi mỗi sự kiện chiếm một khoảng thời gian liên tục từ điểm bắt đầu đến điểm kết thúc.

Đồ thị dây cung (Chordal Graphs)

Đồ thị dây cung (còn gọi là đồ thị tam giác hóa - triangulated graph) là đồ thị mà mọi chu trình có độ dài từ bốn trở lên đều chứa một dây cung (một cạnh nối hai đỉnh không kề nhau trên chu trình). Năm 1974, Fănică Gavril đã chứng minh một định lý đặc trưng cấu trúc kinh điển:

Một đồ thị là đồ thị dây cung khi và chỉ khi nó là đồ thị giao nhau của một họ các cây con (subtrees) nằm trong một cây mẹ (tree).

Định lý Gavril (1974) đưa đồ thị dây cung vào trung tâm của lý thuyết đồ thị giao nhau. Bởi vì một đường đi trên trục thực là trường hợp đơn giản nhất của một cây, đồ thị khoảng chính là trường hợp riêng của đồ thị dây cung khi cây mẹ suy biến thành một đường đi đơn.

Đồ thị cung tròn (Circular-Arc Graphs)

Đồ thị cung tròn là sự mở rộng tự nhiên của đồ thị khoảng lên cấu trúc topo tuần hoàn: chúng là đồ thị giao nhau của một họ các cung đóng trên một đường tròn. Khác với đồ thị khoảng, đồ thị cung tròn có thể chứa các chu trình cảm ứng độ dài lớn (ví dụ chu trình chứa nhiều đỉnh), do đó không nhất thiết phải là đồ thị dây cung hay đồ thị hoàn hảo. Lớp đồ thị này xuất hiện phổ biến trong bài toán lập lịch tuần hoàn theo chu kỳ ngày đêm, phân bổ bộ nhớ vòng, và cấu trúc di truyền học của vi khuẩn có nhiễm sắc thể vòng.

Đồ thị đĩa đơn vị (Unit Disk Graphs)

Đồ thị đĩa đơn vị là đồ thị giao nhau của một họ các hình đĩa tròn đóng có bán kính bằng nhau trong mặt phẳng hai chiều Euclid. Hai đỉnh kề nhau khi khoảng cách Euclid giữa hai tâm đĩa nhỏ hơn hoặc bằng hai lần bán kính. Lớp đồ thị này là mô hình tiêu chuẩn để phân tích các mạng vô tuyến đặc thù (ad-hoc) và mạng cảm biến không dây (wireless sensor networks), trong đó mỗi thiết bị có bán kính truyền dẫn đẳng hướng bằng nhau.

Đặc trưng thuật toán và độ phức tạp tính toán

Bài toán nhận dạng đồ thị giao nhau

Bài toán nhận dạng (recognition problem) yêu cầu kiểm tra xem một đồ thị vô hướng đầu vào có thuộc về một lớp đồ thị giao nhau xác định hay không, và nếu có thì xuất ra biểu diễn hình học tương ứng. Độ phức tạp tính toán của bài toán nhận dạng có sự phân hóa sâu sắc giữa các họ đồ thị:

• Đồ thị khoảng: Có thể nhận dạng và xây dựng mô hình các khoảng trong thời gian tuyến tính với số đỉnh và số cạnh. Năm 1976, K. S. Booth và G. S. Lueker đã phát triển cấu trúc dữ liệu cây PQ (PQ-tree), cho phép kiểm tra tính chất các số 1 liên tiếp (consecutive ones property) của ma trận liên thuộc đỉnh-clique cực đại trong thời gian tối ưu.
• Đồ thị dây cung: Cũng được nhận dạng trong thời gian tuyến tính bằng thuật toán tìm kiếm theo chiều rộng thứ tự từ điển (Lexicographic Breadth-First Search - LexBFS), thông qua việc tìm thứ tự loại trừ hoàn hảo (perfect elimination ordering).
• Đồ thị đoạn thẳng và đồ thị đĩa: Ngược lại, bài toán nhận dạng đồ thị giao nhau của các đoạn thẳng trong mặt phẳng phẳng hoặc nhận dạng đồ thị đĩa đơn vị là bài toán rất khó. Các nghiên cứu hiện đại đã chỉ ra rằng các bài toán nhận dạng này là đầy đủ đối với lý thuyết tồn tại trên trường số thực (Existential Theory of the Reals - đầy đủ cấp thực), đòi hỏi số bit biểu diễn tọa độ các đỉnh có thể tăng theo hàm mũ trong trường hợp xấu nhất.

Tối ưu hóa đa thức trên các lớp đồ thị hoàn hảo

Một trong những giá trị học thuật to lớn nhất của lý thuyết đồ thị giao nhau là biến các bài toán NP-khó thành các bài toán giải được trong thời gian đa thức hiệu quả:

Trên đồ thị tổng quát, các bài toán kinh điển như Tìm tập độc lập cực đại (Maximum Independent Set), Tìm tập phủ đỉnh cực tiểu (Minimum Vertex Cover), Tìm clique cực đại (Maximum Clique), và Tô màu đồ thị (Graph Coloring) đều là các bài toán NP-đầy đủ theo danh mục quy chuẩn của Karp. Tuy nhiên, khi đồ thị đầu vào thuộc lớp đồ thị khoảng hoặc đồ thị dây cung:

• Bài toán Tìm tập độc lập cực đại trên đồ thị khoảng có thể giải bằng thuật toán tham lam đơn giản trong thời gian tỷ lệ thuận với số lượng đỉnh đã sắp xếp theo điểm mút phải.
• Bài toán Tô màu đồ thị và Tìm clique cực đại trên đồ thị dây cung được giải chính xác trong thời gian tuyến tính dựa trên thứ tự loại trừ hoàn hảo. Số màu tối thiểu cần dùng (sắc số) luôn bằng kích thước của clique lớn nhất, phù hợp với định nghĩa và tính chất của lớp đồ thị hoàn hảo.

Ứng dụng thực tiễn trong khoa học máy tính và kỹ thuật

Phân bổ thanh ghi trong trình biên dịch

Trong kỹ nghệ phát triển trình biên dịch ngôn ngữ lập trình, tài nguyên thanh ghi (register) của bộ xử lý là hữu hạn và có tốc độ truy xuất nhanh nhất. Mỗi biến trong chương trình có một khoảng thời gian sống (live range) tính từ lệnh gán giá trị đầu tiên cho đến lệnh sử dụng cuối cùng. Hai biến không thể chia sẻ cùng một thanh ghi vật lý nếu khoảng thời gian sống của chúng giao nhau. Vấn đề này được mô hình hóa chính xác thành bài toán tô màu trên một đồ thị khoảng, trong đó các đỉnh là các biến và màu sắc đại diện cho các thanh ghi vật lý. Nhờ tính chất của đồ thị khoảng, trình biên dịch có thể tìm ra phương án gán thanh ghi tối ưu hoặc phát hiện tối thiểu số biến cần chuyển vào bộ nhớ ngăn xếp (spilling).

Lập lịch công việc và quản lý tài nguyên

Trong các hệ thống phân tán và điều hành sản xuất, bài toán điều độ công việc đòi hỏi bố trí các tác vụ có thời gian bắt đầu và kết thúc cố định vào các máy xử lý sao cho không có hai tác vụ trùng giờ nào chạy trên cùng một máy. Đồ thị xung đột giữa các công việc chính là một đồ thị khoảng. Sắc số của đồ thị này phản ánh đúng số lượng máy tối thiểu cần thiết để vận hành toàn bộ dây chuyền không bị xung đột, giúp các nhà quản lý hệ thống tối ưu hóa chi phí vận hành.

Sinh học phân tử và phân tích trình tự DNA

Lý thuyết đồ thị khoảng từng đóng vai trò lịch sử quan trọng trong việc làm sáng tỏ cấu trúc tuyến tính của gen. Khi nghiên cứu cấu trúc tinh vi của gen, các nhà sinh học phân tử đã sử dụng đồ thị giao nhau của các đột biến mất đoạn trên thực khuẩn thể để kiểm chứng cấu trúc tuyến tính một chiều của vật chất di truyền. Trong kỷ nguyên tin sinh học hiện đại, đồ thị giao nhau của các đoạn đọc ngắn (short reads) được ứng dụng trong các thuật toán lắp ráp hệ gen và phân tích bản đồ phiên mã.

Quy hoạch mạng cảm biến và phân bổ tần số vô tuyến

Trong truyền thông vô tuyến, các trạm phát sóng có bán kính phủ sóng nhất định. Nếu hai trạm ở gần nhau có vùng phủ sóng giao nhau và phát trên cùng một dải tần, hiện tượng can nhiễu tín hiệu sẽ xảy ra. Bằng cách xây dựng đồ thị đĩa đơn vị biểu diễn vùng can nhiễu giữa các trạm, bài toán phân bổ kênh tần số không can nhiễu được quy về bài toán tô màu đồ thị đĩa, hỗ trợ tối đa hóa dung lượng mạng truyền thông.

Ranh giới lý thuyết và các bài toán mở

Giới hạn biểu diễn và độ phức tạp hình học

Mặc dù mô hình đồ thị giao nhau rất mạnh mẽ, việc ánh xạ một đồ thị tùy ý sang các biểu diễn hình học gặp phải những ranh giới toán học cơ bản:

• Chiều giao nhau và độ hộp (Boxicity): Độ hộp của một đồ thị là số chiều tối thiểu của không gian Euclid sao cho đồ thị đó có thể biểu diễn như đồ thị giao nhau của các khối hộp nhiều chiều có các cạnh song song với các trục tọa độ. Việc xác định độ hộp của một đồ thị bất kỳ là bài toán NP-khó.
• Sự bùng nổ độ chính xác số học: Trong các lớp đồ thị giao đoạn thẳng hoặc đồ thị tiếp xúc hình học, việc xác định tọa độ các điểm mút đòi hỏi độ dài biểu diễn bit lớn, dẫn đến việc bài toán nhận dạng và tìm biểu diễn tọa độ hình học thực không thuộc (hoặc chưa biết có thuộc) lớp NP thông thường mà thuộc lớp đầy đủ cấp thực (Existential Theory of the Reals-complete).

Bảng đối sánh các lớp đồ thị giao nhau phổ biến

Dưới đây là bảng tổng hợp và so sánh các đặc trưng toán học chính giữa các lớp đồ thị giao nhau phổ biến được tổng thuật từ các công trình của Brandstädt, Le, Spinrad (1999) và McKee, McMorris (1999):

Lớp đồ thị giao nhau	Họ tập hợp biểu diễn hình học	Độ phức tạp bài toán nhận dạng	Tính chất hoàn hảo	Ứng dụng điển hình
Đồ thị khoảng (Interval Graph)	Các khoảng đóng trên trục số thực	Thời gian tuyến tính (cây PQ)	Đồ thị hoàn hảo	Phân bổ thanh ghi, lập lịch thời gian, sinh học phân tử
Đồ thị dây cung (Chordal Graph)	Các cây con trong một cây mẹ hữu hạn	Thời gian tuyến tính (LexBFS)	Đồ thị hoàn hảo	Phân tích ma trận thưa, mạng Bayes, suy diễn thống kê
Đồ thị cung tròn (Circular-Arc)	Các cung đóng trên đường tròn đơn vị	Thời gian tuyến tính	Không nhất thiết hoàn hảo	Lập lịch tuần hoàn chu kỳ, phân tích nhiễm sắc thể vòng
Đồ thị đĩa đơn vị (Unit Disk)	Các hình đĩa tròn bằng nhau trong mặt phẳng	NP-khó (đầy đủ cấp thực)	Không nhất thiết hoàn hảo	Mạng cảm biến không dây, truyền thông đặc thù
Đồ thị hoán vị (Permutation Graph)	Các đoạn thẳng nối hai đường thẳng song song	Thời gian tuyến tính	Đồ thị hoàn hảo	Bài toán so khớp chuỗi, sắp xếp dữ liệu mạng

Tóm lại, đồ thị giao nhau không chỉ cung cấp một ngôn ngữ toán học giàu sức biểu đạt để biểu diễn các tương tác liên thuộc trong không gian hình học và tập hợp, mà còn là công cụ cấu trúc trọng yếu giúp phân định ranh giới giữa các bài toán tính toán hiệu quả và các bài toán khó giải trong khoa học máy tính hiện đại.