ใบงาน ทฤษฎีกราฟ พร้อมเฉลย

มีจุดยอดของกราฟเพียงจุดเดียวพอดีที่มีดีกรี 2 ให้คลิกจุดนั้น

1. 1A
2. 2B
3. 3C
4. 4D
5. 5E
6. 6F

กราฟอย่างง่ายมี 5 จุดยอดที่มีดีกรี 3, 2, 2, 2, 1 มีกี่เส้นเชื่อม |E|

ต้นไม้มี 4 จุดยอดดีกรี 5, 4 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L

กราฟบริบูรณ์ K₇ มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน

ขั้นตอนวิธีของไดก์สตราเริ่มจาก A ให้คลิกจุดยอดที่ถูกยืนยัน (ทำให้เป็นค่าถาวร) ในรอบที่ 3 โดย A เองคือรอบที่ 1

1. 1A
2. 2B
3. 3C
4. 4D
5. 5E
6. 6F
7. 7G

ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก