Siêu đồ thị phi chu trình và đồ thị dây cung

Bài trước: Phân rã cây và độ rộng cây.
Bài kế tiếp: logic bậc nhất và truy vấn hội (conjunctive queries).

Bài trước lược khảo các khái niệm độ rộng cây, phân rã cây, đồ thị dây cung và một vài bổ đề quan trọng để hiểu thêm về các khái niệm này. Bài cũng đề cập đến một thuật toán thời gian đa thức nhận dạng đồ thị dây cung và xây dựng phân rã cây tối ưu của một đồ thị dây cung. Bài này nói về một thuật toán thời gian tuyến tính để nhận dạng đồ thị dây cung; sau đó ta đề cập đến siêu đồ thị phi chu trình (acyclic hypergraph). Các kết quả này sẽ được dùng đến để thiết kế các thuật toán định trị phép kết nối (join evaluation) trong cơ sở dữ liệu.

1. Nhận dạng đồ thị dây cung

Trong bài trước ta đã chứng minh rằng một đồ thị ${G}$ là dây cung nếu và chỉ nếu tồn tại một thứ tự loại trừ hoàn hảo (perfect elimination order) cho nó. Năm 1984, Robert Tarjan và Mihalis Yannakakis thiết kế một thuật toán rất đơn giản để nhận diện một đồ thị dây cung trong thời gian tuyến tính. (Khi đọc lịch sử lý thuyết cơ sở dữ liệu và xem danh sách những người hiện đang đóng góp nhiều cho ngành cơ sở dữ liệu, bạn sẽ thấy rất nhiều người gốc Hy Lạp! Tôi hy vọng 10 năm nữa sẽ có một anh Hy Lạp viết thế này về người Việt.)

Thuật toán của Tarjan-Yannakakis gồm hai bước đơn giản.

Bước 1: xây dựng một thứ tự các đỉnh đồ thị ${G}$ dùng một thuật toán gọi là thuật toán tìm kiếm lực lượng cực đại (maximum cardinality search, viết tắt là MCS). Ta sẽ chứng minh rằng thứ tự đỉnh mà thuật toán MCS in ra sẽ là thứ tự loại trừ hoàn hảo của ${G}$ nếu và chỉ nếu ${G}$ là đồ thị dây cung.
Bước 2: kiểm tra xem thứ tự sinh bởi MCS có phải là thứ tự loại trừ hoàn hảo không.

Cả thuật toán MCS và bước kiểm tra đều có thời gian chạy là ${O(n+m)}$ , trong đó ${n}$ là số đỉnh của đồ thị và ${m}$ là số cạnh.

1.1. Bước 1

Gọi đồ thị nhập là ${G=(V,E)}$ ; giả sử nó có ${n}$ đỉnh và ${m}$ cạnh. Thuật toán MCS rất đơn giản. Nó sẽ tạo một thứ tự ${\alpha: V \rightarrow [n]}$ , nghĩa là ${\alpha(v)}$ , gọi là nhãn ${\alpha}$ của đỉnh ${v}$ , chính là vị trí của ${v}$ trong thứ tự đó. Đầu tiên ta chọn một đỉnh ${v}$ tuỳ hỉ và gán ${\alpha(v) = n}$ . Sau đó, với ${j=n-1, n-2, \dots, 1}$ , tuần tự chọn một đỉnh ${v}$ chưa có nhãn kề với nhiều đỉnh đã có nhãn nhất và gán nhãn ${\alpha(v) = j}$ . Nếu có hoà thì chọn tuỳ hỉ.

Định lý 1 Thứ tự ${\alpha}$ sinh bởi thuật toán MCS là thứ tự loại trừ hoàn hảo nếu và chỉ nếu ${G}$ là đồ thị dây cung.

Chứng minh: Nếu ${\alpha}$ là thứ tự loại trừ hoàn hảo thì tất nhiên ${G}$ là đồ thị dây cung như đã chứng minh trong bài trước. Để chứng minh điều ngược lại ta cần một khái niệm sau đây. Một đường dẫn (path) ${v_0,v_1,\dots, v_k}$ với ${k\geq 2}$ của đồ thị ${G}$ được gọi là một thung lũng nếu tồn tại một giá trị ${j \in [k-1]}$ sao cho

