ผลต่างระหว่างรุ่นของ "Sgt/lecture4"
Tanee (คุย | มีส่วนร่วม) |
Tanee (คุย | มีส่วนร่วม) |
||
แถว 32: | แถว 32: | ||
จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้) | จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้) | ||
− | {{กล่องทฤษฎีบท|ถ้า 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}} | ||
รุ่นแก้ไขเมื่อ 04:10, 25 กุมภาพันธ์ 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 จะได้ว่า
และสำหรับจำนวนจริง c ใดๆเราเขียนแทน หมายถึง
จากนิยามข้างต้น เราจะได้คุณสมบัติว่า (ในเนื้อหาครั้งนี้ไม่มีการพิสูจน์ทฤษฎีบทนี้)
ถ้า G,H เป็นกราฟที่มีคุณสมบัติว่า จะได้ว่า เมื่อ หมายถึง eigen value ตัวที่ k ของกราฟ G
Path Inequality
ให้กราฟขนาด n โหนด แทนกราฟที่มีเส้นเชื่อมเดียว (1,n) และกราฟที่มีเส้นเชื่อม n-1 เส้น ตามลำดับ
TO BE CONTINUED