Sgt/lecture2

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

สำหรับเนื้อหาในสัปดาห์นี้ เราเรียนรู้เกี่ยวกับ Rayleigh quotient และคุณสมบัติของ eigenvector, eigenvalue ลำดับที่ 2

Rayleigh quotient

นิยาม Rayleigh quotient สำหรับ vector x และ symmetric matrix M คือ $R(M,x)={\frac {x^{T}Mx}{x^{T}x}}$ โดยสังเกตว่าถ้า x เป็น eigenvector ของ M ที่สอดคล้องกับ eigenvalue จะได้ว่า เนื่องจาก

และเราจะพิสูจน์ทฤษฎีบทว่า

"ให้ เป็น symmetric matrix ถ้า $x$ เป็น non-zero vector ที่ทำให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 753601391
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:34 GMT


Sensitive client information

IP address: 158.108.32.49

$R(M,x)$ มีค่ามากที่สุด แล้ว จะเป็น eigenvector ของ $M$ ที่สอดคล้องกับ eigenvalue ที่มากที่สุด"

---

เราจะพิสูจน์โดยการใช้ Spectral theory (เนื้อหาครั้งที่ 1) ให้ M มี dimension ขนาด n (symmetric) ได้ว่า M มี eigenvalue และ eigenvector

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 680687451
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:52 GMT


Sensitive client information

IP address: 158.108.32.49

$\phi _{i}$ ที่สอดคล้องกับ $\lambda _{i}$ เพื่อความสะดวก เราให้ว่า ||x|| = 1 และ ||

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 728934847
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:54 GMT


Sensitive client information

IP address: 158.108.32.49

$\phi _{i}$|| = 1 สำหรับทุก i และเราสามารถเขียน x ในรูป $x=\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i}$ จากนั้นจึงคำนวณหาค่า Rayleigh quotient

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 742463698
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:35 GMT


Sensitive client information

IP address: 158.108.32.49

${\begin{aligned}R(M,x)&={\frac {x^{T}Mx}{x^{T}x}}\\&=(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i})^{T}M(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i})\\&=(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\phi _{i})^{T}(\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)\lambda _{i}\phi _{i})\\&=\sum \limits _{i=1}^{n}\sum \limits _{j=1}^{n}(\phi _{i}^{T}\cdot x)(\phi _{j}^{T}\cdot x)(\phi _{i}^{T}\phi _{j})\lambda _{j}\qquad &&;\ i\neq j\Rightarrow (\phi _{i}^{T}\phi _{j})=0\\&=\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)^{2}(\phi _{i}^{T}\phi _{i})\lambda _{i}\qquad &&;\ (\phi _{i}^{T}\phi _{i})=1\\&=\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)^{2}\lambda _{i}&&(*)\\&\leq \lambda _{n}\sum \limits _{i=1}^{n}(\phi _{i}^{T}\cdot x)^{2}\\&\leq \lambda _{n}\end{aligned}}$

จะเห็นได้ว่า Rayleigh quotient มีค่ามากที่สุดเป็น eigenvalue ที่ใหญ่ที่สุด และ vector x ที่ทำให้มีค่าดังกล่าวได้แก่ eigenvalue ของ M (พิจารณาที่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 757204395
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:35 GMT


Sensitive client information

IP address: 158.108.32.49

$(*)$ )

---

คุณสมบัติของ Eigenvalue กับกราฟ

ให้กราฟ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 733457427
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:36 GMT


Sensitive client information

IP address: 158.108.32.49

$G$ ขนาด โหนดและ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 727623328
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:57 GMT


Sensitive client information

IP address: 158.108.32.49

$A_{G}$ เป็น adjacency matrix ของ $G$ ถ้าสำหรับโหนดที่ ใดๆ เขียนแทนดีกรีด้วย นิยาม diagonal matrix (

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 740595242
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:37 GMT


Sensitive client information

IP address: 158.108.32.49

$D_{G}$) ดังนี้

$D_{G}={\begin{bmatrix}\deg(v_{1})&0&\cdots &0\\0&\deg(v_{2})&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\deg(v_{n})\end{bmatrix}}$

และนิยาม Laplacian matrix (

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 747703122
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:59 GMT


Sensitive client information

IP address: 158.108.32.49

$L_{G}$) ว่า

ต่อไปนี้จะสนใจ eigenvalue จาก Laplacian matrix ของกราฟ

Eigenvalue ตัวแรกของกราฟใดๆ

"สำหรับกราฟ $G$ ใดๆ Laplacian matrix () จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ"

---