$\displaystyle \alpha(v_0) > \alpha(v_k) > \alpha(v_1) > \cdots > \alpha(v_j) < \alpha(v_{j+1}) < \cdots < \alpha(v_k) < \alpha(v_0)$

và không có cạnh nào của ${G}$ nối hai đỉnh không kề nhau trên đường dẫn này. (Đây là một đường dẫn không có dây cung.) Giá trị ${\alpha(v_k)}$ gọi là độ cao bên phải của thung lũng.

Giả sử ${G}$ là đồ thị dây cung nhưng ${\alpha}$ lại không phải là thứ tự loại trừ hoàn hảo. Như vậy, tồn tại ba đỉnh ${u,v,w}$ sao cho ${vu, vw \in E}$ , ${uw \notin E}$ , và ${\alpha(v) < \alpha(u) < \alpha(w)}$ . Như vậy ${wvu}$ là một thung lũng với độ cao bên phải là ${\alpha(u)}$ .

Tại thời điểm MCS chọn gán nhãn cho ${u}$ thì ${u}$ phải kề với một đỉnh ${x}$ đã có nhãn và ${x}$ không kề với ${v}$ . Nếu không thì ta đã chọn gán nhãn cho ${v}$ thay vì ${u}$ . Hơn nữa, ${x}$ cũng không kề với ${w}$ tại vì nếu ${xw\in E}$ thì ta có một chu trình không có dây cung. Do đó, nếu ${\alpha(x) > \alpha(w)}$ thì ${xuvw}$ là một thung lũng; còn nếu ${\alpha(x)<\alpha(w)}$ thì ${wvux}$ là một thung lũng. Lưu ý rằng so với thung lũng ${wuv}$ ban đầu thì thung lũng mới này (hoặc ${wvux}$ hoặc ${xuvw}$ ) có độ cao bên phải lớn hơn.

Tổng quát hơn, xét một thung lũng có chiều dài ${k \geq 2}$ : ${v_0,v_1,\cdots, v_k}$ . Với cùng lý luận như trên, tại thời điểm ${v_k}$ được dán nhãn phải tồn tại một đỉnh ${x}$ đã được gán nhãn kề với ${v_k}$ mà không kề với ${v_1}$ , nếu không thì ${v_1}$ đã được chọn thay vì ${v_k}$ . Gọi ${i}$ là số nhỏ nhất từ ${2}$ đến ${k}$ sao cho ${x}$ kề với ${v_i}$ . Dễ thấy ${x}$ và ${v_0}$ không kề nhau vì nếu không thì ta có một chu trình không có dây cung ${xv_iv_{i-1}\cdots v_0}$ . Tùy theo ${\alpha(x)>\alpha(v_0)}$ hay ngược lại mà ta có hoặc ${xv_i\cdots v_0}$ hoặc ${v_0\cdots v_i x}$ là một thung lũng mới. Và thung lũng mới này có chiều cao bên phải lớn hơn chiều cao bên phải của thung lũng ${v_0, v_1,\dots,v_k}$ ban đầu.

Do đó, từ thung lũng ${wuv}$ đầu tiên ta có thể tạo liên tục các thung lũng với chiều cao bên phải lớn dần. Điều này hiển nhiên là vô lý. $\Box$

Bài tập 1 Chỉ ra cách hiện thực thuật toán MCS chạy trong thời gian ${O(m+n)}$ .

1.2. Bước 2

Kiểm tra xem thứ tự ${\alpha}$ có phải là thứ tự loại trừ hoàn hảo không cũng là một bài tập thiết kế thuật toán cực kỳ thú vị. Đại khái, ta quét các đỉnh của ${G}$ từ nhãn số ${1}$ đến nhãn số ${n}$ . Với mỗi đỉnh ${v}$ , ta lưu trữ hai con trỏ ${\ell(v), r(v)}$ định nghĩa như sau. Giả sử nhãn của ${v}$ là ${i}$ , và hiện nay ta đã quét đến đỉnh có nhãn ${j>i}$ . Con trỏ ${\ell(v)}$ trỏ đến hàng xóm của ${v}$ có nhãn nhỏ nhất trong đoạn ${[i+1,j]}$ ; con trỏ ${r(v)}$ trỏ đến hàng xóm của ${v}$ có nhãn lớn nhất trong đoạn ${[i+1,j]}$ . Nếu không tồn tại hàng xóm nào của ${v}$ có nhãn trong đoạn ${[i+1,j]}$ thì hai con trỏ này gán bằng ${-1}$ .

