Lý thuyết phổ đồ thị III--Spectral Graph Theory III

Trong bài này chúng ta sẽ nghiên cứu phổ của một số đồ thị đặc biệt, đó là:

  1. Đồ thị đây đủ K_n: là đồ thị có n đỉnh và n \choose 2 cạnh.
  2. Đồ thị hình sao S_n: là đồ thị có n đỉnh trong đó một đỉnh có bậc n-1, và tất cả các đỉnh còn lại có bậc 1.
  3. Đồ thị siêu khối (hypercube) H_k : là đồ thị có 2^k đỉnh trong đó mỗi đỉnh là một xâu nhị phân có độ dài k, và hai đỉnh có một cạnh nối nếu 2 xâu nhị phân tương ứng chỉ khác nhau đúng 1 bít. Từ định nghĩa, ta dễ dàng suy ra mỗi đỉnh của đồ thị H_k đều có bậc k, hay còn gọi là k-regular.

def-example

Đồ thị đầy đủ

Ma trận kề A của đồ thị đầy đủ K_n có tất cả các phần tử là 1, ngoại trừ các phần tử trên đường chéo chính. Do đó có thể viết:

A = \mathbf{1}\mathbf{1}^t - I \qquad (1)

và ma trận bậc D có mọi giá trị trên đường chéo là n-1, do đó D = (n-1)I. Từ đó suy ra ma trận Laplace của đồ thị dầy đủ có dạng:

L = nI - \mathbf{1}\mathbf{1}^T \qquad (2)

Gọi \lambda là một trị riêng của L\mathbf{v} là vector riêng tương ứng. Theo bài trước, \mathbf{1} là một vector riêng ứng với trị riêng 0, ta có \mathbf{v}^T \mathbf{1} = 0. Sử dụng Thương Rayleigh, ta có:

\lambda  = \frac{\mathbf{v}^T(nI - \mathbf{1}\mathbf{1}^T )\mathbf{v}}{\mathbf{v}^T\mathbf{v}} = n - \frac{\mathbf{v}^T\mathbf{1}\mathbf{1}^T\mathbf{v}}{\mathbf{v}^T\mathbf{v}} = n \qquad (3)

Từ phương trình trên, ta suy ra \lambda_1 = 0\lambda_2 = \ldots = \lambda_n = n. Ta nói trị riêng n có số bội (multiplicity) n-1 (vì n-1 trị riêng đều bắng n).

Theorem 1: Ma trận Laplace của đồ thị đầy đủ có trị riêng 0 với số bội 1 và trị riêng n với số bội n-1.

 
Việc tìm vector riêng của K_n không quá khó và ta coi như bài tập (bài 1 dưới đây).

Đồ thị hình sao

Với mỗi đỉnh u của đồ thị, gọi \mathbf{\delta}(u) là vector có phần tử thứ u là 1, còn các phần tử khác đều bằng 0. Để đơn giản, ta sẽ giả sử đỉnh 1 của đồ thị S_n là đỉnh có bậc n-1, còn các đỉnh khác đều có bậc 1. Khi đó, ma trận Laplace tương ứng có phần tử đầu tiên của hàng đầu tiên là n-1, còn các phần tử khác của hàng này là -1. Tương tự, phần tử đầu tiên của cột đầu tiên là n-1, còn các phần tử khác của cột này là -1. Với mội hàng tương ứng với đỉnh u, phần tử đầu tiên của hàng này là -1 và phần tử tương ứng với cột u của hàng này là 1.

Gọi u,v là hai đỉnh bất kì khác 1 của S_n. Thử nhân L với \mathbf{\delta}(u) ta thấy vector thu được có phần tử đầu tiên là -1 và phần tử thứ u1. Tương tự như vậy với L\mathbf{\delta}(v) có phần tử đầu tiên là -1 và phần tử thứ v1. Do đó,

L (\mathbf{\delta}(u) - \mathbf{\delta}(v))  = \mathbf{\delta}(u) - \mathbf{\delta}(v)  \qquad (4)

Nói cách khác, \mathbf{\delta}(u) - \mathbf{\delta}(v) là vector riêng của L ứng với trị riêng 1. Có bao nhiêu trị riêng như vây? Câu trả lời là n-2n-2 vecotor riêng tương ứng là \mathbf{\delta}(2) - \mathbf{\delta}(3), \mathbf{\delta}(3) - \mathbf{\delta}(4), \ldots, \mathbf{\delta}(n-1) - \mathbf{\delta}(n). Tại sao không tính \mathbf{\delta}(n) - \mathbf{\delta}(2)? Câu trả lời để dành cho các bạn.

