## MENENTUKAN MINIMUM SPANNING TREE PADA JARINGAN PLN DI KECAMATAN PADANG TIMUR KOTA PADANG

## DETERMINING MINIMUM SPANNING TREE IN PLN NETWORK IN PADANG SUB-DISTRICT EAST OF PADANG CITY
Iswan Rina 1§ , Dwi Sulistiowati 2 , Ilham D Rianjaya 3
1 Universitas Dharma Andalas, Padang, Indonesia [Email: iswanrina0@gmail.com]
2 Universitas Dharma Andalas, Padang, Indonesia [Email:sulistiowati.dwi.86@gmail.com]
3 Universitas Dharma Andalas Padang, Indonesia [Email: ilhamrianjaya@unidha.ac.id]
§ Corresponding Author

## Received 2019; Accepted 2019; Published 2019

## Abstraks
Pada  tulisan  ini  akan  ditunjukkan  penyelesaian  data  PLN  dengan  meminimumkan  jarak    atau menentukan jarak terpendek dari data PLN, dengan kata lain mencari minimum spanning tree dari model tree yang terbentuk Kata kunci : Data PLN, Jalur Graf, Jarak terpendek, Algoritma menentukan jaringan terpendek.

## Abstract
In this paper we will show the completion of PLN data by minimizing distance or determining the shortest  distance  from  PLN  data,  in  other  words  looking  for  a  minimum  spanning  tree  from  the tree model formed
Keywords : PLN data, graph path, shortest distance, algorithm determine the shortest network.

## 1. Pendahuluan
Pada  suatu  wilayah  yang  luas  terdapat berbagai  macam  jaringan.  Diantara  berbagai macam  jaringan  ini  terdapat  suatu  jaringan yaitu  jaringan listrik  yang  dimiliki  oleh  PLN. Jaringan  listrik  ini  dihubungkan  oleh  kabel- kabel  dimana  kabel  tersebut  berada  diatas tiang.  Kabel  ini  akan  menghubungkan  antar suatu  daerah  yang  satu  dengan  daerah  yang lainnya.
Dalam  masalah  jaringan  kabel  listrik  ini ditentukan  jarak  dari  masing-masing  kabel listrik antara daerah yang satu dengan daerah  yang  lainnya.  Pada  penelitian  ini, masing-masing  kabel  listrik  memiliki  jarak yang  berbeda  antara  tiang  kabel  listrik  yang satu  dengan  tiang  kabel  listrik  yang  lainnya. Maka  dengan  adanya  masalah  ini  dibutuhkan suatu cara untuk menyelesaikan jarak minimum  atau  menentukan  jarak  terpendek dari  tiap-  tiap  kabel  listrik  antar  daerah. Dengan meminimumkan jarak tersebut sehingga  dapat  diperoleh  jarak  terpendek  dari penggunaan  kabel  tersebut.  Setelah  diperoleh jarak  terpendek  maka  akan  dapat  diperoleh sebuah model dalam bentuk graf yaitu tree dan akan dicari minimum spanning tree.
Penelitian  ini  di  lakukan  di  wilayah  kota padang  karena  kota  Padang  merupakan  Ibu Kota  Provonsi  Sumatera  Barat  yang  memiliki infrastruktur  yang  banyak  dan  menggunakan jaringan PLN yang lebih layak dan lebih luas, sehingga di perlukan metode untuk menentukan  jarak  terpendek  dalam  jaringan PLN yang ada di Kota Padang.
Dalam  hal  ini  padang  Timur  di  pilih sebagai  objek  penelitian  karena  kurang efektifnya  penggunaan  jaringan  kabel  PLN Wilayah tersebut dengan menggunakan metode Graf
diharrapkan dapat
meminimumkan  penggunaan  jaringan  kabel sehinggan  akan  lebih  ekonomis  dan  praktis untuk diterapkan.