สมมติให้ เป็นกราฟที่มีมีเส้นเชื่อมเพียงหนึ่งเส้น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 749538417
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:38 GMT


Sensitive client information

IP address: 158.108.32.49

$(v_{i},v_{j})$ เราจะได้

สำหรับ vector $x=[x_{1},x_{2},\cdots ,x_{n}]^{T}$ ใดๆ คำนวณค่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 753305615
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:05 GMT


Sensitive client information

IP address: 158.108.32.49

$R(L_{G^{\star }},x)$ ได้ดังนี้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 687336777
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:38 GMT


Sensitive client information

IP address: 158.108.32.49

$R(L_{G^{\star }},x)={\frac {(x_{i}-x_{j})^{2}}{x^{T}x}}$

ต่อมา พิจรณากราฟ $G$ ใดๆ ที่มีจำนวนเส้นเชื่อม $m$ เส้น โดยเราสามารถเขียน

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 744493793
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:08 GMT


Sensitive client information

IP address: 158.108.32.49

$L_{G}$ ได้ในรูป

โดยที่

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 740432536
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:38 GMT


Sensitive client information

IP address: 158.108.32.49

$L_{G_{k}}$ สำหรับ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 727623378
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:10 GMT


Sensitive client information

IP address: 158.108.32.49

$1\leq k\leq m$ แทน Laplacian matrix ของกราฟ $G_{k}$ ซึ่งเป็นกราฟย่อยจาก ที่มีเส้นเชื่อมเส้นที่ $k$ เพียงเส้นเดียว ดังนั้น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 740203400
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:39 GMT


Sensitive client information

IP address: 158.108.32.49

${\begin{aligned}R(L_{G},x)&=R(L_{G_{1}},x)+R(L_{G_{2}},x)+\cdots +R(L_{G_{m}},x)\\&={\frac {\sum \nolimits _{(i,j)\in E(G)}\left(x_{i}-x_{j}\right)^{2}}{x^{T}x}}\end{aligned}}$

ให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 757825621
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:39 GMT


Sensitive client information

IP address: 158.108.32.49

$x_{i}=1$ สำหรับทุกค่า $i$ จะได้ว่า

$R(L_{G},x)={\frac {\sum \nolimits _{E(G)}\left(1-1\right)^{2}}{x^{T}x}}=0$

จากสมการ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 745248402
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:13 GMT


Sensitive client information

IP address: 158.108.32.49

$(*)$ ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 755108671
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:40 GMT


Sensitive client information

IP address: 158.108.32.49

$\lambda _{1}=0$ โดยมี $x$ เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

ดังนั้น สำหรับ Laplacian matrix

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 756418139
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:40 GMT


Sensitive client information

IP address: 158.108.32.49

$L_{G}$ ของกราฟ G ใดๆ

---

Eigenvalue ของกราฟต่อเนื่อง

"สำหรับกราฟ $G$ ใดๆ Laplacian matrix จะมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ก็ต่อเมื่อ G เป็นกราฟต่อเนื่อง"

---

$(\leftarrow )$ สมมติให้ $G$ เป็นกราฟต่อเนื่อง และมี eigenvalue ลำดับที่สองเท่ากับศูนย์ (

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 698148458
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:42 GMT


Sensitive client information

IP address: 158.108.32.49

$\lambda _{2}=0$)

ให้ เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

และทฤษฎีบทก่อนหน้า จะได้ว่ามี

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 742398918
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:42 GMT


Sensitive client information

IP address: 158.108.32.49

$\lambda _{1}=0$ และ

จาก Spectral Theory เนื่องจาก $\phi _{2}\perp \phi _{1}$ ดังนั้น

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 729425491
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:43 GMT


Sensitive client information

IP address: 158.108.32.49

${\begin{aligned}0&=\phi _{2}\phi _{1}^{T}\\&=\sum \limits _{i=1}^{n}x_{i}a_{i}\end{aligned}}$

เนื่องจากกราฟต่อเนื่อง ให้ ทำให้

$0=\sum \limits _{i=1}^{n}a_{i}$

จะเห็นว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 724217982
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:43 GMT


Sensitive client information

IP address: 158.108.32.49

$a_{i}\neq 0$ สำหรับทุก $i$ และมี สำหรับบาง $i\neq j$ ส่งผลให้ $\sum \nolimits _{(i,j)\in E(G)}(a_{i}-a_{j})^{2}\neq 0$

ซึ่งหมายความว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 719239696
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:44 GMT


Sensitive client information

IP address: 158.108.32.49

