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

Tanee เมื่อ 07:14, 26 พฤษภาคม 2558

2015-05-26T07:14:44Z

Pattara.s เมื่อ 10:13, 17 เมษายน 2558

2015-04-17T10:13:04Z

Pattara.s เมื่อ 10:12, 17 เมษายน 2558

2015-04-17T10:12:54Z

Pattara.s เมื่อ 09:30, 17 เมษายน 2558

2015-04-17T09:30:25Z

Pattara.s: /* Theorems */

2015-04-17T09:18:21Z

Theorems

Pattara.s เมื่อ 09:17, 17 เมษายน 2558

2015-04-17T09:17:48Z

Pattara.s: หน้าที่ถูกสร้างด้วย 'เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ e...'

2015-02-13T15:40:03Z

หน้าที่ถูกสร้างด้วย 'เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ e...'

หน้าใหม่

เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ eigen value ลำดับที่ 2 กับกราฟ และบทพิสูจน์
== Intuitive of Rayleight Quotient term numerator ==
จาก

<math>R(M, x) = \frac{x^TMx}{x^Tx}</math>

สังเกตว่า

<math>x^TLx = \sum\limits_{(u,v)} (x(u) - x(v))^2</math>

ถ้าเรามองว่า <math>x(u)</math> คือการเปลี่ยนมิติ ของจุดจากกราฟมายังเส้นตรงแล้ว ราคาที่เพิ่มขึ้นจาก เส้นเชื่อมแต่ละเส้น จะเท่ากับระยะห่างของจุดปลายของเส้นเชื่อมนั้นบนเส้นตรงดังกล่าว

== Terminology ==
สำหรับกราฟ <math>G=(V,E)</math> และเซ็ตของปม <math>S \subseteq V</math>
เราจะนิยาม <math>\partial(S) = \{ (u,v) \in E, u \in S, v \in V-S \}</math>
เป็นขนาดของคัท และ อัตราการขยายตัวของปริมาตรผ่านทางเส้นเชื่อม

== Isoperimetric Inequality ==
Isoperimetric ratio of vertices set <math> \theta (S) = \frac{|\partial (S)|}{|S|} </math>

Isoperimetric ratio of graph <math> \theta (G) = min_{S,|S|<=n/2} \theta(S) </math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 07:14, 26 พฤษภาคม 2558
แถว 1:		แถว 1:
		+	<noinclude>{{Sgt/เนื้อหา}}</noinclude>
		+	{{หัวคำบรรยาย\|Spectral graph theory}}
		+
		+
	เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ eigen value ลำดับที่ 2 กับกราฟ และบทพิสูจน์		เนื้อหาในสัปดาห์นี้ จะเป็นความเกี่ยงเนื่องของ eigen value ลำดับที่ 2 กับกราฟ และบทพิสูจน์
	== Intuitive of Rayleight Quotient term numerator ==		== Intuitive of Rayleight Quotient term numerator ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:13, 17 เมษายน 2558
แถว 99:		แถว 99:
	กำหนดให้ <math> \mu_1 \geq \mu_2 \geq ... \geq \mu_n </math> เป็น eigen value ของ A		กำหนดให้ <math> \mu_1 \geq \mu_2 \geq ... \geq \mu_n </math> เป็น eigen value ของ A

−	เมื่อกราฟ G เป็น regular ได้ว่า <math> \mu_1 = d <math>	+	เมื่อกราฟ G เป็น regular ได้ว่า <math> \mu_1 = d </math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 10:12, 17 เมษายน 2558
แถว 73:		แถว 73:
	</math>		</math>
	{{จบบทพิสูจน์}}		{{จบบทพิสูจน์}}
		+
		+	== The Adjacency Matrix ==
		+
		+	กำหนดให้ A เป็น adjacency matrix ของกราฟ <math>G = (V,E)</math> โดยถ้าเรานำ vector x ไปคูณ ผลลัพธ์ที่ได้คือ
		+
		+	<math> (Ax)(u) = \sum\limits_{(u,v) \in E} w(u,v)x(v) </math>
		+
		+	พิจารณา regular graph G ที่มี degree d เราสามารถหาความสัมพันธ์ระหว่าง laplacian matrix กับ adjacency matrix ได้โดย
		+
		+	<math> L = D - A = Id - A </math>
		+
		+	ถ้า <math>\lambda</math> และ <math>\varphi</math> เป็น eigen value และ eigen vector ที่สอดคล้องกันใน L แล้ว
		+
		+	<math>
		+	\begin{align}
		+	L\varphi &= (Id - A)\varphi = \lambda\varphi \\
		+	A\varphi &= (Id- L)\varphi = (d-\lambda)\varphi \\
		+	\end{align}
		+	</math>
		+
		+	ได้ว่า <math>\mu = (d-\lambda)</math> และ <math>\varphi</math> เป็น eigen value และ eigen vector ที่สอดคล้องกันใน A
		+
		+	สังเกตว่าถ้ากราฟเป็น regular แล้ว eigen vector ของ L กับ A จะเป็นชุดเดียวกัน แต่มี eigen value ต่างกัน
		+
		+	กำหนดให้ <math> \mu_1 \geq \mu_2 \geq ... \geq \mu_n </math> เป็น eigen value ของ A
		+
		+	เมื่อกราฟ G เป็น regular ได้ว่า <math> \mu_1 = d <math>

