Teori graf: soalan latihan dengan penyelesaian langkah demi langkah

Soalan latihan Teori graf percuma dengan rajah, petunjuk dan penyelesaian lengkap. Nilai baharu setiap kali, pada tiga tahap: darjah dan sisi, laluan Euler dan pokok, laluan terpendek dan pokok rentang.

Soalan latihan percumaMudah

Sebuah pokok mempunyai 12 bucu. Berapa banyak sisi |E| yang ada padanya?

|V| = 12

Jawapan tepat: nombor bulat, tanpa pembundaran.

Soalan seterusnya →
Berlatih Teori graf secara percumaBerlatih Teori graf sekarang5 soalan percuma setiap hari. Tiada kad diperlukan.

Apa yang anda latih

  1. Mudahdarjah dan sisi
  2. Sederhanalaluan Euler dan pokok
  3. Sukarlaluan terpendek dan pokok rentang

Cara menyelesaikan soalan Teori graf

  1. Tulis darjah setiap bucu; jumlah darjah ialah dua kali bilangan sisi.
  2. Untuk soalan Euler, semak bahawa graf itu bersambung dan kira bucu yang berdarjah ganjil.
  3. Untuk pokok, gunakan n − 1 sisi dan lema jabat tangan.
  4. Untuk Dijkstra, simpan jadual jarak sementara dan tetapkan bucu tidak tetap yang paling kecil dalam setiap pusingan.
  5. Untuk pokok rentang minimum, isih sisi mengikut berat dan langkau setiap sisi yang menutup satu kitaran (Kruskal), atau tumbuhkan satu pokok daripada bucu permulaan (Prim).

Kesilapan lazim

  • Terlupa membahagi jumlah darjah dengan 2.
  • Menamakan graf sebagai graf Euler tanpa menyemak kesambungan.
  • Menetapkan bucu dalam Dijkstra sebelum jaraknya yang paling kecil.
  • Mengambil sisi paling ringan tanpa menyemak kitaran.
  • Mengira litar Hamilton bagi Kn sebagai n! dan bukan (n − 1)!/2.

Formula utama

Lema jabat tangan
Σ deg(v) = 2|E|
Graf lengkap
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Graf sekata
|E| = n·k/2
Pokok dan hutan
|E| = n − 1, |E| = n − c
Daun sesebuah pokok
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Euler
litar: semua darjah genap; laluan: tepat 2 darjah ganjil
Litar Hamilton dalam Kn
(n − 1)!/2
Kemas kini Dijkstra
d(v) = min(d(v), d(u) + w(u, v))
Jalan sepanjang L
(Mᴸ)ij

Pelajari Teori graf dari awal

Sebelum ini: Set, hubungan & fungsi

1Bucu, sisi dan darjah

Graf terdiri daripada bucu (titik) dan sisi (garis antara dua bucu). Dalam graf ringkas tiada gelung dan tiada sisi berganda.

Darjah sesuatu bucu ialah bilangan sisi yang bertemu padanya. Setiap sisi mempunyai dua hujung, maka ia menambah 1 pada darjah setiap hujung. Itu memberi lema jabat tangan:

Σ deg(v) = 2·|E|

Dua akibat: jumlah darjah sentiasa genap, dan bilangan bucu berdarjah ganjil juga genap.

  • Graf lengkap Kn menghubungkan setiap pasangan: n(n − 1)/2 sisi.
  • Graf dwipartit lengkap Km,n menghubungkan setiap bucu di satu sisi dengan setiap bucu di sisi yang lain: m·n sisi.
  • Graf k-sekata pada n bucu mempunyai n·k/2 sisi.

Matriks kejiranan mempunyai 1 pada (i, j) apabila i dan j bersambung. Bagi graf tak terarah ia simetri, hasil tambah baris ialah darjah, dan entri (i, j) bagi Mᴸ mengira jalan sepanjang L dari i ke j.

Semakan kendiri Sebuah graf mempunyai darjah 3, 3, 2, 2, 2. Berapakah bilangan sisinya?
  1. 10
  2. 12
  3. 5
  4. 6

Jawapan: 6. Darjah berjumlah 12, dan setiap sisi dikira dua kali, maka terdapat 12/2 = 6 sisi. 5 ialah bilangan bucu.

2Euler dan Hamilton

Litar Euler menggunakan setiap sisi tepat sekali dan kembali ke titik mula. Laluan Euler menggunakan setiap sisi sekali tetapi boleh berakhir di tempat lain. Bagi graf bersambung:

  • semua darjah genap: litar Euler wujud;
  • tepat dua darjah ganjil: laluan Euler wujud, dari satu bucu ganjil ke bucu ganjil yang lain;
  • lebih daripada dua darjah ganjil: kedua-duanya tidak wujud.

