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
ABCDEF

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

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
2.Mudah

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

deg: 3, 2, 2, 2, 1
|E| =
3.Sederhana

Sebuah pokok mempunyai 4 bucu berdarjah 5, dan semua bucu lainnya ialah daun (berdarjah 1). Berapa banyak daun L yang ada padanya?

4 × deg 5
L =
4.Sederhana

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

|V| = 6|E| = 9
k =
5.Sukar
161548191210ABCDEF

Algoritma Prim membina pokok rentang minimum bermula dari bucu E. Klik sisi yang ditambahnya sebagai sisi nombor 3.

mula: Ek = 3
  1. 1sisi AB
  2. 2sisi AC
  3. 3sisi BC
  4. 4sisi BD
  5. 5sisi CE
  6. 6sisi DE
  7. 7sisi EF
  8. 8sisi BE
6.Sukar
1411427134413111312ABCDEFG

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

mula: Aakhir: F
d(F) =

Kunci jawapan

  1. 1. F
  2. 2. |E| = 5
  3. 3. L = 14
  4. 4. k = 4
  5. 5. sisi AB
  6. 6. d(F) = 20

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