06

Graf & jaringan

06 · Himpunan, logika & diskrit7 menit · Menengah

Graf adalah kumpulan titik yang dihubungkan garis. Bentuknya sederhana, tetapi cukup untuk mewakili jalan, jaringan komputer, maupun peta pertemanan. Yang menarik bukan gambarnya, melainkan sifat yang tetap sama walaupun gambarnya digambar ulang.

Lihat dulu

LIHAT DULU

Derajat, siklus, dan pohon

Graf mewakili hubungan sebagai titik dan garis. Derajat menghitung garis yang menempel pada satu titik, siklus adalah lintasan yang kembali ke titik awal, dan pohon adalah graf tanpa siklus sama sekali.

5
5/5
Pada pohon hanya ada satu lintasan antara dua titik mana pun, dan itu sebabnya pohon dengan n titik selalu punya n − 1 garis.

Konsep

Titik, sisi, dan derajat

Titik pada graf disebut simpul, dan garis penghubungnya disebut sisi. Derajat sebuah simpul adalah banyaknya sisi yang menempel padanya. Kalau semua derajat dijumlahkan, hasilnya selalu dua kali banyak sisi, karena setiap sisi menyumbang satu pada masing-masing kedua ujungnya.

Lintasan dan siklus

Lintasan adalah perjalanan dari satu simpul ke simpul lain dengan mengikuti sisi. Kalau perjalanan itu kembali ke titik awal tanpa mengulang sisi, bentuknya disebut siklus. Siklus tidak selalu merugikan: pada jaringan listrik ia menjadi jalur cadangan, sedangkan pada pohon ia justru harus tidak ada.

Pohon

Pohon adalah graf terhubung yang tidak punya siklus. Karena tidak ada jalur memutar, di antara dua simpul hanya ada satu lintasan. Sifat itu memaksa hubungan antara banyak simpul dan banyak sisi: pohon dengan n simpul selalu punya tepat n − 1 sisi.

Dipakai di mana

Rute pengiriman, jaringan komputer, dan peta pertemanan semuanya graf. Pertanyaan yang muncul juga berulang: jalur terpendek dari satu titik ke titik lain, simpul mana yang paling banyak terhubung, dan sisi mana yang kalau diputus memisahkan jaringan. Pertanyaan-pertanyaan itu tetap sama walaupun gambarnya digambar ulang.

Rumus yang dipakai

Jumlah derajat
Σ derajat = 2 × banyak sisi

Setiap sisi dihitung dua kali, sekali di tiap ujung.

Pohon
n simpul → n − 1 sisi

Berlaku kalau grafnya terhubung dan tanpa siklus.

Graf lengkap
Kn punya n(n − 1)2 sisi

Setiap pasangan simpul dihubungkan tepat satu sisi.

Contoh pengerjaan

Derajat, siklus, dan pohon

Sebuah graf punya 5 simpul A, B, C, D, E dan 5 sisi: A-B, B-C, B-E, A-D, dan D-E. Hitung jumlah derajatnya, temukan siklusnya, lalu tentukan sisi yang harus dibuang supaya grafnya menjadi pohon.

  1. Derajat tiap simpul dihitung dari sisi yang menempel. A menempel pada A-B dan A-D, jadi derajatnya 2.
  2. B menempel pada A-B, B-C, dan B-E, jadi derajatnya 3. C hanya menempel pada B-C, jadi derajatnya 1.
  3. D menempel pada A-D dan D-E, dan E menempel pada B-E dan D-E, jadi keduanya berderajat 2.
  4. Jumlahnya 2 + 3 + 1 + 2 + 2 = 10, tepat dua kali banyak sisinya, yaitu 2 × 5.
  5. Siklusnya A-B-E-D-A: berangkat dari A, kembali ke A, dan tidak ada sisi yang diulang.
  6. Karena ada siklus, grafnya belum berupa pohon. Buang satu sisi pada siklus itu, misalnya B-E.
  7. Sisa 5 simpul dan 4 sisi, masih terhubung, dan tanpa siklus, jadi sekarang grafnya pohon.

JawabanJumlah derajatnya 10, dan membuang sisi B-E menyisakan sebuah pohon

Poin penting

  • Derajat adalah banyaknya sisi yang menempel pada sebuah simpul.
  • Jumlah semua derajat sama dengan dua kali banyak sisi.
  • Siklus adalah lintasan yang kembali ke titik awal tanpa mengulang sisi.
  • Pohon dengan n simpul punya tepat n − 1 sisi.

Latihan singkat

MudahSoal 1 dari 3

Derajat sebuah simpul pada graf adalah …

SedangSoal 2 dari 3

Sebuah pohon memiliki 8 simpul. Berapa banyak sisinya?

SulitSoal 3 dari 3

Graf pada contoh punya 5 simpul dan 5 sisi. Manakah pernyataan yang benar tentang graf itu?

Skor sesi ini0 / 3