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

Cari jumlah darjah semua bucu graf yang ditunjukkan, Σ deg.

|V| = 6
Σ deg =
2.Mudah
ABCDEF

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

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

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

2 × deg 52 × deg 2
L =
4.Sederhana

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

K7
H =
5.Sukar
1311171591620ABCDE

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

k = 3
  1. 1sisi AB
  2. 2sisi AC
  3. 3sisi BC
  4. 4sisi BD
  5. 5sisi CE
  6. 6sisi DE
  7. 7sisi BE
6.Sukar
146145156121ABCDEF

Algoritma Dijkstra bermula dari A. Klik bucu yang ditetapkan (dijadikan tetap) dalam pusingan 3; A sendiri ialah pusingan 1.

mula: Apusingan 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F

Kunci jawapan

  1. 1. Σ deg = 12
  2. 2. E
  3. 3. L = 8
  4. 4. H = 360
  5. 5. sisi AB
  6. 6. E

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