Paths and circuits

Eulerian

Path

เป็น path ที่ท่องไปในเส้นเชื่อมทุกเส้นเพียงหนึ่งครั้งเท่านั้น

Circuit

เป็น Eulerian path ที่เริ่มและจบที่โหนดเดียวกัน

Existence

เงื่อนไขที่จะมี Eulerian path สำหรับ

• กราฟไม่มีทิศทาง

  • ดีกรีของทุกโหนดเป็นจำนวนคู่ หรือ

  • ดีกรีของสองโหนดเป็นจำนวนคี่

• กราฟมีทิศทาง
  • ในแต่ละโหนด ดีกรีเข้าจะต้องเท่ากับดีกรีออก หรือ
  • มีโหนดหนึ่งมีดีกรีเข้ามากกว่าดีกรีออกเท่ากับหนึ่ง อีกโหนดหนึ่งมีดีกรีออกมากกว่าดีกรีเข้าเท่ากับหนึ่ง และโหนดที่เหลือมีดีกรีเข้่าเท่ากับดีกรีออก

Hierholzer’s algorithm

Hamiltonian

เป็น path ที่ท่องไปในทุกโหนดเพียงหนึ่งครั้งเท่านั้น

Existence

ไม่มี efficient method เนื่องจากยังเป็นปัญหาประเภท NP-hard