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