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

Modul 4 · Graf

Graf, derajat, dan lemma jabat tangan

Setelah pelajaran ini kamu bisa membaca graf sebagai simpul dan sisi, menghitung derajat setiap simpul, dan memakai hubungan jumlah derajat dengan banyak sisi.

  • ±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

Graf terdiri atas himpunan simpul (titik) dan himpunan sisi, dengan setiap sisi menghubungkan dua simpul. Dua simpul yang dihubungkan sebuah sisi disebut bertetangga. Graf dipakai untuk memodelkan apa pun yang berupa objek dan hubungan: kota dan jalan, komputer dan kabel, orang dan pertemanan, halaman web dan tautan. Derajat sebuah simpul adalah banyaknya sisi yang menyentuhnya. Simpul berderajat 0 tidak bertetangga dengan simpul mana pun.

Setiap sisi menambah derajat tepat dua simpul, yaitu kedua ujungnya. Akibatnya, jumlah derajat seluruh simpul selalu sama dengan dua kali banyak sisi. Hasil ini sering disebut lemma jabat tangan, dan punya akibat langsung: jumlah derajat selalu genap, sehingga banyaknya simpul berderajat ganjil juga selalu genap. Contoh: graf lima kota dengan derajat 3, 2, 2, 2, dan 1 punya jumlah derajat 10, jadi sisinya 10 ÷ 2 = 5. Di Python, graf kecil dapat disimpan sebagai daftar sisi, lalu derajatnya dihitung dengan menambah satu untuk kedua ujung setiap sisi.

jalan = [("A", "B"), ("A", "C"), ("B", "C"), ("C", "D")]
derajat_c = sum(1 for u, v in jalan if "C" in (u, v))
print(derajat_c)   # 3

Latihan

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

Latihan 1 dari 3

Sebuah graf punya enam simpul dengan derajat 3, 3, 2, 2, 1, dan 1. Berapa banyak sisinya?

Latihan 2 dari 3

Tujuh orang menghadiri rapat. Mungkinkah setiap orang berjabat tangan dengan tepat tiga orang lain di rapat itu?

Pilih satu jawaban

Catatanmu

Memuat catatan…

tersimpan otomatis, ikut tercetak · 0/4.000

Lanjutkan ke

Tampilkan 1 lagi