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

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

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

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

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

1.ง่าย
ABCDEF

มีจุดยอดของกราฟเพียงจุดเดียวพอดีที่มีดีกรี 3 ให้คลิกจุดนั้น

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
2.ง่าย

ต้นไม้มี 28 เส้นเชื่อม มีกี่จุดยอด |V|

|E| = 28
|V| =
3.ปานกลาง

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

K6
H =
4.ปานกลาง

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

|V| = 9|E| = 14
k =
5.ยาก
14491019513ABCDE

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

เริ่มต้น: Bk = 2
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม BD
  5. 5เส้นเชื่อม CE
  6. 6เส้นเชื่อม DE
  7. 7เส้นเชื่อม BE
6.ยาก
19179148161513ABCDEF

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

เริ่มต้น: Bk = 5
  1. 1เส้นเชื่อม AB
  2. 2เส้นเชื่อม AC
  3. 3เส้นเชื่อม BC
  4. 4เส้นเชื่อม CE
  5. 5เส้นเชื่อม DE
  6. 6เส้นเชื่อม DF
  7. 7เส้นเชื่อม EF
  8. 8เส้นเชื่อม BE

เฉลย

  1. 1. D
  2. 2. |V| = 29
  3. 3. H = 60
  4. 4. k = 6
  5. 5. เส้นเชื่อม AC
  6. 6. เส้นเชื่อม AC

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