คำถามทบทวน

ข้อปัญหาบุรุษไปรษณีย์จีน คือข้อใด

• The chinese postman problem

• The travelling salesman problem

• An algorithm of the chinese postman problem

• Eulerian weighted multigraph

ข้อปัญหาการเดินทางของพนักงานขาย จะต้องใช้กราฟใดเป็นตัวแบบ

• กราฟหลายเชิงถ่วงน้ำหนัก

• กราฟถ่วงน้ำหนัก

• กราฟหลายเชิง

• กราฟหลายเชิงออยเลอเรียน

พนักงานขายไปเมืองต่างๆ แวะทุกเมืองเพียงครั้งเดียว แล้วกลับจุดเริ่มต้น ให้จุดแทนเมือง เส้นแทนถนนที่เชื่อมระหว่างเมือง ข้อปัญหานี้สัมพันธ์กับกราฟใด

• กราฟออนเลอเรียน

• กราฟต้นไม้

• กราฟสองส่วน

• กราฟแฮมิลโทเนียน

กรณีกราฟถ่วงน้ำหนัก G ไม่บรรจุวงจรแบบออยเลอเรียน เนื่องจากสาเหตุใด

• จุดยอดทุกจุดมีดีกรีคู่

• บรรจุจุดยอดคี่ 2 จุด

• จุดเริ่มต้นกับจุดสุดท้ายเป็นจุดเดียวกัน

• เป็นกราฟออยเลอเรียน

การเพิ่มเส้นซ้ำบางเส้นในกราฟถ่วงน้ำหนัก เนื่องจากสาเหตุใด

• ต้องการสร้างกราฟหลายเชิงถ่วงน้ำหนักที่บรรจุวงจร

  ออยเลอเรียน

• ต้องการในดีกรีจุดทุดจุดเป็นจุดคี่

• ต้องการสร้างกราฟหลายเชิงถ่วงน้ำหนักที่บรรจุวง

  แฮมิลโทเนียน

• ต้องการกราฟที่มีน้ำหนักสูงสุด

w(P) มีชื่อเรียกว่าอะไรในข้อปัญหาบุรุษไปรษณีย์จีน

• กราฟหลายเชิงออยเลอเรียน

• ระยะทางของผลแบ่งกั้น

• น้ำหนักของผลแบ่งกั้น

• วงแฮมิลโทเนียน

d(P) มีชื่อเรียกว่าอะไรในข้อปัญหา

• กราฟหลายเชิงออยเลอเรียน

• ระยะทางผลแบ่งกั้น

• น้ำหนักของผลแบ่งกั้น

• วงแฮมิลโทเนียน

จากรูปกราฟ M เกิดจากการเพิ่มเส้นซ้ำใดบ้าง

• ac, ad, bd, cd

• ac, ad, bd, as

• ab, ac, ad, bd, cd

• ab, ac, ad ,aa ,cc

จงหาผลรวมของระยะทางที่น้อยที่สุดโดยใช้ข้อปัญหาบุรุษไปรษณีย์จีน ( ยังไม่ได้เพิ่มเส้นซ้ำ )

• 35

• 40

• 34

• 48

จากข้อปัญหาบุรุษไปรษณีย์ กราฟหลายเชิง

ถ่วงน้ำหนัก M มีน้ำหนักต่ำสุดเท่ากับเท่าใด ( เพิ่มเส้นซ้ำแล้ว )

• 42

• 32

• 38

• 33