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

Trong bài này, chúng ta sẽ tìm hiểu phổ cùa ma trận kề và quan hệ với bài toán tô màu đồ thị. Công cụ chính chúng ta sử dụng đó là Thương Rayleigh.

Definition 1 (Coloring): Một phép tô màu đồ thị là một phép gán cho mỗi đỉnh một màu sao cho không có hai đỉnh kề nào có cùng một màu. Một đồ thị được gọi là $k$-colorable nếu như chúng ta có thể tô đồ thị đó sử dụng tối đa $k$ màu. Sắc số của đồ thị $G$, thường kí hiệu là $\chi(G)$, là số màu ít nhất ta có thể dùng để tô màu $G$.

 

Gọi $A$ là ma trận kề của đồ thị $G(V,E)$ và $\mu_1 ,\mu_2, \ldots,\mu_n$ là $n$ trị riêng tương ứng (của $A$). Ta giả sử:

$\mu_1 \geq \mu_2 \geq \ldots \geq \mu_n \qquad (1)$

Chú ý thứ tự các trị riêng của ma trận kề ngược với trị riêng của ma trập Laplace $L$. Nguyên nhân là vì với đồ thị chính quy bậc $k$ ($k$-regular), ta có:

$L = I - kA\qquad (2)$

và do đó, $\lambda_i = k - \mu_i$.

Trong bài này, ta tập trung chứng mimh quan hệ sau giữa sắc số và phổ của ma trận kề:

Theorem 1:

$1 - \frac{\mu_1}{\mu_n} \leq \chi(G) \leq \lfloor \mu_1\rfloor +1 \qquad (3)$

 

Bất đẳng thức đầu tiên (cận dưới) nhìn có vẻ tầm thường vì đương nhiên $ \chi(G) \geq 1$. Tuy nhiên, ta nên nhớ trị riêng của ma trận kề có thể âm. Ngược lại, trị riêng của ma trận Laplace luôn không âm và nhỏ nhất bằng $0$. Bất đẳng thức đầu tiên là bất đẳng thức Hoffman [2] và bất đẳng thức thứ hai là bất đẳng thưc Wilf [3].

Trị riêng $\mu_1$

Trong phần này ta sẽ chứng minh cận trên của $\chi(G)$. Khi nghiên cứu trị riêng của ma trận Laplace, hai công cụ chính ta sử dụng là Thương Rayleigh và dạng toàn phương. Tuy nhiên, dạng toàn phương của ma trận kề không "đẹp" như của ma trận Laplace, do đó Thương Rayleigh sẽ là công cụ chính.

Theo Thương Rayleigh, ta có:

$\mu_1 = \max_{\mathbf{v} \in \mathbb{R}^V}\frac{\mathbf{v}^TA\mathbf{v}}{\mathbf{v}^T\mathbf{v}} \qquad (4)$

Gọi $d_{avg}$ và $\Delta$ lần lượt là bậc trung bình và bậc lớn nhất của $G$. Ta sẽ chứng minh:

Lemma 1:

$d_{avg} \leq \mu_1 \leq \Delta \qquad(5)$

 

Chứng minh: Chúng minh cận dưới dễ hơn vì ta chỉ cần sử dụng $(4)$. Chọn $\mathbf{v} = \mathbf{1}$ (các phần tử đều là 1) ta có:

$\frac{\mathbf{1}^TA\mathbf{1}}{\mathbf{1}^T\mathbf{1}} = \frac{\sum_{(i,j) \in E} A[i,j]}{n} = \frac{2m}{n} = d_{avg}\qquad (6)$

Từ đó ta suy ra cận dưới của $\mu_1$.

Để chứng minh cận trên, ta gọi $\mathbf{u}$ là vector riêng ứng với $\mu_1$. Theo định nghĩa ta có:

$A\mathbf{u} = \mu_1\mathbf{u} \qquad (7)$

Gọi $N_i$ là tập đỉnh kề với đỉnh $i$ của đồ thị. Tại đỉnh $i$, từ phương trình $(7)$, ta suy ra:

$\sum_{j \in N_i}u_j = \mu_1u_i \qquad (8)$

Chọn $i$ là đỉnh có $u_i$ lớn nhất, i.e, $u_i \geq u_j \forall j \in V, j \not= i$. Ta có thể giả sử $u_i > 0$ vì ta có thể đổi dấu vector riêng. Từ $(8)$, ta suy ra:

$\mu_1 = \frac{\sum_{j \in N_i}u_j}{u_i} \leq \frac{\sum_{j \in N_i}u_i}{u_i} = d(i) \leq \Delta \qquad(9)$

Ở đây, $d(i)$ là bậc của đỉnh $i$.


Bằng cách xét điều kiện dấu bằng xảy ra trong vế phải của $(5)$ ta có thể chứng minh được (bài tập 1):

Lemma 2: Nếu $G$ liên thông và $\mu_1 = \Delta$ thì $G$ là đồ thị chính quy bậc $\Delta$, i.e, mọi đỉnh đều có bậc $\Delta$.

 

Sử dụng cách chứng minh trong Lemma 1, ta có thể chứng minh được (bài tập 2):

Lemma 3:

$d_{avg}(S) \leq \mu_1 \qquad(10)$

với mọi đồ thị con $S$ của $G$. Ở đây $d_{avg}(S)$ là bậc trung bình của đồ thị con $S$.

 
Sử dụng Lemma 3, ta có thể chứng minh vế phải của Theorem 1.

Chứng minh $\chi(G) \leq \lfloor \mu_1 \rfloor + 1$: Gọi $1,2,\ldots,n$ là các đánh số các đỉnh của $G$ sao cho, với mọi $i$, đỉnh $i$ có tối đa $k$ cạnh nối tới các đỉnh $\{1,2,\ldots, i-1\}$. Ta thấy, nếu cách đánh số như vậy tồn tại thì ta có thể tô màu đỉnh của $G$ sử dụng $k+1$ màu như sau: Tô màu bắt đầu từ đỉnh có chỉ số nhỏ nhất (đỉnh 1); khi tô đến đỉnh $i$, ta chỉ cần chọn màu tránh với các hàng xóm đã tô trước đó.

Để chứng minh $\chi(G) \leq \lfloor \mu_1 \rfloor + 1$, ta chỉ cần chứng minh cách đánh số như đoạn văn trước tồn tại với $k = \lfloor \mu_1 \rfloor$. Thật vậy, ta chọn đỉnh nhỏ nhất và đánh số nó là $n$. Do $d_{avg}(G) \leq \mu_1$, bậc của đỉnh này không quá $\mu_1$. Sau đó, ta tiếp tục đánh số đệ quy trên đồ thị con của $G$ sau khi đã đánh số đỉnh $n$.


Trị riêng $\mu_n$

Trong phần này chúng ta sẽ chứng minh cận dưới của sắc số. Trước hết, ta sẽ tìm hiểu quan hệ giữa $\mu_1$ và $\mu_n$. Nhắc lại, $\mu_n$ có thể là số âm.

Lemma 4: Giả sử $G$ là một đồ thị liên thông, ta có:

$\mu_1 \geq - \mu_n \qquad(11)$

Dấu bằng xảy ra khi và chỉ khi $G$ là đồ thị hai phía (bipartite).

 
Chứng minh: Gọi $\mathbf{u}$ là vector riêng đơn vị ứng với $\mu_n$. Gọi $U$ là tập các đỉnh $i$ có tọa độ $u_i \geq 0$, i.e, $U = \{i \in V | u_i \geq 0\}$. Gọi $\mathbf{v}$ là vector với $v_i = |u_i| \quad \forall i\in V$. Dễ thấy $\mathbf{v}$ cũng là vector đơn vị.

Theo Thương Rayleigh, ta có:

$\begin{array} {l} \mu_1 & \geq \mathbf{v}^TA\mathbf{v} \\ & = \sum_{(i,j \in E)} |u_i||u_j| \\ &= \sum_{\substack{(i,j)\in E\\i,j\in U\\}}u_iu_j + \sum_{\substack{(i',j')\in E\\i',j'\in V\setminus U\\}}u_{i'}u_{j'} - \sum_{\substack{(i,j')\in E\\i\in U\\ j' \in V\setminus U}} u_{i}u_{j'} - \sum_{\substack{(i',j)\in E\\i'\in U\\ j \in V\setminus U}} u_{i'}u_{j} \\ & \geq -\sum_{\substack{(i,j)\in E\\i,j\in U\\}}u_iu_j - \sum_{\substack{(i',j')\in E\\i',j'\in V\setminus U\\}}u_{i'}u_{j'} - \sum_{\substack{(i,j')\in E\\i\in U\\ j' \in V\setminus U}} u_{i}u_{j'} - \sum_{\substack{(i',j)\in E\\i'\in U\\ j \in V\setminus U}} u_{i'}u_{j} \\ &= - \sum_{(i,j \in E)} u_iu_j = - \mathbf{u}^TA\mathbf{u} = -\mu_n\end{array}$

Phần kiểm tra điều kiện dấu bằng, xem bài tập 3.


Giả sử $\mu_n$ âm (nếu $\mu_n$ dương thì bất đẳng thức trong Theorem 1 trở nên tầm thường), Lemma 4 cho ta biết $\frac{\mu_1}{-\mu_n} \geq 1$, do đó, Theorem 1 cho ta biết $\chi(G) \geq 2$. Điều kiện dấu bằng xảy ra trong Lemma 4 là $G$ là đồ thị hai phía. Lúc đó, $\chi(G) = 2$.

Để chứng minh Theorem 1, ta cần một số công cụ từ đại số với ma trận và vector riêng. Do đó, từ đoạn này trở về sau, mình sẽ không tập trung vào ma trận kề của đồ thị mà đi "lạc đề" một chút.

Gọi $A$ là một ma trận (không nhất thiết là ma trận kề của đồ thị) vuông kích thước $n\times n$ và $S$ là một tập con của $\{1,2,\ldots, n\}$. Kí hiệu $A(S)$ là ma trận vuông con của $A$ có các hàng, cột là các hàng, cột của $A$ mà chỉ số trong $S$. Kí hiệu $\lambda_{\max}(A),\lambda_{\min}(A)$ lần lượt là trị riêng lớn nhất và nhỏ nhất của ma trận $A$. Ta có:

Lemma 5:

$\lambda_{\min}(A) \leq \lambda_{\min}(A(S)) \leq \lambda_{\max}(A(S)) \leq \lambda_{\max}(A)\qquad(12)$

 
Chứng minh: Bất đẳng thức thứ 2 chính là định nghĩa của trị riêng. Ta sẽ chứng minh bất đẳng thứ thứ 3, bất đẳng thứ thứ nhất chứng minh tương tự (bài tập 4).

Không mất tính tổng quát, ta giả sử $S = \{1,2,\ldots, s\}$ ($s$ là kích thước của $S$). Gọi $\mathbf{u}$ là vector đơn vị tương ứng với $\lambda_{\max}(A(S))$ của ma trận $A(S)$. Gọi $\mathbf{v}$ là vector trong đó $v_i= u_i \quad \forall i \leq s$ và $v_i = 0$ nếu ngược lại. Dễ thấy $\mathbf{v}$ cũng là vector đơn vị. Dễ dàng kiểm tra được:

$\lambda_{\max}(A(S)) = \mathbf{u}^T A(S)\mathbf{u}=\mathbf{v}^T A\mathbf{v} $

Do đó, $\lambda_{\max}(A) \geq \mathbf{v}^T A\mathbf{v} = \lambda_{\max}(A(S))$.


Lemma 6: Gọi $A,B,C,D$ là các ma trận sao cho:

$A = \begin{bmatrix} B & C \\ C^T & D \end{bmatrix}$

Ta có:

$\lambda_{\min}(A) + \lambda_{\max}(A) \leq \lambda_{\max}(B) + \lambda_{\max}(D) \qquad (13)$

 
Chứng minh: Thương Rayleigh lại là công cụ chính cho chứng minh Lemma này và cách chứng minh tương tự như trong Lemma 5.