$\lambda _{2}\neq 0$ และขัดแย้งกับสมมติฐานตั้งต้นว่า ดังนั้นถ้ากราฟ G เป็นกราฟต่อเนื่อง แล้ว $\lambda _{2}\neq 0$

สมมติให้ เป็นกราฟไม่ต่อเนื่อง และมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ()

ให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 737256097
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:45 GMT


Sensitive client information

IP address: 158.108.32.49

$\phi _{2}=[a_{1},a_{2},\cdots ,a_{n}]^{T}$ เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

และทฤษฎีบทก่อนหน้า จะได้ว่ามี

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 721861370
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:25 GMT


Sensitive client information

IP address: 158.108.32.49

$\lambda _{1}=0$ และ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 750520577
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:45 GMT


Sensitive client information

IP address: 158.108.32.49

$\phi _{1}=[x_{1},x_{2},\cdots ,x_{n}]^{T}$

จาก Spectral Theory เนื่องจาก ดังนั้น

เนื่องจากกราฟไม่ต่อเนื่อง ให้

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 750684156
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:28 GMT


Sensitive client information

IP address: 158.108.32.49

$\phi _{1}=[1,\cdots ,1,0,\cdots ,0]^{T}$ ทำให้

$0=\sum \limits _{i=1}^{k}a_{i}$

เมื่อให้โหนดที่ $1$ ถึง เป็นส่วนเดียวกัน และตัดขาดจากโหนดที่ ถึง

ให้ และได้ว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 682258776
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:46 GMT


Sensitive client information

IP address: 158.108.32.49

$L_{G}\phi _{2}={\begin{bmatrix}0\\\vdots \\0\\\deg(k+1)+(-1)\cdot \deg(k+1)\\\vdots \\\deg(n)+(-1)\cdot \deg(n)\end{bmatrix}}=0\cdot \phi _{2}$

ซึ่งหมายความว่า $\lambda _{2}=0$ และขัดแย้งกับสมมติฐานตั้งต้นว่า ดังนั้นถ้ากราฟ G เป็นกราฟไม่ต่อเนื่อง แล้ว $\lambda _{2}=0$

---

Eigenvalue ของกราฟที่มี ส่วน

ให้กราฟที่มีจำนวน $n$ component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ จะมีค่าเป็น 0

---

ให้กราฟมี $n$ ส่วน ให้ eigenvalue จำนวน $n$ ตัวแรกมีค่าเป็น และมี eigenvector ที่สอดคล้องกันคือ

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 753273259
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:47 GMT


Sensitive client information

IP address: 158.108.32.49

$\phi _{i}={\begin{cases}1&{\text{if node is in component }}i{\text{th}}\\0&{\text{otherwise}}\end{cases}}$

จะเห็นว่า

---

Eigenvalue ของกราฟบริบูรณ์

ให้กราฟริบูรณ์ (complete graph) จำนวน $n$ โหนด (

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 686157919
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:37 GMT


Sensitive client information

IP address: 158.108.32.49

$K_{n}$) ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น $n$

---

พิสูจน์โดยให้

เลือก

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 685927299
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:45:39 GMT


Sensitive client information

IP address: 158.108.32.49

$\lambda _{i}=n$ ที่ และเลือก ที่สอดคล้องกันดังนี้

จะเห็นว่า

Error

Too many requests (f061ab2)

If you report this error to the Wikimedia System Administrators, please include the details below.

Request served via cp5021 cp5021, Varnish XID 677213305
Upstream caches: cp5021 int
Error: 429, Too many requests (f061ab2) at Sun, 19 Apr 2026 08:44:48 GMT


Sensitive client information

IP address: 158.108.32.49

$L_{K_{n}}\phi _{i}={\begin{bmatrix}(n-1)(-1)+(-1)(1)\\(-1)(-1)+(-1)(1)\\\vdots \\(-1)(-1)+(-1)(1)\\(-1)(-1)+(n-1)(1)\\(-1)(-1)+(-1)(1)\\\vdots \\(-1)(-1)+(-1)(1)\end{bmatrix}}={\begin{bmatrix}-n\\0\\\vdots \\0\\n\\0\\\vdots \\0\end{bmatrix}}=n\phi _{i}=\lambda _{i}\phi _{i}$

ดังนั้น eigenvalue ลำดับที่สองเป็นต้นไปของกราฟบริบูรณ์จำนวน โหนดมีค่าเป็น $n$

หมายเหตุ eigenvector ที่นำมาประกอบการพิสูจน์ ไม่จำเป็นต้องตั้งฉากกัน เพียงแค่แสดงให้เห็นว่ามี eigenvector ที่สอดคล้องกับ eigenvalue ได้ก็พอ

---