รบกวนแนะนำทฤษฎีกราฟข้อนี้นิดนึงครับ
 

ถ้าทำแบบคิดต้นไม้แผ่ทั่วน้อยสุด ยังพอเก็ทนะครับ:kiki:
แต่ถ้าเจอแบบนี้ มีพี่ๆท่านไหนพอแนะนำได้บ้างไหมครับ :sweat:
ขอบคุณล่วงหน้าครับ:please:
ปล.ถ้าคิดว่าเดินซ้ำedgeเดินได้ไม่จำกัดจำนวนครั้ง

ถ้าดีกรีของทุกจุดยอดเป็นเลขคู่ เราจะสามารถเดินจากจุด A กลับไปที่เดิมโดยผ่านทุกเส้นเชื่อมหนึ่งครั้งพอดีได้ครับ อันนี้เรียกว่า Eulerian circuit
ดังนั้นระยาทางที่สั้นที่สุดก็คือผลรวมของทุกเส้น

เมื่อมีจุดที่มีดีครีเป็นคี่มาด้วย เราสามารถมองแบบนี้ได้ครับ สมมติว่าเราเดินจากจุด A แล้วกลับไปที่เดิมตามข้อ1 เมื่อไหร่ที่เราเดินซ้ำบนเส้นเชื่อมเดิม ให้เราวาดเส้นเชื่อมนั้นเพิ่มขึ้นมา เช่นเราเริ่มเดินด้วย AB แล้วในอนาคตเรากลับมาใช้เส้น AB อีก ให้เราเติมเส้นเชื่อมระหว่าง A กับ B เข้าไปอีกเส้น จะเห็นว่าในกราฟที่ได้มาใหม่ เราเดินบนเส้นเชื่อมแต่ละเส้นหนึ่งครั้งพอดีครับ และระยะทางที่เราเดินก็คือผลรวมของเส้นเชื่อมในกราฟใหม่ครับ

ดังนั้นสิ่งที่เราต้องทำก็คือ หาว่าจะเติมเส้นเชื่อมยังไง เพื่อให้กราฟใหม่มีดีกรีของทุกจุดยอดเป็นคู่ โดยใช้ระยะเพิ่มน้อยที่สุด

กราฟในโจทย์มีจุดยอดที่มีดีกรีคี่คือ A B C H
ในข้อ1 การที่จะให้กราฟใหม่มีดีกรีของทุกจุดยอดเป็นคู่ เส้นเชื่อมที่เราเติมเข้าไปจะต้องรวมกันได้กราฟที่มี A B C H มีดีกรีเป็นคี่และจุดยอดที่เหลือมีดีกรีเป็นคู่

ข้อ2 น่าจะง่ายกว่า มาดูข้อ2กันก่อน เราต้องการเดินจาก A ไป H
ใช้หลักการเดียวกันครับ ข้อแตกต่างก็คือเราต้องเติมเส้นเชื่อมเข้าไปเพื่อให้ดีกรีของทุกจุดยอดเป็นคู่ยกเว้น A กับ H
นั่นก็คือ เส้นเชื่อมที่เราเติมเข้าไปจะต้องรวมกันได้กราฟที่มี B C มีดีกรีเป็นคี่และจุดยอดที่เหลือมีดีกรีเป็นคู่
กราฟดังกล่าวก็ต้องเป็น path จาก B ไป C ที่มีระยะทางสั้นที่สุดครับ นั่นก็คือ path BAC
แปลว่าเมื่อเราเติมเส้นเชื่อม BA กับ AC เข้าไป เราจะได้กราฟที่มีดีกรีของทุกจุดยอดเป็นคู่ยกเว้น A กับ H
คำตอบคือ ผลรวมของระยะทางทั้งหมดในรูป บวกด้วย BA กับ AC ครับ ซึ่งคือ +6+6

กลับมาที่ข้อ1 เราต้องการให้เส้นเชื่อมที่เราเติมเข้าไปจะต้องรวมกันได้กราฟที่มี A B C H มีดีกรีเป็นคี่และจุดยอดที่เหลือมีดีกรีเป็นคู่
สิ่งที่เราต้องทำคือ path สองอันโดยที่ปลายของ path สองอันนี้คือจุดยอด A B C H ครับ โดยที่ผลรวมของระยะทางบน path สั้นที่สุด
เราทำได้โดยหา path ที่สั้นที่สุดนะหว่างทุกๆคู่ใน A B C H ครับ ไล่เอา
Path ที่สั้นที่สุดระหว่าง A B ยาว 6
Path ที่สั้นที่สุดระหว่าง C H ยาว 16
รวมกันได้ 22
Path ที่สั้นที่สุดระหว่าง A C ยาว 6
Path ที่สั้นที่สุดระหว่าง B H ยาว 17
รวมกันได้ 23
Path ที่สั้นที่สุดระหว่าง A H ยาว 20
Path ที่สั้นที่สุดระหว่าง B C ยาว 12
รวมกันได้ 32
ดังนั้นเราควรเลือกแบบแรกครับ คือ path AB กับ path CFH
นั่นคือเราเติมเส้นเชื่อ AB CF FH เข้าไปครับ กราฟที่ได้มาใหม่จะมีดีกรีคี่แค่ที่ A กับ H
และมีระยะทางที่ต้องเดินคือ ผลรวมของระยะทางทั้งหมดในรูป รวมกับระยะทางที่เราเติมเข้าไป ซื่งคือ +22 ครับ

งงตรงไหนถามได้ครับ อ่านเพิ่มเติมที่ได้ที่ https://en.m.wikipedia.org/wiki/Rout...ection_problem

ที่คิดออกคือต้องหาเส้นเดิมทั้งหมด แล้วหาเส้นใหม่ที่สั้นที่สุด แต่พอดูกรณีแล้วงงๆอะครับตอนแรก
แต่ตอนนี้เก็ทหมดแล้ว ขอบคุณมากนะครับ:please: