Teori graf merupakan ilmu terapan yang banyak dimanfaatkan untuk menyelesaikan beberapa masalah. Pemberian nomor vertex pada topologi jaringan bertujuan untuk menghasilkan rute terpendek dan biaya minimum dari lintasan graf. Permasalahan ini dapat diselesaikan dengan minimum spanning tree (MST) menggunakan algoritma BFS Moore.
Misal G = (V,E) adalah sebuah topologi jaringan. 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 mengambil salah satu vertex awal. Selanjutnya menentukan nomor untuk tiap vertex pada minimum spanning tree jaringan graf berdasarkan jarak terjauh menurut algoritma Kamalesh-Srivatsa.
Dalam penelitian ini, dilakukan pemberian nomor pada MST topologi jaringan graf yang berbentuk graf wheel W_n, graf helm H_(n )dan graf lollipop L_(m,n). Didapatkan hasil penelitian berupa penomoran vertex dari MST jaringan graf berdasarkan pada urutan nilai eksentrisitas tiap vertex.
Kata kunci: topologi jaringan, minimum spanning tree, graf wheel, graf helm, graf lollipop.
