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