1.ง่าย
ต้นไม้มี 32 เส้นเชื่อม มีกี่จุดยอด |V|
|E| = 32
|V| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
ต้นไม้มี 30 เส้นเชื่อม มีกี่จุดยอด |V|
|E| = 30
|V| =
3.ปานกลาง
ต้นไม้มี 2 จุดยอดดีกรี 3, 2 จุดยอดดีกรี 4, 3 จุดยอดดีกรี 5, 2 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
2 × deg 32 × deg 43 × deg 52 × deg 2
L =
4.ปานกลาง
ต้นไม้มี 4 จุดยอดดีกรี 3, 3 จุดยอดดีกรี 4, 3 จุดยอดดีกรี 5, 4 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
4 × deg 33 × deg 43 × deg 54 × deg 2
L =
5.ยาก
ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(D) ของเส้นทางที่สั้นที่สุดจาก A ไป D ในกราฟถ่วงน้ำหนัก
เริ่มต้น: Aสิ้นสุด: D
d(D) =
6.ยาก
มีวอล์กปิดความยาว 2 ที่เริ่มและจบที่ E กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N
M = เมทริกซ์ประชิดL = 2
N =
เฉลย
- 1. |V| = 33
- 2. |V| = 31
- 3. L = 17
- 4. L = 21
- 5. d(D) = 20
- 6. N = 3
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com