Teori Graf
Konsep Dasar
Beberapa konsep dasar yang harus dikuasai. Berikut adalah beberapa konsep yang perlu dipahami:
- Graf: Graf adalah struktur data yang terdiri dari simpul-simpul (vertex) yang terhubung oleh sisi-sisi (edge). Setiap sisi menghubungkan dua simpul dalam graf.
- Simpul (Vertex): Simpul atau vertex adalah elemen-elemen dasar dalam graf. Mereka mewakili entitas atau objek dalam graf. Contohnya, dalam graf sosial, setiap simpul bisa mewakili individu, sedangkan dalam graf jalan, simpul bisa mewakili persimpangan.
- Sisi (Edge): Sisi atau edge adalah hubungan antara dua simpul dalam graf. Sisi bisa memiliki arah (graf terarah) atau tidak memiliki arah (graf tak terarah). Jika sisi memiliki arah, maka urutan simpul yang terhubung memiliki arti yang berbeda.
- Graf Terarah (Directed Graph): Graf terarah adalah graf di mana setiap sisi memiliki arah atau panah yang menunjukkan arah hubungan antara simpul-simpul. Misalnya, jika ada sisi dari simpul A ke simpul B, tetapi tidak ada sisi dari simpul B ke simpul A.
- Graf Tak Terarah (Undirected Graph): Graf tak terarah adalah graf di mana sisi-sisi tidak memiliki arah. Hubungan antara simpul-simpul bersifat saling menghubungkan dua arah. Jika ada sisi yang menghubungkan simpul A dan simpul B, maka ada pula sisi yang menghubungkan simpul B dan simpul A.
- Graf Siklik (Cyclic Graph) dan Graf Tak Siklik (Acyclic Graph): Graf siklik adalah graf yang memiliki siklus, yaitu rangkaian sisi yang membentuk jalur yang kembali ke simpul awal. Graf tak siklik adalah graf yang tidak memiliki siklus. Dalam graf tak siklik, simpul-simpul dapat dihubungkan oleh lintasan tanpa membentuk siklus.
- Representasi Graf: Ada beberapa cara untuk merepresentasikan graf, termasuk matriks ketetanggan (adjacency matrix) dan daftar ketetanggan (adjacency list). Matriks ketetanggan menggunakan matriks untuk merepresentasikan hubungan antara simpul-simpul, sedangkan daftar ketetanggan menggunakan struktur data daftar untuk menyimpan hubungan antara simpul-simpul.
Jenis-jenis Graf
Dalam teori graf, terdapat beberapa jenis graf yang memiliki karakteristik dan sifat khusus. Berikut ini adalah beberapa jenis graf yang umum:
Graf Sederhana (Simple Graph): Graf sederhana adalah graf yang tidak memiliki sisi ganda (multiple edges) dan simpul yang terhubung oleh sisi dengan dirinya sendiri (loop). Setiap pasangan simpul yang terhubung oleh sisi dalam graf sederhana dianggap sebagai tetangga satu sama lain.
Graf Berarah (Directed Graph): Graf berarah, juga dikenal sebagai digraf, adalah graf di mana setiap sisi memiliki arah. Sisi dalam graf berarah memiliki panah yang menunjukkan arah hubungan antara dua simpul. Pada graf berarah, pasangan simpul (u, v) dan (v, u) dapat terhubung oleh sisi dengan arah yang berbeda, atau hanya satu dari keduanya.
Graf Berbobot (Weighted Graph): Graf berbobot adalah graf di mana setiap sisi memiliki bobot atau nilai terkait. Bobot ini digunakan untuk menyatakan atribut tambahan pada sisi, seperti jarak, biaya, waktu, atau kapasitas. Graf berbobot digunakan untuk memodelkan masalah yang melibatkan optimisasi berdasarkan bobot, seperti mencari jalur terpendek atau pohon merentang minimum.
Graf Bipartit (Bipartite Graph): Graf bipartit adalah graf yang himpunan simpulnya dapat dibagi menjadi dua himpunan nonkosong, di mana setiap sisi menghubungkan simpul dari himpunan yang berbeda. Artinya, tidak ada sisi yang menghubungkan dua simpul dalam himpunan yang sama. Graf bipartit digunakan untuk memodelkan hubungan dua kelompok yang saling terkait, seperti hubungan antara mahasiswa dan mata kuliah.
Graf Siklik (Cyclic Graph): Graf siklik adalah graf yang memiliki satu atau lebih siklus, yaitu serangkaian sisi yang membentuk lintasan tertutup yang kembali ke simpul awalnya. Graf siklik dapat membentuk jalur kembali ke simpul awal melalui serangkaian sisi yang berbeda, atau melalui serangkaian simpul yang berbeda.
Graf Lintas (Acyclic Graph): Graf lintas, juga dikenal sebagai graf tidak siklik, adalah graf yang tidak memiliki siklus. Graf lintas dapat digunakan untuk mewakili urutan kejadian atau hubungan hierarkis yang tidak memungkinkan adanya siklus.
Graf Terarah Acyclic (Directed Acyclic Graph/DAG): Graf terarah acyclic, disingkat sebagai DAG, adalah graf berarah yang tidak memiliki siklus. DAG sering digunakan untuk memodelkan dependensi antara tugas atau peristiwa yang saling terkait dan tidak boleh memiliki siklus, seperti dalam jadwal proyek atau pengolahan data.
Graf Pohon (Tree): Graf pohon adalah graf berarah atau tidak berarah yang tidak memiliki siklus dan setiap pasangan simpul dapat dihubungkan oleh tepat satu jalur. Graf pohon memiliki simpul akar yang menjadi titik awal dan simpul daun yang menjadi titik akhir dalam struktur hierarkis. Graf pohon digunakan untuk memodelkan struktur hirarki, seperti struktur organisasi atau struktur folder pada komputer.
Setiap jenis graf ini memiliki sifat dan karakteristik yang unik, dan mereka digunakan dalam berbagai aplikasi dan masalah di berbagai bidang, termasuk matematika, ilmu komputer, jaringan, optimisasi, dan lainnya.
Pohon
Pohon (tree) merupakan bagian dari teori graf. Dalam teori graf, pohon adalah jenis graf khusus yang memiliki sifat-sifat tertentu. Secara umum, pohon dapat didefinisikan sebagai graf tak terarah yang terhubung dan tidak memiliki siklus.
Pohon memiliki karakteristik berikut:
Graf tak terarah: Sisi-sisinya tidak memiliki arah. Hubungan antara simpul-simpul bersifat saling menghubungkan dua arah.
Terhubung: Setiap pasang simpul dalam pohon dapat dihubungkan oleh setidaknya satu jalur.
Tidak memiliki siklus: Tidak ada jalur yang membentuk siklus tertutup. Artinya, tidak mungkin ada jalur yang membentuk lintasan yang kembali ke simpul awal.
Pohon memiliki struktur hirarkis dengan simpul akar (root node) dan simpul-simpul anak (child nodes). Simpul akar adalah simpul yang tidak memiliki simpul induk (parent node), sedangkan simpul anak adalah simpul yang memiliki simpul induk. Selain itu, pohon juga dapat memiliki tingkat (level) yang menunjukkan kedalaman simpul dalam pohon.
Studi tentang pohon memiliki peran penting dalam teori graf dan memiliki aplikasi luas dalam berbagai bidang, termasuk algoritma, struktur data, optimisasi, dan pemodelan masalah. Beberapa konsep terkait pohon yang sering dibahas dalam teori graf adalah traversal (penjelajahan) pohon, pencarian jalur terpendek dalam pohon, dan konstruksi pohon minimal (minimum spanning tree).
Dalam banyak literatur, teori pohon sering dipelajari sebagai subbagian dari teori graf atau sebagai topik tersendiri dalam teori graf tergantung pada konteks pembahasannya. Namun, secara umum, pohon adalah konsep yang terkait erat dengan teori graf.
Berikut ringkasan materi Teori Graf