Trong bài tập 2, các bạn sẽ phải chứng minh trị riêng cuối cùng (lớn nhất) của S_nn.

Theorem 2: Ma trận Laplace của đồ thị hình sao S_n có trị riêng 0 với số bội 1, trị riêng 1 với số bội n-2 và trị riêng n với số bội 1.

 

Đồ thị siêu khối

Để hiểu rõ hơn về đồ thị siêu khối H_k, chúng ta sẽ tìm hiểu thao tác lấy tích Đềcác (Cartesian Product) của đồ thị.

Definition 1 (Cartesian Product): Gọi G(V,E)H(W,F) là hai đồ thị cho trước. Đồ thị G \times H, được gọi là tích Đềcác của GH, là đồ thị có tập đỉnh là V\times W và tập cạnh chứa:

((u,v), (u',v)) nếu (u,u') \in E

((u,v), (u,v')) nếu (v,v') \in F

 

Định nghĩa tích Đềcác hơi rối rắm chút và để hình dung, ta thử xét một vài trường hợp đơn giản:

Ví dụ 1: Tìm tích Đềcác G \times H nếu H chỉ có 1 đỉnh (và không có cạnh). Dễ thấy tích đề các là đồ thị thu được bằng cách thêm một "nhãn" mới vào các đỉnh của G (xem hình minh họa dưới đây).

iso-prod

Ví dụ 2: Tìm tích Đềcác G \times H nếu H có 2 đỉnh (và không có cạnh). Ta sẽ thấy tích đề các là đồ thị thu được bằng cách lấy 2 "copy" của G và thêm một "nhãn" vào mỗi đỉnh của một copy (xem hình minh họa dưới đây).

two-iso-prod

Ví dụ 3: Tìm tích Đềcác G \times H nếu H có 2 đỉnh và 1 cạnh. Kết quả rất khó mô tả bằng lời. Xem hình minh họa dưới đây.

edge-prod
Quay trở lại với đồ thị siêu khối. Ta thấy:

  • H_1 chỉ có một cạnh.
  • H_2 là "hình vuông". Theo khái niệm tích Đềcác thì H_2 = H_1 \times H_1.
  • H_3 là "khối lập phương". Theo khái niệm tích Đềcác thì H_3 = H_2 \times H_1.

Suy diễn rộng ra thì ta sẽ có:

H_k = H_{k-1}\times H_1 \qquad(5)

Phương trình (5) cho phép chúng ta nghiên cứu phổ của H_k thông qua phép lấy tích Đềcác.

Giả sử ta đã biết các trị riêng, vector riêng của hai đồ thị GH, liệu có một quan hệ nào giữa trị riêng và vector riêng của G\times H với trị riêng, vector riêng của GH không? Câu trả lời là có và hơn nữa, quan hệ đó khá đơn giản.

Gọi \lambda\mu lần lượt là trị riêng bất kì của GH với hai vector riêng tương ứng \mathbf{x},\mathbf{y}. Ta hoàn toàn có thể giả sử \mathbf{x},\mathbf{y} là các vector đơn vị. Xét vector "tích Đềcác" \mathbf{z} với số chiều |V||W| được định nghĩa như sau:

z_{i,j} = x_iy_j \quad \forall 1 \leq i \leq |V|, 1 \leq j \leq |W|

Ta sẽ chứng minh \mathbf{z} là một vector riêng của G\times H với trị riêng \lambda + \mu. Để chứng minh điều này, ta sẽ sử dụng dạng toàn phương của ma trận Laplace và Thương Rayleigh. Trước hết ta có:

Claim 1: Vector \mathbf{z} là vector đơn vị.

 
Chứng minh coi như bài tập (bài tập 3 dưới đây) cho bạn đọc. Chú ý ở đây \mathbf{x},\mathbf{y} là các vector đơn vị.

Theorem 3: Vector \mathbf{z} là một vector riêng của G\times H ứng với trị riêng \lambda + \mu.

 
Chứng minh: Theo Claim 1, trị riêng tương ứng với \mathbf{z} chính là \mathbf{z}^TL_{G\times H}\mathbf{z}, ở đây L_{G\times H} là ma trận Laplace của G \times H. Sử dụng dạng toàn phương, ta có:

\begin{array} {l} \mathbf{z}^TL_{G\times H}\mathbf{z} & =  \sum_{((u,v),(u',v')) \in E(G\times H)}(z_{u,v} -z_{u',v'})^2 \\ & =   \sum_{v \in W}\sum_{(u,u') \in E}(z_{u,v} -z_{u',v})^2 + \sum_{u \in V}\sum_{(v,v') \in F}(z_{u,v} -z_{u,v'})^2  \\ & =   \sum_{v \in W}y^2_v\sum_{(u,u') \in E}(x_u -x_{u'})^2 + \sum_{u \in V}x^2_u\sum_{(v,v') \in F}(y_{v} -y_{v'})^2 \\ & =   \sum_{v \in W}y^2_v\lambda + \sum_{u \in V}x^2_u\mu \\  & =   \lambda + \mu \end{array} \qquad(6)

Ta sẽ giải thích lần lượt từng phép biến đổi trong (6). Phương trình đầu tiên sử dụng định nghĩa dạng toàn phương của ma trận Laplace (xem lại bài 1). Phương trình thứ 2 sử dụng định nghĩa của tích Đềcác. Phương trình thứ 3 sử dụng định nghĩa của vector \mathbf{z}. Phương trình thứ 4 sử dụng định nghĩa Thương Rayleigh cho \lambda\mu (và dạng toàn phương của Laplace cho \mathbf{x},\mathbf{y}). Phương trình cuối sử dụng tính chất \mathbf{x},\mathbf{y} là các vector đơn vị.


Quay lại đồ thị siêu khối H_k. Sử dụng Theorem 3, ta chỉ cần xét trị riêng và vector riêng của H_1 (đồ thị có 2 đỉnh và đúng 1 cạnh). Trong bài tập 4, ta sẽ chứng minh H_1 có 2 trị riêng là 02, do đó, trị riêng nhỏ thứ 2 của H_k sẽ là 2, i.e, \lambda_2 = 2. Sử dụng bất đẳng thức Cheeger, ta suy ra:

Corollary 1: \Phi(H_k) \geq 1.

 
Hay nói cách khác, với mọi tập đỉnh con S có kích thước không quá một nửa tập đỉnh của đồ thị siêu khối H_k, số cạnh biên (|\partial S|) luôn lớn hơn hoặc bằng số đỉnh của S. Trong bài tập 5 và 6 dưới đây, chúng ta sẽ đi tìm trị riêng và vector riêng của H_k.

Tham khảo
[1] Daniel Speilman. Spectral Graph Theory Notes, Fall 2015, Lecture 02.

Bài tập

Bài 1: Tìm các vector riêng của đồ thị đầy đủ K_n.
Bài 2: Chứng minh rằng trị riêng lớn nhất của S_nn và tìm vector riêng tương ứng.
Bài 3: Chứng minh Claim 1.
Bài 4: Tìm trị riêng và vector riêng của H_1.
Bài 5: Chứng minh rằng 2i là trị riêng của H_K có số bội k \choose i.
Bài 6: Cho trước một vector \mathbf{b} có chiều k và các phần tử chỉ thuộc \{0,1\}, i.e, \mathbf{b} \in \{0,1\}^k. Coi mỗi đỉnh của H_k tương ứng với một vector trong \{0,1\}^k và hai đỉnh có một cạnh nếu 2 vector tương ứng khác nhau đúng 1 vị trí (mã Gray). Chứng minh rằng vector \varphi(\mathbf{b}) được định nghĩa như sau:

\varphi_\mathbf{a}(\mathbf{b}) = (-1)^{\mathbf{a}^T\mathbf{b}} \quad(7)

Là một vector riêng của H_k.

Hướng dẫn giải bài tập SGT02

Bài 1: Gọi \mathbf{v} là vector riêng (đơn vị) tương ứng với \lambda_2. Sử dụng dạng toàn phương và Thương Rayleigh, ta có:

\lambda_2 = \sum_{(i,j) \in E} (v_i - v_j)^2

Từ đó suy ra \lambda_2 = 0 khi và chỉ khi v_i = v_j \quad \forall (i,j) \in E. Nếu G(V,E) là liên thông, ta suy ra v_1 = v_2 =\ldots = v_n. Do \mathbf{v} là vector riêng của \lambda_2, ta suy ra \mathbf{v}^T\mathbf{1} = 0. Từ đó suy ra \mathbf{v} = \mathbf{0}, trái với giả thiết \mathbf{v} là vector đơn vị. Do đó, G phải có ít nhất 2 thành phần liên thông.
Bài 2: Tư tưởng chứng minh giống bài 1 và kết hợp với quy nạp.

Facebook Comments

Tags: ,

Reply

Your email address will not be published. Required fields are marked *