Litar Hamilton melawat setiap bucu tepat sekali. Tiada ujian darjah yang mudah untuknya. Dalam Kn terdapat (n − 1)!/2 litar Hamilton yang berbeza: tetapkan permulaan, susun n − 1 bucu yang lain, dan bahagi dengan 2 untuk dua arah.

Semakan kendiri Sebuah graf bersambung mempunyai darjah 2, 3, 4, 3, 2. Apakah yang dimilikinya?
  1. Kedua-dua litar Euler dan laluan Euler yang bukan litar
  2. Laluan Euler, tetapi tiada litar Euler
  3. Litar Euler
  4. Tiada kedua-duanya

Jawapan: Laluan Euler, tetapi tiada litar Euler. Tepat dua bucu berdarjah ganjil (dua 3), maka terdapat laluan Euler antara keduanya, tetapi tiada litar.

3Pokok

Pokok ialah graf bersambung tanpa kitaran. Setiap pokok dengan n bucu mempunyai tepat n − 1 sisi. Menambah sebarang sisi mencipta kitaran; membuang sebarang sisi memutuskan sambungan.

Hutan yang terdiri daripada c pokok pada n bucu mempunyai n − c sisi. Graf bersambung dengan m sisi mengekalkan pokok rentang selepas membuang m − n + 1 sisi.

Lema jabat tangan mengira daun: Σ deg = 2(n − 1). Bentuk ringkasnya ialah L = 2 + Σ (d − 2) ke atas bucu berdarjah d ≥ 3. Pokok dengan dua bucu berdarjah 3 dan selebihnya daun mempunyai 2 + 1 + 1 = 4 daun.

4Dijkstra dan pokok rentang minimum

Algoritma Dijkstra mencari jarak terpendek dari bucu permulaan dalam graf dengan berat tak negatif.

  1. Beri jarak permulaan 0 dan setiap bucu lain ∞.
  2. Tetapkan bucu tidak tetap yang berjarak paling kecil; jaraknya kini muktamad.
  3. Bagi setiap jiran v, kemas kini d(v) = min(d(v), d(u) + w(u, v)).
  4. Ulang sehingga sasaran ditetapkan.

Pokok rentang minimum menyambungkan semua bucu dengan jumlah berat terkecil. Kruskal mengisih sisi dari ringan ke berat dan mengambil setiap satu melainkan ia menutup kitaran. Prim menumbuhkan satu pokok daripada bucu permulaan, sentiasa menambah sisi teringan yang keluar daripadanya. Kedua-duanya berhenti selepas n − 1 sisi.

Contoh terselesai

Cari jarak terpendek dari A ke E dalam graf di bawah.

1

Mula

412581ABCDE

d(A) = 0. Jirannya mendapat d(B) = 4 dan d(C) = 1.

2

Tetapkan C (1)

Melalui C: d(B) = min(4, 1 + 2) = 3 dan d(E) = 1 + 8 = 9.

3

Tetapkan B (3)

Melalui B: d(D) = 3 + 5 = 8.

4

Tetapkan D (8)

Melalui D: d(E) = min(9, 8 + 1) = 9. Tiada penambahbaikan, seri.

5

Tetapkan E (9)

E telah ditetapkan: jaraknya muktamad.

Jawapan

Jarak terpendek ialah d(E) = 9, sepanjang A → C → E. Laluan A → C → B → D → E mempunyai panjang yang sama, 1 + 2 + 5 + 1 = 9.

Semakan kendiri Algoritma Kruskal telah mengambil sisi berat 1, 2 dan 3. Sisi teringan seterusnya, berat 4, menghubungkan dua bucu yang sudah bersambung. Apa yang berlaku?
  1. Algoritma berhenti
  2. Ia diambil kerana ia yang teringan yang tinggal
  3. Ia dilangkau kerana ia akan menutup kitaran
  4. Sisi berat 3 dibuang sebagai gantinya

Jawapan: Ia dilangkau kerana ia akan menutup kitaran. Kruskal tidak pernah menutup kitaran: sisi antara dua bucu dalam komponen yang sama dilangkau, dan algoritma beralih ke sisi seterusnya.

