1.ง่าย
ต้นไม้มี 12 จุดยอด มีกี่เส้นเชื่อม |E|
|V| = 12
|E| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
ป่า (กราฟที่ไม่มีวัฏจักร) มี 10 จุดยอดและ 6 ส่วนประกอบเชื่อมโยง มีกี่เส้นเชื่อม |E|
|V| = 10c = 6
|E| =
3.ปานกลาง
กราฟเชื่อมโยงนี้มีวงจรออยเลอร์ ทางเดินออยเลอร์ที่ไม่ใช่วงจร หรือไม่มีทั้งสองอย่าง ให้คลิกคำตอบของคุณ
|V| = 5|E| = 5
- 1วงจรออยเลอร์
- 2ทางเดินออยเลอร์ ไม่มีวงจร
- 3ไม่ใช่ทั้งสองอย่าง
4.ปานกลาง
กราฟเชื่อมโยงมี 8 จุดยอดและ 10 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม
|V| = 8|E| = 10
k =
5.ยาก
ขั้นตอนวิธีของพริมสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเริ่มจากจุดยอด C ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 6
เริ่มต้น: Ck = 6
- 1เส้นเชื่อม AB
- 2เส้นเชื่อม AC
- 3เส้นเชื่อม BC
- 4เส้นเชื่อม CE
- 5เส้นเชื่อม DE
- 6เส้นเชื่อม DF
- 7เส้นเชื่อม EF
- 8เส้นเชื่อม GB
- 9เส้นเชื่อม GC
- 10เส้นเชื่อม GE
6.ยาก
ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก
เริ่มต้น: Aสิ้นสุด: F
d(F) =
เฉลย
- 1. |E| = 11
- 2. |E| = 4
- 3. ไม่ใช่ทั้งสองอย่าง
- 4. k = 3
- 5. เส้นเชื่อม DF
- 6. d(F) = 18
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com