หน้านี้แสดงรายการเนื้อหาวิชาทฤษฎีกราฟเบื้องต้น สำหรับค่ายอบรมเข้มคอมพิวเตอร์โอลิมปิก ตุลาคม 2552

• กราฟ, นิยาม, ตัวอย่าง
• การเก็บกราฟ (representation)
  • Implementation ในภาษา C++
• แนวคิดพื้นฐาน: เส้นทาง, วงรอบ, การไปถึงกัน (reachability), (หน้าตัด)
• การค้นหาในกราฟ
  • การค้นหาเชิงกว้าง (BFS)
    • คุณสมบัติ
      • layer
  • การค้นหาเชิงลึก (DFS)
    • Implementation
      • เขียนแบบ recursion
      • เขียนโดยจัดการ stack เอง
    • คุณสมบัติ
      • คุณสมบัติวงเล็บ
      • ประเภทของเส้นเชื่อม: tree edges; forward, backward, cross edges
• การประยุกต์ใช้งาน
  • connectivity
  • BFS
    • testing bipartiteness
    • 2-coloring
  • DFS
    • topological sorting
  • อื่น ๆ
    • coloring