ผลต่างระหว่างรุ่นของ "Sgt/lecture4"
Tanee (คุย | มีส่วนร่วม) (หน้าที่ถูกสร้างด้วย '<noinclude>{{Sgt/เนื้อหา}}</noinclude> {{หัวคำบรรยาย|Spectral graph theory}}') |
Tanee (คุย | มีส่วนร่วม) |
||
แถว 1: | แถว 1: | ||
<noinclude>{{Sgt/เนื้อหา}}</noinclude> | <noinclude>{{Sgt/เนื้อหา}}</noinclude> | ||
{{หัวคำบรรยาย|Spectral graph theory}} | {{หัวคำบรรยาย|Spectral graph theory}} | ||
+ | |||
+ | ในสัปดาห์นี้ เราได้พูดถึง [http://en.wikipedia.org/wiki/Min-max_theorem Courant–Fischer Theorem] | ||
+ | |||
+ | ==Courant–Fischer Theorem== | ||
+ | ให้ A เป็น symmetric matrix ขนาด n ที่มี eigen value <math>\mu_1 \geq \mu_2 \geq \ldots \geq \mu_n</math> (สังเกตว่าเรียงสลับด้านกับ <math>\lambda</math> ในเลคเชอร์อื่นๆ) | ||
+ | |||
+ | เราจะได้ว่า | ||
+ | {{กล่องทฤษฎีบท|:<math> | ||
+ | \begin{align} | ||
+ | \mu_k &= \max\limits_{S \subseteq \mathbb{R}^n \ ; \ dim(S) = k} &&\min_{x \in S \ ; \ x \neq \bar{0}} \frac{x^TAx}{x^Tx}\\ | ||
+ | &= \min\limits_{T \subseteq \mathbb{R}^n \ ; \ dim(T) = n-k+1} &&\max_{x \in S \ ; \ x \neq \bar{0}} \frac{x^TAx}{x^Tx} | ||
+ | \end{align} | ||
+ | </math>}} | ||
+ | |||
+ | {{เริ่มบทพิสูจน์}} | ||
+ | To be proved... | ||
+ | {{จบบทพิสูจน์}} | ||
+ | |||
+ | ==Graphic Inequality== | ||
+ | เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง<br/> | ||
+ | ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย <math>A \succeq 0</math> โดยนิยามดังนี้ | ||
+ | {{กล่องทฤษฎีบท|<math>A \succeq 0</math> เมื่อและต่อเมื่อ <math>\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 ; B \succeq C</math> จะได้ว่า <math>A \succeq C</math> | ||
+ | |||
+ | ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราแทนว่า <math>G \succeq H</math> เมื่อและต่อเมื่อ <math>L_G \succeq L_H</math> | ||
+ | และสังเกตว่า ถ้า H เป็น subgraph ของ G จะได้ว่า <math>G \succeq H</math> | ||
+ | |||
+ | |||
+ | TO BE CONTINUED |
รุ่นแก้ไขเมื่อ 07:57, 24 กุมภาพันธ์ 2558
บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง
ในสัปดาห์นี้ เราได้พูดถึง Courant–Fischer Theorem
Courant–Fischer Theorem
ให้ A เป็น symmetric matrix ขนาด n ที่มี eigen value (สังเกตว่าเรียงสลับด้านกับ ในเลคเชอร์อื่นๆ)
เราจะได้ว่า
To be proved...
Graphic Inequality
เป็นการเปรียบเทียบกราฟโดยให้ sense ของการ "มากกว่า" "น้อยกว่า" เหมือนการเปรียบเทียบจำนวนจริง
ให้ A เป็น matrix ใดๆ เราเขียนแทนว่า A เป็น positive semi-definite ด้วย โดยนิยามดังนี้
เมื่อและต่อเมื่อ
และสำหรับ matrix A,B ใดๆ เราเขียนแทนว่า เมื่อและต่อเมื่อ
ความสัมพันธ์นี้มีคุณสมบัติถ่ายทอด คือถ้า จะได้ว่า
ทำนองเดียวกัน สำหรับกราฟ G,H ใดๆ เราแทนว่า เมื่อและต่อเมื่อ และสังเกตว่า ถ้า H เป็น subgraph ของ G จะได้ว่า
TO BE CONTINUED