Trail ในกราฟ
Trail คือเส้นทางที่เป็นลำดับของเส้นขอบ (v1,v2), (v2,v3), ..., (vk-1,vk) ที่โหนดทั้งหมดอาจไม่แตกต่างกัน (อาจซ้ำ) แต่เส้นขอบทั้งหมดต้องแตกต่างกัน (ไม่ซ้ำ)
ตัวอย่าง Trail: {(B,A), (A,C), (C,D), (D,A), (A,F)} นี่เป็น Trail แต่ไม่ใช่ Simple Path เพราะโหนด A ถูกเยี่ยมชม 2 ครั้ง ถ้าโหนดแรกและสุดท้ายเหมือนกัน จะเป็น Closed Trail
Eulerian Trail
Eulerian Trail ในกราฟ G(V,E) คือ Trail ที่รวมเส้นขอบทุกเส้นขอบได้ทุกเส้นขอบพอดี 1 ครั้ง ถ้า G มี Closed Eulerian Trail กราฟนั้นเรียกว่า Eulerian Graph กล่าวคือ เริ่มจากโหนดหนึ่ง เดินผ่านทุกเส้นขอบ 1 ครั้ง กลับมายังโหนดเริ่มต้นได้ Euler พิสูจน์ว่า: กราฟเป็น Eulerian Graph ก็ต่อเมื่อ องศา (Degree) ของทุกโหนดเป็นเลขคู่
Hamiltonian Cycle
Cycle ใดที่ผ่านทุกโหนดของกราฟ G พอดี 1 ครั้ง เรียกว่า Hamiltonian Cycle มีทฤษฎีหลายอย่างให้เงื่อนไขพอเพียงสำหรับกราฟ Hamiltonian แต่ปัญหาการตัดสินใจว่ากราฟสุ่มเป็น Hamiltonian หรือไม่ เป็นปัญหา NP-Complete
