ผลต่างระหว่างรุ่นของ "Sgt/lecture4"
Tanee (คุย | มีส่วนร่วม) |
Tanee (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 13 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 14: | แถว 14: | ||
\end{align} | \end{align} | ||
</math>}} | </math>}} | ||
| − | |||
| − | |||
| − | |||
| − | |||
==Graphic Inequality== | ==Graphic Inequality== | ||
เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง<br/> | เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง<br/> | ||
ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย <math>A \succeq 0</math> โดยนิยามดังนี้ | ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย <math>A \succeq 0</math> โดยนิยามดังนี้ | ||
| − | |||
| − | และสำหรับ matrix A,B ใดๆ เราเขียน <math>A \succeq B</math> แทน <math>A-B \succeq 0</math> โดยความสัมพันธ์นี้มีคุณสมบัติถ่ายทอด คือ <math>A \succeq B \and B \succeq C \Rightarrow A \succeq C</math> | + | :<math>A \succeq 0 \Leftrightarrow \forall\psi\in\mathbb{R}^n\ ;\ \psi^TA\psi \geq 0</math> |
| + | |||
| + | และสำหรับ matrix A,B ใดๆ เราเขียน <math>A \succeq B</math> แทน <math>A-B \succeq 0</math> โดยความสัมพันธ์นี้มีคุณสมบัติถ่ายทอด คือ | ||
| + | |||
| + | :<math>A \succeq B \and B \succeq C \Rightarrow A \succeq C</math> | ||
ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราเขียน <math>G \succeq H</math> แทน <math>L_G \succeq L_H</math> | ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราเขียน <math>G \succeq H</math> แทน <math>L_G \succeq L_H</math> | ||
| แถว 32: | แถว 31: | ||
จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้) | จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้) | ||
| − | {{กล่องทฤษฎีบท|ถ้า G,H เป็นกราฟที่มีคุณสมบัติว่า <math>G \succeq c \cdot H</math> จะได้ว่า <math>\forall k\\ | + | {{กล่องทฤษฎีบท|ถ้า G,H เป็นกราฟที่มีคุณสมบัติว่า <math>G \succeq c \cdot H</math> จะได้ว่า <math>\forall k\ ;\ |
\lambda_k(G) \geq c\cdot\lambda_k(H)</math> เมื่อ <math>\lambda_k(G)</math> หมายถึง eigen value ตัวที่ k ของกราฟ G}} | \lambda_k(G) \geq c\cdot\lambda_k(H)</math> เมื่อ <math>\lambda_k(G)</math> หมายถึง eigen value ตัวที่ k ของกราฟ G}} | ||
| แถว 39: | แถว 38: | ||
{{กล่องทฤษฎีบท|<math>(n-1)P_n \succeq G_n</math>}} | {{กล่องทฤษฎีบท|<math>(n-1)P_n \succeq G_n</math>}} | ||
| + | {{เริ่มบทพิสูจน์}} | ||
| + | พิจารณา vector x ขนาด n ใดๆ เราต้องการจะแสดงว่า | ||
| + | :<math> | ||
| + | \begin{align} | ||
| + | (n-1)x^TL_{P_n}x &\geq x^TL_{G_n}x \\ | ||
| + | (n-1)\sum\limits_{i=1}^{n-1}(x(i+1) - x(i))^2 &\geq (x(1)-x(n))^2 \\ | ||
| + | \end{align} | ||
| + | </math> | ||
| + | ให้ <math>\delta(i) = x(i+1)-x(i)</math> และนิยาม vector ขนาด n-1 เพิ่มดังนี้ <math>a(i) = 1</math> และ <math>b(i) = \delta(i)</math> | ||
| + | |||
| + | จาก[http://en.wikipedia.org/wiki/Cauchy%E2%80%93Schwarz_inequality Cauchy–Schwarz inequality] ได้ว่า | ||
| + | :<math> | ||
| + | \begin{align} | ||
| + | a^Ta \cdot b^Tb &\geq |a^Tb|^2 \\ | ||
| + | (n-1) \cdot \sum\limits_{i=1}^{n-1}\delta(i)^2 &\geq |\sum\limits_{i=1}^{n-1}\delta(i)|^2 \\ | ||
| + | (n-1)\sum\limits_{i=1}^{n-1}(x(i+1) - x(i))^2 &\geq |x(1)-x(n)|^2 \\ | ||
| + | &\geq (x(1)-x(n))^2 | ||
| + | \end{align} | ||
| + | </math> | ||
| + | ตามต้องการ | ||
| + | {{จบบทพิสูจน์}} | ||
| + | |||
| + | และเราจะแสดงให้เห็นว่า <math>\lambda_2(P_n) = \Theta(\frac{1}{n^2})</math> โดยประกอบด้วยสองขั้นตอน | ||
| + | |||
| + | 1.<math>\lambda_2(P_n) = O(\frac{1}{n^2})</math> | ||
| + | {{เริ่มบทพิสูจน์}} | ||
| + | สร้างเวคเตอร์ x โดยให้ <math>x(i) = (n+1) - 2i</math> จะเห็นว่า x ตั้งฉากกับ <math>\bar{1}</math> | ||
| + | |||
| + | คำนวณ <math>\frac{\sum\limits_{i=1}^{n}(x(i+1)-x(i))^2}{\sum\limits_{i=1}^{n}(x(i)^2}</math> | ||
| + | |||
| + | จาก Courant–Fischer Theorem จะเห็นว่า <math>\lambda_2 = O(\frac{1}{n^2})</math> | ||
| + | |||
| + | {{จบบทพิสูจน์}} | ||
| + | 2.<math>\lambda_2(P_n) = \Omega(\frac{1}{n^2})</math> | ||
| + | {{เริ่มบทพิสูจน์}} | ||
| + | หาค่าคงที่ c ที่ | ||
| + | |||
| + | <math>c \cdot P_n \succeq K_n </math> และเรารู้ว่า <math>K_n = \sum\limits_{i,j} G_{i,j}</math> | ||
| + | |||
| + | จึงได้ว่า | ||
| + | :<math> | ||
| + | \begin{align} | ||
| + | \sum\limits_{i>j}(i-j)P_n &\succeq K_n \\ | ||
| + | \frac{n(n+1)(n-1)}{6}P_n &\succeq K_n \\ | ||
| + | \therefore \Omega(\frac{1}{n^2}) &\leq \lambda_2(P_2) \\ | ||
| + | \end{align} | ||
| + | </math> | ||
| + | |||
| + | <math>\lambda_2(P_n) = \Omega(\frac{1}{n^2})</math> | ||
| + | {{จบบทพิสูจน์}} | ||
| + | |||
| + | {{กล่องทฤษฎีบท|<math>\forall \epsilon > 0</math> จะมี ค่า d > 0 ที่ถ้า n มีขนาดมากพอ จะมี d-regular graph <math>G_n</math> ที่ <math>(1+\epsilon)G_n \succeq K_n \succeq \frac{G_n}{(1+\epsilon)}</math>}} | ||
| + | |||
| + | และสำหรับ Complete binary tree ที่มีความลึก d แทนด้วย <math>T_d</math> เราจะได้ว่า | ||
| − | + | :<math>\Omega(\frac{1}{n\cdot log(n)} \leq \lambda_2(T_d) \leq \frac{2}{n-1})</math> | |
| + | โดยการใช้วิธีเดียวกับการพิสูจน์ด้านบน โดยสร้างเวคเตอร์ x ที่ x(root) = 0 และลูกฝั่งซ้ายทั้งหมดเป็น 1 ฝั่งขวาทั้งหมดเป็น -1 | ||
รุ่นแก้ไขปัจจุบันเมื่อ 10:27, 2 เมษายน 2558
บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
ในสัปดาห์นี้ เราได้พูดถึง Courant–Fischer Theorem
Courant–Fischer Theorem
ให้ A เป็น symmetric matrix ขนาด n ที่มี eigen value (สังเกตว่าเรียงสลับด้านกับ ในเลคเชอร์อื่นๆ)
เราจะได้ว่า
Graphic Inequality
เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง
ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย โดยนิยามดังนี้
และสำหรับ matrix A,B ใดๆ เราเขียน แทน โดยความสัมพันธ์นี้มีคุณสมบัติถ่ายทอด คือ
ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราเขียน แทน สังเกตว่า ถ้า H เป็น subgraph ของ G จะได้ว่า
และสำหรับจำนวนจริง c ใดๆเราเขียนแทน หมายถึง
จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้)
ถ้า G,H เป็นกราฟที่มีคุณสมบัติว่า จะได้ว่า เมื่อ หมายถึง eigen value ตัวที่ k ของกราฟ G
Path Inequality
ให้กราฟขนาด n โหนด แทนกราฟที่มีเส้นเชื่อมเดียว (1,n) และกราฟที่มีเส้นเชื่อม n-1 เส้น ตามลำดับ
พิจารณา vector x ขนาด n ใดๆ เราต้องการจะแสดงว่า
ให้ และนิยาม vector ขนาด n-1 เพิ่มดังนี้ และ
จากCauchy–Schwarz inequality ได้ว่า
ตามต้องการ
และเราจะแสดงให้เห็นว่า โดยประกอบด้วยสองขั้นตอน
1.
สร้างเวคเตอร์ x โดยให้ จะเห็นว่า x ตั้งฉากกับ
คำนวณ
จาก Courant–Fischer Theorem จะเห็นว่า
2.
หาค่าคงที่ c ที่
และเรารู้ว่า
จึงได้ว่า
จะมี ค่า d > 0 ที่ถ้า n มีขนาดมากพอ จะมี d-regular graph ที่
และสำหรับ Complete binary tree ที่มีความลึก d แทนด้วย เราจะได้ว่า
โดยการใช้วิธีเดียวกับการพิสูจน์ด้านบน โดยสร้างเวคเตอร์ x ที่ x(root) = 0 และลูกฝั่งซ้ายทั้งหมดเป็น 1 ฝั่งขวาทั้งหมดเป็น -1
