Graph atau grafik adalah salah satu materi penting dalam matematika dan ilmu komputer yang sering digunakan untuk merepresentasikan hubungan antar objek. Graph terapan banyak muncul dalam berbagai soal ujian, baik untuk siswa SMA maupun mahasiswa, karena konsep ini mencakup logika, analisis, dan penerapan praktis dalam kehidupan sehari-hari. Dalam artikel ini, kita akan membahas kumpulan contoh soal graph terapan lengkap dengan jawaban dan pembahasan agar mudah dipahami dan bisa langsung dipraktikkan.
Pengertian Graph dan Jenis-jenisnya
Sebelum masuk ke soal, penting untuk memahami apa itu graph. Graph adalah himpunan simpul (vertices) yang dihubungkan oleh sisi (edges). Graph digunakan untuk merepresentasikan jaringan seperti jaringan sosial, transportasi, atau koneksi komputer.
baca juga:Contoh Soal Osmosis dalam Biologi Sel Beserta Penjelasannya
Jenis-jenis graph yang sering muncul antara lain:
- Graph Berarah (Directed Graph) yaitu graph yang tiap sisi memiliki arah tertentu.
- Graph Tak Berarah (Undirected Graph) yaitu graph di mana sisi tidak memiliki arah.
- Graph Berbobot (Weighted Graph) yaitu graph yang setiap sisi memiliki nilai tertentu, misalnya jarak atau biaya.
- Graph Tak Berbobot (Unweighted Graph) yaitu graph tanpa nilai pada sisi.
Memahami jenis graph akan memudahkan saat menyelesaikan soal terapan karena strategi penyelesaiannya berbeda-beda tergantung jenis graph.
Contoh Soal 1: Graph Tak Berarah Sederhana
Soal:
Diberikan sebuah graph tak berarah dengan simpul A, B, C, D, dan E, serta sisi {A-B, A-C, B-D, C-D, D-E}. Tentukan:
a. Derajat masing-masing simpul
b. Jumlah sisi
c. Apakah graph ini terhubung?
Jawaban:
a. Derajat tiap simpul:
- A: 2 (terhubung ke B dan C)
- B: 2 (terhubung ke A dan D)
- C: 2 (terhubung ke A dan D)
- D: 3 (terhubung ke B, C, dan E)
- E: 1 (terhubung ke D)
b. Jumlah sisi = 5
c. Graph terhubung karena dari setiap simpul bisa dicapai simpul lainnya melalui jalur tertentu.
Pembahasan:
Derajat simpul dihitung berdasarkan jumlah sisi yang menempel pada simpul tersebut. Graph terhubung berarti tidak ada simpul yang terisolasi.
Contoh Soal 2: Graph Berarah
Soal:
Sebuah perusahaan memiliki struktur hubungan kerja antar karyawan yang digambarkan dalam graph berarah. Terdapat simpul A, B, C, D dengan arah sisi A → B, B → C, C → D, D → B. Tentukan:
a. Derajat masuk dan derajat keluar setiap simpul
b. Apakah ada siklus dalam graph?
Jawaban:
a. Derajat masuk (in-degree) dan keluar (out-degree):
- A: in-degree = 0, out-degree = 1
- B: in-degree = 2 (A dan D), out-degree = 1
- C: in-degree = 1 (B), out-degree = 1
- D: in-degree = 1 (C), out-degree = 1
b. Ada siklus: B → C → D → B
Pembahasan:
In-degree adalah jumlah sisi yang menuju simpul, sedangkan out-degree adalah jumlah sisi keluar dari simpul. Siklus muncul ketika jalur dari satu simpul kembali ke simpul yang sama mengikuti arah sisi.
Contoh Soal 3: Graph Berbobot
Soal:
Sebuah kota memiliki jaringan jalan yang diwakili graph berbobot. Tabel bobot jarak antar kota adalah:
- A-B = 5 km
- A-C = 10 km
- B-D = 3 km
- C-D = 1 km
- D-E = 2 km
Tentukan jalur terpendek dari kota A ke kota E menggunakan algoritma Dijkstra.
Jawaban:
Langkah algoritma Dijkstra:
- Inisialisasi jarak awal: A=0, B=∞, C=∞, D=∞, E=∞
- Update jarak dari A: B=5, C=10
- Pilih simpul dengan jarak terkecil yang belum dikunjungi (B=5): Update D = min(∞, B+D=5+3) = 8
- Pilih D=8: Update E = min(∞, D+E=8+2) = 10
- C=10: Tidak ada update karena D sudah lebih kecil
- Jalur terpendek A → B → D → E = 10 km
Pembahasan:
Algoritma Dijkstra digunakan untuk menemukan jalur terpendek dari satu simpul ke semua simpul lainnya. Jalur A-B-D-E memberikan total jarak minimal 10 km.
Contoh Soal 4: Graph Tak Berarah dengan Matriks Ketetanggaan
Soal:
Diberikan graph tak berarah dengan 4 simpul A, B, C, D dan sisi {A-B, A-C, B-D, C-D}. Buatlah matriks ketetanggaan graph tersebut dan tentukan apakah graph ini lengkap.
Jawaban:
Matriks ketetanggaan:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
Graph ini tidak lengkap karena tidak semua simpul saling terhubung langsung.
Pembahasan:
Matriks ketetanggaan menunjukkan hubungan antar simpul, dengan 1 berarti ada sisi dan 0 berarti tidak ada. Graph lengkap memiliki semua pasangan simpul saling terhubung.
Contoh Soal 5: Graph dan Aplikasi Sosial
Soal:
Di media sosial, setiap pengguna diwakili oleh simpul, dan pertemanan diwakili oleh sisi. Jika terdapat 6 pengguna dengan sisi {A-B, A-C, B-C, B-D, C-E, D-E, E-F}, tentukan:
a. Degree centrality simpul
b. Siapa yang paling berpengaruh berdasarkan degree centrality
Jawaban:
Degree centrality (jumlah teman):
- A = 2
- B = 3
- C = 3
- D = 2
- E = 3
- F = 1
Pengguna paling berpengaruh: B, C, dan E (degree centrality tertinggi = 3)
Pembahasan:
Degree centrality digunakan dalam analisis jaringan sosial untuk mengukur pengaruh simpul. Semakin banyak koneksi, semakin besar pengaruhnya.
Contoh Soal 6: Graph Berarah dan Aliran
Soal:
Sebuah jaringan air di kota digambarkan dalam graph berarah dengan kapasitas:
- A → B = 10 liter
- A → C = 5 liter
- B → D = 15 liter
- C → D = 10 liter
Hitung kapasitas maksimal aliran dari A ke D.
Jawaban:
Gunakan metode aliran maksimum:
- Jalur A-B-D: kapasitas = min(10,15) = 10 liter
- Jalur A-C-D: kapasitas = min(5,10) = 5 liter
Total aliran maksimal = 10 + 5 = 15 liter
Pembahasan:
Metode aliran maksimum menghitung total kapasitas dari sumber ke tujuan melalui jalur yang tersedia. Konsep ini penting dalam jaringan transportasi dan distribusi.
Contoh Soal 7: Graph dan Matriks Insidensi
Soal:
Diberikan graph tak berarah dengan simpul {A, B, C} dan sisi {A-B, B-C}. Buat matriks insidensi.
Jawaban:
Matriks insidensi (baris = simpul, kolom = sisi):
| e1 | e2 | |
|---|---|---|
| A | 1 | 0 |
| B | 1 | 1 |
| C | 0 | 1 |
Pembahasan:
Matriks insidensi merepresentasikan hubungan antara simpul dan sisi. Baris menunjukkan simpul, kolom menunjukkan sisi. Nilai 1 menandakan simpul terhubung ke sisi tersebut.
Contoh Soal 8: Graph untuk Rute Transportasi
Soal:
Sebuah jaringan transportasi kota digambarkan dengan graph berbobot:
- X-Y = 4 km
- X-Z = 7 km
- Y-Z = 2 km
- Y-W = 5 km
- Z-W = 3 km
Tentukan rute terpendek dari X ke W menggunakan algoritma Dijkstra.
Jawaban:
- X → Y = 4
- X → Z = 7
- Pilih Y=4, update Z = min(7, 4+2=6), W = 4+5=9
- Pilih Z=6, update W = min(9, 6+3=9)
Jalur terpendek X → Y → Z → W atau X → Y → W, jarak = 9 km
Pembahasan:
Dijkstra memperbarui jarak minimum setiap simpul dan memilih jalur optimal. Dalam transportasi, metode ini membantu menentukan rute tercepat.
Contoh Soal 9: Graph dan Analisis Proyek
Soal:
Dalam manajemen proyek, setiap tugas diwakili simpul dan ketergantungan oleh sisi berarah. Tugas A, B, C, D dengan ketergantungan A → B, A → C, B → D, C → D. Tentukan jalur kritis.
Jawaban:
Jalur kritis adalah jalur terpanjang yang menentukan durasi proyek:
- Jalur 1: A → B → D
- Jalur 2: A → C → D
Jika durasi masing-masing tugas sama, jalur kritis bisa keduanya. Jika ada durasi berbeda, pilih jalur dengan total durasi terbesar.
Pembahasan:
Jalur kritis digunakan untuk mengidentifikasi tugas yang menentukan durasi proyek. Graph membantu visualisasi ketergantungan tugas.
Contoh Soal 10: Graph dan Pencarian Jalur
Soal:
Sebuah labirin digambarkan sebagai graph tak berarah. Simpul = titik persimpangan, sisi = jalan. Tentukan algoritma yang tepat untuk menemukan semua jalur dari simpul start ke simpul end.
Jawaban:
Gunakan Depth-First Search (DFS) untuk menelusuri semua jalur atau Breadth-First Search (BFS) untuk menemukan jalur terpendek.
Pembahasan:
DFS menelusuri jalur hingga titik akhir, kembali jika buntu, dan melanjutkan jalur lain. BFS menelusuri level demi level, cocok untuk menemukan jalur terpendek. Algoritma ini banyak diterapkan dalam robotika dan game.
Kesimpulan
Graph terapan adalah konsep penting untuk analisis jaringan, transportasi, sosial, dan proyek. Dengan memahami jenis graph, derajat simpul, algoritma Dijkstra, aliran maksimum, serta matriks ketetanggaan dan insidensi, siswa SMA dan mahasiswa dapat menyelesaikan berbagai soal dengan lebih mudah. Latihan soal seperti yang dibahas di atas sangat membantu meningkatkan pemahaman konsep graph secara praktis dan aplikatif.
penulis:ilham
Post Comment