PENERAPAN ALGORITMA PRIM PADA JARINGAN LISTRIK PERUMAHAN PT INALUM (Studi Kasus)

PENERAPAN ALGORITMA PRIM PADA JARINGAN LISTRIK PERUMAHAN PT INALUM

(Studi Kasus)

SKRIPSI

RAYI SYAHFITRI 040803028 MURNI

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009

Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

PENERAPAN ALGORITMA PRIM PADA JARINGAN LISTRIK PERUMAHAN PT INALUM (Studi Kasus)

SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains

RAYI SYAHFITRI 040803028 MURNI

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009 Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

PERSETUJUAN

Judul PADA

Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas ILMU

:

PENERAPAN ALGORITMA PRIM

: : : : : :

JARINGAN LISTRIK PERUMAHAN PT INALUM (Studi Kasus) SKRIPSI RAYI SYAHFITRI 040803028 SARJANA (S1) MATEMATIKA MATEMATIKA FAKULTAS MATEMATIKA DAN PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA

Medan, 27 Februari 2009 Komisi Pembimbing : Pembimbing 2

Drs. Pangarapen Bangun, M.Si M.Si NIP. 131474680

Pembimbing 1

Drs. Ujian Sinulingga, NIP. 131757011

Diketahui oleh Departemen Matematika FMIPA USU Ketua,

Dr. Saib Suwilo, MSc NIP. 131796149


PERNYATAAN i PENERAPAN ALGORITMA PRIM PADA JARINGAN LISTRIK PERUMAHAN PT INALUM (Studi Kasus)

SKRIPSI

Penulis mengakui bahwa skripsi ini adalah hasil kerja penulis sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan, 27 Februari 2009

RAYI SYAHFITRI 040803028


PENGHARGAAN ii Alhamdulillahirabbil’alamin, segala puji syukur kehadirat ALLAH SWT yang telah memberikan berbagai rahmat dan nikmat-Nya kepada seluruh makhluk hidup, sehingga penulis dapat menyelesaikan skripsi ini dengan sebaik-baiknya, dan tidak lupa salawat dan salam untuk Nabi besar Muhammad SAW. Skripsi ini merupakan salah satu mata kuliah wajib yang harus diselesaikan oleh seluruh mahasiswa/i Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara. Pada Skripsi ini penulis melakukan studi kasus tentang Perbandingan Keoptimalan Antara Jaringan Listrik Yang Telah Terpasang Di Perumahan PT Inalum Dengan Metode Pemasangan Jaringan Listrik Menggunakan Algoritma Prim. Dalam kesempatan ini, penulis mengucapkan terima kasih yang sebesarbesarnya kepada: 1. Bapak Dr. Eddy Marlianto, M.Sc selaku Dekan FMIPA USU. Bapak Dr. Saib Suwilo, M.Sc dan Bapak Drs. Henry Sitepu, M.Si selaku Ketua dan Sekretaris Departemen Matematika di FMIPA USU. 2. Bapak Drs. Ujian Sinulingga, M.Si selaku pembimbing I penulis dan Bapak Drs. Pangarapen Bangun, M.Si selaku pembimbing II penulis yang telah membimbing dan mengarahkan penulis serta kebaikkannya untuk meluangkan waktu, tenaga, pikiran dan bantuannya sehingga skripsi penulis ini dapat selesai tepat waktu. 3. Bapak Drs. H Haluddin Panjaitan, M.Si dan Bapak Drs. Henry Rani Sitepu, M.Si selaku penguji skripsi. 4. Seluruh Staf Pengajar Matematika di FMIPA USU 5. Seluruh Pegawai departemen Matematika FMIPA USU. 6. Ayahanda dan Ibunda tercinta yang telah memberikan dukungan penuh kepada penulis. Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

7. Nenek tercinta, abang, dan adik-adik penulis yang telah membantu dalam bentuk apapun. 8. Taufiq Afandi yang selalu mendampingi penulis di kampus tanpa lelah dalam menyelesaikan skripsi ini. 9. Etika, Fitrie, Noya dan teman-teman iii yang lainnya. Insya’Allah segala bentuk bantuan yang telah diberikan mendapat balasan yang jauh lebih baik dari ALLAH SWT. Sebagai seorang mahasiswa yang menyadari bahwa masih banyak terdapat kekurangan dalam menyelesaikan skripsi ini. Oleh karena itu kritik dan saran yang membangun sangat diharapkan demi perbaikkan tulisan ini.

Medan, 27 Februari 2008 Penulis

Rayi Syahfitri


ABSTRAK iv Skripsi ini bersifat studi kasus sebagai penerapan algoritma Prim pada suatu jaringan listrik disebuah perumahan Kabupaten Asahan, yaitu perumahan PT Inalum khususnya blok-P. Permasalahan yang akan diulas disini adalah panjang kabel listrik yang telah terpasang di blok-P adalah 4331.95 meter dan panjang kabel listrik yang diperoleh dengan menggunakan algoritma Prim adalah 3862.04 meter. Keoptimalan panjang kabel yang terpasang inilah yang akan

lebih

dititikberatkan

dalam

skripsi

ini.

Jaringan

listrik

akan

direpresentasikan sebagai connected, weighted dan undirected graph. Untuk teori-teori graph dan beberapa pendukungnya akan dijelaskan dalam skripsi ini.


ABSTRACT v This Skripsi have the character of case study as applying of algorithm Prim at one particular electrics network a housing of Grindings Regency, that is housing of PT Inalum specially blok-P. Comparison to be commented here is length of power cable which have been attached in blok-P is 4331.95 metre and length of power cable obtained by using algorithm Prim is 3862.04 metre. Optimal of cable length attached this will be more dititikberatkan in this skripsi. Electrics network of direpresentasikan as connected, weighted and undirected graph. For the theory of graph and some its supporter will be explained in this skripsi.


DAFTAR ISI vi

Halaman PERSETUJUAN

i

PERNYATAAN

ii

PENGHARGAAN

iii

ABSTRAK

v

ABSTRACT

vi

DAFTAR ISI

vii

DAFTAR GAMBAR

ix

BAB 1.

PENDAHULUAN

1

1.1. Latar Belakang Masalah

1

1.2. Perumusan Masalah

2

1.3. Batasan Masalah

2

1.4. Tinjauan Pustaka

2

1.5. Tujuan Penelitian

3

1.6. Manfaat Penelitian

3

1.7. Metode Penelitian

3

2. LANDASAN TEORI Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

5

2.1. Representasi Visual

5

2.2. Connected Graph

6

2.3. Undirected Graph

8

2.4. Weighted Graph

11

2.5. Tree

12 vii

2.6. Spanning Tree

13

2.7. Algoritma Prim

15

3. PEMBAHASAN

17

3.1. Jaringan Listrik Yang Terpasang di Perumahan Blok-P PT Inalum

4.

18

3.2. Penentuan Minimum Spanning Tree

20

KESIMPULAN DAN SARAN

37

4.1. Kesimpulan

37

4.2. Saran

37

DAFTAR PUSTAKA


x

DAFTAR GAMBAR viii Halaman Gambar 2.1 Graph yang memuat 3 verteks dan 3 edge

6

Gambar 2.2 (a) Connected graph, (b) Bukan connected graph

7

Gambar 2.3 Representasi grafis dari undigraph

9

Gambar 2.4 Undigraph yang memuat path, cycle, loop, hamilton path dan sirkuit

10

Gambar 2.5 Graph yang memuat multiple edge dan loop

11

Gambar 2.6 Subgraph

11

Gambar 2.7 Weighted graph

12

Gambar 2.8 Labeled graph

12

Gambar 2.9 Representasi Tree

13

Gambar 2.10 Graph G yang memuat spaning tree

14

Gambar 2.11 Hubungan antara Graph G dengan spaning treenya

14

Gambar 2.12 Graph G yang memuat minimum spanning tree

15

Gambar 3.1 Weighted, undirected dan connected graph G(11,18)

17

Gambar 3.2 Minimum spanning tree T dari G(11,18) menggunakan algoritma prim

18

Gambar 3.3 Jaringan listrik yang terpasang di blok-P Inalum G(253,242) 19 Gambar 3.4 Graph G(253,393)

23

Gambar 3.5 Representasi Algoritma Prim

32

Gambar 3.6 Minimum Spanning Tree dari G(253,393)

33


BAB 1 ix PENDAHULUAN

1.1 Latar Belakang Masalah Zaman kini sudah berkembang begitu pesatnya. Perkembangan ilmu pengetahuan matematika sekarang ini juga tidak ketinggalan menciptakan aplikasi-aplikasi baru yang lebih efisien dalam segi produktifitas dan biayanya. Sehubung dengan semakin banyaknya wirausaha yang membangun komplek perumahan dengan unit yang cukup besar, sehingga memunculkan banyak segi yang harus diminimumkan tanpa mengurangi fungsinya. Semakin berkembang suatu zaman, semakin banyak permasalahan yang dihadapi. Permasalahan timbul karena orang menginginkan kenyamanan dan keuntungan yang lebih. Misalnya saja kabel jaringan listrik yang akan dipasang haruslah optimal, dalam arti panjang kabel yang terpasang haruslah minimal dan dapat mengalirkan listrik keseluruh rumah yang terbangun. Perumahan yang diteliti adalah perumahan Inalum. Perusahaan PT Inalum didirikan sejak 6 Januari 1976, dan proyek Asahan yaitu pembangunan perumahan PT Inalum diatas tanah seluas 200ha dimulai pada November 1977. Dalam hal ini dapat digunakan salah satu cabang ilmu matematika yaitu teori graph. Jaringan kabel listrik yang terpasang di perumahan blok-P Inalum dapat direpresentasikan ke dalam bentuk graph terhubung, tak berarah dan berbobot (Connected, Undirected dan Weighted Graph). Di sini rumah dan tiang listrik direpresentasikan dengan verteks V. Sedangkan jalur kabel tiang listrik yang terpasang untuk mengalirkan listrik di blok-P Inalum direpresentasikan dengan edge E. Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

Salah satu metode meminimumkan panjang kabel yang terpasang di perumahan Inalum adalah dengan minimum spanning tree. Misalkan G adalah suatu simple graph dan G disebut tree jika dan hanya jika G tidak memuat sirkuit dan terhubung. Spanning tree T merupakan subgraf G yang merupakan tree yang memuat semua verteks di G. Minimum spanning tree dapat diperoleh dari 2 pendaftaran seluruh spanning tree yang terbentuk dari weighted graph G. Sehingga pada akhirnya diperoleh yang mana spanning tree yang paling minimum. Cara ini cukup sulit untuk graph yang besar. Pada tahun 1956, Prim berhasil menyusun algoritma untuk membuat minimum spanning tree secara 1 efisien yaitu algoritma prim. Algoritma prim membentuk minimum spanning tree dengan langkah per langkah. Pada setiap langkah kita mengambil edge G yang memiliki bobot minimum tapi yang terhubung dengan spanning tree T yang telah terbentuk mulai dari langkah awalnya. Sehingga akan terbentuk hingga langkah terakhir spanning tree dengan masing-masing edge yang termuat di T adalah minimum. Jadi, bagaimanakah menentukan keoptimalan panjang kabel yang terpasang di perumahan blok-P Inalum menggunakan algoritma Prim ?.

1.2 Perumusan Masalah Yang menjadi masalah dalam studi kasus ini adalah apakah panjang kabel yang terpasang di perumahan PT Inalum sudah optimal.

1.3 Batasan Masalah Batasan masalah yang tertera didalam penulisan ini diharapkan dapat membatasi ruang lingkup permasalahan yang akan dibahas dalam tulisan ini, antara lain: hanya meneliti Blok-P perumahan PT Inalum. Tidak menggunakan program dalam penyelesaian. Dalam penulisan ini tidak memperhitungkan kualitas dari jaringan listrik yang terpasang dengan menggunakan algoritma Prim. Konsep graph yang diuraikan dalam tulisan ini hanya menyangkut undirected graph.

1.4 Tinjauan Pustaka Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

Sebagai sumber pendukung teori dalam penulisan ini, maka penulis menggunakan beberapa pustaka antara lain : 1. Johnsonbaugh, Richard, 5th ed (2001). Discrete Mathematics, 263-296, 323343. Menyatakan bahwa,

Suatu graph terhubung G atau sering disebut

G = (V , E ) , dimana V = (v1 , v 2 ,  , v n ) dan 3 dikatakan connected (terhubung) jika dan hanya jika setiap 2

Connected Graph G. Graph E = (e1 , e2 ,  , en )

verteks dalam G connected oleh edge elemen dari G. 2. Grimaldi, Ralph P. (2004). Discrete and Combinatorial Mathematics, An Apllied Introduction, fifth edition. Rose-Hulman Institute Of Technology. Menyatakan bahwa, suatu walk di G dengan panjang m yang menghubungkan vetex u dan v adalah barisan edge di G dengan bentuk v = (v0 , v1 ), (v1 , v 2 ),  , (v n −1 , v n ) = w Panjang dari suatu walk adalah banyaknya edge yang termuat di dalam walk tersebut. Suatu path di G adalah suatu walk dengan semua verteksnya berbeda kecuali verteks awal dan verteks akhir. Dua buah verteks adjacent jika kedua verteks tersebut dihubungkan oleh sebuah edge.

1.5 Tujuan Penelitian Penulis berharap dapat menyelesaikan tugas akhir dengan hasil yang memuaskan dan memperkaya literature dalam bidang graph. Dan hasil penelitian ini juga dapat menambah wawasan terutama tentang aplikasi graph dalam kehidupan sehari-hari, dengan menerapkan teori minimum spanning tree menggunakan algoritma prim pada jaringan listrik di perumahan PT Inalum.

1.6 Manfaat Penelitian Manfaat yang dicapai oleh penulis adalah minimum spanning tree dari pada panjang kabel listrik yang terpasang di perumahan blok-P PT Inalum, dengan menggunakan algoritma Prim. Sehingga penulis dapat mengetahui apakah panjang kabel yang terpasang di perumahan tersebut sudah optimal atau belum.

1.7 Metode Penelitian Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

Penelitian ini bersifat studi kasus yang disusun berdasarkan rujukan pustaka dengan langkah-langkah sebagai berikut: Langkah-1

:

Menjelaskan beberapa definisi yang berkaitan dengan masalah yang diangkat.

Langkah- 2

:

Mencari data nyata tentang kabel listrik yang telah

4

diperoleh dari perusahaan PT Inalum. Langkah- 3

:

Mencari data dari hasil pengukuran penulis.

Langkah- 4

:

Menjelaskan penyelesaian masalah yang diangkat dari jaringan listrik blok-P PT Inalum menggunakan metode minimum spanning tree yaitu menggunakan algoritma prim.


BAB 2

LANDASAN TEORI

Pada bab ini akan dibahas beberapa konsep dasar yang akan digunakan sebagai landasan berpikir seperti definisi dan contoh yang berkaitan dengan penelitian ini. Dengan begitu akan mempermudah dalam hal pembahasan pada bab berikutnya.

2.1 Representasi visual Dalam kehidupan sehari-hari, banyak persoalan yang dapat disimpulkan sebagai persoalan yang berhubungan dengan himpunan, yang mana logika dari persoalan tersebut sering kali dapat digambarkan dengan sebuah graph. Graph digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graph dinyatakan berupa objek sebagai verteks, noktah (titik) atau bulatan, sedangkan hubungan antara objekobjek dinyatakan dengan edge. Penggunaan Teori graph banyak memberikan solusi untuk menyelesaikan permasalahan yang terjadi di dalam masyarakat. Contoh umum dari teori graph adalah penggunaan minimum spanning tree dengan menggunakan Algoritma Prim. Salah satu penggunaan Algoritma dalam memecahkan masalah dalam kehidupan sehari-hari adalah pengoptimalisasian jaringan listrik dengan menggunakan algoritma tersebut. Jaringan listrik dapat direpresentasikan sebagai graph, dimana tiang listrik dan rumah sebagai verteks sedangkan kabel sebagai edge. Untuk mendapatkan jaringan listrik yang optimal Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

(dengan panjang kabel terpendek) maka diperlukan suatu metode atau algoritma. Dalam menyelesaikan masalah tersebut dapat digunakan Algoritma Prim yang merupakan algoritma untuk mencari minimum spanning tree. Berdasarkan data yang diperoleh dari Perusahaan Inalum Asahan dapat diketahui bahwa panjang kabel total yang terpasang di Perumahan Inalum BlokP adalah sepanjang 4331.95 meter. Untuk melakukan analisis dengan 6 menggunakan Algoritma Prim terhadap jaringan listrik yang terpasang di Perumahan Inalum Asahan, maka harus dilakukan penelitian lebih lanjut, yaitu dengan cara melakukan pengukuran jarak antar rumah, antar tiang listrik dan antara rumah dan tiang listrik. Setelah 5 dilakukan pengukuran, data yang diperoleh dari Perusahaan Inalum dan data hasil pengukuran direpresentasikan dalam graph, yang mana graph hasil representasi tersebut akan dianalisis dengan menggunakan Algoritma Prim.

2.2 Graph Terhubung (Connected Graph) Suatu graph G adalah merupakan suatu pasangan {E(G),V(G)} dimana : V(G) merupakan sebuah himpunan berhingga yang tidak kosong(non empty finite set) yang elemennya disebut verteks(point/ simpul/ lingkaran kecil), dinotasikan v1 , v 2 ∈ V (G ) . Sedangkan, E(G) merupakan suatu family dengan elemen-elemennya adalah pasangan yang tidak berurut dari elemen-elemen verteks V(G) yang disebut dengan edge(arc/ line), dinotasikan (v1 , v 2 ) ∈ E (G ) atau dapat ditulis ei ∈ E (G ) . Edge direpresentasikan berupa garis lurus atau garis melengkung. Contoh 1. Diberikan graph sebagai berikut

e1

v1

e2

v2

e2

v3 Gambar 2.1 Graph yang memuat 3 verteks dan 3 edge Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

Berdasarkan Gambar 2.1 di atas dapat diberikan contoh dari verteks dan edge sebagai berikut, v1 , v 2 dan v3 merupakan verteks dan (v1 , v 2 ), (v1 , v3 ) dan (v 2 , v3 ) merupakan edge. Suatu graph G = (V , E ) dikatakan terhubung atau sering disebut Connected Graph G, dimana terdapat V = (v1 , v 2 ,  , v n ) dan E = (e1 , e2 ,  , en ) 7 jika dan hanya jika setiap 2 verteks yang terdapat di dalam G terhubung oleh edge. Dua

buah

verteks

v1 , v 2 ∈ V (G )

dikatakan

adjacent(berdekatan),

jika

v1 , v 2 ∈ V (G )

keduanya merupakan verteks ujung dari pada edge e-

1 ∈ E (G ) maka

v1 dan v 2 disebut incidency terhadap edge e1 tersebut. Dan

apabila dua buah edge e1 , e2 ∈ E (G ) yang berbeda (non pararel edge) incidency terhadap verteks sekutu maka kedua edge tersebut dikatakan adjacent edge.

Contoh 2. Diberikan graph sebagai berikut e2

v1

v2

v1

e2

v2 v5

e1

e3

e4

e1

e3

e4

e6 v6

v4

e5

v3

v4

(a)

v3

e5 (b)

Gambar 2.2 (a) Connected graph, (b) Disconnected graph

Dari Gambar 2.2 dapat kita lihat, sebagai berikut: Gambar 2.2.(a) Adjacent verteks

Incidency

Adjacent edge


v1 dan v2

v1, v2 incidency terhadap e2

v1 dan v4


v1 dan v3


v2 dan v3


v4 dan v3


e1, e2 dan e3 e3, e4 dan e5 e2 dan e4 e1 dan e5

Gambar 2.2.(b) merupakan disconnected graph karena tidak setiap 2 verteks di dalam G terhubung dengan edge, yaitu verteks v5 dan v6 Degree atau derajat suatu verteks adalah jumlah edge yang incidency atau bersisian dengan verteks tersebut, dinotasikan dengan d(vi). Tinjau gambar 2.2.(a) :

8

d(v1) = d(v3) = 3 d(v2) = d(v4) = 2.

2.3 Graph Tak Berarah (Undirected Graph) Suatu graph G adalah suatu kumpulan verteks, titik atau lingkaran kecil yang dihubungkan oleh garis, sisi atau edge, dan jika edge yang menghubungkan verteks tersebut berarah maka graph tersebut disebut dengan graph berarah (directed graph) atau disebut juga dengan istilah digraph. Dan sebaliknya graph yang setiap verteksnya dihubungi dengan edge tanpa arah, maka graph tersebut disebut graph tak berarah atau sering disebut undirected graph atau undigraph. Andaikan V adalah suatu himpunan objek berhingga tak kosong. Sebuah graph tak berarah U adalah suatu objek yang dibentuk oleh himpunan V = {v1 , v 2 ,  , v n } yang unsurnya disebut verteks dari U, bersama dengan himpunan E yang terdiri dari pasangan berurut verteks di V. Setiap pasangan berurut

dari

verteks

di

V

disebut

dengan

edge.

Jika

diberikan

v1 , v 2 ∈ V dengan (v1 , v 2 ) ∈ E , maka terdapat edge yang menghubungkan verteks v1 dan v 2 di undigraph U. Contoh 3. Himpunan verteks V = { v1 , v 2 , v3 , v 4 , v5 } bersama dengan himpunan edge E = {(v1 , v3 ), (v1 , v 4 ), (v1 , v5 ), (v 2 , v1 ), (v 2 , v 4 ), (v3 , v 2 ), (v 4 , v3 ), (v5 , v 4 )} adalah suatu undigraph dengan 5 verteks dan 8 edge. Suatu undigraph dapat direpresentasikan secara grafis, yakni setiap verteks di V direpresentasikan sebagai titik dan setiap edge yang Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

menghubungkan kedua verteksnya direpresentasikan sebagai garis tak berarah yang menghubungkan suatu verteks dengan verteks lainnya. Representasi undigraph pada contoh 3 diperlihatkan pada gambar 2.3 berikut, pada halaman 9.

9

v5

v1

v2

v3

v4

Gambar 2.3 Representasi grafis dari undigraph

Suatu walk dari a ke b yang panjangnya n adalah suatu barisan edge dalam bentuk a = v0 − v1 − v2 −  − vn −1 − vn = b Dari definisi walk di atas, panjang dari suatu walk adalah banyaknya edge yang terdapat di walk tersebut. Suatu walk w dengan verteks awal a dan dengan verteks akhir b disebut sebagai ab-walk dinotasikan dengan wab. Suatu walk dikatakan terbuka jika

a ≠ b dan dikatakan tertutup jika a = b. Panjang dari walk wab dinyatakan dengan (wab ). Dari Gambar 2.3, diperoleh Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

v1 − v5 − v4 − v3 − v2 − v1 yang merupakan suatu walk tertutup dengan panjang 5. Sedangkan v1 − v5 − v4 − v3 − v2 merupakan suatu walk terbuka dengan panjang 3.

Path adalah walk yang memuat verteks-verteks yang berbeda kecuali mungkin verteks awal dan verteks akhir. Cycle adalah suatu path tertutup dan loop adalah suatu cycle dengan panjang satu (vi= vi). Suatu hamilton path di graph G adalah suatu path yang memuat seluruh verteks di G. Sirkuit dengan panjang n adalah path yang dimulai dan diakhiri dengan verteks yang sama. 10

Contoh 4. Diberikan undigraph sebagai berikut: v6

v5

v1

v2

v3

v4

Gambar 2.4 Undigraph yang memuat path, cycle, loop, hamilton path dan sirkuit

Berdasarkan gambar 2.4 di atas dapat di tunjukkan contoh daripada path, cycle dan hamilton path, yaitu : v1 − v5 − v4 − v3 − v2 − v6 merupakan salah satu path dengan panjang 5, v1 − v5 − v4 − v3 − v2 − v1 merupakan salah satu cycle dengan panjang 5, Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

v5 − v5 merupakan suatu loop, v6 − v3 − v2 − v1 − v5 − v4 merupakan salah satu hamilton path, dan v6 − v2 − v1 − v3 − v4 − v5 − v6 merupakan salah satu sirkuit.

Suatu graph G dikatakan Simple graph atau graf sederhana jika dan hanya jika didalam graph G tidak terdapat loop dan multiple edge (edge ganda). 11

Contoh 5. Diberikan graph yang bukan merupakan simple graph sebagai berikut: e1 v1

v2

e2 e3

e4

v3 Gambar 2.5 Graph yang memuat multiple edge dan loop

Dari gambar 2.5 diketahui bahwa graph bukan merupakan simple graph karena memuat loop yaitu v2 − v2 dan multiple egde yaitu e1 dan e2. Himpunan yang terdapat didalam graph disini berupa himpunan dari verteks dan edge. Maka S dikatakan subgraph dari graph G jika dan hanya jika verteks dan edge yang berada di S merupakan yang berada di G. Sedangkan suatu subgraph yang memuat seluruh verteks dari graph G dikatakan spanning subgraph (subgraph merentang). Contoh 6. Diberikan graph G dan subgraph

Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. (b) (a) USU Repository © 2009

Gambar 2.6 Subgraph

Dari gambar 2.6 diterangkan bahwa, Gambar 2.6.(b) merupakan spanning subgraph dari Gambar 2.6.(a).

2.4 Graph Berbobot (Weighted Graph) dan Berlabel (Labeled Graph) Graph berbobot adalah graph yang setiap edgenya mempunyai nilai berupa bilangan non negatif.

12

Contoh 7. Diberikan weighted graph v2

v4

3

12

v6

3

8 2

v1

2

6

2

v8

3 19

4 v3

13

v5

3

v7

Gambar 2.7 Weighted graph Dari gambar 2.7 dapat dijelaskan bobot dari masing-masing edge, yaitu:

(v1 , v2 ) = 3 (v1 , v3 ) = 4 (v2 , v3 ) = 2 (v2 , v4 ) = 3 (v3 , v4 ) = 2 (v3 , v5 ) = 13 (v7 , v8 ) = 19

(v4 , v5 ) = 2 (v6 , v4 ) = 12 (v4 , v7 ) = 6 (v5 , v7 ) = 3 (v6 , v7 ) = 3 (v6 , v8 ) = 8

Sedangkan labeled graph yaitu disetiap edgenya hanya ditandai dengan simbol yang bukan merupakan bilangan non-negatif. Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

Contoh 8. Diberikan labeled graph

e2 v1

v2 e1

Gambar 2.8 Labeled graph

2.5 Tree Tree adalah suatu connected graph yang tidak memuat cycle, loop dan multiple edge. Pada sebuah tree hanya terdapat satu path antara setiap pasangan verteksnya. Tree yang hanya terdiri dari 1 verteks disebut tree yang menyusut atau tree yang mengalami degenerasi. Forest adalah himpunan dari paling sedikit 2 tree atau lebih.

13

Contoh 9. Diberikan beberapa contoh tree

(a)

(b)

(c)

Gambar 2.9 Representasi Tree

Dari gambar 2.9 dapat dilihat, Gambar 2.9.(a) merupakan tree yang menyusut Gambar 2.9.(b) merupakan tree dengan 5 verteks dan 4 edge Gambar 2.9.(c) merupakan forest yang memuat 4 komponen tree.

