1.ง่าย
ป่า (กราฟที่ไม่มีวัฏจักร) มี 12 จุดยอดและ 6 ส่วนประกอบเชื่อมโยง มีกี่เส้นเชื่อม |E|
|V| = 12c = 6
|E| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
ต้นไม้มี 28 จุดยอด มีกี่เส้นเชื่อม |E|
|V| = 28
|E| =
3.ปานกลาง
กราฟเชื่อมโยงนี้มีวงจรออยเลอร์ ทางเดินออยเลอร์ที่ไม่ใช่วงจร หรือไม่มีทั้งสองอย่าง ให้คลิกคำตอบของคุณ
|V| = 7|E| = 12
- 1วงจรออยเลอร์
- 2ทางเดินออยเลอร์ ไม่มีวงจร
- 3ไม่ใช่ทั้งสองอย่าง
4.ปานกลาง
ต้นไม้มี 2 จุดยอดดีกรี 3, 2 จุดยอดดีกรี 5, 2 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L
2 × deg 32 × deg 52 × deg 2
L =
5.ยาก
มีวอล์กความยาว 2 จาก C ไป B กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N
M = เมทริกซ์ประชิดL = 2
N =
6.ยาก
ขั้นตอนวิธีของพริมสร้างต้นไม้ทอดข้ามค่าน้อยที่สุดโดยเริ่มจากจุดยอด F ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 4
เริ่มต้น: Fk = 4
- 1เส้นเชื่อม AB
- 2เส้นเชื่อม AC
- 3เส้นเชื่อม BC
- 4เส้นเชื่อม BD
- 5เส้นเชื่อม CE
- 6เส้นเชื่อม DE
- 7เส้นเชื่อม DF
- 8เส้นเชื่อม EF
- 9เส้นเชื่อม BE
เฉลย
- 1. |E| = 6
- 2. |E| = 27
- 3. วงจรออยเลอร์
- 4. L = 10
- 5. N = 2
- 6. เส้นเชื่อม CE
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com