บทนิยาม ให้ u และ v เป็นจุดยอดของกราฟแนวเดิน
u - v (u - v walk) คือ ลำดับจำกัดของจุดยอดและเส้นเชื่อมสลับกัน
u = u0, e1, u1, e2,
u2, …, un-1, en, un = v
โดยเริ่มต้นที่จุดยอด u และสิ้นสุดที่จุดยอด v และแต่ละเส้นเชื่อม ei จะเกิดกับจุดยอด
ui-1 และ ui เมื่อ i ∈ {1, 2, …, n}
ตัวอย่าง สมมติว่า แผนผังของเมืองหนึ่งแทนด้วยกราฟดังรูป
โดยให้จุดยอดแทนอำเภอ และเส้นเชื่อมแทนถนนที่เชื่อมระหว่างอำเภอสองอำเภอ
ในการเดินทางจากอำเภอ
A ไปยังอำเภอ D มีเส้นทางการเดินทางหลายเส้นทางเส้นทางต่างๆ
จะแทนดัวยลำดับของจุดยอดและเส้นเชื่อม ดังนี้ เส้นทาง A,
e1, E, e5, D
บทนิยาม
รอยเดิน (trail) คือ แนวเดินในกราฟที่เส้นเชื่อมทั้งหมดแตกต่างกัน
วิถี(Path) คือ แนวเดินในกราฟที่จุดยอดทั้งหมดแตกต่างกัน
วงจร(Circuit) คือ แนวเดินที่เส้นเชื่อมทั้งหมดแตกต่างกัน โดยมีจุดเริ่มต้นและจุดสุดท้ายเป็นจุดยอดเดียวกัน
วัฏจักร(Cycle) คือวงจรที่ไม่มีจุดยอดซ้ำกัน ยกเว้นจุดเริ่มต้นและจุดสุดท้าย
ไม่มีความคิดเห็น:
แสดงความคิดเห็น