1.ง่าย
ป่า (กราฟที่ไม่มีวัฏจักร) มี 18 จุดยอดและ 3 ส่วนประกอบเชื่อมโยง มีกี่เส้นเชื่อม |E|
|V| = 18c = 3
|E| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
แสดงเมทริกซ์ประชิดของกราฟอย่างง่ายไม่มีทิศทาง กราฟมีกี่เส้นเชื่อม |E|
|E| =
3.ปานกลาง
ต้นไม้มี 3 จุดยอดดีกรี 4, 2 จุดยอดดีกรี 5 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
3 × deg 42 × deg 5
L =
4.ปานกลาง
กราฟเชื่อมโยงมี 9 จุดยอดและ 12 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม
|V| = 9|E| = 12
k =
5.ยาก
ขั้นตอนวิธีของพริมสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเริ่มจากจุดยอด D ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 2
เริ่มต้น: Dk = 2
- 1เส้นเชื่อม AB
- 2เส้นเชื่อม AC
- 3เส้นเชื่อม BC
- 4เส้นเชื่อม BD
- 5เส้นเชื่อม CE
- 6เส้นเชื่อม DE
- 7เส้นเชื่อม EF
- 8เส้นเชื่อม GB
- 9เส้นเชื่อม GC
- 10เส้นเชื่อม GD
- 11เส้นเชื่อม GE
6.ยาก
ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุด ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 5 เส้นที่ถูกข้ามไม่นับ
k = 5
- 1เส้นเชื่อม AB
- 2เส้นเชื่อม AC
- 3เส้นเชื่อม BC
- 4เส้นเชื่อม BD
- 5เส้นเชื่อม CE
- 6เส้นเชื่อม DE
- 7เส้นเชื่อม DF
- 8เส้นเชื่อม EF
เฉลย
- 1. |E| = 15
- 2. |E| = 5
- 3. L = 14
- 4. k = 4
- 5. เส้นเชื่อม GB
- 6. เส้นเชื่อม AC
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com