Khi quét đến đỉnh ${w}$ , ta cập nhật các con trỏ ${\ell(v),r(v)}$ của các đỉnh ${v}$ với nhãn ${\alpha(v)<\alpha(w)}$ . Với mỗi hàng xóm ${v}$ của ${w}$ sao cho ${\alpha(v)<\alpha(w)}$ , nếu ${\ell(v) = r(v) = -1}$ thì ta gán ${\ell(v) = r(v) = \alpha(w)}$ . Nếu ${\ell(v)}$ (và vì thế cả ${r(v)}$ ) có giá trị lớn hơn ${-1}$ thì ta gán ${r(v) = \alpha(w)}$ .

Sau khi cập nhật xong các con trỏ ${\ell(v), r(v)}$ , ta lại xét từng hàng xóm ${v}$ của ${w}$ . Nếu tồn tại một hàng xóm ${v}$ với ${\alpha(v)<\alpha(w)}$ sao cho ${\ell(v) \neq w}$ và ${r(\ell(v)) < \alpha(w)}$ thì ta “báo lỗi” rằng ${\alpha}$ không phải là thứ tự loại trừ hoàn hảo. (Tại sao?)

Nếu sau khi đã quét hết các đỉnh mà không bị báo cáo lỗi thì ta báo cáo ${G}$ là đồ thị dây cung, vì ${\alpha}$ là thứ tự loại trừ hoàn hảo.

Bài tập 2 Chứng minh rằng thuật toán trên chạy đúng cho Bước 2, và có thể thiết kế để nó chạy trong thời gian ${O(m+n)}$ .

2. Siêu đồ thị phi chu trình

2.1. Định nghĩa và vài tính chất

Ta thảo luận siêu đồ thị phi chu trình (acyclic hypergraph) vì ít nhất 2 lý do. Một là (đồ thị Gaifman của) nó tương đương với đồ thị dây cung. Hai là ta sẽ dùng nó để thiết kế thuật toán kết nối (join algorithm) cho các truy vấn hội (conjunctive query) trong cơ sở dữ liệu, sẽ thảo luận trong bài kế tiếp.

Định nghĩa 2 Một siêu đồ thị ${\mathcal H = (V, E)}$ là phi chu trình nếu tồn tại một phân rã cây ${(\mathcal T = (T, E^{\mathcal T}), \{X_t\}_{t\in T})}$ sao cho mỗi khối ${X_t}$ là một siêu cạnh nào đó của ${\mathcal H}$ ; nói cách khác ${X_t \in E}$ với mọi ${t\in T}$ . Cụ thể hơn, ${\mathcal T}$ là một cây thoả hai tính chất: (a) với mọi siêu cạnh ${e\in E}$ thì ${e\subseteq X_t}$ với một đỉnh cây ${t\in T}$ nào đó, và (b) với mọi đỉnh ${v\in V}$ thì tập ${\{t \ | \ v\in X_t\}}$ là khác rỗng và tạo thành một cây con của ${\mathcal T}$ .

Mục tiêu của chúng ta trong phần này của bài là tìm một thuật toán hiệu quả để xem một siêu đồ thị cho trước có phải là phi chu trình hay không, và xây dựng một phân rã cây cho nó. Các kết quả cũng của Tarjan và Yannakakis. Để thiết kế được thuật toán, chúng ta cần phân tích một số thuộc tính của siêu đồ thị phi chu trình. Cho một siêu đồ thị bất kỳ ${\mathcal H =(V,E)}$ , đồ thị Gaifman ${\mathcal G(\mathcal H)}$ của ${\mathcal H}$ là một đồ thị thông thường (không phải siêu đồ thị) với tập đỉnh là ${V}$ và ${uv}$ là một cạnh của ${\mathcal G(\mathcal H)}$ nếu và chỉ nếu ${\{u,v\}\subseteq e}$ với ${e}$ là một siêu cạnh nào đó của ${\mathcal H}$ . Định lý sau đây cho ta ít nhất ba cách để định nghĩa đồ thị phi chu trình.

