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

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

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

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

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

1.ง่าย

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

K11
|E| =
2.ง่าย
AABBCCDDEEFF001000001110110010010011011101000110

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

deg(B) =
3.ปานกลาง

กราฟเชื่อมโยงมี 11 จุดยอดและ 19 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม

|V| = 11|E| = 19
k =
4.ปานกลาง

กราฟเชื่อมโยงมี 6 จุดยอดและ 9 เส้นเชื่อม ต้องเอาเส้นเชื่อมออกกี่เส้น k เพื่อให้เหลือต้นไม้ทอดข้าม

|V| = 6|E| = 9
k =
5.ยาก
1561451215125ABCDEFG

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

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

มีวอล์กความยาว 3 จาก D ไป A กี่วอล์ก วอล์กอาจซ้ำจุดยอดและเส้นเชื่อมได้ เรียกจำนวนนี้ว่า N

M = เมทริกซ์ประชิดL = 3
N =

เฉลย

  1. 1. |E| = 55
  2. 2. deg(B) = 3
  3. 3. k = 9
  4. 4. k = 4
  5. 5. d(G) = 18
  6. 6. N = 3

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