Sifat-sifat tree, Misalkan G = (V, E) adalah graph tak-berarah sederhana dan jumlah simpulnya n. Maka, semua pernyataan di bawah ini adalah ekivalen: - G adalah tree. Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

- Setiap pasang verteks di dalam G terhubung dengan edge tunggal. - G terhubung dan memiliki m = (n − 1) edge. - G tidak mengandung cycle (acyclic) dan memiliki m = (n − 1) edge. - G tidak mengandung cycle (acyclic) dan multiple edge. - G terhubung dan setiap edge-nya adalah bridge(jembatan/ penghubung). (jurnal: Universitas Gunadharma)

2.6 Spanning Tree Spanning tree T atau pohon rentangan dari suatu connected graph adalah suatu subgraph dari graph G yang mengandung semua verteks dari G, dan merupakan suatu tree. Edge pada suatu spanning tree T biasa disebut branch (cabang). Dan edge di G yang tidak terdapat di spanning tree T disebut chord (tali).

14

Contoh 10. Diberikan graph G yang memuat spanning tree v1

e1

v2

e13 e14

e2 e8

e9

e3 e7

v8 e15

e11

v7

e10

v3

v6

v4

e6

e4

e5

v5

Gambar 2.10 Graph G yang memuat spanning tree

Dari gambar 2.10 dapat dilihat bahwa salah satu spanning tree yang merupakan subgraph G ditandai oleh yang bergaris tebal. Sehingga dapat dilihat juga bahwa e1, e13, e11, e15, e6, e5 dan e3 merupakan branch-branch yang termuat pada spanning tree tersebut. Dan e2, e14, e9, e8, e4, e10 dan e7 merupakan chord. Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

Pada gambar 2.11 berikut menunjukkan hubungan dari graph G dengan spanning treenya. (jurnal: Universitas Gunadharma)

Graph G n verteks m edge

Spanning tree n verteks n − 1 edge

m − (n − 1) edge

BRANCH (CABANG)

CHORD

Gambar 2.11 Hubungan antara Graph G dengan spanning tree-nya 15 Jika T merupakan spanning tree didalam suatu weighted graph G maka bobot dari suatu spanning tree didefinisikan sebagai berikut: bobot dari suatu spanning tree adalah jumlah dari semua bobot yang terdapat pada branch di tree tersebut, dinotasikan sebagai berikut:

W (T ) =

∑ ( x, y )

x , y∈T

Secara umum untuk spanning tree yang berbeda pada graph G akan mempunyai bobot yang berbeda pula, karena pada suatu connected graph G mungkin mempunyai banyak spanning tree dengan total bobot yang masing-masing mungkin berbeda. Sehingga karena persoalan ini pula dapat dipilih satu spanning tree yang memiliki total bobot yang paling minimum disebut sebagai minimum spanning tree(MST) atau pohon merentang minimum. Contoh 11. Diberikan graph G yang memuat minimum spanning tree 10

10

3

3

3 5

1 1

3

1 4 1

4

4

4 Listrik Perumahan 1 1 Jaringan Rayi Syahfitri : Penerapan Algoritma Prim Pada PT Inalum, 2009. USU Repository © 2009 2

1

2

Gambar 2.12 Graph G yang memuat minimum spanning tree

Pada gambar 2.12 minimum spanning tree ditandai dengan garis tebal, dimana total bobotnya adalah 3 + 1 + 3 + 1 + 1 + 2 + 1 + 2 + 1 + 1 + 3 + 1 + 3 = 23 . Minimum spanning tree ini merupakan spanning tree yang paling penting. Sehingga lebih dari satu algoritma yang muncul untuk menyelesaikan persoalan minimum spanning tree.

2.7 Algoritma Prim Salah satu algoritma yang sering digunakan untuk menyelesaikan persoalan minimum spanning tree adalah algoritma Prim. Algoritma 16ini ditemukan oleh Robert C.Prim. Algoritma-algoritma selain Prim, yaitu: algoritma Greedy, Boruvka, Kruskal, Bernard Chazell dan Waktu Linier. Berbeda dengan Kruskal yang dimulai dengan graph tanpa edge, algoritma Prim dimulai dari graph kosong. Algoritma Prim membentuk pohon merentang minimum langkah per langkah. Pada setiap langkah kita mengambil edge dari graph G yang mempunyai bobot paling minimum dengan mengambil verteksverteks yang incidency terhadap edge tersebut, namun pada pemilihan edge berikutnya selalu terhubung dengan minimum spanning tree T yang telah terbentuk. Jika G merupakan suatu weighted dan connected graph, maka dengan algoritma Prim dapat diperoleh minimum spanning tree-nya dengan langkah-langkahnya sebagai berikut: Langkah 1 :

Ambil edge dari graph G yang berbobot minimum, masukkan ke dalam T.

Langkah 2 :

