[passer-by]

คุณ Rover หมายถึง Eulerian cycle กับ Eulerian path หรือเปล่าครับ

ถ้า ใช่ มันก็คือ กราฟที่สามารถลากให้ผ่านทุกเส้น โดยไม่ทับเส้นเดิมที่เคยลากผ่านไปแล้ว

คล้ายๆกับ เกมที่เขาให้วาดรูปโดยไม่ยกปากกา ทำนองนั้นแหละครับ

กราฟใดที่ดีกรีของทุกจุดเป็นเลขคู่ ก็จะเป็น Eulerian cycle กล่าวคือ เป็นกราฟออยเลอร์ ประเภทที่ ลากเสร็จแล้ว วกกลับมาที่จุดเริ่มต้น

แต่ถ้ากราฟใด มีดีกรีจุด 2 จุดเท่านั้นเป็นเลขคี่ และที่เหลือเป็นเลขคู่ ก็จะเป็น Eulerian path ซึ่งก็คือ กราฟ ออยเลอร์ที่ จุดเริ่มต้นและ จุดสิ้นสุดเป็นคนละจุด

และถ้าจะถามว่า มี Eulerian cycle ที่ ดีกรีบางจุดเป็นเลขคี่ บ้างมั้ย คำตอบคือ ไม่มีครับ
ซึ่งสรุปเป็นทฤษฎีบทว่า กราฟ G มี Eulerian cycle ก็ต่อเมื่อ ดีกรีทุกจุดเป็นเลขคู่
(ในกรณีของ Eulerian path ก็เช่นเดียวกัน)

เมื่อพูดถึง กราฟออยเลอร์ ก็มักจะมีอีกคำที่คล้ายคลึงกัน คือ กราฟแฮมิลโทเนียน (Hamiltonian graph) ซึ่งเป็นประเภทที่ ลากผ่านทุกจุด โดยไม่ทับจุดเดิมที่ลากผ่านไปแล้ว

ในวิชา graph theory เราศึกษา Eulerian cycle/path กันทะลุปรุโปร่ง หมดแล้วครับ เหลือแต่เจ้า Hamiltonian graph ซึ่งยังไม่มีทฤษฎีรองรับแบบ โป้งเดียวจอด เหมือน Eulerian cycle/ path ว่ากราฟที่กำหนดให้ เป็น hamiltonian graph หรือไม่ มีแต่เพียงทฤษฎีบทรองรับบางรูปแบบของกราฟเท่านั้น เช่น ถ้าตรงตาม เงื่อนไข นี้ นี้ นี้ ก็เป็น Hamiltonian graph แต่ถ้าไม่ตรงตามนี้ ก็ยังฟันธงไม่ได้ ว่า เป็น หรือไม่

ในทาง computer science ปัญหาการหาทางเดิน hamiltonian graph ถือเป็นปัญหาที่สำคัญ และจัดอยู่ในกลุ่ม NP ซึ่งพูดง่ายๆ ก็คือยังไม่มี algorithm ดีๆ ที่เมื่อเขียนเป็นโปรแกรม แล้วจะทำงานเสร็จในเวลาที่มนุษย์คอยได้ เช่น อาจจะต้องรอเป็นหลายหมื่นหลายแสนปี กว่า โปรแกรมจะคำนวณผลเสร็จ ในกรณีที่เจอกราฟที่มีจุดมากๆ

แต่ถ้า เมื่อใด คอมพิวเตอร์แบบ quantum computer สำเร็จ ปัญหาตระกูล NP ก็จะเป็นเรื่องเล็กๆ อย่างแน่นอนครับ

รู้สึกผมจะอธิบายเพลินไปหน่อย พอดีกว่าเนอะ