1.ง่าย
กราฟสองส่วนบริบูรณ์ K3,5 มีกี่เส้นเชื่อม |E|
K3,5
|E| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
ต้นไม้มี 36 เส้นเชื่อม มีกี่จุดยอด |V|
|E| = 36
|V| =
3.ปานกลาง
ต้นไม้มี 3 จุดยอดดีกรี 5, 2 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
3 × deg 52 × deg 2
L =
4.ปานกลาง
กราฟเชื่อมโยงนี้มีวงจรออยเลอร์ ทางเดินออยเลอร์ที่ไม่ใช่วงจร หรือไม่มีทั้งสองอย่าง ให้คลิกคำตอบของคุณ
|V| = 6|E| = 7
- 1วงจรออยเลอร์
- 2ทางเดินออยเลอร์ ไม่มีวงจร
- 3ไม่ใช่ทั้งสองอย่าง
5.ยาก
จงหาน้ำหนักรวม W ของต้นไม้ทอดข้ามค่าน้อยที่สุดของกราฟถ่วงน้ำหนัก
|V| = 5|E| = 7
W =
6.ยาก
ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก
เริ่มต้น: Aสิ้นสุด: F
d(F) =
เฉลย
- 1. |E| = 15
- 2. |V| = 37
- 3. L = 11
- 4. ทางเดินออยเลอร์ ไม่มีวงจร
- 5. W = 43
- 6. d(F) = 19
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com