5Kesilapan lazim

  • Terlupa membahagi jumlah darjah dengan 2 untuk mendapat bilangan sisi.
  • Menguji litar Euler tanpa menyemak bahawa graf itu bersambung.
  • Menetapkan bucu dalam Dijkstra sebelum ia mempunyai jarak sementara yang paling kecil.
  • Mengambil n − 1 sisi teringan tanpa menyemak kitaran.
  • Mengira litar Hamilton bagi Kn sebagai n! dan bukan (n − 1)!/2.

6Rupa soalan peperiksaan

  • Mudah: darjah dan sisi. Anda menggunakan lema jabat tangan, mengira sisi Kn, Km,n, graf sekata dan pokok, membaca matriks kejiranan, atau mengklik bucu dengan darjah yang diberikan.
  • Sederhana: laluan Euler dan pokok. Anda menentukan sama ada graf mempunyai litar atau laluan Euler, mengira daun pokok, mengira sisi yang perlu dibuang untuk pokok rentang, atau mengira litar Hamilton dalam Kn.
  • Sukar: laluan terpendek dan pokok rentang. Anda menjalankan algoritma Dijkstra, mencari bucu yang ditetapkan dalam pusingan tertentu, mencari berat pokok rentang minimum, mengklik sisi yang ditambah oleh Kruskal atau Prim seterusnya, atau mengira jalan dengan matriks kejiranan.

Belajar langkah demi langkah dalam aplikasiBelajar langkah demi langkah dalam aplikasi

Contoh penyelesaian

Contoh 1Mudah
AABBCCDDEE0010000001100010000101110

Matriks kejiranan bagi graf tak terarah ringkas ditunjukkan. Berapa banyak sisi |E| yang ada pada graf itu?

Cari nilai |E|

Tunjukkan petunjuk
  1. Entri (i, j) ialah 1 apabila bucu i dan j disambungkan oleh sisi.
  2. Setiap sisi {i, j} memberi dua 1: satu pada (i, j) dan satu pada (j, i).
  3. Matriks itu mengandungi 8 satu.
Tunjukkan jawapan dan penyelesaian langkah demi langkah

Darjah: darjah sesuatu bucu ialah bilangan sisi yang bertemu padanya. Setiap sisi mempunyai dua hujung, maka jumlah darjah ialah dua kali bilangan sisi: Σ deg(v) = 2|E| (lema jabat tangan). Bilangan bucu berdarjah ganjil oleh itu genap. Kn mempunyai n(n − 1)/2 sisi, graf k-sekata pada n bucu mempunyai nk/2, dan pokok pada n bucu mempunyai n − 1 sisi.

Kira bit satu

hasil tambah baris: 1 + 1 + 2 + 1 + 3 = 8
|E| = 8/2 = 4

Jawapan

|E| = 4
Contoh 2Sederhana
ABCDEFGLitar 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| = 7|E| = 10
  1. 1Litar Euler
  2. 2Laluan Euler, tiada litar
  3. 3tiada kedua-duanya
Tunjukkan petunjuk
  1. Teorem Euler hanya memerlukan darjah bucu (graf itu bersambung).
  2. Semua darjah genap: litar Euler. Tepat dua darjah ganjil: laluan Euler antara keduanya. Lebih daripada itu: tiada kedua-duanya.
  3. Kira bucu berdarjah ganjil.
Tunjukkan jawapan dan penerangan

Euler, Hamilton dan pokok: graf bersambung mempunyai litar Euler (setiap sisi sekali, kembali ke permulaan) apabila setiap bucu berdarjah genap, dan laluan Euler yang bukan litar apabila tepat dua bucu berdarjah ganjil; laluan itu kemudian bermula dari satu bucu ganjil ke bucu ganjil yang lain. Litar Hamilton melawat setiap bucu sekali; Kn mempunyai (n − 1)!/2 daripadanya. Pokok pada n bucu mempunyai n − 1 sisi, dan graf bersambung dengan m sisi mengekalkan pokok rentang selepas membuang m − n + 1 sisi.

Darjah

deg(A) = 1, deg(B) = 4, deg(C) = 2, deg(D) = 4, deg(E) = 4, deg(F) = 2, deg(G) = 3

Bucu ganjil

A, G → 2
Laluan Euler, tiada litar

Jawapan

Laluan Euler, tiada litar

Laluan Euler bermula pada satu bucu ganjil dan berakhir pada bucu ganjil yang lain.

Contoh 3Sukar
ABCDEF

Berapa banyak jalan tertutup sepanjang 3 bermula dan berakhir di E? Jalan boleh mengulang bucu dan sisi. Panggil nombor ini N.

M = matriks kejirananL = 3

Cari nilai N

