Struktur data graph merupakan salah satu topik inti dalam mata kuliah struktur data dan algoritma. Graph digunakan untuk merepresentasikan hubungan antar objek yang bersifat kompleks dan saling terhubung. Konsep graph sangat luas dan banyak digunakan dalam berbagai bidang, seperti pemetaan rute, jaringan komputer, kecerdasan buatan, analisis media sosial, hingga pengembangan sistem informasi modern.
Meskipun sangat penting, banyak mahasiswa masih merasa kesulitan dalam memahami graph karena melibatkan konsep abstrak, notasi matematis, serta berbagai jenis dan representasi graph. Oleh karena itu, kumpulan contoh soal graph pada struktur data beserta penyelesaian sangat dibutuhkan agar mahasiswa dapat memahami konsep graph secara bertahap dan aplikatif.
Artikel ini menyajikan kumpulan contoh soal graph mulai dari konsep dasar hingga penerapan, lengkap dengan pembahasan yang sistematis dan mudah dipahami.
Baca juga:Contoh Soal Perbandingan Matematika dan Cara Menyelesaikannya Step by Step
Pengantar Konsep Graph dalam Struktur Data
Graph adalah struktur data non-linear yang terdiri dari sekumpulan simpul atau vertex dan sisi atau edge yang menghubungkan simpul-simpul tersebut. Graph digunakan untuk memodelkan relasi antar data yang tidak dapat direpresentasikan secara efektif menggunakan struktur data linear seperti array, stack, atau queue.
Secara formal, graph ditulis sebagai G = (V, E), di mana V merupakan himpunan vertex dan E merupakan himpunan edge. Edge dapat bersifat berarah atau tidak berarah, serta dapat memiliki bobot atau tidak.
Tujuan Mempelajari Contoh Soal Graph
Mempelajari contoh soal graph membantu mahasiswa memahami bagaimana konsep teoritis diterapkan dalam pemecahan masalah nyata. Soal-soal graph juga melatih kemampuan analisis, logika, serta pemahaman algoritma yang berkaitan dengan graph.
Dengan latihan yang cukup, mahasiswa akan lebih siap menghadapi ujian, tugas kuliah, maupun implementasi graph dalam pemrograman.
Contoh Soal Graph 1 Menentukan Jumlah Vertex dan Edge
Soal
Sebuah graph memiliki simpul P, Q, R, S, dan T. Edge yang terbentuk adalah (P,Q), (Q,R), (R,S), (S,T), dan (T,P). Tentukan jumlah vertex dan edge pada graph tersebut.
Penyelesaian
Jumlah vertex ditentukan dari banyaknya simpul yang ada. Graph tersebut memiliki lima vertex, yaitu P, Q, R, S, dan T.
Jumlah edge ditentukan dari banyaknya pasangan simpul yang terhubung. Terdapat lima edge pada graph tersebut.
Jadi, graph memiliki 5 vertex dan 5 edge.
Contoh Soal Graph 2 Jenis Graph Berdasarkan Arah
Soal
Sebuah graph digunakan untuk merepresentasikan hubungan jalan satu arah antar kota. Setiap jalan hanya dapat dilalui dari satu kota ke kota lain tanpa arah sebaliknya. Jenis graph apa yang sesuai digunakan.
Penyelesaian
Karena setiap edge memiliki arah tertentu dan tidak dapat dilalui dua arah, maka graph yang sesuai adalah graph berarah atau directed graph.
Contoh Soal Graph 3 Menentukan Degree pada Graph Tidak Berarah
Soal
Pada sebuah graph tidak berarah, vertex A terhubung dengan vertex B, C, D, dan E. Tentukan degree dari vertex A.
Penyelesaian
Degree adalah jumlah edge yang terhubung ke suatu vertex. Karena vertex A terhubung dengan empat vertex lain, maka degree vertex A adalah 4.
Contoh Soal Graph 4 Indegree dan Outdegree
Soal
Dalam graph berarah, vertex K memiliki tiga edge masuk dan satu edge keluar. Tentukan indegree dan outdegree vertex K.
Penyelesaian
Indegree adalah jumlah edge yang masuk ke vertex, sedangkan outdegree adalah jumlah edge yang keluar.
Indegree vertex K adalah 3 dan outdegree vertex K adalah 1.
Contoh Soal Graph 5 Graph Berbobot
Soal
Sebuah graph digunakan untuk merepresentasikan jarak antar kota. Setiap edge memiliki nilai jarak tertentu. Termasuk jenis graph apakah graph tersebut.
Penyelesaian
Graph yang memiliki nilai atau bobot pada setiap edge disebut graph berbobot. Bobot tersebut dapat menunjukkan jarak, biaya, atau waktu tempuh.
Contoh Soal Graph 6 Adjacency Matrix
Soal
Diberikan graph dengan vertex A, B, dan C. Edge yang ada adalah (A,B), (B,C), dan (A,C). Buatlah adjacency matrix dari graph tersebut.
Penyelesaian
Adjacency matrix berukuran 3×3 karena terdapat tiga vertex.
Baris A menunjukkan hubungan A ke A, B, dan C yaitu 0, 1, 1.
Baris B menunjukkan hubungan B ke A, B, dan C yaitu 1, 0, 1.
Baris C menunjukkan hubungan C ke A, B, dan C yaitu 1, 1, 0.
Matriks ini menggambarkan hubungan antar vertex secara menyeluruh.
Contoh Soal Graph 7 Adjacency List
Soal
Buatlah adjacency list dari graph dengan vertex X, Y, Z, dan W serta edge (X,Y), (X,Z), dan (Z,W).
Penyelesaian
Adjacency list graph tersebut adalah sebagai berikut.
X terhubung dengan Y dan Z.
Y terhubung dengan X.
Z terhubung dengan X dan W.
W terhubung dengan Z.
Representasi adjacency list lebih hemat memori untuk graph dengan edge yang relatif sedikit.
Contoh Soal Graph 8 Graph Siklik dan Asiklik
Soal
Sebuah graph memiliki lintasan A ke B, B ke C, dan C ke A. Tentukan apakah graph tersebut termasuk graph siklik atau asiklik.
Penyelesaian
Graph tersebut memiliki lintasan yang kembali ke vertex awal, sehingga membentuk siklus. Oleh karena itu, graph tersebut termasuk graph siklik.
Contoh Soal Graph 9 Graph Lengkap
Soal
Sebuah graph memiliki 4 vertex dan setiap vertex terhubung dengan semua vertex lainnya. Termasuk jenis graph apakah graph tersebut.
Penyelesaian
Graph di mana setiap vertex terhubung dengan semua vertex lain disebut graph lengkap atau complete graph.
Contoh Soal Graph 10 Penerapan Graph dalam Sistem Nyata
Soal
Jelaskan mengapa struktur data graph sangat cocok digunakan untuk sistem navigasi seperti Google Maps.
Penyelesaian
Graph mampu merepresentasikan lokasi sebagai vertex dan jalan sebagai edge. Bobot pada edge dapat digunakan untuk menunjukkan jarak atau waktu tempuh, sehingga graph sangat cocok untuk menentukan rute terpendek dan efisien dalam sistem navigasi.
Contoh Soal Graph 11 Analisis Kompleksitas Graph
Soal
Mengapa adjacency list lebih efisien dibandingkan adjacency matrix untuk graph dengan jumlah edge sedikit.
Penyelesaian
Adjacency list hanya menyimpan edge yang ada, sehingga penggunaan memori lebih efisien. Sebaliknya, adjacency matrix tetap menggunakan ruang besar meskipun banyak elemen bernilai nol.
Contoh Soal Graph 12 Studi Kasus Jaringan Komputer
Soal
Dalam jaringan komputer, perangkat direpresentasikan sebagai vertex dan kabel sebagai edge. Jenis graph apakah yang biasanya digunakan.
Penyelesaian
Graph tidak berarah sering digunakan jika koneksi bersifat dua arah, sedangkan graph berarah digunakan jika aliran data memiliki arah tertentu.
Tips Mengerjakan Soal Graph
Untuk mengerjakan soal graph dengan baik, mahasiswa perlu memahami konsep dasar seperti vertex, edge, dan degree terlebih dahulu. Membuat sketsa graph dari soal juga sangat membantu dalam memahami hubungan antar simpul.
Selain itu, pahami jenis graph dan representasinya agar tidak keliru dalam menentukan solusi.
Kesimpulan
Kumpulan contoh soal graph pada struktur data beserta penyelesaian ini memberikan gambaran menyeluruh tentang konsep dan penerapan graph. Dengan memahami berbagai jenis soal graph, mahasiswa dapat meningkatkan kemampuan analisis dan pemahaman struktur data secara signifikan.
Latihan yang konsisten dan pemahaman konsep dasar akan memudahkan mahasiswa dalam mempelajari algoritma graph yang lebih kompleks di tahap selanjutnya.
Penulis:kiara salsabilla
Post Comment