Pemberian Nomor Vertex Pada Minimum Spanning Tree Dari Graf Matahari, Graf Lengkap K-Partit, Dan Graf Korona Hasil Kali Graf Bintang

Oleh :
Dimas Ari Kurniawan Perdana - M0108085 - Fak. MIPA

Minimum spanning tree menggunakan edge untuk menghubungkan setiap vertex bertujuan menghasilkan rute terpendek dari jaringan graf. Jaringan graf yang efisien adalah jaringan graf yang memberikan hasil maksimal dengan biaya minimal. Misal G = (V, E) adalah sebuah jaringan graf. Jarak dari vertex u ke v di G adalah panjang lintasan terpendek dari vertex u ke v dalam G, dinotasikan dengan d(u, v). Eksentrisitas dari vertex u adalah jarak terjauh dari vertex u ke vertex lain, dinotasikan dengan e(u). Untuk membentuk jaringan graf yang efsien terlebih dahulu dibentuk minimum spanning tree dari jaringan graf menggunakan algoritma Breadth First Search (BFS) Moore dengan u_1 sebagai root (vertex awal). Selanjutnya menentukan nomor untuk tiap vertex pada minimum spanning tree jaringan graf berdasarkan jarak terjauh menurut algoritma Kamalesh-Srivatsa. Tujuan dari penelitian ini adalah membentuk model minimum spanning tree jaringan graf yang efisien dalam menempuh jarak vertex terjauh dengan memberikan nomor urut untuk tiap vertex. Hasil penelitian menunjukkan bahwa dari bentuk minimum spanning tree graf matahari S_n dengan n > 3, graf lengkap k-partit K_(n_1, n_2, …,? n?_k ) dengan k = 2 dan 3, dan graf korona hasil kali graf bintang B_m?B_n dengan m dan n > 3, dengan root u_1 diperoleh penomoran untuk masing-masing vertex berdasarkan pada urutan besarnya eksentrisitas dari tiap vertex.