ทฤษฎีกราฟ

กราฟไม่ระบุทิศทาง (Undirected Graph)

พิจารณาปัญหาต่อไปนี้ เจ้าหน้าที่คนหนึ่งอาศัยอยู่ที่เมือง A ต้องการส ารวจเส้นทางไปยังเมืองต่าง ๆ ทุกเส้นทาง โดยมีเงื่อนไขดังนี้

1) ผู้เดินทางต้องผ่านเมืองต่าง ๆ โดยใช้เส้นทางที่ไม่ซ้ ากันและต้องผ่านทุกเส้นทาง

2) ผู้เดินทางต้องเริ่มที่เมือง A และจบที่เมือง A

วิถี (Paths)

วิถี คือ ลำดับของจุดยอด โดยจุดยอดเริ่มต้นในวิถีต้องมีเส้นเชื่อมไปยังจุดถัดไปในลำดับจนถึงจุด ยอดสุดท้าย เช่น วิถีจาก A ไป J คือ {A, C, F, I, J} และยังมีคำตอบอื่นได้อีก เช่น {A, B, D, G, J} 
อย่างไรก็ตามการหาวิถีที่สั้นที่สุดถูกนำไปใช้ประโยชน์อย่างกว้างขวาง ซึ่งจะนำเสนอต่อไปในเรื่องการ หาวิถีสั้นสุดโดยขั้นตอนวิธีของไดก์สตรา

วัฏจักร (Cycles)

วัฏจักร คือ วิถีที่มีจุดยอดเริ่มต้นและจุดยอดสุดท้ายในล าดับเป็นจุดเดียวกัน เช่น {A, B, D, C, A}
วัฏจักรอย่างง่าย คือ วิถีที่ไม่มีจุดยอดซ้ำกัน ยกเว้นจุดยอดเริ่มต้นและจุดยอดสุดท้าย เช่น {A, B, D, G, H, E, D, C, A} ไม่ใช่วัฏจักรอย่างง่าย เนื่องจากการซ้ำกันของจุด D นอกจากนี้วัฏจักรอย่างง่ายยังต้องมีอย่างน้อย 2 จุดยอดที่แตกต่างกัน เช่น {A, B, A} เป็นวัฏจักรอย่างง่าย แต่ {A, A} ไม่เป็น

วัฏจักรออยเลอร์ (The Euler Cycle)

วัฏจักรออยเลอร์ระบุว่า กราฟ G จะมีวัฏจักรออยเลอร์ที่เริ่มต้นจากจุดยอด v1 กลับมายัง v1 โดยใช้ เส้นเชื่อมที่ไม่ซ้ำกัน ถ้าจำนวนเส้นเชื่อมที่เข้ามาเชื่อม (degree) ในแต่ละจุดยอด เป็นเลขคู่

สรุป คำศัพท์

  • เส้นเชื่อมขนาน (parallel edges) คือ เส้นเชื่อมที่มีจุดต้นและจุดปลายเป็นจุดเดียวกัน
  • วงวน (loop) คือ เส้นเชื่อมที่มีจุดปลายทั้งสองอยู่ที่จุดเดียวกัน
  • จุดยอดเอกเทศ (isolated vertex) คือจุดที่ไม่มีเส้นเชื่อมต่อไปยังจุดใด ๆ ในกราฟ
  • กราฟอย่างง่าย (simple graph) คือ กราฟที่ไม่มีวงวนและไม่มีเส้นเชื่อมขนาน
  • กราฟเชื่อมโยง (connected graph) คือ กราฟที่มีวิถีเชื่อมระหว่างจุดยอด 2 จุดใด ๆ ในกราฟ