Sgt/lecture2 - ประวัติรุ่นแก้ไข

Neizod: /* Eigenvalue ของกราฟที่มี n ส่วน */

2015-02-10T11:09:32Z

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

Neizod: /* Eigenvalue ของกราฟที่มี n ส่วน */

2015-02-10T11:09:05Z

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

Neizod: /* Eigenvalue ของกราฟบริบูรณ์ */

2015-02-02T07:23:21Z

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

Neizod: /* Eigenvalue ของกราฟต่อเนื่อง */

2015-02-02T03:54:52Z

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

Neizod: /* Eigenvalue ของกราฟต่อเนื่อง */

2015-02-02T03:54:04Z

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

Neizod: /* Eigenvalue ของกราฟต่อเนื่อง */

2015-02-02T03:34:56Z

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

Neizod: /* Eigenvalue ตัวแรกของกราฟใดๆ */

2015-02-01T23:47:11Z

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

Neizod: /* คุณสมบัติของ eigenvalue กับกราฟ */

2015-02-01T23:18:02Z

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

Neizod: แยกหัวข้อ

2015-02-01T23:07:20Z

แยกหัวข้อ

Neizod เมื่อ 20:26, 1 กุมภาพันธ์ 2558

2015-02-01T20:26:25Z

@@ แถว 190: / แถว 190: @@
 ให้กราฟที่มีจำนวน <math>n</math> component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ <math>n</math> จะมีค่าเป็น 0
-{เริ่มบทพิสูจน์}
+{{เริ่มบทพิสูจน์}}
 ให้กราฟมี <math>n</math> ส่วน ให้ eigenvalue จำนวน <math>n</math> ตัวแรกมีค่าเป็น <math>0</math> และมี eigenvector ที่สอดคล้องกันคือ
@@ แถว 202: / แถว 202: @@
 จะเห็นว่า <math>0 \phi_i = L \phi_i</math>
-{จบบทพิสูจน์}
+{{จบบทพิสูจน์}}
 === Eigenvalue ของกราฟบริบูรณ์ ===

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 11:09, 10 กุมภาพันธ์ 2558
แถว 190:		แถว 190:
	ให้กราฟที่มีจำนวน <math>n</math> component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ <math>n</math> จะมีค่าเป็น 0		ให้กราฟที่มีจำนวน <math>n</math> component ค่า eigenvalue ของ Laplacian matrix ลำดับที่หนึ่งจนถึงลำดับที่ <math>n</math> จะมีค่าเป็น 0

		+	{เริ่มบทพิสูจน์}
		+
		+	ให้กราฟมี <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 ของกราฟบริบูรณ์ ===		=== Eigenvalue ของกราฟบริบูรณ์ ===

@@ แถว 235: / แถว 235: @@
 \end{bmatrix} = n \phi_i = \lambda_i \phi_i
 </math>
 {{จบบทพิสูจน์}}

@@ แถว 141: / แถว 141: @@
 </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>
+จะเห็นว่า <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>
 {{col-break|width=50%}}

@@ แถว 118: / แถว 118: @@
 {{เริ่มบทพิสูจน์}}
+{{col-begin}}
-<math>(\leftarrow)</math> สมมติให้ <math>G</math> เป็นกราฟต่อเนื่อง และมีค่า eigenvalue ลำดับที่สองเท่ากับศูนย์ (<math>\lambda_2 = 0</math>)
+{{col-break|width=50%}}
 ให้ <math>\phi_2 = [a_1,a_2,\cdots,a_n]^T</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
@@ แถว 140: / แถว 141: @@
 </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>
+จะเห็นว่า <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>
-<math>(\rightarrow)</math> สมมติให้ <math>G</math> เป็นกราฟไม่ต่อเนื่อง และมีค่า eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ (<math>\lambda_2 \ne 0</math>)
+{{col-break|width=50%}}
 ให้ <math>\phi_2 = [a_1,a_2,\cdots,a_n]^T</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
@@ แถว 180: / แถว 180: @@
 </math>
-ซึ่งหมายความว่า <math>\lambda_2 = 0</math> และขัดแย้งกับสมมติฐานต้นว่า <math>\lambda_2 \ne 0</math> ดังนั้นถ้ากราฟ G เป็นกราฟไม่ต่อเนื่อง แล้ว <math>\lambda_2 = 0</math>
+ซึ่งหมายความว่า <math>\lambda_2 = 0</math> และขัดแย้งกับสมมติฐานตั้งต้นว่า <math>\lambda_2 \ne 0</math> ดังนั้นถ้ากราฟ G เป็นกราฟไม่ต่อเนื่อง แล้ว <math>\lambda_2 = 0</math>
 {{จบบทพิสูจน์}}

@@ แถว 115: / แถว 115: @@
 === Eigenvalue ของกราฟต่อเนื่อง ===
-จาก Spectral Theory พิจารณา non-zero vector <math>\phi_2 = [a_1,a_2,\cdots,a_n]</math> ซึ่งคือ eigenvector ที่สอดคล้องกับ eigenvalue  <math>\lambda_2</math> ที่มีค่าน้อยที่สุดรองลงมา
+{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix <math>L_G</math> จะมี eigenvalue ลำดับที่สองไม่เท่ากับศูนย์ ก็ต่อเมื่อ G เป็นกราฟต่อเนื่อง"}}
-เนื่องจาก <math>\phi_2 \perp \phi_1</math> ดังนั้น <math>\sum\limits_{i=1}^n a_i = 0</math>
+{{เริ่มบทพิสูจน์}}
-{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix <math>L_G</math> จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ
+<math>(\leftarrow)</math> สมมติให้ <math>G</math> เป็นกราฟต่อเนื่อง และมีค่า eigenvalue ลำดับที่สองเท่ากับศูนย์ (<math>\lambda_2 = 0</math>)
 === Eigenvalue ของกราฟที่มี <math>n</math> ส่วน ===

@@ แถว 66: / แถว 66: @@
 === Eigenvalue ตัวแรกของกราฟใดๆ ===
-ให้ <math>G</math> มีเส้นเชื่อมเพียงหนึ่งเส้น <math>(v_i,v_j)</math> เราจะได้
+{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix (<math>L_G</math>) จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ"}}
-:<math>L_G =
+{{เริ่มบทพิสูจน์}}
-\begin{bmatrix}
+สมมติให้ <math>G^{\star}</math> เป็นกราฟที่มีมีเส้นเชื่อมเพียงหนึ่งเส้น <math>(v_i,v_j)</math> เราจะได้
-สำหรับ vector <math>x = [x_1,x_2,\cdots,x_n]</math> ใดๆ เราจะคำนวณค่า <math>R(L_G,x)</math> ได้ว่า
+:<math>
-:<math>R(L_G,x) = \frac{(x_i-x_j)^2}{x^Tx}</math>
+สำหรับ vector <math>x = [x_1,x_2,\cdots,x_n]^T</math> ใดๆ คำนวณค่า <math>R(L_{G^{\star}},x)</math> ได้ดังนี้
-ดังนั้น ถ้าเราเขียน <math>L_G</math> ให้อยู่ในรูป
+ต่อมา พิจรณากราฟ <math>G</math> ใดๆ ที่มีจำนวนเส้นเชื่อม <math>m</math> เส้น โดยเราสามารถเขียน <math>L_G</math> ได้ในรูป
-:<math>L_G = L_1 + L_2 + \cdots + L_m</math>
+:<math>
-เมื่อ <math>m</math> เป็นจำนวนเส้นเชื่อมของ <math>G</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_1,x) + R(L_2,x) + \cdots + R(L_m,x) \\
+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)}(x_i-x_j)^2}{x^Tx}
+         &= \frac{\sum\nolimits_{(i,j) \in E(G)}\left(x_i-x_j\right)^2}{x^Tx}
 \end{align}
 </math>
-จากสมการ <math>(*)</math> ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient จะมีค่าน้อยที่สุด (เป็นศูนย์) เมื่อ <math>x</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue <math>\lambda_1 = 0</math>
+ให้ <math>x_i = 1</math> สำหรับทุกค่า <math>i</math> จะได้ว่า
-ดังนั้น สำหรับ Laplacian matrix <math>L_G</math> ของกราฟ G ใดๆ, vector <math>\phi_1 = [1,1,\cdots,1]</math>
+จากสมการ <math>(*)</math> ในหัวข้อ Rayleigh quotient จะได้ว่า Rayleigh quotient มีค่าน้อยที่สุดเมื่อ <math>\lambda_1 = 0</math> โดยมี <math>x</math> เป็น eigenvector ที่สอดคล้องกับ eigenvalue ดังกล่าว
 === Eigenvalue ของกราฟต่อเนื่อง ===

@@ แถว 41: / แถว 41: @@
 จะเห็นได้ว่า 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     \\
-& deg(v_2) & \cdots & 0 \\
+    & \deg(v_2) & \cdots &     0     \\
-  \vdots  & \vdots  & \ddots & \vdots  \\
+    \vdots  &   \vdots  & \ddots &   \vdots  \\
-& 0 & \cdots & deg(v_n)
+    &     0     & \cdots & \deg(v_n)
-\end{bmatrix}</math>
+\end{bmatrix}
-และนิยาม Laplacian matrix ของ ''G'' ว่า
+และนิยาม Laplacian matrix (<math>L_G</math>) ว่า
 :<math>
 L_G = D_G - A_G
 </math>
 ต่อไปนี้จะสนใจ eigenvalue จาก Laplacian matrix ของกราฟ
