1.ง่าย
จงหาผลบวกของดีกรีของทุกจุดยอดของกราฟที่แสดง Σ deg
|V| = 5
Σ deg =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
กราฟอย่างง่ายมี 5 จุดยอดที่มีดีกรี 3, 2, 2, 2, 1 มีกี่เส้นเชื่อม |E|
deg: 3, 2, 2, 2, 1
|E| =
3.ปานกลาง
กราฟเชื่อมโยงมี 16 จุดยอดและ 18 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม
|V| = 16|E| = 18
k =
4.ปานกลาง
กราฟบริบูรณ์ K4 มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน
K4
H =
5.ยาก
ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(D) ของเส้นทางที่สั้นที่สุดจาก A ไป D ในกราฟถ่วงน้ำหนัก
เริ่มต้น: Aสิ้นสุด: D
d(D) =
6.ยาก
จงหาน้ำหนักรวม W ของต้นไม้ทอดข้ามค่าน้อยที่สุดของกราฟถ่วงน้ำหนัก
|V| = 5|E| = 7
W =
เฉลย
- 1. Σ deg = 12
- 2. |E| = 5
- 3. k = 3
- 4. H = 3
- 5. d(D) = 16
- 6. W = 31
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com