1.ง่าย
ต้นไม้มี 40 จุดยอด มีกี่เส้นเชื่อม |E|
|V| = 40
|E| =
ใบงาน ทฤษฎีกราฟ พร้อมเฉลย
2.ง่าย
แสดงเมทริกซ์ประชิดของกราฟอย่างง่ายไม่มีทิศทาง จงหาดีกรี deg(C) ของจุดยอด C
deg(C) =
3.ปานกลาง
กราฟเชื่อมโยงมี 8 จุดยอดและ 13 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม
|V| = 8|E| = 13
k =
4.ปานกลาง
กราฟบริบูรณ์ K5 มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน
K5
H =
5.ยาก
ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุด ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 2 เส้นที่ถูกข้ามไม่นับ
k = 2
- 1เส้นเชื่อม AB
- 2เส้นเชื่อม AC
- 3เส้นเชื่อม BC
- 4เส้นเชื่อม BD
- 5เส้นเชื่อม CE
- 6เส้นเชื่อม DE
- 7เส้นเชื่อม DF
- 8เส้นเชื่อม EF
6.ยาก
มีวอล์กปิดความยาว 2 ที่เริ่มและจบที่ D กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N
M = เมทริกซ์ประชิดL = 2
N =
เฉลย
- 1. |E| = 39
- 2. deg(C) = 2
- 3. k = 6
- 4. H = 12
- 5. เส้นเชื่อม DF
- 6. N = 3
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com