Gọi $\mathbf{v}$ là vector riêng lớn nhất ứng với trị riêng $\lambda_{\max}(A)$. Ta phân hoạch $\mathbf{v} = \left( \begin{array}{c} \mathbf{v}_1 \\ \mathbf{v}_2 \end{array} \right)$ thành hai thành phần giống như $A$. Giả sử cả 2 vector $\mathbf{v}_1,\mathbf{v}_2$ đều khác $\mathbf{0} $. Gọi:

$\mathbf{u} = \left( \begin{array}{c} -\frac{||\mathbf{v}_2||}{||\mathbf{v}_1||}\mathbf{v}_1 \\ \frac{||\mathbf{v}_1||}{||\mathbf{v}_2||}\mathbf{v}_2 \end{array} \right)$

Dễ dàng kiểm tra được $\mathbf{u}$ là một vector đơn vị. Do đó, theo Thương Rayleigh, ta có;

$\begin{array} {l}\lambda_{\min}(A) + \lambda_{\max}(A) & \leq \mathbf{u}^TA\mathbf{u} + \mathbf{v}^TA\mathbf{v} \\ & =(\frac{||\mathbf{v}_2||}{||\mathbf{v}_1||})^2\mathbf{v}_1^TB\mathbf{v}_1 - \mathbf{v}^T_1C\mathbf{v}_2 - \mathbf{v}_2^TC^T\mathbf{v}_1 + (\frac{||\mathbf{v}_1||}{||\mathbf{v}_2||})^2\mathbf{v}^T_2 D\mathbf{v}_2 \\ & + \mathbf{v}_1^TB\mathbf{v}_1 - \mathbf{v}^T_1C\mathbf{v}_2 - \mathbf{v}_2^TC^T\mathbf{v}_1 + \mathbf{v}^T_2 D\mathbf{v}_2 \\ & = (1 + (\frac{||\mathbf{v}_2||}{||\mathbf{v}_1||})^2)\mathbf{v}_1^TB\mathbf{v}_1 + (1 + (\frac{||\mathbf{v}_1||}{||\mathbf{v}_2||})^2)\mathbf{v}^T_2 D\mathbf{v}_2 \\ &\leq (1 + (\frac{||\mathbf{v}_2||}{||\mathbf{v}_1||})^2)\lambda_{\max}(B)\mathbf{v}_1^T\mathbf{v}_1 + (1 + (\frac{||\mathbf{v}_1||}{||\mathbf{v}_2||})^2)\lambda_{\max}(D)\mathbf{v}^T_2 \mathbf{v}_2\\ &= \lambda_{\max}(B) + \lambda_{\max}(D)\end{array}$

Ở bất đẳng thức thứ 5, ta sử dụng Thương Rayleigh cho $\lambda_{\max}(B)$ và $\lambda_{\max}(D)$.

Trường hợp $\mathbf{v}_1 = \mathbf{0}$ (hoặc $\mathbf{v}_2 = \mathbf{0}$), xem bài tập 5.


Lemma 7: Gọi $A$ là một ma trận đối xứng có phân hoạch:

$A = \begin{bmatrix} A_{1,1} & A_{1,2} & \cdots & A_{1,k} \\ A_{2,1} & A_{2,2} & \cdots & A_{2,k} \\ \vdots & \vdots & \ddots & \vdots \\ A_{k,1} & A_{k,2} & \cdots & A_{k,k} \end{bmatrix}$

Ta có:

$(k-1)\lambda_{\min}(A) + \lambda_{\max}(A) \leq \sum_{i=1}^k \lambda_{\max}(A_{i,i}) \qquad (14)$

 
Dựa trên Lemma 6, chứng minh Lemma 7 không còn là việc quá khó (xem bài tập 6).

Chứng minh Theorem 1 Giờ ta đã có đầy đủ công cụ để chứng minh cận dưới của Theorem 1. Giả sử ta có thể tô màu đồ thị $G$ bằng $k$ màu. Theo định nghĩa, hai đỉnh có cùng màu sẽ KHÔNG có cạnh nối. Do đó, ta có thể sắp xếp lại ma trận kề theo dạng trong Lemma 7 với $A_{i,i} = 0$. Hay nói cách khác, mỗi khối $A_{i,i}$ tương ứng với ma trận kề của các đỉnh được tô màu $i$, và do đó, ma trận này là ma trận 0.

