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

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 2 รุ่นระหว่างกลางโดยผู้ใช้ 1 คน)
แถว 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 ==
แถว 73: แถว 77:
 
</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>

รุ่นแก้ไขปัจจุบันเมื่อ 07:14, 26 พฤษภาคม 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 นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง


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

Intuitive of Rayleight Quotient term numerator

จาก

สังเกตว่า

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

Terminology

สำหรับกราฟ และเซ็ตของปม เราจะนิยาม เป็นขนาดของคัท และ อัตราการขยายตัวของปริมาตรผ่านทางเส้นเชื่อม

Isoperimetric Inequality

Isoperimetric ratio of vertices set

Isoperimetric ratio of graph

ณ จุดนี้ เราจะพิจารณาขอบล่างของ เทียบกับ โดยจะพิจารณาขอบบน ซึ่งก็คือ Cheeger Inequality ใน lecture ครั้งถัดไป

"For every "


จาก Rayleight Quotient เรารู้ว่า

แสดงว่า ถ้าเราหยิบ vector ใด ๆ ซึ่งไม่ใช่ 0 ที่ตั้งฉากกับ vector 1 มา เราสามารถนำมาบอกขอบเขตของ ได้เสมอ

พิจารณา characteristic vector โดย

สังเกตว่า แต่ ไม่ตั้งฉากกับ vector

พิจารณา สังเกตว่า

จากนั้นเราจะพิจารณาผลของ

โดย

และ

ดังนั้น

Littlebox.png

The Adjacency Matrix

กำหนดให้ A เป็น adjacency matrix ของกราฟ โดยถ้าเรานำ vector x ไปคูณ ผลลัพธ์ที่ได้คือ

พิจารณา regular graph G ที่มี degree d เราสามารถหาความสัมพันธ์ระหว่าง laplacian matrix กับ adjacency matrix ได้โดย

ถ้า และ เป็น eigen value และ eigen vector ที่สอดคล้องกันใน L แล้ว

ได้ว่า และ เป็น eigen value และ eigen vector ที่สอดคล้องกันใน A

สังเกตว่าถ้ากราฟเป็น regular แล้ว eigen vector ของ L กับ A จะเป็นชุดเดียวกัน แต่มี eigen value ต่างกัน

กำหนดให้ เป็น eigen value ของ A

เมื่อกราฟ G เป็น regular ได้ว่า