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