PENGGUNAAN DEKOMPOSISI SISI GRAF PADA MASALAH PENGOPTIMUMAN

Abstract

Dekomposisi sisi merupakan salah satu pendekatan dalam teori graf yang digunakan untuk membagi himpunan sisi suatu graf menjadi subgraf-subgraf yang lebih sederhana sehingga struktur jaringan dapat dianalisis secara lebih efisien. Penelitian ini bertujuan memodelkan dan menyelesaikan beberapa masalah pengoptimuman dengan memanfaatkan berbagai bentuk dekomposisi sisi, yaitu matching, subgraf planar, spanning subgraph dan spanning tree. Metode yang digunakan meliputi studi literatur terhadap konsep dasar teori graf dan analisis terapan pada beberapa kasus nyata. Hasil penelitian menunjukkan bahwa setiap jenis dekomposisi sisi memiliki keunggulan dalam menyelesaikan kategori masalah tertentu: matching efektif untuk penjadwalan dan alokasi sumber daya, subgraf planar sesuai untuk perancangan jaringan tanpa tumpang tindih, spanning subgraph dapat membagi sistem menjadi beberapa bagian operasional yang tetap terhubung, dan spanning tree memberikan solusi jalur minimum yang efisien pada suatu jaringan. Pemanfaatan dekomposisi sisi terbukti mampu mempermudah proses pemodelan, mengurangi kompleksitas permasalahan, serta memberikan solusi optimal pada berbagai konteks pengoptimuman.