Tunjukkan petunjuk
  1. Dengan matriks kejiranan M, bilangan jalan sepanjang L dari i ke j ialah entri (i, j) bagi Mᴸ.
  2. Kira jalan sepanjang 2 dari E ke setiap bucu dahulu, kemudian ambil satu langkah lagi.
  3. Jalan sepanjang 2 dari E: A: 2, B: 1, C: 0, D: 2, E: 4, F: 1.
Tunjukkan jawapan dan penyelesaian langkah demi langkah

Darjah: darjah sesuatu bucu ialah bilangan sisi yang bertemu padanya. Setiap sisi mempunyai dua hujung, maka jumlah darjah ialah dua kali bilangan sisi: Σ deg(v) = 2|E| (lema jabat tangan). Bilangan bucu berdarjah ganjil oleh itu genap. Kn mempunyai n(n − 1)/2 sisi, graf k-sekata pada n bucu mempunyai nk/2, dan pokok pada n bucu mempunyai n − 1 sisi.

Matriks kejiranan

A: 0 1 1 0 0 0
B: 1 0 0 1 1 0
C: 1 0 0 0 1 0
D: 0 1 0 0 1 1
E: 0 1 1 1 0 1
F: 0 0 0 1 1 0

Satu langkah lagi

(M³)EE = 2·0 + 1·1 + 0·1 + 2·1 + 4·0 + 1·1 = 4

Jawapan

N = 4

Soalan dan jawapan

Apakah Teori graf?

Dua akibat: jumlah darjah sentiasa genap, dan bilangan bucu berdarjah ganjil juga genap.

Bagaimanakah saya menyelesaikan soalan Teori graf langkah demi langkah?
  1. Tulis darjah setiap bucu; jumlah darjah ialah dua kali bilangan sisi.
  2. Untuk soalan Euler, semak bahawa graf itu bersambung dan kira bucu yang berdarjah ganjil.
  3. Untuk pokok, gunakan n − 1 sisi dan lema jabat tangan.
  4. Untuk Dijkstra, simpan jadual jarak sementara dan tetapkan bucu tidak tetap yang paling kecil dalam setiap pusingan.
  5. Untuk pokok rentang minimum, isih sisi mengikut berat dan langkau setiap sisi yang menutup satu kitaran (Kruskal), atau tumbuhkan satu pokok daripada bucu permulaan (Prim).
Apakah kesilapan lazim dalam Teori graf?
  • Terlupa membahagi jumlah darjah dengan 2.
  • Menamakan graf sebagai graf Euler tanpa menyemak kesambungan.
  • Menetapkan bucu dalam Dijkstra sebelum jaraknya yang paling kecil.
  • Mengambil sisi paling ringan tanpa menyemak kitaran.
  • Mengira litar Hamilton bagi Kn sebagai n! dan bukan (n − 1)!/2.
Apakah yang diliputi oleh latihan Teori graf?
  • Mudah: darjah dan sisi
  • Sederhana: laluan Euler dan pokok
  • Sukar: laluan terpendek dan pokok rentang

Setiap soalan mempunyai nilai baharu, jadi anda mempelajari kaedah dan bukannya jawapan. Buntu? Buka petunjuk kecil dahulu, dan penerangan penuh hanya apabila anda memerlukannya.

Cara latihan berfungsi

  • Setiap soalan mempunyai nilai baharu, jadi anda mempelajari kaedah dan bukannya jawapan.
  • Buntu? Buka petunjuk kecil dahulu, dan penerangan penuh hanya apabila anda memerlukannya.
  • Kemajuan, kesilapan dan soalan tersimpan anda dikekalkan, jadi anda boleh menyemak sebelum peperiksaan.

Topik sebelum dan selepas topik ini

Pelajari dahulu

Set, hubungan & fungsi

Kursus dengan topik ini

Struktur Data dan AlgoritmaAsas Sains KomputerMatematik Diskret

Lebih banyak topik dalam Matematik & statistik

HadTerbitanPengoptimumanKamiranJujukan & siriKalkulus multipemboleh ubahPersamaan pembezaanNombor kompleksKaedah berangkaMatriks & penentuVektor: hasil darab titik & silangLogik proposisi & pembuktianSet, hubungan & fungsiTeori nombor & aritmetik moduloKebarangkalianStatistik perihalanTaburan normalSelang keyakinanUjian hipotesis & selang keyakinanRegresi linear & korelasiUjian khi kuasa dua

Lembaran kerja boleh cetak

Lembaran kerja Teori graf dengan jawapan
Berlatih Teori graf secara percumaBerlatih Teori graf sekarang5 soalan percuma setiap hari. Tiada kad diperlukan.