Do $A_{i,i} = 0\quad \forall i$, theo $(14)$, ta có $(k-1)\lambda_{\min}(A) + \lambda_{\max}(A) \leq 0$. Từ đó suy ra $k \geq 1 - \frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}$ (chú ý $\lambda_{\min}(A) $ < $0$).


Tham khảo

[1] Daniel Speilman. Spectral Graph Theory Notes, Fall 2015, Lecture 03.
[2] A. J. Hoffman. On eigenvalues and colorings of graphs. In Graph Theory and its Applications, pages 79{92. Academic Press, New York, 1970.
[3] Herbert S. Wilf. The eigenvalues of a graph and its chromatic number. J. London Math. Soc., 42:330-332, 1967.

Bài tập

Bài 1: Chứng minh Lemma 2.
Bài 2: Chứng minh Lemma 3 sử dụng kĩ thuật trong chứng minh Lemma 1.
Bài 3: Chứng minh $\mu_1 = - \mu_n$ khi và chỉ khi $G$ là đồ thị hai phía.
Bài 4: Chứng minh bất đẳng thức đầu tiên của Lemma 5.
Bài 5: Chứng minh Lemma 6 trong trường hợp $\mathbf{v}_2 = \mathbf{0}$.
Bài 6 Chứng minh Lemma 7 sử dụng Lemma 6. Hints: dùng quy nạp và bất đẳng thức $\lambda_{\min}(A) \leq \lambda_{\min}(A_{i,i})$ (Lemma 5).

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

Bài 1: Vector riêng thứ $i$ có $v_i = -(n-1)$ và $v_j = 1 \quad \forall j \not= i$.

Bài 2: Sử dụng tính chất trong Bài tập 6 trong bài Lý thuyết đồ thị phổ I. $\mathrm{Tr}(A) = \sum_{i=1}^n \lambda_i$, sẽ suy ra $\lambda_n = n$. Ta có thể đoán trị riêng này tương ứng với đỉnh $1$ của $S_n$ và vector riêng ứng với $\lambda_n$ sẽ có giá trị $x$ tại đỉnh $1$ và $y$ tại các đỉnh còn lại. Ta sẽ suy ra phương trình:

$(n-1)x - (n-1)y = nx$

giải phương trình này và chọn bộ $x,y$ phù hợp để suy ra vector riêng tương ứng.

Bài 3:

$\sum_{i,j}z^2_{ij} = \sum_{i,j}x^2_iy^2_j = (\sum_i x_i^2)(\sum_j y_j^2) = 1$

Bài 4: $H_1$ chính là $S_2$, đồ thị mà chúng ta đã nghiên cứu kĩ. Hai trị riêng là $0$ và $2$.

Bài 5: Sử dụng quy nạp và Theorem 3 trong bài Lý thuyết đồ thị phổ III. Ta có thể tách $2i = 2(i-1) + 2 = 2i + 0$. Chú ý $H_{i} = H_{i-1}\times H_1$. Theo quy nạp, $H_i$ có trị riêng $2i-2$ với số bội $k-1 \choose i-1$ và trị riêng $2i$ với số bội $k-1 \choose i$. Do đó, $H_i$ có trị riêng $2i$ với số bội (theo Theorem 3):

${k-1 \choose i-1} + {k-1 \choose i} = {k \choose i}$

Bài 6: Bài này chỉ cần bạn đọc hiểu kĩ đề bài là làm được.

Facebook Comments

Tags: , ,

  1. Quỳnh’s avatar

    Cảm ơn bài viết của bạn rất nhiều. bạn đã viêt bài tiếp theo chưa vậy?

    Reply

    1. Hung Le’s avatar

      Mình chưa có thời gian nên hiện tại chỉ có vậy thôi. Mình vẫn có kế hoach update thêm materials.

      Hùng

      Reply

Reply

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