Penggunaan prosedur Edge Exchange dan metode matriks untuk menentukan jumlah Spanning Tree pada Graph terhubung

ABSTRAK

Permasalahan-permasalahan yang sering terjadi dalam kehidupan sehari-hari selalu berkaitan dengan atematif-altematif. Cara menyelesaikan alternatif tersebut dengan bantuan tree (spanning tree). Terjadinya spanning tree dari graph terhubung menjadi penting untuk masalah-masalah yang tidak memperhitungkan jarak. Skripsi ini menyajikan cara menentukan jumlah spanning tree pada graph terhubung baik berarah maupun tidak berarah dengan menggunakan prosedur edge exchange dan metode matriks.

Prosedur edge exchange adalah pertukaran sisi karena telah diketahui bahwasanya spanning tree dari suatu graph pada umumnya tidaklah tunggal. Metode matriks adalah kumpulan bilangan-bilangan (elemen-elemen) yang disusun menurut baris dan kolom sehingga berbentuk empat persegi panjang dimana panjang lebarnya ditunjukkan oleh banyaknya kolom dan baris.

Dalam menghitung jumlah spanning tree dengan prosedur edge exchange pada graph terhubung baik berarah maupun tidak berarah langkahnya dengan menambahkan sisi pada spanning tree awal dan menghapus sisi yang lain agar tidak terjadi cycle. Sedangkan dengan metode matriks pada graph terhubung tidak berarah langkahnya adalah mencari matriks insidensinya A dan transpose A، terlebih dahulu kemudian dicari determinannya Det (AA٠). Matriks In Degree digunakan untuk menentukan jumlah spanning tree pada graph terhubung berarah melalui determinan (Krr) dimana K merupakan matriks in degree graph terhubung berarah dengan r=l.

Prosedur edge exchange kelebihannya mudah dan praktis dalam menentukan jumlah spanning tree untuk graph terhubung baik berarah maupun tidak berarah dan kelemahannya tidak dapat mengetahui jumlah spanning treenya secara langsung dan tidak menghasilkan bentuk-bentuk majomya. Sedangkan untuk metode matriks kelebihannya adalah dapat menentukan secara langsung jumlah spanning treenya dan dapat diketahui bentuk-bentuk majomya. Kelemahannya adalah membutuhkan waktu yang lama dan memerlukan ketelitian khusus, selain itu untuk matriks dengan ordo yang lebih dari tiga dalam mencari determinannya harus menggunakan eselon baris.