Lembaran kerja Teori graf dengan jawapan

Lembaran kerja Teori graf percuma untuk dicetak: 6 soalan dari mudah hingga tahap peperiksaan, dengan skema jawapan. Cetak atau simpan sebagai PDF.

Lembaran kerja baharuBerlatih dalam talian dengan petunjuk

Untuk pensyarah dan guru: percuma untuk dicetak, disalin dan digunakan di dalam kelas. Setiap lembaran kerja baharu mempunyai nilai baharu dan skema jawapannya sendiri. Pautan ke ExamProblems di halaman kursus anda amat dihargai.

Nama: ____________________   Tarikh: ____________

1.Mudah

Graf ringkas mempunyai 6 bucu dengan darjah 4, 4, 3, 2, 2, 1. Berapa banyak sisi |E| yang ada padanya?

deg: 4, 4, 3, 2, 2, 1
|E| =
2.Mudah
ABCDE

Tepat satu bucu graf itu berdarjah 3. Klik bucu itu.

deg = 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
3.Sederhana

Graf bersambung mempunyai 9 bucu dan 17 sisi. Berapa banyak sisi k yang mesti dibuang untuk meninggalkan pokok rentang?

|V| = 9|E| = 17
k =
4.Sederhana

Berapa banyak litar Hamilton H yang berbeza pada graf lengkap K8? Litar yang hanya berbeza pada bucu permulaan atau arah dikira sama.

K8
H =
5.Sukar
14897121276ABCDEF

Gunakan algoritma Dijkstra untuk mencari panjang d(F) laluan terpendek dari A ke F dalam graf berpemberat.

mula: Aakhir: F
d(F) =
6.Sukar
5415320141261016ABCDEFG

Algoritma Kruskal membina pokok rentang minimum. Klik sisi yang ditambahnya sebagai sisi nombor 6; sisi yang dilangkau tidak dikira.

k = 6
  1. 1sisi AB
  2. 2sisi AC
  3. 3sisi BC
  4. 4sisi CE
  5. 5sisi DE
  6. 6sisi DF
  7. 7sisi EF
  8. 8sisi GB
  9. 9sisi GC
  10. 10sisi GD

Kunci jawapan

  1. 1. |E| = 8
  2. 2. B
  3. 3. k = 9
  4. 4. H = 2520
  5. 5. d(F) = 28
  6. 6. sisi DF

Penyelesaian langkah demi langkah yang lengkap: berlatih topik ini di examproblems.com.