Lompat ke konten utama
Kelas
Matematika DiskritPelajaran 15 dari 16 · Modul 4, Graf

Modul 4 · Graf

Pohon

Setelah pelajaran ini kamu bisa mengenali pohon sebagai graf terhubung tanpa siklus, memakai hubungan banyak sisi = banyak simpul − 1, dan memeriksa sebuah graf dengan Python.

  • ±13 menit
  • 3 latihan
  • Diperiksa 27 Sep 2026

Latihan di pelajaran ini butuh akun gratis. Progres, kode, dan catatanmu hanya tersimpan di browser ini. Masuk untuk menyimpannya

Materi

Siklus adalah lintasan yang kembali ke simpul awalnya tanpa mengulang sisi. Pohon adalah graf yang terhubung dan tidak memuat siklus. Tiga fakta tentang pohon dipakai terus-menerus. Pertama, di antara dua simpul mana pun pada pohon ada tepat satu lintasan; sebaliknya, graf yang punya sifat ini adalah pohon. Kedua, pohon dengan v simpul selalu punya tepat v − 1 sisi. Ketiga, simpul berderajat 1 disebut daun, dan setiap pohon dengan paling sedikit dua simpul punya daun.

Pohon muncul di mana pun sesuatu harus terhubung dengan sambungan sesedikit mungkin: jaringan kabel atau pipa yang menjangkau semua gedung tanpa putaran, struktur folder di komputer, bagan organisasi, dan silsilah keluarga. Bila salah satu simpul ditetapkan sebagai akar, misalnya folder utama, pohonnya disebut pohon berakar, dan setiap simpul selain akar punya satu induk. Contoh: jaringan listrik yang menyambung 12 rumah dan satu gardu tanpa putaran memakai 13 − 1 = 12 kabel. Menambah satu kabel lagi pasti membentuk siklus, dan membuang satu kabel pasti memutus jaringan menjadi dua bagian.

Latihan

Jawaban diperiksa di server. Lulus berarti kamu memahami contohnya, bukan penilaian seluruh pekerjaanmu.

Latihan 1 dari 3

Sebuah kampus menyambung 25 gedung dengan kabel serat optik sehingga setiap gedung terjangkau, tanpa ada putaran. Berapa banyak kabel yang dipakai?

Latihan 2 dari 3

Graf dengan enam simpul punya lima sisi: A–B, B–C, C–A, D–E, dan E–F. Apakah graf ini pohon?

Pilih satu jawaban

Catatanmu

Memuat catatan…

tersimpan otomatis, ikut tercetak · 0/4.000

Lanjutkan ke

Tampilkan 1 lagi