Pilih edge (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi (u, v) tidak membentuk sirkuit di T. Tambahkan (u, v) ke dalam T.

Langkah 3 :

Ulangi langkah 2 sebanyak n – 2 kali. Jumlah langkah seluruhnya


didalam algoritma Prim adalah 1 + (n − 2 ) = n − 1 , yaitu sebanyak jumlah sisi di dalam pohon merentang dengan n buah simpul.

BAB 3

PEMBAHASAN

Pada Bab sebelumnya telah dipaparkan algoritma Prim yang digunakan dalam menyelesaikan permasalahan minimum spanning tree. Pada Bab ini akan diperlihatkan algoritma prim untuk mengoptimalkan panjang kabel yang terpasang di perumahan blok-P PT Inalum. Dan sebelum memulai pembahasan penemuan minimum spanning tree pada jaringan listrik di perumahan blok-P PT Inalum, akan diperlihatkan secara lengkap contoh penyelesaian masalah minimum spanning tree menggunakan algoritma Prim. Contoh 3.1 Diberikan undirected, weighted dan connected graph G, sebagai berikut: 4

v2

v5 7

v8

Rayi Syahfitri : Penerapan Algoritma 7 Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009 4 2 3 6

v1

2 4

5

v3

5 v6

3

2

v9 6

2

v11 7

Gambar 3.1 Weighted, undirected dan connected graph G(11,18)

Dari gambar 3.1 dapat kita peroleh minimum spanning tree menggunakan algoritma prim dengan melalui beberapa tahapan, yaitu: -

(1)Pilih edge yang memiliki bobot paling minimum dari graph G dan masukkan ke dalam T, yaitu 2 dengan edge (v1,v3).

-

(2)Pilih edge (v3,v4) yang incidency dengan salah satu verteks ujung dari tree yang telah terbentuk dan memiliki bobot paling minimum, yaitu 18 3.

-

(3)Pilih edge (v3,v6) yang incidency dengan salah satu verteks ujung dari tree yang telah terbentuk dan memiliki bobot paling minimum, yaitu 5.

-

(4)Pilih edge (v6,v7) yang incidency dengan salah satu verteks ujung dari tree yang telah terbentuk dan memiliki 17 bobot paling minimum, yaitu 2.

-


-


-


-


-



-


Sehingga minimum spanning tree dari graph G(11,18) adalah W (vi , v j ) = 2 + 3 + 5 + 2 + 2 + 4 + 4 + 5 + 2 + 3 = 32

Tahapan dan algoritma prim diatas dapat direpresentasikan pada graph berikut: v2

v1

(6) v5

(1) v3

(3) v6 (2)

v4

v8

(5)

(10)

(8) (4)

v9

(9)

v7

(7)

v11

v10

Gambar 3.2 Minimum spanning tree T dari G(11,18) menggunakan algoritma prim

19

3.1 Jaringan listrik yang terpasang di perumahan blok-P PT Inalum. Hasil pengukuran panjang kabel dari jaringan listrik yang terpasang di blok-P Inalum dapat direpresentasikan sebagai graph terhubung, tak berarah dan berbobot (Connected, Undirected dan Weighted Graph). Suatu undigraph G dengan himpunan verteks V dan edge E dinotasikan dengan G={V,E}, dengan rumah dan tiang listrik direpresentasikan sebagai verteks yang dinotasikan dengan v∈V. Sedangkan jalur-jalur kabel tiang listrik yang terpasang untuk mengalirkan listrik di-blok-P Inalum direpresentasikan dengan edge yang dinotasikan dengan e∈E.


Data yang diperoleh dari PT Inalum,

Gambar 3.3 Jaringan listrik yang terpasang di blok-P Inalum G(253,242)

20

3.2 Penentuan Minimum Spanning Tree Selanjutnya membuat langkah-langkah untuk menentukan minimum spanning tree dari graph yang diambil di perumahan blok-P PT Inalum, yaitu: Diketahui bahwa G = {V , E} -

Mengetahui jumlah verteks yang termuat pada graph G(253,393), yaitu:

i ∈ V (G ), i = 1,2,3,,253 .


-

Mengetahui seluruh edge yang termuat pada graph G(253,393), dinotasikan sebagai

( j ) ∈ E (G ), j = 1,2,3,,393

dengan masing-masing bobot(dalam

satuan meter) sebagai berikut: edge

bobot edge bobot

edge bobot edge bobot edge

bobot

(1)

2

(22)

39.2

(43)

4.8

(64)

21.8

(85)

3.6

(2)

3

(23)

32.1

(44)

4.7

(65)

6.2

(86)

4.35

(3)

5

(24)

14.1

(45)

16.4

(66)

8.7

(87)

4.2

(4)

5.4

(25)

12.6

(46)

15.6

(67)

18.4

(88)

3.6

(5)

3.6

(26)

2.8

(47)

4.2

(68)

6.5

(89)

4.6

(6)

13

(27)

3.3

(48)

4.2

(69)

4.7

(90)

4.7

(7)

31.45

(28)

7

(49)

3.9

(70)

5.5

(91)

4.8

(8)

31.4

(29)

2.6

(50)

16.69

(71)

6.8

(92)

18.6

(9)

35.6

(30)

3.3

(51)

17.7

(72)

19

(93)

4.5

(10)

38.5

(31)

6.8

(52)

19

(73)

12.6

(94)

4.6

(11)

39.1

(32)

2.7

(53)

17.8

(74)

4

(95)

3.2

(12)

16.2

(33)

3.1

(54)

20.8

(75)

4.2

(96)

4.7

(13)

5.5

(34)

3.4

(55)

4.2

(76)

4.5

(97)

5.1

(14)

5.6

(35)

5

(56)

4.2

(77)

4.6

(98)

19

(15)

18

(36)

5.1

(57)

21.3

(78)

4.8

(99)

20

(16)

7.1

(37)

6.7

(58)

4.9

(79)

14

(100)

4.1

(17)

19

(38)

5.4

(59)

5

(80)

15.4

(101)

21.8

(18)

35.7

(39)

4.8

(60)

30

(81)

4.8

(102)

4.3

(19)

36.7

(40)

8.9

(61)

31.7

(82)

4

(103)

3.8

(20)

23.7

(41)

41

(62)

3.8

(83)

3.6

(104)

(21)

5

(42)

5.2

(63)

3.5

(84)

4.5

(105)

22.5 21 18

edge

bobot

edge bobot

edge

bobot

edge

bobot edge

bobot

(106)

18.9

(137)

6.6

(168)

15.4

(199)

29.4

(230)

19.5

(107)

16.9

(138)

18

(169)

9.2

(200)

19.7

(231)

5.6

(108)

8.9

(139)

14.8

(170)

3.7

(201)

10.9

(232)

34

(109)

17

(140)

3.9

(171)

22.9

(202) 17.85 (233)

36


(110)

5.6

(141)

16.8

(172)

24.2

(203)

19.5

(234)

35.6

(111)

25

(142)

22.8

(173)

19.1

(204)

7.4

(235)

37.8

(112)

25.5

(143)

12.4

(174)

3.4

(205)

17.6

(236)

38

(113)

6.9

(144)

5.1

(175)

10.5

(206)

26.4

(237)

38.3

(114)

9.4

(145)

19.4

(176)

18

(207)

31.1

(238)

39.1

(115)

18.9

(146)

20.4

(177)

6

(208)

31.1

(239)

38.9

(116)

6.3

(147)

6.2

(178)

7.2

(209)

34.2

(240)

39.4

(117)

5

(148)

20.4

(179)

22.1

(210)

26.9

(241)

21.9

(118)

23.8

(149)

25.6

(180)

6

(211)

28.3

(242)

23.7

(119)

16.8

(150)

6.75

(181)

18.6

(212)

27.2

(243) 28.85

(120)

20

(151)

26

(182)

7.45

(213)

35.2

(244)

7.6

(121)

4.8

(152)

18.1

(183)

24.9

(214)

35.4

(245)

16.1

(122)

6.9

(153)

16.7

(184)

17.6

(215)

36

(246)

23.2

(123)

22.1

(154)

6.5

(185)

20.9

(216)

36.3

(247)

4.5

(124)

4.9

(155)

16

(186)

6.6

(217)

36.5

(248)

10.9

(125)

6.4

(156)

5.9

(187)

8.7

(218)

33.4

(249)

9.95

(126)

21.6

(157)

14

(188)

21.5

(219)

35.4

(250)

6.2

(127)

25.1

(158)

4

(189)

7.4

(220)

5.9

(251)

39.8

(128)

16.8

(159)

19.5

(190)

9.2

(221)

15.9

(252)

41.1

(129)

19.4

(160)

4.2

(191)

21.7

(222)

16.4

(253)

40

(130)

3.4

(161)

6.2

(192)

24.7

(223)

8.7

(254)

39.9

(131)

7.1

(162)

15.3

(193)

5.6

(224)

18.5

(255)

18

(132)

20.4

(163)

10

(194)

16.3

(225)

21.8

(256)

17.4

(133)

5.7

(164)

5

(195)

27.4

(226)

26.4

(257)

45.8

(134)

8.1

(165) 21.45 (196) 28.45 (227)

23.4

(135)

19.4

(166)

3.7

(197)

28.7

(228)

13

(258) 38.85 22 (259) 37.4

(136)

16.1

(167)

6.1

(198)

28.7

(229)

4.6

(260)

41.4

edge

bobot

edge bobot

edge

bobot

edge

bobot edge

bobot

(261)

40

(292)

52

(323)

41.2

(354) 18.75 (385)

25.1

(262)

40

(293)

120

(324) 52.42 (355)

19

(386)

19

(263)

18.4

(294)

35.8

(325)

4.4

(387)

8

30.6

(356)


-

(264)

25.9

(295)

41

(326)

41.1

(357)

9.4

(388)

5

(265)

76.8

(296)

95

(327)

24.1

(358)

23.8

(389)

21

(266)

25.1

(297)

38.8

(328)

23

(359)

29.1

(390)

16.9

(267)

39.6

(298)

39.1

(329)

32.8

(360) 18.85 (391)

20.4

(268)

36.8

(299)

52.2

(330) 30.46 (361)

25.6

(392)

7.3

(269)

36.6

(300)

41

(331)

24

(362)

26.1

(393)

35.4

(270)

41.2

(301)

54.2

(332)

32.8

(363)

20.9

(271)

17

(302)

25

(333)

80

(364)

39.4

(272)

37.1

(303)

22.2

(334)

58.8

(365)

38.9

(273)

15.3

(304)

31.5

(335)

40

(274)

35.9

(305)

23.1

(336)

39.5

(367)

40.1

(275)

47.1

(306)

26.2

(337)

36.2

(368)

36.2

(276)

46.85 (307)

39.4

(338)

40

(369)

40.2

(277)

40.7

41.6

(339)

25.6

(370)

40.2

(278)

35

(309) 54.45 (340)

38.6

(371)

80

(279)

26.3

(310)

66

(341)

30.6

(372)

30

(280)

25.2

(311)

64.9

(342)

19.2

(373)

4.9

(281)

24.9

(312)

52.8

(343)

32

(374)

22.3

(282)

27.7

(313)

38

(344)

31

(375)

19

(283)

26.2

(314)

80

(345)

29.2

(376)

4.8

(284)

18.3

(315)

60.1

(346)

28.3

(377)

4.9

(285)

86.7

(316)

36.2

(347)

21.6

(378)

26.8

(286)

85.6

(317)

25.2

(348)

20.4

(379)

30.8

(287)

28.4

(318)

28.2

(349)

7.5

(380)

20.4

(288)

38.5

(319) 79.85 (350)

21.2

(381)

20.5

(289)

40.7

(320)

82.2

(351)

16.8

(382)

25

(290)

48.1

(321)

78

(352)

27

(383)

6

(291)

49.4

(322)

76.7

(353)

16.8

(384)

4.9

(308)

(366) 36.35

23

Merepresentasikan jaringan listrik di blok-P Inalum dari gabungan data perusahaan dan pengukuran, yaitu graph G(253,393).


39.8 (251)

38 (236) 37.8 (235) 27 .4 (1 95 )

39,6 (267) 20 (1 .4 36.8 (268) 48 19 ) (1.4 6.2 41 45 (147) 28 36.6 (269) .2 22 ) 20.4 (146) .4 (1 (2 .8 12.4 5( 70 (143)42 17 5.1 19 ) 16.8 ) (2 (144) (141) 6) 71 18(138) ) 15.3 37.1(272) (273) 3.9(140) 14.8(139)

40 (253) 39 .9( 25 4)

36.3 (216)

28 .7 25(111) (1 5. 98 6( 17(109) ) 11 18 0) 28 (2 45.8 (257)38 .7 35.6 (234) 17.4 8.9(108) 55 (1 6.6(137) (256) .8 16 16.9 ) 97 5 36 37 .1( ) (107) (2 (2 .4 18.9(106)18 (105) 13 58 33 (2 6) 19.4(135) 5.7 ) 59 41 ) 18 25 (133) 22.5 (104) (2 ) .4( 35 34 .4 (1 3. (1 8. 20.4 3.4 .6( 40 63 35.8(294) .9( 26 (2 (130) 34 1(132) 03 8 14 (2 21 ) 27 (1 7. 19.4 0) 32 ) ) (1 9) 61 .8 4) 31 (129) ) 1 01 ) 4.3 41(295) 6.75 ) 40(262) ) 35 8.7 (223) 16.8 21.8 (102) (150) 40 .4( 47.1(275) 25.9(264) (225) (128) 20 12 4.1 18.516.4 (222) 27.7 .7( 39 9. (9 (224) (282) 0( (100) 27 4.9 (124) 35 5.6 (231) 3) 46.85(276) 76 25.1 4( 25 26.4 9) 29 21.6 (2 7) (126) .8( (226) .1( (127) 11 3) (6 8. 15.9 (221) 23.4 19.5 (230) 78 33 26 5. 4) 22.1 6) 7 (227) 18 26 ) 4.8 (121) .4( 5) 25.5 6( 6) 35.4(219) 5.9 (220) (123) .9( 6.9(113) (6 21 4. (112) 52(292) 6.4 (125) 19 4. 11 16 13 (228) 95(296) 20 9)7 6 48 8) 3) 38.8(297) (120) 6.9 (122) 5) .3( 18.4 (2 49.4(291) .1( 5.5 16.8 39 6.5 19 29 29 (1 24 (167) (70) (119) 21 6.2(65) 36 .1( 40 25.2(280) 4) (68) ) 0) 92 .7 .8( .5( 29 .7( 6.8 20.5 24 ) 64 21 8) 28 (71) .9( 23.8 19 (381) ) 52.2(299) 7) 6,3 9) 21.7 41 3. 12 28(118) (116) 7.4(189) (72) (191) (3 5( .6( 9. 38 1) 00 26.3(279) 63 73 2 21.5 .5( 64 5(117) 3. 6.6 (186) ) ) ) 4( 25(302) (188) (1 28 27 40 31 .9( 7 8( 90 20.4(348) 4) 4.8(78) 19(98) 20.9 (185) 8) 28.4(287) (3 .2( .1( 31 66 62 15 ) 52 8.7 (187) 30.8(379) 36 20 1) (3 54.2(301) (3 25 .4 ) 6( 26 14(79)4.2(75) 85 .1 36 (8 9) ) 8) 3 10 25(382) 4(82) (3 40.2(370) 60.1(315) ) (1 31 4. 31.1(207) 8 80(314)(1 7. 21.45 4.8(81) 0) .2 17.6(184) ) 4.6(77) 4.5(76) 68 (3 26 9( 20 3) .7( 51 7.4 (204) 54 82 45 (165) 78 .8 4.9(373) 3 10.9 (201) 26 .4 4. 19 38 ) 17 61 19 3.6(83) ) .4 38(313) ) ) 41 5. 36 24.9(183)3.7 (166) 4.8(376) 18 4. (3 7( (3 4) 26.6(306) .2( .6( (2 .5 17(2 ) 2( 4.5(84) 19 5( .6( .6 5( 91 96 5(86 .2( .8 19 79.85 03 28 52.8 93 20 402 4.2 (160) ) 21 38) (3 (2 (319) 4.7(90) (9 18.6 18.1(152) 39 4.9(58) 30 ) 22.2(303) 31 5 02 (312) 30 .7 (3 8) ) 3) 6.1 (167) 86.7 .1(1 3.6(85) 55 2) ) 5) 4.8(91) 4. 9) ) 00 .5( (181) 8) 3.89 8( 6) (5 ) (2 18(285) 7.2 (178) 36 22.1 4.35(86) (3 22 9( ) 3 4.6(94)2() 33 19.5(159) 15 7) 21 37 84 .3 6.2 (161) 9 3.45 7) 8 7 3..3 (179) .3 5(59) 34 26.4(206) 25.2(317) 28.2(318) 23.1(305) 6) .4( 7) 36(215) 5) 7) (174) 16.7 ) 4)6( (180) 5.1(97) 4.2(87) .2( 36.35 29.4 16 (1 6 18 39 (153) 8 6 15 (176) (366) 30(372) 20 (199) 85.6 38 .4 8)4.6(89) 77 8) 19.1 31.5(304) .3( 82 6.5(154) (286) 9) .9( (3 (327) ) (1 10 (173) 07 16 .2( 20 4.7(44) 26 16 78 24.1 75 .5 80 19 36 ) 32 2) .9( .9( (1 35 (3 ) (3 (5 5) 24.2(172) 0) 36 21 55 9.2 (169) .4( 21 71 2) 22.9 4.8(43) 76 3) 0) ) ) ) 28 23(171) 172621 41 .7( (5 .1 4.2(56)4. 4) 30.6(325) 5.2(42) .3( (3 .2( 3).8(3 32 2( 20.8(54) 6.2 (250) 3.7 (170) 32.8(332)10 (163) 21 28 62 5. 5 31 5.9 (156) 32 2) 1 4.8 (41) 52.42(324) 23.8(358) ) 28.3(346) (3 5) ) 1) 1( 7. 3) 9.95 4.5 (247) 25.6(361) 7( 44 3. 40 30.46(330) 5 (164) 24(331) 8.9 9. 29.1 36 14(157) 27 (249) 10.9 9( 19.2(342) ) 5 (3 (40) (359) ) 7.6 (244) 29.2(345) 49 (248) 23.2 .2( 5. 1) (3 4 35 4.8 ) 4.2(48) 4. (246) 16.1 32.8(329) 80(333) (39)8) 4 18.85 21 2( (3 4.4(356) ) 16.9(50) 4(158) (360) (245) 28.85 2) 15,6(46) 47 57 2. 32(343) (243) ) 16.8(351) 5(35) 5( 7( 7.3(392) ) 58 23 21 3.43.1(33) 32 3. 23.7 (242) 16.4(45) 6.7 .8( .7( (34) 19(375)) 3( 7.5(349) ) 21.2(350) (37) 38.3(237) 6. 3 33 30.6(341) 20 5. 8( 2.6(29) 0) 3. 4) 21.9 (241) 18.75 ) 31 16.9(390) 5( 3( 39.1(238) (354) 7( 30 2 13 7.1 28 16.8 ) 14 (6 38.9(239) 7) 19(17) (16) 18 ) 41.1(252) 41.1(326) 39.4(240) 39.5(364) 21.6(347) (353) ) 2.8 40(338) .1( 0) 36.7(19) (26) 12.6(25) 20.4 (15) 5.6(14) 24 35.7(18) 3. (380) ) 36.2(337) 6( 16.2(12) 32 5) 5.4(4) 2(1) 13 .1( 39.1(11) 3( (6) 23 2) ) 35.6(9) 5(3) 39 25.6 31 .2( (339) .4 22 5( 38.6(340) ) 7) 31 .4( 38.5(10) 8)

Gambar 3.4 Graph G(253,393)

24

-

Menentukan minimum spanning tree dengan menggunakan algoritma prim.


Langkah-langkah menemukan minimum spanning tree pada graph yang merupakan representasi jaringan listrik yang terpasang di perumahan blok-P PT Inalum, menggunakan algoritma Prim, yaitu sebanyak (n-1) dengan n banyaknya verteks.

Langkah

Pemilihan edge

(1)*

Pilih edge yang memiliki bobot paling minimum diantara edge-edge dari graph Blok-P dan masukkan ke dalam T, yaitu 2 pada edge (1).

(2)*

Pilih edge yang incidency dengan salah satu verteks ujung dari tree yang telah terbentuk dan memiliki bobot paling minimum, yaitu 3 pada edge (2).

(3)*

Pilih edge dengan cara yang sama, yaitu 5 pada edge (3).

(4)*

5.4 pada edge (4).

(5)*

3.6 pada edge (5).

(6)*

13 pada edge (6).

(7)*

31.45 pada edge (7).

(8)*

31.4 pada edge (8).

(9)*

35.6 pada edge (9).

(10)*


(11)*


(12)*


(13)*

5.5 pada edge (13).

(14)*

5.6 pada edge (14).

(15)*

18 pada edge (15).

(16)*

7.1 pada edge (16).

(17)*

19 pada edge (17).

(18)*


(19)*


(20)*


(21)*

5 pada edge (21).

(22)*



25

(23)*


(24)*


(25)*


(26)*

2.8 pada edge (26).

(27)*

3.3 pada edge (27).

(28)*

7 pada edge (28).

(29)*

2.6 pada edge (29).

(30)*

3.3 pada edge (30).

(31)*

6.8 pada edge (31).

(32)*

2.7 pada edge (32).

(33)*

3.1 pada edge (33).

(34)*

3.4 pada edge (34).

(35)*

5 pada edge (35).

(36)*

5.1 pada edge (36).

(37)*

6.7 pada edge (37).

(38)*

5.4 pada edge (38).

(39)*

4.8 pada edge (39).

(40)*

8.9 pada edge (40).

(41)*

41 pada edge (41).

(42)*

5.2 pada edge (42).

(43)*

4.8 pada edge (43).

(44)*

4.7 pada edge (44).

(45)*


(46)*


(47)*

4.2 pada edge (47).

(48)*

4.2 pada edge (48).

(49)*

3.9 pada edge (49).

(50)*

16.69 pada edge (50).

(51)*


(52)*

19 pada edge (52).

(53)*



26

(54)*


(55)*

4.2 pada edge (55).

(56)*

4.2 pada edge (56).

(57)*


(58)*

4.9 pada edge (58).

(59)*

5 pada edge (59).

(60)*

30 pada edge (60).

(61)*


(62)*

3.8 pada edge (62).

(63)*

3.5 pada edge (63).

(64)*


(65)*

6.2 pada edge (65).

(66)*

8.7 pada edge (66).

(67)*


(68)*

6.5 pada edge (68).

(69)*

4.7 pada edge (69).

(70)*

5.5 pada edge (70).

(71)*

6.8 pada edge (71).

(72)*

19 pada edge (72).

(73)*


(74)*

4 pada edge (74).

(75)*

4.2 pada edge (75).

(76)*

4.5 pada edge (76).

(77)*

4.6 pada edge (77).

(78)*

4.8 pada edge (78).

(79)*

14 pada edge (79).

(80)*


(81)*

4.8 pada edge (81).

(82)*

4 pada edge (82).

(83)*

3.6 pada edge (83).

(84)*

4.5 pada edge (84).


27 (85)*

3.6 pada edge (85).

(86)*


(87)*

4.2 pada edge (87).

(88)*

3.6 pada edge (88).

(89)*

4.6 pada edge (89).

(90)*

4.7 pada edge (90).

(91)*

4.8 pada edge (91).

(92)*


(93)*

4.5 pada edge (93).

(94)*

4.6 pada edge (94).

(95)*

3.2 pada edgen(95).

(96)*

4.7 pada edge (96).

(97)*

5.1 pada edge (97).

(98)*

19 pada edge (98).

(99)*

20 pada edge (99).

(100)*


(101)*

21.8 pada edge (101).

(102)*


(103)*


(104)*

22.5 pada edge (104).

(105)*

18 pada edge (105).

(106)*

18.9 pada edge (106).

(107)*

16.9 pada edge (107).

(108)*


(109)*

17 pada edge (109).

(110)*


(111)*

25 pada edge (111).

(112)*

25.5 pada edge (112).

(113)*


(114)*


(115)*

18.9 pada edge (115).


28 (116)*


(117)*

5 pada edge (117).

(118)*

23.8 pada edge (118).

(119)*

16.8 pada edge (119).

(120)*

20 pada edge (120).

(121)*


(122)*


(123)*

22.1 pada edge (123).

(124)*


(125)*


(126)*

21.6 pada edge (126).

(127)*

25.1 pada edge (127).

(128)*

16.8 pada edge (128).

(129)*

19.4 pada edge (129).

(130)*


(131)*


(132)*

20.4 pada edge (132).

(133)*


(134)*


(135)*

19.4 pada edge (135).

(136)*

16.1 pada edge (136).

(137)*


(138)*

18 pada edge (138).

(139)*

14.8 pada edge (139).

(140)*


(141)*

16.8 pada edge (141).

(142)*

22.8 pada edge (142).

(143)*

12.4 pada edge (143).

(144)*


(145)*

19.4 pada edge (145).

(146)*

20.4 pada edge (146).


(147)*


(148)*

20.4 pada edge (148).

(149)*

25.6 pada edge (149).

(150)*

6.75 pada edge (150).

(151)*

26 pada edge (151).

(152)*

18.1 pada edge (152).

(153)*

16.7 pada edge (153).

(154)*


(155)*

16 pada edge (155).

(156)*


(157)*

14 pada edge (157).

(158)*

4 pada edge (158).

(159)*

19.5 pada edge (159).

(160)*


(161)*


(162)*

15.3 pada edge (162).

(163)*

10 pada edge (163).

(164)*

5 pada edge (164).

(165)*

21.45 pada edge (165).

(166)*


(167)*


(168)*

15.4 pada edge (168).

(169)*


(170)*


(171)*

22.9 pada edge (171).

(172)*

24.2 pada edge (172).

(173)*

19.1 pada edge (173).

(174)*


(175)*

10.5 pada edge (175).

(176)*

18 pada edge (176).

(177)*

6 pada edge (177).


29

(178)*


(179)*

22.1 pada edge (179).

(180)*

6 pada edge (180).

(181)*

18.6 pada edge (181).

(182)*

7.45 pada edge (182).

(183)*

24.9 pada edge (183).

(184)*

17.6 pada edge (184).

(185)*

20.9 pada edge (185).

(186)*


(187)*


(188)*

21.5 pada edge (188).

(189)*


(190)*


(191)*

21.7 pada edge (191).

(192)*

24.7 pada edge (192).

(193)*


(194)*

16.3 pada edge (194).

(195)*

27.4 pada edge (195).

(196)*

28.45 pada edge (196).

(197)*

28.7 pada edge (197).

(198)*

28.7 pada edge (198).

(199)*

29.4 pada edge (199).

(200)*

19.7 pada edge (200).

(201)*

10.9 pada edge (201).

(202)*

17.85 pada edge (202).

(203)*

19.5 pada edge (203).

(204)*


(205)*

17.6 pada edge (205).

(206)*

26.4 pada edge (206).

(207)*

31.1 pada edge (207).

(208)*

31.1 pada edge (208).


30

(209)*

34.2 pada edge (209).

(210)*

26.9 pada edge (210).

(211)*

28.3 pada edge (211).

(212)*

27.2 pada edge (212).

(213)*

35.2 pada edge (213).

(214)*

35.4 pada edge (214).

(215)*

36 pada edge (215).

(216)*

36.3 pada edge (216).

(217)*

36.5 pada edge (217).

(218)*

33.4 pada edge (218).

(219)*

35.4 pada edge (219).

(220)*


(221)*

15.9 pada edge (221).

(222)*

16.4 pada edge (222).

(223)*


(224)*

18.5 pada edge (224).

(225)*

21.8 pada edge (225).

(226)*

26.4 pada edge (226).

(227)*

23.4 pada edge (227).

(228)*

13 pada edge (228).

(229)*


(230)*

19.5 pada edge (230).

(231)*


(232)*

34 pada edge (232).

(233)*

36 pada edge (233).

(234)*

35.6 pada edge (234).

(235)*

37.8 pada edge (235).

(236)*

38 pada edge (236).

(237)*

38.3 pada edge (237).

(238)*

39.1 pada edge (238).

(239)*

38.9 pada edge (239).


31

(240)*

39.4 pada edge (240).

(241)*

21.9 pada edge (241).

(242)*

23.7 pada edge (242).

(243)*

28.85 pada edge (243).

(244)*


(245)*

16.1 pada edge (245).

(246)*

23.2 pada edge (246).

(247)*


(248)*

10.9 pada edge (248).

(249)*

9.95 pada edge (249).

(250)*


(251)*

39.8 pada edge (251).

(252)*

41.1 pada edge (252).

Total

32

3862.04

Langkah-langkah dari algoritma diatas dapat direpresentasikan kedalam graph pada gambar 3.5 sebagai berikut: (251)*

(236)*

(253)

(235)*

(268) (269)

(234)* (2 33 )*

(1 96 )*

(1 (267) 95 )* (1 48 )* (1 (2 45 (146)* (1 (147)* 70 )* ) 42 )* (144)* (143)* (2 (141)* 71 (137)* (138)* ) (1 (1 (272) 36 (273) 39 )* )* (140)* (135)*

(2 54 )

(216)*

(111)* (1 10 (109)* )* (257)

(108)* (2 58 )

(256)

(1 98 )* (2 55 )

(1 97 )*

(107)* (1 (2 (106)* 05 59 )* ) (2 (1 (133)* (2 (2 60 (2 (1 (2 49 (1 (104)* 63 74 (294) ) 32 34 (132)* 61 )* 03 (130)* ) ) (1 )* (1 )* ) )* 31 (2 01 (129)* )* 23 (2 (295) (262) )* (3 (102)* (2 )* 22 (150)* (275) (264) 93 (225)* (128)* (2 77 )* ) (2 (2 (1 (282) 93 ) (224)* (2 (1 (276) (100)* (2 30 31 14 (99)* ) (2 (127)* (2 (2 78 (126)* 24 65 )* )* )* (1 )* (220)* 2126 ) (2 (166 ) (2 21 (125)* ) )* )* (227)* (113)* 18 15 (219)* (1 28 (123)* )* (66)* )* )* (292) 94 (112)* )* (296) (120)* (2 (122)* (297) )* (69)* (193)* (229)* 90 (1 (2 (291) (65)* (67)* ) (1 (70)* (119)* 16 (6 (2 (280) (2 98 (68)* (1 92 )* 4) 17 89 ) 89 )* * (71)* )* (1 (381) ) )* (2 (1 (299) 86 (118)*17 (6 (7 81 (72)* (3 (191)* )* 3) 3) ) (2 )* 00 (279) (190)* * * 88 (3 (1 (6 ) (7 (302) (188)* 87 ) (2 27 (3 11 2) (78)* (98)* (287) (348) 4) 08 (3 69 ) (3 * )* (185)* * (8 (3 (379) 0) )* 52 ) 10 (301) (3 8 (79)* (1 (75)* * ) 8 ) (382) (370) (82)* 5) (3 (315) (184)* 51 (6 (207)* (3 (81)* (314) (1 (2 (76)* (77)* 3) (1 (3 2 68 8 (3 )* 1) (3 (2 82 (165)* 04 7 6. (373) (2 9 66 ) (1 (2 (3 4) (83)* (2 * (313) 09 (2 01 )* 8) 8 (376) (3 (3 )* (2 (306) (9 (9 1) (9 8 83 (183)* )* 60 13 (1 05 ) (84)* (3 )* (3 02 08 2) 3) 6) (36) 16 03 ) (3 )* )* 67 (3* 8 )* (2 (90)* 5 * * (58)* (3 ) )* (303) ) (312) 8 8) )* (85)* 5) (3 67 (91)* )* 00 19 (181)* 36 (152)* (2 (99) (3 (5 7 ) (86)* (285) (1 ) )* 8 (3 (94)* 5) (1 7) ) (1 7) 84 (161)* (159)* * (317) 78 7 (8 7) (179)* (305) (59)* (2 (206)* (318) 68 74 (1 * ) (1 )* 4)8) (87)* (180)* (153)* (97)* 09 (366) (215)*(3 )* )* 73 * (199)* 77 (1 (176)* (372) )* 0 (89)* (304) 62 )* (3 (154)* (286) )* (3 7) (1 )* 20 65 (3 (44)* 75 (2 (1 (3 (3 (327) ) ) 63 )* 10 55 21 71 (1 (172)* (5 (2 ) )* )* ) ) 69 2) (43)* 14 (3 (3(171)* )* (1 (2 (2 * (53)* (3 )* (3 22 (56)* 6 (325) 28 (42)* 63 (1 50 11 (5 23 2) ) (4 (332) ) (170)* (2 5) (54)* 56 )* )* )* (3 (3 ) 1) (324) * 47 (358) (346) (5 4 )* (1 6) * (2 (361) (3 (331) 1) 4) (4 (342) (330) )* 64 * (359) (157)* (249)* 9) (2 44 (3 35 (40)* * )* (345) (248)* * (3 57 12 )* (48)* ) (4 (246)* (329) (333) (39)* 8) )* 7) ) (356) (360) (158)* (50)* (245)* (46)* * * (2 32(343) (243)* (3 (392) (35)* (351) (2 42 2) (3 (2 1) (3 (33)* * )* (37)* (45)* (3 34 0) * (2 4) (375) (350) (237)* 0) (349) ) * (3 (29)* * 41 * (1 1) (390) (354) (2 (341) )* 3) (238)* * (6 7) (2 (353) * (240)* 8) 0) (239)* (364) * (252)* (326) (17)* (16)* (338) (26)* (347) * (25)* (2 * (19)* (14)* (15)* (380) (18)* 4) (5) (12)* * (337) * (2 (4)* (1)* (6) 3) (11)* (2) * * * (9)* (3)* (339) (2 (7) 2) * * (340)


33 Gambar 3.5 Representasi langkah-langkah Algoritma Prim Dengan demikian minimum spanning tree dari jaringan kabel listrik di blok-P PT Inalum menggunakan algoritma Prim adalah sepanjang 3862.04 meter, sedangkan data dari PT Inalum panjang kabel listrik yang telah terpasang adalah sepanjang 4331.95 meter. Selisih dari panjang kabel listrik PT Inalum dengan yang menggunakan algoritma prim adalah sebesar 469.91 meter. Gambar 3.6 (pada halaman 36) merupakan jaringan listrik yang diperoleh dengan menggunakan algoritma prim.


(251)*

(236)* (235)*

(1 96 )* (234)* (2 33 )*

(1 95 )* (1 48 )* (1 45 (146)* (1 (147)* )* 42 )* (144)* (143)* (141)* (138)* (1 39 )* (140)*

(2 23 (2 )* 22 )*

(225)*

(2 (2 30 31 )* )*

(2 (2 2126 )* )*

(220)*

(227)* (2 28 )* (229)*

(219)*

(191)* (190)* (2 08 )* (2 (204 05)* (2 03 )* )*

(2 02 )*

(2 01 )* (2 00 )*

(2 (206)* 09 )* (2 10 )*

(1 66 (183)* (1 )* 67 )*

(1 68 )*

(248)*

(246)* (245)*

(243)* (237)* (238)* (239)*

(252)*

(1 60 )*

(153)*

(2 1) *

(240)*

(71)* (72)*

(2 13 )*

(1 63 )*

(81)*

(84)*

(215)* (87)*

(9 3) *

(96)*

(9 (94)* 5) *

(8 8) * (89)*

(2 14 )*

(42)* (4 1) *

(40)* (3 (39)* 8) *

(97)*

(1 3) * (16)*

(3 6) *

(5 1) *

(5 2) *

(56)* (5 5) *

(54)* (4 9) *

(50)*

(37)*

(17)*

(77)*

(9 2) *

(44)*

(2 0) *

(18)*

(90)* (91)*

(85)* (86)*

(53)*

(19)*

(76)*

(98)*

(83)*

(43)*

(1 56 )* (157)*

(364)

(7 3) *

(7 4) (78)* * (8 0) (79)* (75)* *

(82)*

(6 1) *

(1 55 )*

(70)* (68)*

(154)*

(158)*

(2 42 )* (2 41 )*

(65)* (67)*

(6 3) *

(58)* (5 7) (59)* *

(152)*

(1 64 )*

(2 44 )*

(1 51 )*

(165)*

(1 62 )*

(170)*

(66)* (112)* (69)*

(161)* (159)*

(1 69 )*

(100)*

(99)*

(6 4) *

(6 2) *

(171)*

(249)*

(2 12 )*

(113)*

(1 16 )*

(1 (188)* 87 )* (185)*

(1 (1 (179)* 78 74 (1 (1 )* (180)* (199)* 77 (176)* )* 73 )* )* (1 75 )* (172)*

(1 14 )*

(127)*

(1 (118)*17 )*

(184)*

(2 47 )*

(1 01 )*

(102)*

(1 15 )*

(1 86 )*

(181)*

(2 50 )*

(2 11 )*

(1 (104)* 03 )*

(1 21 )* (120)* (119)*

(1 82 )*

(106)*

(1 34 (132)* (130)* (1 )* 31 (129)* )*

(122)* (1 89 )*

(1 05 )*

(128)*

(193)* (1 92 )*

(2 17 )*

(207)*

(107)*

(133)*

(1 (126)* 24 )* (125)* (123)*

(1 94 )*

(1 97 )*

(108)* (137)* (1 36 )* (135)*

(150)*

(224)*

(1 98 )*

(111)* (1 10 (109)* )*

(1 49 )*

(2 32 )*

(2 18 )*

(216)*

(15)* (14)* (12)*

(35)* (3 4) *

(3 2) (33)* * (3 1) *

(3 0) (29)* * (2 8) *

(48)* (46)*

(45)* (2 7) * (26)* (25)*

(6 0) (2 * 4) *

(5) * (4)* (6) *

(11)* (9)*

(4 7) *

(2 3) *

(1)* (2) * (3)* (7) *

(2 2) *

(8) * (10)*

Gambar 3.6 Minimum Spanning Tree dari G(253,393) BAB 4

KESIMPULAN DAN SARAN

4.1 Kesimpulan - Panjang kabel yang telah terpasang di blok-P Inalum adalah 4331.95 meter. - Analisis graph hasil representasi dari jaringan listrik yang terpasang di Perumahan Blok-P PT Inalum dengan menggunakan Algoritma Prim menghasilkan minimal spanning tree dengan bobot total 3862.04 meter. Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

- Dari bobot total minimal spanning tree yang diperoleh maka dapat diketahui panjang kabel pada rancangan jaringan listrik optimal yang terpasang di Perumahan Blok-P PT Inalum yaitu 3862.04 meter. - Sehingga jaringan listrik yang telah terpasang di perumahan blok-P PT Inalum belum optimal.

4.2 Saran Pada tulisan ini penulis meneliti jaringan kabel listrik yang telah terpasang di perumahan blok-P Inalum. Dimana dengan menggunakan teori graph yaitu minimum spanning tree diperoleh hasil yang lebih optimal. Maka disarankan untuk membangun suatu jaringan listrik, jalan atau komputer menggunakan minimum spanning tree.

DAFTAR PUSTAKA 34

1. Boffey, T. B. 1989. Graph Theory in Operation Research. The Mac Millan Press Ltd, London,. 2. Bondy, J.A dan Murty, U.S.R. 2008. Graph Theory. Editorial Board by S. Axler dan K.A. Ribet. 3. Bondy, J.A dan Murty, U.S.R. 1982. Graph Theory with Application. 5th ed. New York. Rayi Syahfitri : Penerapan Algoritma Prim Pada Jaringan Listrik Perumahan PT Inalum, 2009. USU Repository © 2009

4. Chartrand, Gary and Oellermann, Ortrud R. 1993. Applied and Algorithmic Graph Theory. McGraw-Hill,Inc. 5. Diestel, Reinhard. 2005. Graph Theory. Electronic Edition © SpringerVerlag New York. 6. Grimaldi, Ralph P. 2004. Discrete and Combinatorial Mathematics, An Apllied Introduction, fifth edition. Rose-Hulman Institute Of Technology. 7. Harary, Frank, Professor of Mathematics University of Michigan. 1969. Graph Theory. 8. Johnsonbaugh, Richard. 2001. Discrete Mathematics. 5th edition. New Jersey: Printice Hall, Inc. 9. Syslo, M, Maciej.,Deo, N., dan Kowalik, S, Janusz. 1983. Discrete Optimization Algorithms with Pascal Programs. New Jersey: PrinticeHall, Inc.

x


PENERAPAN ALGORITMA PRIM PADA JARINGAN LISTRIK PERUMAHAN PT INALUM (Studi Kasus)

Recommend Documents