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

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

ใบงานใหม่ฝึกออนไลน์พร้อมคำใบ้

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

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

1.ง่าย

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

K9
|E| =
2.ง่าย

กราฟอย่างง่ายมี 7 จุดยอดที่มีดีกรี 4, 3, 3, 3, 2, 2, 1 มีกี่เส้นเชื่อม |E|

deg: 4, 3, 3, 3, 2, 2, 1
|E| =
3.ปานกลาง
ABCDEFวงจรออยเลอร์ทางเดินออยเลอร์ ไม่มีวงจรไม่ใช่ทั้งสองอย่าง

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

|V| = 6|E| = 7
  1. 1วงจรออยเลอร์
  2. 2ทางเดินออยเลอร์ ไม่มีวงจร
  3. 3ไม่ใช่ทั้งสองอย่าง
4.ปานกลาง

ต้นไม้มี 2 จุดยอดดีกรี 3, 2 จุดยอดดีกรี 4, 2 จุดยอดดีกรี 5, 4 จุดยอดดีกรี 2 และจุดยอดอื่นทั้งหมดเป็นใบ (ดีกรี 1) มีกี่ใบ L

2 × deg 32 × deg 42 × deg 54 × deg 2
L =
5.ยาก
137564584ABCDEF

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

เริ่มต้น: Aสิ้นสุด: F
d(F) =
6.ยาก
1210611171248ABCDEFG

จงหาน้ำหนักรวม W ของต้นไม้ทอดข้ามค่าน้อยที่สุดของกราฟถ่วงน้ำหนัก

|V| = 7|E| = 9
W =

เฉลย

  1. 1. |E| = 36
  2. 2. |E| = 9
  3. 3. วงจรออยเลอร์
  4. 4. L = 14
  5. 5. d(F) = 15
  6. 6. W = 33

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