1.ง่าย
ป่า (กราฟที่ไม่มีวัฏจักร) มี 10 จุดยอดและ 2 ส่วนประกอบเชื่อมโยง มีกี่เส้นเชื่อม |E|
|V| = 10c = 2
|E| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
จงหาผลบวกของดีกรีของทุกจุดยอดของกราฟที่แสดง Σ deg
|V| = 6
Σ deg =
3.ปานกลาง
ต้นไม้มี 4 จุดยอดดีกรี 5 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
4 × deg 5
L =
4.ปานกลาง
กราฟบริบูรณ์ K4 มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน
K4
H =
5.ยาก
ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก
เริ่มต้น: Aสิ้นสุด: F
d(F) =
6.ยาก
มีวอล์กปิดความยาว 3 ที่เริ่มและจบที่ A กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N
M = เมทริกซ์ประชิดL = 3
N =
เฉลย
- 1. |E| = 8
- 2. Σ deg = 12
- 3. L = 14
- 4. H = 3
- 5. d(F) = 20
- 6. N = 2
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com