ใบงาน ทฤษฎีกราฟ พร้อมเฉลย

ใบงาน ทฤษฎีกราฟ ฟรีสำหรับพิมพ์: 6 ข้อ ตั้งแต่ระดับง่ายถึงระดับข้อสอบจริง พร้อมเฉลย พิมพ์หรือบันทึกเป็น PDF ได้

สำหรับผู้สอน: พิมพ์ ทำสำเนา และใช้ในชั้นเรียนได้ฟรี ใบงานใหม่แต่ละชุดมีค่าตัวเลขใหม่และเฉลยของตัวเอง หากใส่ลิงก์ไปยัง ExamProblems ในหน้ารายวิชาของคุณ เราจะขอบคุณมาก

ชื่อ: ____________________ วันที่: ____________

1.ง่าย

แสดงเมทริกซ์ประชิดของกราฟอย่างง่ายไม่มีทิศทาง จงหาดีกรี deg(A) ของจุดยอด A

deg(A) =

2.ง่าย

กราฟบริบูรณ์ K₈ มีกี่เส้นเชื่อม |E|

K₈

|E| =

3.ปานกลาง

กราฟเชื่อมโยงนี้มีวงจรออยเลอร์ ทางเดินออยเลอร์ที่ไม่ใช่วงจร หรือไม่มีทั้งสองอย่าง ให้คลิกคำตอบของคุณ

|V| = 5|E| = 6

1วงจรออยเลอร์
2ทางเดินออยเลอร์ ไม่มีวงจร
3ไม่ใช่ทั้งสองอย่าง

4.ปานกลาง

กราฟบริบูรณ์ K₅ มีวงจรแฮมิลตันที่แตกต่างกันกี่วงจร H วงจรที่ต่างกันเพียงจุดยอดเริ่มต้นหรือทิศทางนับเป็นวงจรเดียวกัน

K₅

H =

5.ยาก

ขั้นตอนวิธีของครัสคัลสร้างต้นไม้ทอดข้ามค่าน้อยที่สุด ให้คลิกเส้นเชื่อมที่เพิ่มเป็นเส้นหมายเลข 6 เส้นที่ถูกข้ามไม่นับ

k = 6

1เส้นเชื่อม AB
2เส้นเชื่อม AC
3เส้นเชื่อม BC
4เส้นเชื่อม DF
5เส้นเชื่อม EF
6เส้นเชื่อม GB
7เส้นเชื่อม GC
8เส้นเชื่อม GD
9เส้นเชื่อม GE

6.ยาก

ใช้ขั้นตอนวิธีของไดก์สตราเพื่อหาความยาว d(F) ของเส้นทางที่สั้นที่สุดจาก A ไป F ในกราฟถ่วงน้ำหนัก

เริ่มต้น: Aสิ้นสุด: F

d(F) =

เฉลย

1. deg(A) = 2
2. |E| = 28
3. วงจรออยเลอร์
4. H = 12
5. เส้นเชื่อม EF
6. d(F) = 11

เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com