## 2. Landasan Teori
Menentukan  jaringan spaning tree pada jaringan PLN
Graf  adalah  suatu  pasangan  terurut  (V,E) terdiri dari himpunnan objek yang  disebut  dengan  vertex,
sedangkan  E  adalah  himpunan  berhingga atau  bolleh  kosong  yang  menghubungkan sepasang  titik  yangdiseut  dengan  edges (sisi).  Biasanya  E  dilambangkan  dengan
.  Sisi  dalam  graf  dapat ditulis dengan
.
Graf  G  dikatakan graf  terhubung jika untuk  setiap  dua  titik  di  G  ada  lintasan yang mneghubungkan kedua titik tersebut, jika  tidak  demikian  maka  G  disebut graf tidak terhubung. Jadi graf tidak terhubung, sekurang- kurangnya memuat dua komponen.
Graf  G  (V,E)  dikatakan  graf  dengan pembobotan,  apabila  ada  fungsi  bobot  w bernilai  positif  pada  sisi-sisi  dari  graf  G. Jadi sebesar  bobot  sisi  antara  titik ke-I dengan titik ke-j.
a. Matriks bobot sisi.
Matriks  bobot  sisi  dari  graf  dengan pembobotan  sebesar  matriks [ ] yang  entri-entrinya  sebesar ( ) jika sebesar  bobot sisiantara  titik  ke-I  dan  titik  ke-j  dan entri-entrinya sebesar , jika tidak ada sisi  yang  menghubungkan  titik  ke-I dan titik ke-j.
b. Matriks insiden bobot sisi Misalkan  pada  graf  berbobot  G diberikan  arah  sebarang,  titik-titik
diberi  nomor dan  sisi-sisi diberi nomor maka
matriks  insiden  bobot  sisi  dari  graf berarah  G  sebesar  matriks
[ ] yang  entri-entrinya  sebesar
( ) jika  sisi  ke-j  arahnya  keluar dari  titik  ke-I  , ( ) jika  sisi  ke-j arahnya  masuk  pada  titik  ke-i,  dan entrinya  sebesar jika  sisi  ke-j  tidak menempel pada titik ke-i.
Tree  adalah  graf  terhubung  yang  tidak mengandung cycle .  Jadi  tree  sebesar  graf sederhana  yang  tidak  mempunyai loop atau  sisi  parallel  yang  akan  membentuk cycle. Sebuah  graf    terhubung  dikatakan terhubung minimal, jika pada graf dihapus satu  sisi  sebarang  dari  sisi-sisinya,  maka graf  tersebut  menjadi  graf  yang  tidak terhubung.  Ini  berarti  graf  terhubung minimal  tidak  mempunyai  cycle.  Sifat- sifat dari Tree dapat dilihat dibawah ini:
a. Sebuah tree dengan n titik mempunyai sisi.
b. Sebuah  graf  G  dengan  n  titik, sisi  dan  tidak  ada  cycle  sebesar  graf terhubung.
c. Jika  graf  G  adalah  sebuah  tree  dengan p titik dan q sisi maka
.
Tree  T  dikatakan  spaning  tree  dari  graf terhubung  G  jika  T  subgraf  dari  G  dan  T memuat  semua  titik  G. Spaning  tree merupakan  graf  paling  besar (dengan banyaknya  sisi  maksimum) dari  semua  tree di  dalam  G  atau  dengan  kata  lain spaning tree sebesar  subgraf  minimal  yang menghubungkan
semua titik G.
Spaningtree hanya didefinisikan pada graf terhubung,  karena tree selalu  terhubung. Pada  graf  tidak  terhubung  dengan n titik
tidak  dapat  dicari  subgraf  dengan n titik. Koleksi  dari tree-  tree disebut forest. Setiap  komponen  dari  graf  terhubung bagaimanapun  mempunyai spaning  tree. Jadi  graf  terhubung  dengan k komponen memunyai spaning forest yang terdiri  dari k  spaning  tree. Menentukan spaning  tree dari  sebuah  graf  terhubung  G  sebesar sederhana. Jika G mempunyai cycle, maka G  itu  sendiri  yang  merupakan spaning tree . Jika G mempunyai cycle, maka hapus satu  sisi  dari cycle tersebut  dan  hasilnya masih  graf  terhubung.  Jika  banyak cycle maka ulangi
operasi  tersbut sampai  sebuah sisi  dari cycle terakhir  dihapus  dan  hasilnya  masih graf  terhubung.  Dengan  demikian  graf  G tanpa cycle memuat suatu titik dari G. Sisi yang  ada  dalam spaning  tree  T disebut branch dari  T  dan  sisi  yang  tidak  ada  di dalam spaning  tree disebut chord. Setiap graf  terhubung  paling  sedikit  mempunyai satu spaning tree merupakan sipat spaning tree.  Jarak  terpendek  yang  diperoleh  dari spaning  tree  disebut  dengan  minimum spaning tree.

## 3. Hasil Dan Pembahasan

## Data pada jaringan PLN
Pada  suatu  daerah  yang  luas  terdapat berbagai  macam  jaringan.  Diantara  berbagai macam  jaringan  ini  terdapat  suatu  jaringan yaitu  jaringan listrik  yang  dimiliki  oleh  PLN. Jaringan  listrik  ini  dihubungkan  oleh  kabel- kabel  dimana  kabel  tersebut  berada  diatas tiang.  Kabel  ini  akan  menghubungkan  antar suatu  daerah  yang  satu  dengan  daerah  yang lainnya.  Di  dalam  jaringan  kabel  PLN  ini ditentukan  jarak  dari  masing  –  masing  kabel
yang satu dengan kabel yang lainnya. Apabila jarak suatu kabel PLN antara daerah yang satu ke  daerah  yang  lain  membutuhkan  banyak kabel  secara  langsung  maka  kabel  yang dibutuhkan sangat panjang untuk menghubungkan antara daerah tersebut.
Sehingga  akan  mengeluarkan  dana  atau  biaya yang  sangat  banyak.  Oleh  sebab  itu  maka dibutuhkan  suatu  cara  untuk  menyelesaikan masalah tersebut.
Salah satu cara dapat dilakukan dengan meminimumkan  jarak  kabel  PLN  atau menentukan  jarak  terpendek  dari  jaringan kabel PLN antar daerah supaya diperoleh jarak yang  lebih  kecil  atau  pendek  antar  daerah tersebut.
Dalam  menyelesaikan  masalah  untuk meminimumkan jarak kabel PLN diatas, maka dibutuhkan  suatu  bentuk  model  penyelesaian berdasarkan  dengan  teori  graf.  Berdasarkan dengan  teori  graf  tersebut,  masalah  dari  jarak kabel  PLN  ini  dapat  diselesaikan  terlebih dahulu  dengan  model  penyelesaian  dalam bentuk matriks.
Pada pembahasan penelitian ini penulis memperoleh  suatu  data  tentang  jarak  kabel PLN  antar  daerah  yang  satu  dengan  daerah yang  lain.  Di  mana  data  tersebut  terlebih dahulu  akan  dibuat  dalam  bentuk  model sebuah matriks yang berukuran
Berikut  bentuk  data  pada  jaringan  kabel PLN :
Gambar 1. Tabel Data Kabel PLN
Sebagai  contoh  dari  data  pada  tabel  diatas, dapat  ditentukan  nilai  dari  model  pada  data diatas  yaitu  dapat  dilihat  pada  nilai dengan nilai .  Di  mana  nilai dengan  nilai sebesar jarak dari daerah  ke – i dengan daerah ke – j yaitu dengan jarak 0. Dapat juga di lihat  dari  contoh  yang  lainnya  yaitu  dari bentuk matriks berikut :
Entri  dari  data  dalam  bentuk  matriks
berarti  jarak  dari  daerah dengan daerah memliki jarak sebesar 624. Entri dari  data  dalam  bentuk  matriks berarti  jarak  dari  daerah dengan  jarak memiliki jarak sebesar 666.
Untuk selanjutnya akan ditentukan titik pusat  yaitu  titik  –  titik  di  mana  titik  lainnya terhubung  langsung  ke  titik  pusat  tersebut.
Maka  secara  teori  graf  titik  –  titik  ini mempunyai derajat lebih dari 2.
Berdasarkan  dengan  penelitian  ini maka  akan  dibangun  sebuah  jaringan  kabel
PLN dengan titik
pusat
.  Di  mana  titik – titik. Ini dikatakan sebagai titik pusat dari jaringan  kabel  PLN.  Sedangkan  titik  –  titik lainnya  akan  terhubung  secara  langsung dengan  salah  satu  titik  pusat  dari  jaringan kabel PLN tersebut.
Pembagian  data    ini  berdasarkan  pada jarak terpendek dari setiap titik  – titik lainnya ke titik pusat dari jaringan kabel PLN di  atas. Maka  dari  pembagian  data  tersebut  akan diperoleh  sebuah  model  dalam  bentuk  graf yaitu tree.
Di  mana  langkah  –  langkah  yang  dapat  di lakukan sebelum terbentuk Tree dapat di lihat sebagai berikut :
1. Terlebih  dahuli  diketahui  graf lengkap  G  dengan  pembobotan  n titik.
2. Buatlah  matriks  ketetanggaan  dari graf  G  tersebut  yang  berukuran seperti  yang  terlihat  pada tabel 1.
3. Diketahui sebagai pusat dari jaringan,  misalkan  titik
4. Selidiki  semua  titik  yang  ada  pada graf  G  yang  tidak  menjadi  titik pusat,
Missal : dengan Hitung  jarak dengan
Ambil sisi untuk
jarak yang terkecil atau terpendek 5. Proses  diulang  lagi  dengan  semua titik  –  titik  lainnya  yang  sudah terhubung dengan titik – titik kabel PLN yang berpusat di
Jadi  dari  langkah  –  langkah  di  atas  dapat membuktikan  data  yang  sudah  ada,  sehingga dari  pembuktian data tersebut dapat diperoleh sebuah  jalur  graf  berbentuk Tree, yang  dapat dilihat dari gambar  dibawah ini :
Gambar 2. Jalur Graf
Aplikasi Untuk Menentukan Jaringan Terpendek Pada Data Kabel PLN
Dari Algortima sebelumnya dapat diselesaikan data PLN diatas dengan cara di bawah ini:
1. Titik
a. Bila dihubungkan  dengan diperoleh  jarak  sebesar  630  satuan jarak b. Bila dihubungkan  dengan diperoleh  jarak  sebesar  757  satuan jarak c. Bila dihubungkan  dengan diperoleh  jarak  sebesar  743  satuan jarak d. Bila dihubungkan  dengan diperoleh  jarak  sebesar  741  satuan jarak e. Bila dihubungkan  dengan diperoleh  jarak  sebesar  696  satuan jarak
f. Bila dihubungkan  dengan diperoleh  jarak  sebesar  697  satuan jarak g. Bila dihubungkan  dengan diperoleh  jarak  sebesar  694  satuan jarak Dari  hasil  diatas,  bila dihubungkan dengan titik – titik pusat maka  terlihat
bahwa  jarak  yang  paling  pendek  dihasilkan dari  jarak  antara  titik dengan  titik yaitu 630.  Dengan  demikian  titik terhubung secara  langsung  dengan  titik Sedangkan dengan  titik  pusat  yang  lainnya tidak terhubung. Dalam hal ini jarak titik dengan titik sebesar  630.  Berdasarkan  teori  graf,
berarti  semua  sisi  yang  menghubungkan  titik dengan  titik
dihapus karena nilai jaraknya tidak menghasilkan nilai minimum.
2. Titik
a. Bila dihubungkan  dengan diperoleh  jarak  sebesar  616  satuan jarak b. Bila dihubungkan  dengan diperoleh  jarak  sebesar  653  satuan jarak c. Bila dihubungkan  dengan diperoleh  jarak  sebesar  646  satuan jarak d. Bila dihubungkan  dengan diperoleh  jarak  sebesar  645  satuan jarak e. Bila dihubungkan  dengan diperoleh  jarak  sebesar  636  satuan jarak f. Bila dihubungkan  dengan diperoleh  jarak  sebesar  639  satuan jarak g. Bila dihubungkan  dengan diperoleh  jarak  sebesar  637  satuan jarak Dari  hasil  diatas,  bila dihubungkan dengan titik – titik pusat maka  terlihat
bahwa  jarak  yang  paling  pendek  dihasilkan dari  jarak  antara  titik dengan  titik yaitu
616.  Dengan  demikian  titik
terhubung secara  langsung  dengan  titik
Sedangkan dengan  titik  pusat  yang  lainnya tidak terhubung. Dalam hal ini jarak titik dengan titik sebesar  616.  Berdasarkan  teori  graf, berarti  semua  sisi  yang  menghubungkan  titik
dengan  titik
dihapus karena nilai jaraknya tidak menghasilkan nilai minimum.
Dengan cara yang sama penyelesaiannya sama dengan diatas untuk titik-titik berikut dibawah ini:
3. Titik
4. Titik
5. Titik
6. Titik
7. Titik
8. Titik
9. Titik
10. Titik
11. Titik
12. Titik
13. Titik
14. Titik
15. Titik
16. Titik
17. Titik
18. Titik
19. Titik
20. Titik
21. Titik
22. Titik
23. Titik
24. Titik
25. Titik
26. Titik
27. Titik
28. Titik
Dari  langkah-langkah  penyelesaian diatas  dapat  diketahui  titik-titik  mana  saja yang terhubung dengan titik pusat dan pada  jaringan kabel  PLN.  Sehingga  dengan  diketahuinya titik-titik  yang  terhubung  tersebut  dapat diketahui  titik-titik  mana  saja  yang  memiliki jarak terpendek dengan titik pusat diatas.
Dengan  diketahuinya  jarak  terpendek dari pengujian masing-masing titik pusat kabel PLN  dengan  titik-titik  lainnya,maka  dapat dibentuk  sebuah  jaringana  yang  dalam  teori graf disebut Tree .

## 4. Kesimpulan Dan Saran
Pada masalah graf jaringan PLN dapat ditentukan minimum jarak atau jarak terpendek  dari  tiap  –  tiap  kabel  PLN  antar daerah.  Jika  dalam  menyelesaikan  masalah meminimumkan  jarak  kabel  PLN  tersebut dibutuhkan  suatu  bentuk  model  penyelesaian dengan  teori  graf  dapat  diselesaikan  dalam bentuk  matriks  yang  berukuran yang telah  ditentukan  datanya.  Darai  data  tersebut diperoleh  sebuah  Tree  dengan  menggunakan langkah  –  langkah  untuk  menentukan  jarak terpendek.

## 5. Ucapan Terima Kasih
Syukur  alhamdulillah  penulis  ucapkan kepada  Allah  Swt,  shalawat  dan  salam  tak luput  penulis  hadiahkan  kepada  baginda rasulullah  Muhammad  Saw  dan  tak  lupa  juga ucapan  terima  kasih  penulis  kepada  semua pihak  yang  telah  membantu  dalam  penulisan artikel  ini,semoga  artikel  ini  bermanfaat  bagi kita semua terutama dalam bidang matematika khususnya dan pendidikan pada umumnya.

## Daftar Pustaka
[1]  C.L.  Liu.  1995. Dasar-dasar  Matematika Diskrit  Edisi  Kedua .    PT.  Gramedia Pustaka Utama. Jakarta.
[2]  Fletcher,  P,  H,  Hoyle  and  C.  W.  Patty. 1991. Foundation of Discrite Mathematics . PWS  –  KENT  Publishing  Company, Buston.
[3]  Munir,  R.  2001. Matematika  Diskrit  Edisi Kedua. Informatika, Bandung.
[4]  Deo,  Narshing.  1986. Graph  Teory  With Applications to Engineering and Computer Science , Prentice Hall, New Delhi.
[5]  Harary,  Frank.  1969. Graph  Teory . Addison  –  Wesley  Publishing  Company. Fhilipina.
[6] Jhonsonbaugh, Richard. 2002. Matematika Diskrit Jilid 2 .  Prenhallindo. Jakarta.
[7]  Lipschutz,  Seymoure  and  Lipson,  Marc Lars. 2002. Matematika Diskrit 2 .
Penerbit Salemba Teknika. Jakarta.