-=== eigenvalue ตัวแรกของกราฟใดๆ ===
+=== Eigenvalue ตัวแรกของกราฟใดๆ ===
 ให้ <math>G</math> มีเส้นเชื่อมเพียงหนึ่งเส้น <math>(v_i,v_j)</math> เราจะได้
@@ แถว 82: / แถว 85: @@
 :<math>L_G = L_1 + L_2 + \cdots + L_m</math>
-เมื่อ ''m'' เป็นจำนวนเส้นเชื่อมของ ''G'' และแต่ละ
+เมื่อ <math>m</math> เป็นจำนวนเส้นเชื่อมของ <math>G</math> และแต่ละ
-<math>L_k</math> แทน Laplacian matrix ของกราฟ <math>G_k</math> ที่มีเส้นเชื่อมคือเส้นที่ ''k'' ของ ''G'' เพียงเส้นเดียว ดังนั้น
+<math>L_k</math> แทน Laplacian matrix ของกราฟ <math>G_k</math> ที่มีเส้นเชื่อมคือเส้นที่ <math>k</math> ของ <math>G</math> เพียงเส้นเดียว ดังนั้น
 :<math>
@@ แถว 98: / แถว 101: @@
-=== eigenvalue ของกราฟต่อเนื่อง ===
+=== Eigenvalue ของกราฟต่อเนื่อง ===
 จาก Spectral Theory พิจารณา non-zero vector <math>\phi_2 = [a_1,a_2,\cdots,a_n]</math> ซึ่งคือ eigenvector ที่สอดคล้องกับ eigenvalue  <math>\lambda_2</math> ที่มีค่าน้อยที่สุดรองลงมา
@@ แถว 104: / แถว 107: @@
 เนื่องจาก <math>\phi_2 \perp \phi_1</math> ดังนั้น <math>\sum\limits_{i=1}^n a_i = 0</math>
 จะเห็นได้ว่า ถ้า G เป็น connected graph เราไม่สามารถหา <math>\phi_2</math> ที่สอดคล้องกับ <math>\lambda_2 = 0</math> ได้
-เพราะ ต้องมีบางคู่ ''i,j'' ที่ไม่เท่ากันและ <math>a_i \neq a_j</math> แต่เนื่องจากกราฟ connected, บน path จาก node ที่ i ไปยัง node ที่ j
+เพราะ ต้องมีบางคู่ <math>i,j</math> ที่ไม่เท่ากันและ <math>a_i \neq a_j</math> แต่เนื่องจากกราฟ connected, บน path จาก node ที่ i ไปยัง node ที่ j
-จะมีบาง edge ''(u,v)'' ที่ <math>a_u \neq a_v</math> และส่งผลให้ <math>\sum\nolimits_{(i,j) \in E(G)}(x_i-x_j)^2</math> ไม่เท่ากับศูนย์
+จะมีบาง edge <math>(u,v)</math> ที่ <math>a_u \neq a_v</math> และส่งผลให้ <math>\sum\nolimits_{(i,j) \in E(G)}(x_i-x_j)^2</math> ไม่เท่ากับศูนย์
 เพราะฉะนั้น
-{{กล่องทฤษฎีบท|"สำหรับกราฟ ''G'' ใดๆ Laplacian matrix <math>L_G</math> จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ
+{{กล่องทฤษฎีบท|"สำหรับกราฟ <math>G</math> ใดๆ Laplacian matrix <math>L_G</math> จะมี eigenvalue (น้อยไปมาก) ลำดับที่หนึ่งเป็นศูนย์เสมอ
 และ eigenvalue ลำดับที่สองจะมีค่าเป็นศูนย์ เมื่อและต่อเมื่อ G ไม่เป็น connected graph"}}
-ให้กราฟริบูรณ์ (complete graph) จำนวน ''n'' โหนด (<math>K_n</math>) ค่า eigenvalue ของ Laplacian matrix ลำดับที่สองจนถึงลำดับสุดท้าย จะมีค่าเป็น ''n''
+=== Eigenvalue ของกราฟที่มี <math>n</math> ส่วน ===
 {{เริ่มบทพิสูจน์}}
@@ แถว 156: / แถว 165: @@
 </math>
 {{จบบทพิสูจน์}}

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 20:26, 1 กุมภาพันธ์ 2558
แถว 1:		แถว 1:
		+	<noinclude>{{Sgt/เนื้อหา}}</noinclude>
	{{หัวคำบรรยาย\|Spectral graph theory}}		{{หัวคำบรรยาย\|Spectral graph theory}}