Trong bài này chúng ta sẽ nghiên cứu phổ của một số đồ thị đặc biệt, đó là:
- Đồ thị đây đủ $K_n$: là đồ thị có $n$ đỉnh và $n \choose 2$ cạnh.
- Đồ 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$.
- Đồ 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.
Đồ 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$).
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$.
Đồ 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ị.
$((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).
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).
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.
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ó:
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ị.
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:
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.
No comments
Comments feed for this article
Trackback link: http://www.giaithuatlaptrinh.com/wp-trackback.php?p=1406