วิถี (ทฤษฎีกราฟ)

ในคณิตศาสตร์ วิถี (path) ในกราฟคือลำดับของจุดยอด ซึ่งจุดยอดแต่ละจุดจะมีเส้นเชื่อมเชื่อมจุดยอดในลำดับที่อยู่ติดกัน. จุดยอดแรกเรียกว่า จุดยอดเริ่ม และจุดยอดสุดท้าย เรียกว่า จุดยอดปลาย จุดยอดอื่นๆในวิถี เรียกว่า จุดยอดภายใน

วัฏจักรระบุทิศทาง ที่ไม่เป็นวัฏจักรเชิงเดียว เพราะใช้จุดยอดสีน้ำเงินซ้ำกัน 2 ครั้ง

วัฏจักร (cycle) คือ วิถีที่จุดยอดเริ่มเป็นจุดเดียวกับจุดยอดปลาย

วิถีที่ไม่มีจุดยอดซ้ำกัน เรียกว่า วิถีเชิงเดียว (simple path) เช่นเดียวกันนั้น วัฏจักรที่ไม่มีจุดยอดซ้ำกัน (ยกเว้นจุดยอดเริ่มต้นกับจุดยอดปลาย) เรียกว่า วัฏจักรเชิงเดียว (simple cycle)

วิถี 2 วิถีจะเป็นอิสระ (independent) ต่อกัน ถ้ามันไม่มีจุดยอดภายในร่วมกัน

กราฟที่มี จุดยอด 6 จุด และเส้นเชื่อม 7 เส้น

ความยาว (length) ของวิถี คือจำนวนของเส้นเชื่อมที่ใช้ในวิถี ซึ่งอาจนับเส้นเชื่อมหลายครั้งได้ เช่น จากกราฟในรูป (1, 2, 5, 1, 2, 3) คือวิถีที่มีความยาว 5 และ (5, 2, 1) คือวิถีเชิงเดียวที่มีความยาว 2

กราฟถ่วงน้ำหนัก จะกำหนดค่า น้ำหนัก (weight) ให้เส้นเชื่อมแต่ละเส้นภายในกราฟ น้ำหนักของวิถีในกราฟถ่วงน้ำหนัก คือ ผลบวกของน้ำหนักของเส้นเชื่อมที่แวะผ่าน บางครั้งใช้คำว่า ค่าใช้จ่าย (cost) หรือ ความยาว แทนคำว่าน้ำหนัก

ดูเพิ่ม

• อภิธานศัพท์ทฤษฎีกราฟ
• ปัญหาวิถีสั้นสุด