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

Berapa banyak sisi |E| yang ada pada graf lengkap K8?

K8
|E| =
2.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
3.Sederhana

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

4 × deg 34 × deg 5
L =
4.Sederhana
ABCDELitar EulerLaluan Euler, tiada litartiada kedua-duanya

Adakah graf bersambung itu mempunyai litar Euler, laluan Euler yang bukan litar, atau tiada kedua-duanya? Klik jawapan anda.

|V| = 5|E| = 5
  1. 1Litar Euler
  2. 2Laluan Euler, tiada litar
  3. 3tiada kedua-duanya
5.Sukar
14812618131515ABCDEFG

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

mula: Fk = 6
  1. 1sisi AB
  2. 2sisi BC
  3. 3sisi CE
  4. 4sisi DE
  5. 5sisi DF
  6. 6sisi EF
  7. 7sisi GB
  8. 8sisi GD
  9. 9sisi GE
6.Sukar
15101310151315ABCDEF

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

mula: Aakhir: E
d(E) =

Kunci jawapan

  1. 1. |E| = 28
  2. 2. A
  3. 3. L = 18
  4. 4. Litar Euler
  5. 5. sisi AB
  6. 6. d(E) = 20

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