Định lý 3 Gọi ${\mathcal H}$ là một siêu đồ thị. Ba điều sau đây tương đương nhau.

(i) ${\mathcal H}$ là phi chu trình
(ii) ta có thể xoá tất cả các đỉnh của ${\mathcal H}$ bằng cách lập đi lập lại một trong hai tác vụ: (a) xoá một đỉnh chỉ thuộc về một siêu cạnh duy nhất, (b) xoá một siêu cạnh là tập con của một siêu cạnh khác.
(iii) đồ thị Gaifman ${\mathcal G(\mathcal H)}$ của ${\mathcal H}$ là một đồ thị dây cung, và mọi clique của ${\mathcal G(\mathcal H)}$ đều là tập con của một siêu cạnh nào đó của ${\mathcal H}$ .

Chứng minh: ${(i) \Rightarrow (ii)}$ Xét phân rã cây ${(\mathcal T=(T,E^{\mathcal T}), \{X_t\}_{t\in T})}$ của ${\mathcal H}$ thoả điều kiện trong định nghĩa đồ thị phi chu trình. Trước hết, ta xoá tất cả các siêu cạnh ${e}$ của ${\mathcal H}$ thoả điều kiện: siêu cạnh ${e}$ không phải là một khối của ${\mathcal H}$ và ${e\subseteq X_t}$ với ${t\in T}$ nào đó. Kế đến, xét một lá ${t}$ tuỳ ý của phân rã cây ${\mathcal T}$ . Lưu ý rằng ${X_t}$ là một cạnh của ${\mathcal H}$ . Gọi ${t'}$ là đỉnh kề với ${t}$ trên phân rã cây. Ta xoá các phần tử trong ${X_t \setminus X_{t'}}$ . Từ định nghĩa của phân rã cây ta biết rằng tại thời điểm này thì các phần tử thuộc ${X_t\setminus X_{t'}}$ chỉ thuộc về một mình ${X_t}$ . Sau đó xoá ${X_t}$ và xoá đỉnh ${t}$ khỏi phân rã cây. Lập lại quá trình này với cây mới.

${(ii) \Rightarrow (iii)}$ Thứ tự xoá các đỉnh thoả điều kiện ${(ii)}$ là thứ tự loại trừ hoàn hảo của đồ thị ${\mathcal G(\mathcal H)}$ . Do đó ${\mathcal G(\mathcal H)}$ là đồ thị dây cung. Xét một cái clique ${K}$ bất kỳ của ${\mathcal G(\mathcal H)}$ . Tất nhiên nếu ${|K|=2}$ thì tồn tại siêu cạnh chứa ${K}$ . Xét ${|K|\geq 3}$ và giả sử không có siêu cạnh nào chứa ${K}$ . Bằng quy nạp, ta có thể giả sử rằng với mọi ${v\in K}$ thì tồn tại một siêu cạnh chứa ${K-v}$ (cũng là một clique). Chọn một siêu cạnh ${e_v}$ tuỳ hỉ sao cho ${K-v \subseteq e_v}$ . Với mỗi ${v\in K}$ thì ${v}$ thuộc về ${e_u}$ với mọi ${u\in K-v}$ ; do ${|K|\geq 3}$ có ít nhất ${2}$ cạnh ${e_u}$ chứa ${v}$ . Giả sử ${v}$ là đỉnh đầu tiên của ${K}$ bị xoá. Ta không thể xoá đỉnh ${v}$ bằng tác vụ (a) cho đến khi ${|K|-2}$ các cạnh ${e_u}$ đã được xoá. Để xoá ${e_u}$ bằng tác vụ (b) thì tại thời điểm đó nó phải là tập con của một ${e'_u}$ nào đó, mà như vậy thì ${e'_u}$ vẫn chứa toàn bộ ${K-u}$ . Sau khi xoá xong ${e_u}$ , thay ${e_u}$ bằng ${e'_u}$ thì ta lại vẫn có một bộ các cạnh chứa đám ${K-u}$ như cũ. Tóm lại, ta không có cách nào xoá khối ràng buộc này được.

${(iii) \Rightarrow (i)}$ Ta dùng thuật toán giải Bài toán (2) trong bài trước để xây dựng một phân rã cây cho ${\mathcal G(\mathcal H)}$ . Trong phân rã cây này thì các khối ${X_t}$ đều là các cliques cực đại. Mà các cliques cực đại thì đều là các cạnh của ${\mathcal H}$ . $\Box$

2.2. Thuật toán nhận dạng

Từ thuộc tính ${(ii)}$ của định lý 3, ta có thể thiết kế một thuật toán thời gian đa thức để xác minh xem một siêu đồ thị cho trước có phải là siêu đồ thị phi chu trình hay không. Tuy nhiên, thuật toán này có thời gian chạy không tốt. Trong phần này của bài, ta trình bày thuật toán thời gian tuyến tính để xác minh xem một siêu đồ thị có phải phi chu trình hay không.

Chọn một siêu cạnh ${f_1 \in E(\mathcal H)}$ tuỳ hỉ. Tất cả các đỉnh nằm trong cạnh này được gán nhãn bằng ${1}$ . Để dùng về sau, ta sẽ dùng hàm ${\beta: V \rightarrow [n]}$ để chỉ cái nhãn này; nghĩa là ta gán ${\beta(v)=1}$ với mọi ${v\in f_1}$ . Sau đó loại đi tất cả các cạnh chỉ chứa các đỉnh có nhãn ${\beta}$ bằng ${1}$ .
Với ${j=2,3,\cdots}$ , trong khi vẫn còn đỉnh chưa có nhãn thì chọn cạnh ${f_j}$ chứa nhiều đỉnh đã có nhãn ${\beta}$ nhất. Cạnh mới ${f_j}$ sẽ phủ một số đỉnh chưa có nhãn. Ta gán cho các đỉnh mới này nhãn ${j}$ . Rồi lại loại đi các cạnh chỉ chứa các đỉnh đã gán nhãn. Tăng ${j}$ lên ${1}$ và lặp lại bước này.
Giả sử sau khi vòng lặp trên chạy xong thì ta đã chọn các cạnh ${f_1,f_2,\cdots,f_k}$ ; các cạnh này phủ tất cả các đỉnh.
Với mọi tập đỉnh ${S\subset V}$ , định nghĩa ${\beta(S) = \max_{v\in S} \beta(v)}$ , và ${L_i(S) = \{v \in S \ | \ \beta(v) = i\}}$ .
Thuật toán kết luận rằng là đồ thị phi chu trình nếu và chỉ nếu
- với mọi ${e \in E-\{f_1,\dots,f_k\}}$ ta có ${e \subseteq f_{\beta(e)}}$ , và
- với mọi ${f_i}$ , nếu ${f_i - L_i(f_i) \neq \emptyset}$ thì ${f_i-L_i(f_i) \subseteq f_{\beta(f_i-L_i(f_i))}}$ .

Để chứng minh rằng thuật toán chạy đúng, ta cần một bổ đề.

Bổ đề 4 Giả sử ${\mathcal H}$ là đồ thị phi chu trình. Gọi ${\alpha: V \rightarrow [n]}$ là một thứ tự của tất cả các đỉnh định nghĩa bằng cách xếp các đỉnh trong ${L_k(f_k)}$ trước theo một trật tự bất kỳ, rồi đến các đỉnh của ${L_{k-1}(f_{k-1})}$ , rồi đến ${L_{k-2}(f_{k-2})}$ , vân vân, cho đến ${L_1(f_1)}$ . Thì ${\alpha}$ là một output hợp lệ của thuật toán MCS chạy trên đồ thị Gaifman của ${\mathcal H}$ .

Chứng minh: Trước hết, ${\alpha}$ gán nhãn $n,n-1,\cdots$ cho các đỉnh trong ${L_1(f_1)}$ . Dễ thấy rằng các nhãn này không mâu thuẫn với MCS. Giả sử nhãn ${\alpha}$ của các đỉnh từ ${L_1(f_1)}$ đến ${L_i(f_i)}$ cũng đều thống nhất với MCS. Xét một đỉnh ${u}$ tuỳ ý trong ${L_{i+1}(f_{i+1})}$ . Giả sử ta chạy MCS và MCS không chọn ${u}$ mà chọn ${v}$ . Như vậy, ${v}$ phải có ít nhất nhiều hàng xóm đã có nhãn ${\alpha}$ như ${u}$ . (Tại thời điểm này, các hàng xóm đã có nhãn ${\alpha}$ là các hàng xóm đã có nhãn ${\beta}$ từ ${1}$ đến ${i}$ .) Gọi tập các hàng xóm của ${v}$ đã có nhãn ${\alpha}$ là ${N_\alpha(v)}$ . Do ${\mathcal H}$ là phi chu trình, đồ thị Gaifman của ${\mathcal H}$ là đồ thị dây cung, và MCS trả về một thứ tự loại trừ hoàn hảo. Vì thế ${v \cup N_\alpha(v)}$ là một clique của đồ thị Gaifman của ${\mathcal H}$ . Do Tính chất ${(iii)}$ trong định lý 3, phải tồn tại một siêu cạnh ${e}$ sao cho ${v \cup N_\alpha(v) \subseteq e}$ .

Tại thời điểm ${f_{i+1}}$ sắp được chọn thì ${e}$ chưa được chọn (vì ${e}$ chứa đỉnh ${v}$ chưa có nhãn ${\beta}$ ). Do đó, số đỉnh đã có nhãn ${\beta}$ của ${e}$ nhỏ hơn hoặc bằng số đỉnh đã có nhãn ${\beta}$ của ${f_{i+1}}$ . Từ đó dễ thấy rằng số hàng xóm đã có nhãn ${\alpha}$ của ${v}$ nhỏ hơn hoặc bằng số hàng xóm đã có nhãn ${\alpha}$ của ${u}$ . Và vì thế MCS có thể chọn ${u}$ cũng được. Tóm lại, ${u}$ là một chọn lựa không mâu thuẫn với MCS. Khi ${u}$ đã không mâu thuẫn với MCS thì tất cả các đỉnh còn lại trong ${L_{i+1}(f_{i+1})}$ chọn theo bất kỳ thứ tự nào cũng không mâu thuẫn với MCS vì mỗi lần chọn thêm một đỉnh ${w}$ từ ${L_{i+1}(f_{i+1})}$ thì số hàng xóm đã có nhãn ${\alpha}$ của ${w}$ tăng lên ${1}$ so với ${w}$ trước đó. $\Box$

Định lý 5 Thuật toán trên trả về câu trả lời đúng. Nghĩa là, ${\mathcal H}$ là đồ thị phi chu trình nếu và chỉ nếu

với mọi ${e \in E-\{f_1,\dots,f_k\}}$ ta có ${e \subseteq f_{\beta(e)}}$ , và
với mọi ${f_i}$ , nếu ${f_i - L_i(f_i) \neq \emptyset}$ thì ${f_i-L_i(f_i) \subseteq f_{\beta(f_i-L_i(f_i))}}$ .

Chứng minh: Trước hết, giả sử ${\mathcal H=(V,E)}$ là đồ thị phi chu trình. Xét ${e \in E-\{f_1,\dots, f_k\}}$ trước. Đặt ${j = \beta(e)}$ cho tiện. Ta phải chứng minh rằng ${e \subseteq f_{j}}$ . Nếu ${L_j(e) = e}$ có nghĩa là tất cả các đỉnh trong ${e}$ đều được phủ ở cùng bước ${j}$ thì hiển nhiên ${e \subseteq f_j}$ . Như vậy chỉ còn trường hợp ${e-L_j(e) \neq \emptyset}$ . Giả sử ${e \not\subseteq f_j}$ , thì ${(e-L_j(e)) \setminus f_j \neq \emptyset}$ . Gọi ${u \in L_j(e)}$ là đỉnh tuỳ ý. Do ${f_j}$ được chọn ở bước ${j}$ , ta phải có ${|f_j - L_j(f_j)| \geq |e-L_j(e)|}$ . Trong đồ thị Gaifman của ${\mathcal H}$ thì ${u}$ kề với tất cả các đỉnh trong ${e-L_j(e)}$ và với tất cả các đỉnh trong ${f_j - L_j(f_j)}$ . Vì ${\mathcal H}$ là đồ thị phi chu trình, theo Bổ đề 4 thì ${u \cup (e-L_j(e)) \cup (f_j - L_j(f_j)}$ tạo thành một clique. Do đó, tồn tại một siêu cạnh ${f}$ sao cho ${u \cup (e-L_j(e)) \cup \bar (f_j - L_j(f_j) \subseteq f}$ . Mà như vậy thì ${f}$ chứa nhiều đỉnh đã có nhãn ${\beta}$ hơn ${f_j}$ , vô lý! Kế đến, xét ${f_i}$ tuỳ hỉ sao cho ${f_i - L_i(f_i) \neq \emptyset}$ . Định nghĩa ${j = \beta(f_i-L_i(f_i))}$ và giả sử ${f_i-L_i(f_i) \not\subseteq f_j}$ , nghĩa là ${(f_i-L_i(f_i)) \setminus f_j \neq \emptyset}$ . Tương tự như trên gọi ${u}$ là đỉnh tuỳ ý trong ${L_j(f_i)}$ và lập luận như trên ta sẽ có điều vô lý.

Ngược lại, giả sử hai điều kiện trong phát biểu định lý là đúng. Ta sẽ chứng minh rằng ${\mathcal H}$ thoả tính chất ${(ii)}$ trong trong Định lý 3 để chứng minh rằng ${\mathcal H}$ là đồ thị phi chu trình. Chạy chỉ số ${j=k, k-1,\dots,1}$ . Trước hết, ta loại đi tất cả các cạnh ${e\neq f_j}$ sao cho ${\beta(e) = j}$ . Sau đó, loại đi các đỉnh nằm trong ${L_j(f_j)}$ vì lúc này ta biết chắc chúng là các đỉnh chỉ thuộc về ${f_j}$ . Rồi giảm ${j}$ đi ${1}$ . Dễ thấy rằng bằng cách như vậy ta có thể loại hết các đỉnh của ${\mathcal H}$ . $\Box$

Bài tập 3 Hiện thực hoá thuật toán xác minh đồ thị phi chu trình như mô tả ở trên sao cho nó có thời gian chạy là ${O(m+n)}$ .

2.3. Thuật toán xây dựng phân rã cây của một đồ thị phi chu trình

Để xây dựng phân rã cây cho đồ thị phi chu trình ${\mathcal H}$ , ta chạy thuật toán xác minh như trong phần trước. Sau đó, ta tạo một phân rã cây mà các khối là các siêu cạnh của ${\mathcal H}$ . Với mỗi khối ${e\in E - \{f_1,\dots,f_k\}}$ , ta nối ${e}$ với ${f_{\beta(e)}}$ . Với mỗi khối ${f_i}$ sao cho ${f_i - L_i(f_i) \neq \emptyset}$ , ta nối ${f_i}$ với ${f_{\beta(f_i-L_i(f_i))}}$ . Đến đây ta được một cái rừng. Nối các cây trong rừng này theo một cách bất kỳ thành một cây lớn.

Bài tập 4 Chứng minh rằng cách xây dựng như trên trả về một phân rã cây của đồ thị phi chu trình ${\mathcal H}$ . Thời gian chạy của thuật toán là ${O(m+n)}$ .

Thật ra để xây dựng phân rã cây thì ta không cần nối ${e}$ với ${f_{\beta(e)}}$ cho đám ${e \in E - \{f_1,\cdots,f_k\}}$ . Một phân rã cây ${\mathcal T'}$ bất kỳ của siêu đồ thị ${\mathcal H' = (V,\{f_0,\cdots,f_k\})}$ cũng là một siêu đồ thị của ${\mathcal H}$ . Đám ${\{f_1,\cdots,f_k\}}$ không có tập nào chứa tập nào, và chúng tạo thành bộ khung cho phân rã cây của ${\mathcal H}$ . Phân rã cây ${\mathcal T'}$ gọi là phân rã cây không dư thừa vì không có khối nào là tập con của khối nào. Thuật toán trên cho phép ta xây dựng phân rã cây không dư thừa cho một đồ thị phi chu trình trong thời gian tuyến tính. Cũng dễ thấy rằng ${k \leq n}$ , do đó

Định lý 6 Phân rã cây không dư thừa của đồ thị phi chu trình ${\mathcal H}$ có số đỉnh nhỏ hơn ${|V(\mathcal H)|}$ , và ta có thể xây dựng một phân rã cây như vậy trong thời gian tuyến tính.

Siêu đồ thị phi chu trình và đồ thị dây cung

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Chuyên Mục

Kho bài

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý