Pengertian graph theory
**Graph theory** adalah cabang matematika yang mempelajari tentang grafik, yaitu struktur yang digunakan untuk memodelkan pasangan hubungan antara objek-objek. Grafik terdiri dari **simpul (vertices)** dan **sisi (edges)** yang menghubungkan pasangan simpul.
### Komponen Dasar dalam Graph Theory:
1. **Simpul (Vertex) atau Titik:**
- Simpul adalah objek dasar dalam sebuah grafik. Biasanya dilambangkan dengan huruf atau angka.
2. **Sisi (Edge):**
- Sisi adalah garis yang menghubungkan dua simpul dalam grafik. Sisi bisa berupa garis tunggal yang menghubungkan dua simpul (grafik tak berarah) atau memiliki arah dari satu simpul ke simpul lain (grafik berarah).
3. **Grafik Tak Berarah (Undirected Graph):**
- Dalam grafik tak berarah, sisi-sisi tidak memiliki arah tertentu. Artinya, jika ada sisi yang menghubungkan simpul A ke B, maka juga ada sisi yang menghubungkan simpul B ke A.
4. **Grafik Berarah (Directed Graph):**
- Dalam grafik berarah, sisi-sisi memiliki arah tertentu. Sisi yang menghubungkan simpul A ke B tidak sama dengan sisi yang menghubungkan simpul B ke A.
5. **Lintasan (Path):**
- Lintasan adalah urutan simpul yang terhubung oleh sisi-sisi. Lintasan bisa sederhana (tanpa mengulang simpul atau sisi) atau kompleks.
6. **Siklus (Cycle):**
- Siklus adalah lintasan yang kembali ke simpul awalnya, membentuk lingkaran.
7. **Grafik Terhubung (Connected Graph):**
- Sebuah grafik dikatakan terhubung jika ada lintasan antara setiap pasangan simpul dalam grafik.
8. **Grafik Tak Terhubung (Disconnected Graph):**
- Jika terdapat setidaknya dua simpul dalam grafik yang tidak dapat dihubungkan oleh lintasan, maka grafik itu dikatakan tidak terhubung.
9. **Grafik Lengkap (Complete Graph):**
- Grafik lengkap adalah grafik di mana setiap simpul terhubung ke setiap simpul lainnya oleh sisi yang berbeda.
### Contoh Grafik dalam Graph Theory:
1. **Grafik Jaringan Sosial:**
- Simpul-simpul mewakili orang, dan sisi-sisi mewakili hubungan antara mereka, seperti "teman" di media sosial.
2. **Grafik Jaringan Komputer:**
- Simpul-simpul mewakili komputer atau router, dan sisi-sisi mewakili koneksi jaringan di antara mereka.
3. **Grafik Transportasi:**
- Simpul-simpul mewakili titik-titik (misalnya, kota atau stasiun), dan sisi-sisi mewakili jalan atau rute yang menghubungkan titik-titik tersebut.
### Teorema dan Konsep Penting dalam Graph Theory:
1. **Teorema Euler:**
- Diberikan grafik tak berarah, sebuah lintasan yang melewati setiap sisi tepat sekali (disebut sirkuit Euler) ada jika dan hanya jika setiap simpul memiliki derajat genap.
2. **Teorema Kuratowski:**
- Grafik planar (grafik yang dapat digambar di bidang tanpa memotong sisi) dapat diidentifikasi dengan tidak mengandung subgraf yang merupakan graf K5 (grafik lengkap dengan lima simpul) atau K3,3 (grafik dua bagian lengkap dengan tiga simpul di setiap bagian).
3. **Pewarnaan Graf (Graph Coloring):**
- Pewarnaan graf adalah penugasan warna ke simpul graf sehingga tidak ada dua simpul yang berdekatan memiliki warna yang sama. Ini sering digunakan dalam masalah penjadwalan.
### Aplikasi Graph Theory:
1. **Jaringan Komputer:**
- Digunakan untuk memodelkan dan menganalisis jaringan komputer, rute internet, dan optimisasi jaringan.
2. **Analisis Rangkaian Listrik:**
- Digunakan untuk memodelkan dan menganalisis sirkuit listrik.
3. **Optimisasi:**
- Digunakan dalam masalah optimisasi, seperti menentukan rute terpendek atau masalah jembatan Konigsberg.
4. **Jaringan Sosial:**
- Digunakan untuk memodelkan dan menganalisis hubungan sosial, penyebaran informasi, dan epidemi.
5. **Ilmu Komputer:**
- Digunakan dalam algoritma pencarian, representasi data, pemrograman dinamis, dan lain-lain.
**Graph theory** sangat luas dan penting, karena banyak masalah di dunia nyata dapat dimodelkan sebagai grafik, membuatnya relevan dalam berbagai disiplin ilmu, termasuk ilmu komputer, ekonomi, dan biologi.
0 komentar:
Posting Komentar