@@ แถว 21: / แถว 21: @@
 Isoperimetric ratio of graph <math> \theta (G) = min_{S,|S|\leq n/2} \theta(S) </math>
-== Theorems ==
+ณ จุดนี้ เราจะพิจารณาขอบล่างของ <math> \theta (G) </math> เทียบกับ <math> \lambda_{2} </math> โดยจะพิจารณาขอบบน ซึ่งก็คือ Cheeger Inequality ใน lecture ครั้งถัดไป
 {{กล่องทฤษฎีบท|"For every <math>S \subset V, \theta (S) \geq {\lambda}_{2}(1-s), where s = \frac{|S|}{|V|}  </math>"}}
 {{เริ่มบทพิสูจน์}}

@@ แถว 34: / แถว 34: @@
 <math>
 \begin{align}
-x(u) = 1,  u \in S \\
+x(u) = 1&,  u \in S \\
-x(u) = 0,  otherwise
+x(u) = 0&,  otherwise
 \end{align}
 </math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 09:17, 17 เมษายน 2558
แถว 19:		แถว 19:
	Isoperimetric ratio of vertices set <math> \theta (S) = \frac{\|\partial (S)\|}{\|S\|} </math>		Isoperimetric ratio of vertices set <math> \theta (S) = \frac{\|\partial (S)\|}{\|S\|} </math>

−	Isoperimetric ratio of graph <math> \theta (G) = min_{S,\|S\|<=n/2} \theta(S) </math>	+	Isoperimetric ratio of graph <math> \theta (G) = min_{S,\|S\|\leq n/2} \theta(S) </math>
		+
		+	== Theorems ==
		+	{{กล่องทฤษฎีบท\|"For every <math>S \subset V, \theta (S) \geq {\lambda}_{2}(1-s), where s = \frac{\|S\|}{\|V\|} </math>"}}
		+	{{เริ่มบทพิสูจน์}}
		+	จาก Rayleight Quotient เรารู้ว่า
		+	<math>
		+	{\lambda}_{2} = min_{x \neq 0, x\perp {\bold{1}}} \frac{x^TLx}{x^Tx}
		+	</math>
		+
		+	แสดงว่า ถ้าเราหยิบ vector ใด ๆ ซึ่งไม่ใช่ 0 ที่ตั้งฉากกับ vector 1 มา เราสามารถนำมาบอกขอบเขตของ <math>\lambda_{2}</math> ได้เสมอ
		+
		+	พิจารณา characteristic vector <math>x</math> โดย
		+	<math>
		+	\begin{align}
		+	x(u) = 1, u \in S \\
		+	x(u) = 0, otherwise
		+	\end{align}
		+	</math>
		+
		+	สังเกตว่า <math> \frac{x^TLx}{x^Tx} = \theta (S) </math> แต่ <math>x</math> ไม่ตั้งฉากกับ vector <math>{\bold{1}}</math>
		+
		+	พิจารณา <math> x' = x - \frac{\|S\|}{\|V\|} {\bold{1}} = x - s{\bold{1}} </math>
		+	สังเกตว่า <math> x' \perp {\bold{1}}, x' \neq 0</math>
		+
		+	จากนั้นเราจะพิจารณาผลของ <math> \frac{{x'}^TLx'}{{x'}^Tx'} </math>
		+
		+	โดย <math> {x'}^TLx' = \|\partial{S}\|</math>
		+
		+	และ
		+
		+	<math>
		+	\begin{align}
		+	{x'}^Tx' & = \sum\limits_{u} (x'(u))^2 \\
		+	& = \sum\limits_{u} (x(u)-s)^2 \\
		+	& = \sum\limits_{u} x(u)^2 - 2x(u)s + s^2 \\
		+	& = \|S\| - 2s\|S\| + \|V\|s^2 \\
		+	& = \|S\| - 2\frac{ \|S\|^2}{\|V\|} + \frac{\|S\|^2}{\|V\|} \\
		+	& = \|S\| - \frac{\|S\|^2}{\|V\|} \\
		+	& = \|S\|(1-s)
		+	\end{align}
		+	</math>
		+
		+	ดังนั้น
		+
		+	<math>
		+	\begin{align}
		+	\lambda_{2} & \leq \frac{{x'}^TLx'}{{x'}^Tx'} \\
		+	\lambda_{2} (1-s) & \leq \frac{{x'}^TLx'}{\|S\|} \\
		+	\lambda_{2} (1-s) & \leq \theta{S}
		+	\end{align}
		+	</math>
		+	{{จบบทพิสูจน์}}