ผลต่างระหว่างรุ่นของ "Sgt/lecture2"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(ใช้ bmatrix (วงเล็บเหลี่ยม) แทน pmatrix (วงเล็บโค้ง) ในการเขียนแสดง matrix)
 
(ไม่แสดง 9 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 1: แถว 1:
 +
<noinclude>{{Sgt/เนื้อหา}}</noinclude>
 
{{หัวคำบรรยาย|Spectral graph theory}}
 
{{หัวคำบรรยาย|Spectral graph theory}}
  
แถว 40: แถว 41:
 
จะเห็นได้ว่า Rayleigh quotient มีค่ามากที่สุดเป็น eigenvalue ที่ใหญ่ที่สุด และ vector ''x'' ที่ทำให้มีค่าดังกล่าวได้แก่ eigenvalue ของ ''M'' (พิจารณาที่ <math>(*)</math> ){{จบบทพิสูจน์}}
 
จะเห็นได้ว่า Rayleigh quotient มีค่ามากที่สุดเป็น eigenvalue ที่ใหญ่ที่สุด และ vector ''x'' ที่ทำให้มีค่าดังกล่าวได้แก่ eigenvalue ของ ''M'' (พิจารณาที่ <math>(*)</math> ){{จบบทพิสูจน์}}
  
== คุณสมบัติของ eigenvalue กับกราฟ ==
+
== คุณสมบัติของ Eigenvalue กับกราฟ ==
  
ให้กราฟ ''G'' ขนาด ''n'' nodes และ <math>A_G</math> เป็น adjacency matrix ของ ''G'' ถ้าสำหรับ node ที่ ''i'' ใดๆ เราแทนดีกรีด้วย <math>deg(v_i)</math> เราจะนิยาม diagonal matrix <math>D_G</math> ดังนี้
+
ให้กราฟ <math>G</math> ขนาด <math>n</math> โหนดและ <math>A_G</math> เป็น adjacency matrix ของ <math>G</math> ถ้าสำหรับโหนดที่ <math>i</math> ใดๆ เขียนแทนดีกรีด้วย <math>\deg(v_i)</math> นิยาม diagonal matrix (<math>D_G</math>) ดังนี้
  
:<math>D_G =
+
:<math>
\begin{bmatrix}
+
D_G = \begin{bmatrix}
   deg(v_1) & 0 & \cdots & 0 \\
+
   \deg(v_1) &     0     & \cdots &     0     \\
  0 & deg(v_2) & \cdots & 0 \\
+
      0     & \deg(v_2) & \cdots &     0     \\
  \vdots  & \vdots  & \ddots & \vdots  \\
+
    \vdots  &   \vdots  & \ddots &   \vdots  \\
  0 & 0 & \cdots & deg(v_n)
+
      0     &     0     & \cdots & \deg(v_n)
\end{bmatrix}</math>
+
\end{bmatrix}
 +
</math>
  
และนิยาม Laplacian matrix ของ ''G'' ว่า
+
และนิยาม Laplacian matrix (<math>L_G</math>) ว่า
  
 
:<math>
 
:<math>
 +
\begin{align}
 
L_G = D_G - A_G
 
L_G = D_G - A_G
 +
\end{align}
 
</math>
 
</math>
  
 
ต่อไปนี้จะสนใจ eigenvalue จาก Laplacian matrix ของกราฟ
 
ต่อไปนี้จะสนใจ eigenvalue จาก Laplacian matrix ของกราฟ
  
=== eigenvalue ตัวแรกของกราฟใดๆ ===
+
=== Eigenvalue ตัวแรกของกราฟใดๆ ===
 +
 
 +
{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix (<math>L_G</math>) จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ"}}
 +
 
 +
{{เริ่มบทพิสูจน์}}
 +
สมมติให้ <math>G^{\star}</math> เป็นกราฟที่มีมีเส้นเชื่อมเพียงหนึ่งเส้น <math>(v_i,v_j)</math> เราจะได้
 +
 
 +
:<math>
 +
L_{G^{\star}} = \begin{bmatrix}
 +
        & \vdots &        & \vdots &        \\
 +
  \cdots &    1  & \cdots &  -1  & \cdots \\
 +
        & \vdots &        & \vdots &        \\
 +
  \cdots &  -1  & \cdots &    1  & \cdots \\
 +
        & \vdots &        & \vdots &
 +
\end{bmatrix}
 +
</math>
 +
 
 +
สำหรับ vector <math>x = [x_1,x_2,\cdots,x_n]^T</math> ใดๆ คำนวณค่า <math>R(L_{G^{\star}},x)</math> ได้ดังนี้
 +
 
 +
:<math>
 +
R(L_{G^{\star}},x) = \frac{(x_i-x_j)^2}{x^Tx}
 +
</math>
 +
 
 +
ต่อมา พิจรณากราฟ <math>G</math> ใดๆ ที่มีจำนวนเส้นเชื่อม <math>m</math> เส้น โดยเราสามารถเขียน <math>L_G</math> ได้ในรูป
 +
 
 +
:<math>
 +
L_G = L_{G_1} + L_{G_2} + \cdots + L_{G_m}
 +
</math>
 +
 
 +
โดยที่ <math>L_{G_k}</math> สำหรับ <math>1 \le k \le m</math> แทน Laplacian matrix ของกราฟ <math>G_k</math> ซึ่งเป็นกราฟย่อยจาก <math>G</math> ที่มีเส้นเชื่อมเส้นที่ <math>k</math> เพียงเส้นเดียว ดังนั้น
 +
 
 +
:<math>
 +
\begin{align}
 +
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^Tx}
 +
\end{align}
 +
</math>
 +
 
 +
ให้ <math>x_i = 1</math> สำหรับทุกค่า <math>i</math> จะได้ว่า
 +
 
 +
:<math>
 +
R(L_G,x) = \frac{\sum\nolimits_{E(G)}\left(1-1\right)^2}{x^Tx} = 0
 +
</math>
 +
 
 +
จากสมการ <math>(*)</math> ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ <math>\lambda_1 = 0</math> โดยมี <math>x</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
 +
 
 +
ดังนั้น สำหรับ Laplacian matrix <math>L_G</math> ของกราฟ G ใดๆ <math>\lambda_1 = 0</math>
 +
{{จบบทพิสูจน์}}
 +
 
 +
=== Eigenvalue ของกราฟต่อเนื่อง ===
  
ให้ ''G'' มีเส้นเชื่อมเพียงหนึ่งเส้น <math>(v_i,v_j)</math> เราจะได้
+
{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix <math>L_G</math> จะมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ก็ต่อเมื่อ G เป็นกราฟต่อเนื่อง"}}
  
:<math>L_G =
+
{{เริ่มบทพิสูจน์}}
\begin{bmatrix}
+
{{col-begin}}
  & \vdots &  & \vdots &    \\
+
{{col-break|width=50%}}
  \cdots & 1 & \cdots & -1 & \cdots    \\
+
<math>(\leftarrow)</math> สมมติให้ <math>G</math> เป็นกราฟต่อเนื่อง และมี eigenvalue ลำดับที่สองเท่ากับศูนย์ (<math>\lambda_2 = 0</math>)
  & \vdots &  & \vdots &  \\
 
  \cdots & -1 & \cdots & 1 & \cdots  \\
 
  & \vdots &  & \vdots &  \\
 
\end{bmatrix}</math>
 
  
สำหรับ vector <math>x = [x_1,x_2,\cdots,x_n]</math> ใดๆ เราจะคำนวณค่า <math>R(L_G,x)</math> ได้ว่า
+
ให้ <math>\phi_2 = [a_1,a_2,\cdots,a_n]^T</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
  
:<math>R(L_G,x) = \frac{(x_i-x_j)^2}{x^Tx}</math>
+
และทฤษฎีบทก่อนหน้า จะได้ว่ามี <math>\lambda_1 = 0</math> และ <math>\phi_1 = [x_1,x_2,\cdots,x_n]^T</math>
  
ดังนั้น ถ้าเราเขียน <math>L_G</math> ให้อยู่ในรูป
+
จาก Spectral Theory เนื่องจาก <math>\phi_2 \perp \phi_1</math> ดังนั้น
  
:<math>L_G = L_1 + L_2 + \cdots + L_m</math>
+
:<math>
 +
\begin{align}
 +
0 &= \phi_2 \phi_1^T \\
 +
  &= \sum\limits_{i=1}^n x_i a_i
 +
\end{align}
 +
</math>
  
เมื่อ ''m'' เป็นจำนวนเส้นเชื่อมของ ''G'' และแต่ละ
+
เนื่องจากกราฟต่อเนื่อง ให้ <math>\phi_1 = [1,1,\cdots,1]^T</math> ทำให้
<math>L_k</math> แทน Laplacian matrix ของกราฟ <math>G_k</math> ที่มีเส้นเชื่อมคือเส้นที่ ''k'' ของ ''G'' เพียงเส้นเดียว ดังนั้น
+
 
 +
:<math>
 +
0 = \sum\limits_{i=1}^n a_i
 +
</math>
 +
 
 +
จะเห็นว่า <math>a_i \ne 0</math> สำหรับทุก <math>i</math> และมี <math>a_i \ne a_j</math> สำหรับบาง <math>i \ne j</math> ส่งผลให้ <math>\sum\nolimits_{(i,j) \in E(G)}(a_i-a_j)^2 \ne 0</math>
 +
 
 +
ซึ่งหมายความว่า <math>\lambda_2 \ne 0</math> และขัดแย้งกับสมมติฐานตั้งต้นว่า <math>\lambda_2 = 0</math> ดังนั้นถ้ากราฟ G เป็นกราฟต่อเนื่อง แล้ว <math>\lambda_2 \ne 0</math>
 +
 
 +
{{col-break|width=50%}}
 +
<math>(\rightarrow)</math> สมมติให้ <math>G</math> เป็นกราฟไม่ต่อเนื่อง และมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ (<math>\lambda_2 \ne 0</math>)
 +
 
 +
ให้ <math>\phi_2 = [a_1,a_2,\cdots,a_n]^T</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
 +
 
 +
และทฤษฎีบทก่อนหน้า จะได้ว่ามี <math>\lambda_1 = 0</math> และ <math>\phi_1 = [x_1,x_2,\cdots,x_n]^T</math>
 +
 
 +
จาก Spectral Theory เนื่องจาก <math>\phi_2 \perp \phi_1</math> ดังนั้น
  
 
:<math>
 
:<math>
 
\begin{align}
 
\begin{align}
R(L_G,x) &= R(L_1,x) + R(L_2,x) + \cdots + R(L_m,x) \\
+
0 &= \phi_2 \phi_1^T \\
&= \frac{\sum\nolimits_{(i,j) \in E(G)}(x_i-x_j)^2}{x^Tx}
+
  &= \sum\limits_{i=1}^n x_i a_i
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
จากสมการ <math>(*)</math> ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient จะมีค่าน้อยที่สุด (เป็นศูนย์) เมื่อ ''x'' เป็น eigenvector ที่สอดคล้องกับ eigenvalue <math>\lambda_1 = 0</math>
+
เนื่องจากกราฟไม่ต่อเนื่อง ให้ <math>\phi_1 = [1,\cdots,1,0,\cdots,0]^T</math> ทำให้
 +
 
 +
:<math>
 +
0 = \sum\limits_{i=1}^k a_i
 +
</math>
 +
 
 +
เมื่อให้โหนดที่ <math>1</math> ถึง <math>k</math> เป็นส่วนเดียวกัน และตัดขาดจากโหนดที่ <math>k+1</math> ถึง <math>n</math>
  
ดังนั้น สำหรับ Laplacian matrix <math>L_G</math> ของกราฟ G ใดๆ, vector <math>\phi_1 = [1,1,\cdots,...,1]</math>
+
ให้ <math>\phi_2 = [0,\cdots,0,1,\cdots,1]</math> และได้ว่า
จะเป็น eigenvector ที่สอดคล้องกับ eigenvalue <math>\lambda_1 = 0</math> เสมอ
 
จาก Spectral Theory พิจารณา non-zero vector <math>\phi_2 = [a_1,a_2,\cdots,a_n]</math> ซึ่งคือ eigenvector ที่สอดคล้องกับ eigenvalue  <math>\lambda_2</math> ที่มีค่าน้อยที่สุดรองลงมา
 
  
เนื่องจาก <math>\phi_2 \perp \phi_1</math> ดังนั้น <math>\sum\limits_{i=1}^n a_i = 0</math>
+
:<math>
จะเห็นได้ว่า ถ้า G เป็น connected graph เราไม่สามารถหา <math>\phi_2</math> ที่สอดคล้องกับ <math>\lambda_2 = 0</math> ได้
+
L_G \phi_2 = \begin{bmatrix}
เพราะ ต้องมีบางคู่ ''i,j'' ที่ไม่เท่ากันและ <math>a_i \neq a_j</math> แต่เนื่องจากกราฟ connected, บน path จาก node ที่ i ไปยัง node ที่ j
+
              0                 \\
จะมีบาง edge ''(u,v)'' ที่ <math>a_u \neq a_v</math> และส่งผลให้ <math>\sum\nolimits_{(i,j) \in E(G)}(x_i-x_j)^2</math> ไม่เท่ากับศูนย์
+
          \vdots              \\
เพราะฉะนั้น
+
              0                 \\
 +
  \deg(k+1) + (-1)\cdot\deg(k+1) \\
 +
          \vdots              \\
 +
    \deg(n) + (-1)\cdot\deg(n)
 +
\end{bmatrix} = 0 \cdot\phi_2
 +
</math>
  
{{กล่องทฤษฎีบท|"สำหรับกราฟ ''G'' ใดๆ Laplacian matrix <math>L_G</math> จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ
+
ซึ่งหมายความว่า <math>\lambda_2 = 0</math> และขัดแย้งกับสมมติฐานตั้งต้นว่า <math>\lambda_2 \ne 0</math> ดังนั้นถ้ากราฟ G เป็นกราฟไม่ต่อเนื่อง แล้ว <math>\lambda_2 = 0</math>
และ eigenvalue ลำดับที่สองจะมีค่าเป็นศูนย์ เมื่อและต่อเมื่อ G ไม่เป็น connected graph"}}
+
{{col-end}}
 +
{{จบบทพิสูจน์}}
  
 +
=== Eigenvalue ของกราฟที่มี <math>n</math> ส่วน ===
  
=== eigenvalue ของกราฟบริบูรณ์ ===
+
ให้กราฟที่มีจำนวน <math>n</math> component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ <math>n</math> จะมีค่าเป็น 0
  
ให้กราฟริบูรณ์ (complete graph) จำนวน ''n'' โหนด (<math>K_n</math>) ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น ''n''
+
{{เริ่มบทพิสูจน์}}
 +
 
 +
ให้กราฟมี <math>n</math> ส่วน ให้ eigenvalue จำนวน <math>n</math> ตัวแรกมีค่าเป็น <math>0</math> และมี eigenvector ที่สอดคล้องกันคือ
 +
 
 +
:<math>
 +
\phi_i = \begin{cases}
 +
1 & \text{if node is in component } i \text{th} \\
 +
0 & \text{otherwise}
 +
\end{cases}
 +
</math>
 +
 
 +
จะเห็นว่า <math>0 \phi_i = L \phi_i</math>
 +
{{จบบทพิสูจน์}}
 +
 
 +
=== Eigenvalue ของกราฟบริบูรณ์ ===
 +
 
 +
ให้กราฟริบูรณ์ (complete graph) จำนวน <math>n</math> โหนด (<math>K_n</math>) ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น <math>n</math>
  
 
{{เริ่มบทพิสูจน์}}
 
{{เริ่มบทพิสูจน์}}
แถว 151: แถว 248:
 
\end{bmatrix} = n \phi_i = \lambda_i \phi_i
 
\end{bmatrix} = n \phi_i = \lambda_i \phi_i
 
</math>
 
</math>
{{จบบทพิสูจน์}}
 
  
 +
ดังนั้น eigenvalue ลำดับที่สองเป็นต้นไปของกราฟบริบูรณ์จำนวน <math>n</math> โหนดมีค่าเป็น <math>n</math>
  
=== eigenvalue ของกราฟที่มี ''n''-component ===
+
''หมายเหตุ eigenvector ที่นำมาประกอบการพิสูจน์ ไม่จำเป็นต้องตั้งฉากกัน เพียงแค่แสดงให้เห็นว่ามี eigenvector ที่สอดคล้องกับ eigenvalue ได้ก็พอ''
 
+
{{จบบทพิสูจน์}}
ให้กราฟที่มีจำนวน ''n'' component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ ''n'' จะมีค่าเป็น 0
 

รุ่นแก้ไขปัจจุบันเมื่อ 11:09, 10 กุมภาพันธ์ 2558

Spectral Graph Theory

  1. บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ)
  2. คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ)
  3. คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร)
  4. คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี)
  5. Cheeger Inequality (ศุภชวาล)
  6. การทดลอง Cheeger Inequality และ Effective Resistance (ธานี)
  7. Random Walks และ Psuedo Random Generator (ศุภชวาล)
  8. Psuedo Random Generator[2] (ภัทร)
  9. Coding Theory และ Expander code (ธานี)
  10. Expander graph from Linear coding (ภัทร)
  11. Chebyshev polynomial (ศุภชวาล)
  12. Preconditioning (ธานี)

แก้ไขกล่องนี้แก้ไขสารบัญ

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

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

Rayleigh quotient

นิยาม Rayleigh quotient สำหรับ vector x และ symmetric matrix M คือ โดยสังเกตว่าถ้า x เป็น eigenvector ของ M ที่สอดคล้องกับ eigenvalue จะได้ว่า เนื่องจาก

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

"ให้ เป็น symmetric matrix ถ้า เป็น non-zero vector ที่ทำให้ มีค่ามากที่สุด แล้ว จะเป็น eigenvector ของ ที่สอดคล้องกับ eigenvalue ที่มากที่สุด"


เราจะพิสูจน์โดยการใช้ Spectral theory (เนื้อหาครั้งที่ 1) ให้ M มี dimension ขนาด n (symmetric) ได้ว่า M มี eigenvalue และ eigenvector ที่สอดคล้องกับ เพื่อความสะดวก เราให้ว่า ||x|| = 1 และ |||| = 1 สำหรับทุก i และเราสามารถเขียน x ในรูป จากนั้นจึงคำนวณหาค่า Rayleigh quotient

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

Littlebox.png

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

ให้กราฟ ขนาด โหนดและ เป็น adjacency matrix ของ ถ้าสำหรับโหนดที่ ใดๆ เขียนแทนดีกรีด้วย นิยาม diagonal matrix () ดังนี้

และนิยาม Laplacian matrix () ว่า

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

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

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


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

สำหรับ vector ใดๆ คำนวณค่า ได้ดังนี้

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

โดยที่ สำหรับ แทน Laplacian matrix ของกราฟ ซึ่งเป็นกราฟย่อยจาก ที่มีเส้นเชื่อมเส้นที่ เพียงเส้นเดียว ดังนั้น

ให้ สำหรับทุกค่า จะได้ว่า

จากสมการ ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ โดยมี เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว

ดังนั้น สำหรับ Laplacian matrix ของกราฟ G ใดๆ

Littlebox.png

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

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


Littlebox.png

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

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



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

จะเห็นว่า

Littlebox.png

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

ให้กราฟริบูรณ์ (complete graph) จำนวน โหนด () ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น


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

เลือก ที่ และเลือก ที่สอดคล้องกันดังนี้

จะเห็นว่า

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

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

Littlebox.png