ทฤษฎีกราฟ
- เล็มมาการจับมือ
- Σ deg(v) = 2|E|
- กราฟบริบูรณ์
- |E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
- กราฟปรกติ
- |E| = n·k/2
- ต้นไม้และป่า
- |E| = n − 1, |E| = n − c
- ใบของต้นไม้
- L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
- ออยเลอร์
- วงจร: ดีกรีเป็นคู่ทุกจุดยอด; ทางเดิน: มีดีกรีคี่พอดี 2 จุดยอด
- วงจรแฮมิลตันใน Kn
- (n − 1)!/2
- การปรับค่าของไดก์สตรา
- d(v) = min(d(v), d(u) + w(u, v))
- วอล์กความยาว L
- (Mᴸ)ij
วิธีการ
- เขียนดีกรีของทุกจุดยอด ผลบวกของดีกรีเท่ากับสองเท่าของจำนวนเส้นเชื่อม
- สำหรับโจทย์ออยเลอร์ ให้ตรวจว่ากราฟเชื่อมโยงกัน และนับจุดยอดที่มีดีกรีคี่
- สำหรับต้นไม้ ให้ใช้ว่ามี n − 1 เส้นเชื่อม และเล็มมาการจับมือ
- สำหรับไดก์สตรา ให้เก็บตารางระยะทางชั่วคราว และยืนยันจุดยอดที่ยังไม่ยืนยันซึ่งมีค่าน้อยที่สุดในแต่ละรอบ
- สำหรับต้นไม้ทอดข้ามค่าน้อยที่สุด ให้เรียงเส้นเชื่อมตามน้ำหนักและข้ามทุกเส้นที่ทำให้เกิดวัฏจักร (ครัสคัล) หรือขยายต้นไม้ต้นเดียวจากจุดยอดเริ่มต้น (พริม)