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$ và $\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$ và $\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ứ $u$ là $1$. 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ứ $v$ là $1$. 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-2$ và $n-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_n$ là $n$.

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)$ và $H(W,F)$ là hai đồ thị cho trước. Đồ thị $G \times H$, được gọi là tích Đềcác của $G$ và $H$, 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ị $G$ và $H$, 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 $G$ và $H$ không? Câu trả lời là có và hơn nữa, quan hệ đó khá đơn giản.

Gọi $\lambda$ và $\mu$ lần lượt là trị riêng bất kì của $G$ và $H$ 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$ và $\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à $0$ và $2$, 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_n$ là $n$ 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 *