LAPORAN
PRAKTEK KERJA LAPANGAN
PENCARIAN LINTASAN TERPENDEK PENGIRIMAN SURAT DALAM RANGKA PERINGATAN HUT
RI DI KECAMATAN WARUNGPRING KABUPATEN PEMALANG DENGAN MENGGUNAKAN ALGORITMA
KRUSKAL
Disusun
Oleh:
ATIK
RUMARIYANTI
24010113120003
JURUSAN
MATEMATIKA
FAKULTAS
SAINS DAN MATEMATIKA
UNIVERSITAS
DIPONEGORO
SEMARANG
2016
HALAMAN PENGESAHAN
Laporan Praktek Kerja Lapangan
dengan judul:
PENCARIAN LINTASAN
TERPENDEK PENGIRIMAN SURAT DALAM RANGKA
PERINGATAN HUT RI DI KECAMATAN WARUNGPRING KABUPATEN PEMALANG DENGAN
MENGGUNAKAN ALGORITMA KRUSKAL
Disusun Oleh :
Nama : Atik Rumariyanti
NIM : 24010113120003
Fakultas/Jurusan : FSM/Matematika
Telah
diseminarkan di hadapan penguji dan disahkan pada tanggal : 18 Januari 2016
Semarang,
20 Januari 2016
Mengetahui,
Ketua Jurusan Matematika
Fakultas
Sains dan Matematika
Universitas
Diponegoro
Drs. Solichin Zaki, M.Kom
NIP.
195312191979031007
|
Menyetujui,
Dosen Pembimbing
Drs. Kartono, M.Si.
NIP.
196308251990031003
|
KATA PENGANTAR
Puji syukur Alkhamdulillah penulis
panjatkan kehadirat Allah SWT, karena atas izin-Nya penulis bisa menyelesaikan
Laporan Praktek Kerja Lapangan dengan judul “Pencarian Lintasan Terpendek Pengiriman Surat dalam Rangka Peringatan HUT
RI di Kecamatan Warungpring dengan Menggunakan Algoritma Kruskal”.
Tanpa adanya dukungan dan bantuan
berbagai pihak, laporan ini tidak akan dapat terselesaikan dengan baik. Oleh
karena itu, penulis ingin mengucapkan terimakasih kepada :
1. Drs.
Solichin Zaki, M.Kom, selaku
Ketua Jurusan Matematika Fakultas Sains dan Matematika Universitas Diponegoro.
2. Drs.
Kartono, M.Si, selaku dosen pembimbing yang
telah memberikan bimbingan dalam proses pembuatan laporan ini.
3. Robertus Heri Soelistyo Utomo, M.Si, selaku koordinator
Praktek Kerja Lapangan yang telah mengarahkan penulis dalam prosedur
pelaksanaan Praktek Kerja Lapangan.
4. Bapak
H. Amrullah, S.IP, M.Si, selaku Camat Warungpring yang telah memberikan ijin
melaksanakan Praktek Kerja Lapangan.
5. Seluruh
jajaran di Kantor Kecamatan Warungpring yang telah membimbing dan pengarahan
selama pelaksanaan Praktek Kerja Lapangan.
6. Ibu,
Bapak serta keluarga yang ada dirumah yang selalu mendukung dan memberi
semangat.
7.
Semua pihak yang telah
memberikan bantuan yang tidak dapat penulis sebutkan satu persatu.
Penulis
menyadari bahwa laporan ini masih jauh dari sempurna. Oleh karena itu, kritik
dan saran yang sifatnya membangun sangat penulis harapkan. Penulis berharap
laporan ini dapat bermanfaat bagi semua pihak.
Semarang, 19 Januari 2016
Penulis
DAFTAR
ISI
HALAMAN JUDUL............................................................................................... i
HALAMAN PENGESAHAN
............................................................................... ii
KATA PENGANTAR
........................................................................................... iii
DAFTAR ISI ........................................................................................................... iv
BAB I PENDAHULUAN
...................................................................................... 1
1.1 Latar
Belakang ............................................................................................ 1
1.2 Perumusan
Masalah .................................................................................... 2
1.3 Pembatasan
Masalah ................................................................................... 2
1.4 Tujuan
dan Manfaat .................................................................................... 3
1.4.1
Tujuan.............................................................................................. 3
1.4.2
Manfaat............................................................................................ 3
BAB II TINJAUAN PUSTAKA............................................................................ 4
2.1 Pengertian Graf............................................................................................ 4
2.2 Istilah-Istilah dalam Graf............................................................................. 5
2.3 Macam-Macam Graf.................................................................................... 5
2.4 Isomorfisma................................................................................................. 7
2.5 Macam-Macam Lintasan dalam Graf.......................................................... 7
2.6 Tree.............................................................................................................. 9
2.6.1Sifat-Sifat Tree.................................................................................... 9
2.6.2 Spanning Tree..................................................................................... 10
BAB III METODOLOGI PENELITIAN............................................................. 12
3.1 Sumber Data............................................................................................... 12
3.2 Metoda Pengumpulan Data........................................................................ 12
3.3 Analisis Data............................................................................................... 13
BAB IV PEMBAHASAN....................................................................................... 14
4.1 Profil
Singkat Kecamatan Warungpring...................................................... 14
4.2 Hasil
Pengambilan Data............................................................................... 15
4.3 Analisis
Data ............................................................................................... 21
BAB V PENUTUP.................................................................................................. 69
5.1 Kesimpulan
................................................................................................. 69
5.2 Saran
........................................................................................................... 71
DAFTAR PUSTAKA
........................................................................................... 72
LAMPIRAN ............................................................................................................ 73
BAB I
PENDAHULUAN
1.1
Latar Belakang
Hampir
kurang lebih 350 tahun Indonesia menjadi negara jajahan kurang lebih dari tahun
1595 sampai dengan 1945. Pada tahun 1945 tepatnya pada tanggal 17 Agustus proklamasi
kemerdekaan Indonesia dibacakan oleh Ir. Soekarno presiden pertama Indonesia.
Perjuangan para pemuda Indonesia membuahkan hasil yang akhirnya tercapai suatu
hari kemerdekaan bangsa Indonesia yaitu hari lahirnya bangsa Indonesia. Hari
para bangsa Indonesia terlepas dari siksa jajahan berabad abad lamanya. Oleh
karena itu, rutin setiap tahunnya bangsa Indonesia merayakan hari kemerdekaan
Indonesia pada tanggal 17 Agustus. Setiap wilayah di Indonesia pada tanggal 17
Agustus memperingati hari jadinya bangsa Indonesia dengan berbagai kegiatan yang meriah tak
terkecuali di wilayah Kecamatan Warungpring. Rutin setiap tahunnya di Kecamatan
Warungpring mengadakan serangkaian acara peringatan HUT RI untuk seluruh warga
di Kecamatan Warungpring. Adapun serangkain acaranya antara lain upacara
peringatan detik-detik Proklamasi Kemerdekaan, upacara penurunan bendera,
karnaval, malam wungon, dan lain-lain. Serangkaian acara kegiatan peringatan
proklamasi kemerdekaan ini merupakan acara besar dan penting bagi bangsa
Indonesia tak terkecuali warga masyarakat Kecamatan Warungpring khususnya, sehingga
sangat perlu adanya persiapan yang matang untuk menyiapkan segala halnya. Pada
kegiatan tersebut sangat memerlukan partisipasi semua warga untuk ikut serta
dalam serangkaian kegiatan yang telah direncanakan.
Untuk
keberlangsungan suatu kegiatan maka diperlukan kepanitiaan di Kecamatan
Warungpring yang dalam hal ini para pegawai kantor Kecamatan Warungpring. Untuk
meramaikan hari kemerdekaan, maka dibuat suatu daftar nama penerima surat
undangan yang terdiri atas muspika, dinas/ instansi, ormas, sekolah, desa,
tokoh masyarakat yang ada di wilayah Kecamatan Warungpring untuk peran serta
dalam kegiatan peringatan kemerdekaan tersebut. Dilihat dari kegiatan
peringatan HUT RI yang dilakukan secara rutin, kesulitan yang dirasakan pegawai
dalam mengirim surat dalam menentukan tempat tujuan mana yang harus ditempuh
terlebih dahulu untuk menefisienkan waktu, serta mengingat kegiatan ini yang
sangat dinantikan karena hanya satu tahun sekali sehingga sangat disayangkan
jika terhambat pada proses pengiriman surat maka penulis mempunyai ide untuk mencari lintasan
terpendek dari kantor kecamatan ke penerima surat kegiatan dengan menggunakan
algoritma kruskal dengan harapan dapat membantu proses pengiriman surat yang
berkaitan dengan menentukan tempat mana yang dituju terlebih dahulu.
1.2
Perumusan
Masalah
Dari latar belakang
diatas maka dapat dirumuskan masalah sebagai berikut:
1.
Bagaimana lintasan pengiriman surat sehingga memperoleh jarak yang minimum?
2.
Berapa jarak minimum yang ditempuh dalam pengiriman surat peringatan HUT RI?
1.3
Pembatasan
Masalah
Pada Praktik Kerja Lapangan (PKL) ini pembahasan
masalah hanya dibatasi pada:
1.
Pencarian lintasan terpendek pengiriman
surat kegiatan menggunakan algoritma kruskal
2.
Lintasan
terpendek ditentukan berdasarkan jarak bukan waktu tempuh
3. Terdapat 2 pegawai kecamatan yang bertugas
dalam pengiriman surat
1.4
Tujuan dan Manfaat
1.4.1 Tujuan
Tujuan
dari Praktek Kerja Lapangan ( PKL ) ini adalah sebagai berikut:
1.
Memenuhi tugas mata
kuliah Praktek Kerja Lapangan yang harus dilaksanakan sesuai kurikulum yang
berlaku.
2.
Memaparkan aplikasi
ilmu matematika terapan yang dapat diterapkan untuk menyelesaikan permasalahan di
Kecamatan Warungpring.
3.
Mengetahui lintasan pengiriman surat peringatan
HUT RI untuk memperoleh jarak yang minimum dengan algoritma kruskal.
1.4.2
Manfaat
1.
Bagi mahasiswa
Menambah
pengalaman dan wawasan Mahasiswa khususnya dalam mengaplikasikan ilmu
matematika terapan yang diperoleh di bangku perkuliahan ke dalam dunia kerja.
2.
Bagi Dinas
Sebagai
bahan masukan dan pertimbangan dalam menentukan kebijakan-kebijakan yang
terkait dengan proses pengiriman surat, salah satunya yaitu menentukkan lintasan
dalam pengiriman surat peringatan HUT RI.
BAB II
TINJAUAN PUSTAKA
Teori graf adalah salah satu ilmu yang mempelajari tentang diagram yang
berisi titik-titik dan garis-garis, dimana setiap garis menghubungkan tepat dua
titik. Dalam kehidupan sehari-hari banyak sekali masalah yang penyelesaiannya
dapat dibawa kebentuk diagram yang terdiri dari titik-titik dan garis-garis,
misalnya menentukan rute suatu perjalanan, jaringan listrik, jaringan
telekomunikasi, kimia isomer dan lain-lain. Jaringan-jaringan ini dapat
dimodelkan kedalam kesatuan matematika yang disebut graf. Graf digunakan untuk
mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.
2.1. Pengertian
Graf
Graf
G(V,E) didefinisikan sebagai pasangan himpunan (V,E), dengan V adalah himpunan
berhingga dan tidak kosong dari simpul-simpul atau titik, dan E adalah himpunan
berhingga dari garis.[1]
Graf dengan satu titik dan tidak mempunyai garis disebut
graf trivial. Titik pada graf dapat dinomori dengan huruf-huruf v1,
v2, v3,..., a, b, c, ... sedangkan garis yang menghubungkan
suatu titik vi dengan titik vj
dapat disimbolkan dengan ek, ditulis ek
= (vi, vj).
Dua
garis atau lebih yang menghubungkan pasangan titik yang sama disebut garis
ganda dan sebuah garis yang menghubungkan suatu titik ke dirinya sendiri
disebut lup.[2]
2.2. Istilah-Istilah dalam Graf
2.2.1.
Ketetanggaan (adjacent)
Dua buah titik
dikatakan bertetangga, jika terdapat garis e dengan ujung awal dan akhir adalah
v1 dan v2. ( e=(v1,v2) )
2.2.2
Bersisian (incident)
Suatu garis dikatakan
bersisian pada suatu titik, jika garis tersebut menghubungkan titik tersebut.
2.2.3.
Derajat (degree)
Banyaknya garis yang
ada pada suatu titik v, ( d(v) )
2.2.3. Subgraf
Misal G auatu graf
dengan himpunan titik V(G) dan himpunan garis E(G), subgraf dari G adalah graf
yang semua titiknya anggota dari V(G) dan semua garisnya anggota dari E(G)
2.3. Macam-Macam Graf [1]
Graf dapat
dikelompokkan menjadi beberapa kategori, yaitu :
2.3.1.
Graf Kosong (Null graph)
Graf dengan himpunan garis merupakan
himpunan kosong. Contoh :
● ● ● ●
N4
2.3.2.
Graf Sederhana (simple graph)
Graf yang tidak
mempunyai lup atau garis ganda (multiple edge) Terdapat beberapa macam
graf sederhana, yaitu :
2.3.2.1.
Graf lengkap (complete graph)
Graf
lengkap adalah graf dengan setiap pasang titiknya saling bertetangga.
2.3.2.2.
Graf teratur (regular graph)
Graf teratur adalah
graf yang semua titik dalam graf tersebut berderajat sama.
2.3.2.3.
Graf Lintasan (paths)
Graf lintasan adalah graf yang bentuknya
menyerupai garis lurus.
2.3.2.4.
Graf lingkaran (Cycles)
Graf lingkaran adalah
graf yang bentuknya menyerupai lingkaran.
2.3.3.
Graf Tidak Sederhana (unsimple graph)
Graf tidak sederhana adalah graf yang mempunyai
lup atau garis ganda (multiple
edge)
2.3.4. Graf dengan Kekhususan Tertentu
2.3.4.1. Graf Planar
Graf Planar adalah graf
yang dapat digambarkan pada suatu bidang datar dengan garis-garis yang tidak
saling memotong.
2.3.4.2.Graf
Bipartite
Graf bipartite adalah graf
G dengan himpunan titiknya dapat dibedakan dan dipisahkan menjadi dua himpunan
bagian, yaitu V1 dan V2, sedemikian sehingga setiap garis
di G menghubungkan ke satu titik di V1 ke satu titik di V2,
dengan kata lain setiap pasang titik di V1 tidak bertetangga, dan
setiap pasang titik di V2 juga tidak bertetangga.
2.3.4.3. Graf Berbobot (Weighted graph)
Contoh:
2.4 Isomorfisma [1]
Isomorfik adalah dua
buah benda yang sama tetapi secara geometri bersifat berbeda. Dua buah graf G1
dan G2 dikatakan mempunyai isomorfisma (isomorfiks), jika terdapat
pemetaan satu-satu antara titik-titik di G1 dan titik-titik di G2,
dan dipenuhinya syarat :
1) jumlah garis masing-masing
graf sama,
2) jumlah titik
masing-masing graf sama,
Contoh:
2.5. Macam-Macam
Lintasan dalam Graf [1]
Lintasan adalah
sederetan garis atau titik secara berselang seling yang membentuk sambungan
yang tidak putus pada graf G. Macam Lintasan antara lain:
2.5.1. Lintasan Sederhana
Lintasan sederhana adalah lintasan yang setiap
titik yang dilalui berbeda (atau setiap
garis yang dilalui hanya satu kali).
2.5.2.
Lintasan Tertutup
Lintasan tertutup (closed path) adalah lintasan yang berawal dan berakhir pada titik
yang sama.
2.5.3.
Lintasan Terbuka
Lintasan terbuka (open path) adalah lintasan yang berawal
dan berakhir pada titik yang berbeda..
Jalan
(walk) adalah sederetan garis-garis
yang membentuk sambungan yang tidak putus di G
Definisi Keterhubungan
dalam graf [1]
Suatu
graf G disebut terhubung (connected)
apabila setiap pasang titik sembarang, misal: u dan v di G mempunyai suatu
lintasan dari titik u menuju titik v. Lintasan tertutup adalah lintasan dengan
titik awal dan titik akhir lintasan sama (u=v).
Contoh:
Graf Euler
Lintasan
Euler adalah lintasan yang melalui masing-masing garis dalam graf tepat satu
kali. Bila lintasan tersebut kembali ke titik asal, membentuk lintasan
tertutup, maka lintasan itu dinamakan sirkuit Euler. Graf yang mempunyai
sirkuit Euler dinamakan graf Euler, dan graf yang mempunyai lintaan Euler
dinamakan graf semi-Euler.[1]
Graf Hamilton
Lintasan
Hamilton adalah lintasan yang melalui setiap titik di dalam graf tepat satu
kali. Bila lintasan itu kembali ke titik awal dan membentuk lintasan tertutup
maka disebut sirkuit Hamilton. Graf yang memiliki sirkuit Hamilton dinamakan
graf Hamilton, sedangkan graf yang memiliki lintasan Hamilton disebut graf semi
Hamilton.[1]
2.6 Tree
Suatu tree
adalah suatu graf terhubung yang tidak memuat sikel.
Contoh:
2.6.1 Sifat-sifat Tree [2]
Misalkan T suatu graf dengan n
titik, maka
1.
T
adalah terhubung dan tidak memuat sikel
2.
T
adalah terhubung dan mempunyai n-1 garis
3.
T
mempunyai n-1 garis dan tidak memuat sikel
4.
T
terhubung d
an setiap garis
adalah suatu jembatan(bridge)
5.
Setiap
dua titik dari T terhubung dengan tepat satu path
6.
T
tidak memuat sikel, tetapi penambahan dari setiap garis baru membuat tepat satu
sikel.
2.6.2
Spanning Tree
Misalkan
G graf terhubung. Suatu
spanning tree dalam G adalah subgraf
dari G yang memuat semua titik dari G dan juga adalah tree.[2]
Minimum Spanning Tree
Dalam praktek biasanya
setiap garis dari graf mempunyai bobot dan diharapkan spanning tree yang dihasilkan mempunyai bobot total minimal atau
biasa disebut minimum spanning tree.
Ada beberapa algoritma yang
digunakan untuk mencari Minimun Spanning
Tree, antara lain:
1.
Algoritma Kruskal
2.
Algoritma Solin
3.
Algoritma Greedy
Algoritma Kruskal
Langkah-langkah
Algoritma kruskal
1.
Lakukan
pengurutan terhadap setiap garis dengan bobot terkecil sampai terbesar
2.
Buat
graf G yang terdiri dari titik
3. Buat
tree (T) dari graf G tersebut dengan memasukkan 1 garis yang mempunyai bobot
minimum atau garis terpendek yang tidak membentuk sirkuit di T
4. Ulangi
langkah 3 sampai minimum spanning tree
terbentuk, yaitu ketika banyak garis T = (banyak titik G) – 1
Algoritma
Solin
Langkah-langkah Algoritma solin
1.
Lakukan
pengurutan terhadap setiap garis dengan bobot terbesar sampai terkecil
2.
Lakukan
penghapusan pada garis yang mempunyai bobot terbesar berdasarkan urutan yang
tidak menyebabkan graf G menjadi tidak terhubung atau garis yang membentuk
sirkuit pada graf G
Algoritma
Greedy
Langkah-langkah Algoritma greedy
1. Pilih
garis dengan bobot minimal dari graf G
2. Ulangi
langkah 1 sampai semua titik G terhubung dan tidak membentuk sikel
BAB
III
METODOLOGI
PENELITIAN
3.1
Sumber data
Pengumpulan
data dilakukan dengan Praktek Kerja Lapangan (PKL) selama 1 bulan yang dimulai
dari tanggal 3 Agustus
2015 sampai dengan 27 Agustus 2015 di kantor Kecamatan Warungpring Jalan Warungpring-Pakembaran km 1.
Data-data yang diperoleh dari antara lain :
1. Data primer
Data
primer diperoleh secara langsung melalui observasi dan wawancara dengan pihak
tertentu yang berhubungan dengan pengiriman surat.
2. Data Sekunder
Data
sekunder diperoleh secara tidak langsung dari sumber-sumber yang telah ada di kantor Kecamatan Warungpring, meliputi
data- data yang berhubungan dengan serangkaian kegiatan peringatan HUT RI di
Kecamatan Warungpring.
3.2
Metoda Pengumpulan Data
1. Metode
yang digunakan untuk memperoleh data dari Praktek Kerja Lapangan ini adalah
melalui dokumen perusahaan yang tersedia
dan wawancara kepada pihak tertentu, meliputi data-data serangkaian
kegiatan peringatan HUT RI di Kecamatan Warungpring.
2.
Dari data jarak tempuh
diperoleh dengan mengukur lewat bantuan aplikasi google map Kecamatan Warungpring, dengan mendatangi tempat penerima
surat satu persatu. Kemudian dilakukan analisa yang akan menghasilkan data
lintasan terpendek pengiriman surat dari kantor Kecamatan Warungpring ke
penerima surat.
3.3 Analisis
Data
Teknik yang digunakan dalam proses pencarian
lintasan terpendek adalah teori graf dengan Metode algoritma
kruskal.
BAB
IV
PEMBAHASAN
4.1 Profil Singkat Kecamatan
Warungpring
Kecamatan Warungpring merupakan salah satu wilayah di Kabupaten
Pemalang Provinsi Jawa Tengah yang
terletak di sebelah utara Jawa Tengah bagian barat, sekitar 145 km dari Ibukota
Propinsi Jawa Tengah. Sedangkan dari Ibukota Kabupaten Pemalang berjarak kurang
lebih 34 km. Ada 6 desa di Kecamatan Warungpring yaitu desa Warungpring, desa
Karangdawa, desa Cibuyur, desa Datar, desa Mereng, dan desa Pakembaran yang
secara keseluruhan mempunyai 192 Rukun Tetangga dan 31 Rukun Warga dengan luas
wilayah Kecamatan Warungpring adalah 26,31 km2. Guna memberikan arah
dalam mencapai tujuan organisasi Pemerintah Kecamatan, maka diperlukan visi yang menjadi acuan dalam pelaksanaan tupoksi dan
misi yang menjadi langkah-langkah yang ditempuh dalam mewujudkan visi Kecamatan
Warungpring adalah sebagai berikut:
Visi :
“Terwujudnya tertib administrasi dalam
penyelenggaraan pemerintah yang efektif”
Misi:
1. Meningkatkan
kualitas pelayanan masyarakat yang berbasis pelayanan prima
2. Meningkatkan
kualitas penyelenggaraan pemerintahan dan administrasi ketatausahaan
3. Meningkatkan
kualitas kemampuan kelembagaan organisasi yang optimal melalui pemantapan tugas
dan kewenangan aparatur yang berjiwa profesional
4. Meningkatkan
upaya pemberdayaan masyarakat
5. Meningkatkan
peran dan fungsi koordinasi dan pembinaan berkesinambungan dalam bidang
pemerintahan, pembangunan dan kemasyarakatan.
4.2
Hasil
Pengambilan Data
Data yang
digunakan dalam penelitian ini yaitu data daftar nama serta alamat penerima surat.
Daftar nama penerima surat dapat dilihat sebagai berikut:
Tabel
1. Penerima Surat
NO
|
NAMA/DINAS/INSTANSI
|
ALAMAT
|
I.
|
MUSPIKA
1. Camat Warungpring
2. Danposramil Warungpring
3. Kapolsek Warungpring
|
Warungpring
Warungpring
Warungpring
|
II.
|
DINAS/INSTANSI
1. Kepala UPP Kec. Warungpring
2. Kepala UPPU Wil. II
3. Kepala Puskesmas Warungpring
4. Kepala KUA Kec. Warungpring
5. Kepala UPKB Warungpring
6. Petugas Kehutanan Lapangan
7. Petugas Perikanan dan Peternakan
8. Mantri Statistik
9. Mantri Tani
10. Petugas PBB
11. Koordinator BPP
12. Kepala Pasar Warungpring
13. Petugas Disdukcatpil
|
Polsek Warungpring
Randudongkal
Warungpring
Warungpring
Kec. Warungpring
Kec. Warungpring
Kec. Warungpring
Kec. Warungpring
Kec. Warungpring
Kec. Warungpring
Kec. Warungpring
Warungpring
Kec. Warungpring
|
III.
|
BUMN/BUMD/LAINNYA
1. BKK Warungpring
2. BRI Warungpring
3. Kantor Pos dan Giro Kec.
4. PDAM Ranting Warungpring
|
Warungpring
Warungpring
Warungpring
Karangdawa
|
IV.
|
ORMAS/ OKP
1. KNPI
2. Karang Taruna
3. LVRI
4. PWRI
5. MWC NU
6. Fatayat NU
7. IPNU
8. IPPNU
9. PKK Kec.
10. Dharma Wanita Kec.
11. Dharma Pertiwi
12. Bhayangkari
13. DHR 45
|
Mereng
Warungpring
Warungpring
Warungpring
Warungpring
Karangdawa
Mereng
Mereng
Kec. Warungpring
Kec. Warungpring
Polsek Warungpring
Polsek Warungpring
Warungpring
|
V.
|
SMA/SMP
1. SMK Idaman Warungpring
2. MA Salafiyah Karangtengah
3. MA Nurul Huda Mereng
4. SMP N 1 Warungpring
5. SMP N 2 Warungpring
6. SMP Islam Warungpring
7. MTs Al-Maskuriyah Datar
8. MTs. Salafiyah Karangtengah
9. MTs. Nurul Huda Mereng
|
Warungpring
Karangtengah
Mereng
Warungpring
Mulian
Mereng
Datar
Warungpring
Mereng
|
VI.
|
KEPALA DESA
1. Kepala Desa Warungpring
2. Kepala Desa Mereng
3. Kepala Desa Karangdawa
4. Kepala Desa Datar
5. Kepala Desa Cibuyur
6. Kepala Desa Pakembaran
|
Warungpring
Mereng
Karangdawa
Datar
Cibuyur
Pakembaran
|
VII.
|
TOKOH
ULAMA/TOKOH MASYARAKAT
1. KH. ABDUL AZIZ
2. KH. FARIKHIN
3. KH. MAHMUD
4. ANWAR SUPADI
5. SLAMET SODIKIN, S.Pd, M.Pd.
6. SURAJI
7. H. SUWARNO
8. SAOJI
9. MAHMUD, S.Ag
10. FATKHUROHMAN
11. SUGIYANTO
12. AHMAD SONHAJI
13. KH. SYAMSUDIN
14. UST. MUHLISIN LABIB, S.Ag.
15. JAUHAR MAKNUN
16. K. RAHMAT
17. SYAMSUDIN
18. K. SAHARI
19. UST. MANSYUR
20. H. DARSONO
21. AKHMAD FAIZIN HS
22. SULASTRO
23. UST.ABDUL CKOLIQ RUMLI
|
Karangtengah
Karangtengah
Mereng
Warungpring
Cibuyur
M2M Cibuyur
Cibuyur
Warungpring
Mereng
Datar
Karangdawa
Warungpring
Pakembaran
Mereng
Karangdawa
Karangdawa
Gombong
Cibuyur
Cibuyur
Cibuyur
Cibuyur
Cibuyur
Cibuyur
|
Berdasarkan data diatas,
setelah dilakukan pengukuran jarak lewat aplikasi google map maka didapat sebuah gambar graf sebagai berikut:
Gambar
1.netwoks pengiriman surat bagian barat
Gambar
2.netwoks pengiriman surat bagian timur
Untuk
lebih mudah dalam perhitungan lintasan terpendek network dapat juga di
representasikan sebagai berikut:
Gambar 3. graf G
pengiriman surat di Kecamatan Warungpring
4.3
Analisis
Data
Setiap garis menyatakan lintasan
penghubung antar lokasi Kantor Kecamatan dan lokasi penerima surat. Angka-angka
yang terdapat pada setiap garis merupakan bobot graf yang mewakili panjang
jalan dengan satuan meter.
Pembentukan
minimum spanning tree dengan
menggunakan algoritma kruskal:
Keterangan
|
|
1 :
|
Kantor Kec. Warungpring
|
2 :
|
SMPN 1 Warungpring
|
3 :
|
Bpk. Ahmad Sonhaji
|
4 :
|
Kepala Pasar Warungpring
|
5 :
|
Puskesmas, DHR 45, LVRI, Anwar Supadi, BRI
|
6 :
|
Kantor Desa Warungpring
|
7 :
|
Bpk. Saoji
|
8 :
|
Bpk. Jauhar Maknun
|
9 :
|
Kantor Desa Karangdawa
|
10 :
|
K. Rahmat, Bpk. Sugiyanto
|
11 :
|
PDAM Warungpring
|
12 :
|
Fatayat NU
|
13 :
|
SMPN 2 Warungpring
|
14 :
|
Mts. dan MA Salafiyah Karang Tengah, MNC NU
|
15 :
|
Kh. Abdul Aziz, Kh. Farikhin
|
16 :
|
Kh. Syamsudin
|
17 :
|
Kantor Desa Pakembaran
|
18 :
|
KNPI
|
19 :
|
Bpk. Syamsudin
|
20 :
|
Danposranmil Warungpring
|
21 :
|
Kh. Mahmud
|
22 :
|
Mts dan MA Nurul Huda Mereng, IPNU, IPPNU
|
23 :
|
Ust. Muhlis
|
24 :
|
SMP Islam Warungpring
|
25 :
|
Bpk. Mahmud
|
26 :
|
Kantor Desa Mereng
|
27 :
|
KUA Kecamatan Warungpring
|
28 :
|
SMK Idaman Warungpring
|
29 :
|
Kantor Pos, BKK Warungpring
|
30 :
|
Bpk. Suraji
|
31 :
|
Ust. Mansyur
|
32 :
|
Bpk. Warsito
|
33 :
|
Bpk. Ahmad Faizin
|
34 :
|
H. Suwarno
|
35 :
|
Ust. Abdul Ckoliq
|
36 :
|
H. Darsono
|
37 :
|
Bpk. Slamet Sodikin, Kantor Desa Cibuyur
|
38 :
|
Kantor Desa Datar
|
39 :
|
Bpk. Fatkhurohman
|
40 :
|
Mts. Al-Maskuriyah Datar
|
41 :
|
K. Sahari
|
42 :
|
Bpk. Sulastro
|
43 :
|
UPPU Wilayah 2 Randudongkal
|
44 :
|
Kapolsek Warungpring, Dharma Pertiwi, Bhayangkari
|
1) Lakukan
pengurutan terhadap setiap garis dengan bobot terkecil sampai terbesar
Garis
|
Bobot (m)
|
Garis
|
Bobot (m)
|
(1,2)
|
50
|
(31,32)
|
600
|
(20,44)
|
50
|
(31,34)
|
600
|
(23,24)
|
50
|
(7,8)
|
650
|
(29,30)
|
50
|
(9,10)
|
700
|
(2,3)
|
90
|
(34,37)
|
700
|
(21,22)
|
90
|
(12,14)
|
850
|
(8,9)
|
120
|
(11,12)
|
850
|
(18,19)
|
130
|
(24,25)
|
850
|
(5,6)
|
150
|
(34,36)
|
850
|
(4,5)
|
160
|
(22,25)
|
900
|
(38,40)
|
160
|
(31,35)
|
900
|
(14,15)
|
190
|
(12,13)
|
950
|
(6,7)
|
200
|
(26,27)
|
1000
|
(6,29)
|
200
|
(16,17)
|
1200
|
(3,4)
|
210
|
(15,19)
|
1200
|
(37,41)
|
210
|
(20,21)
|
1200
|
(10,11)
|
220
|
(38,41)
|
1200
|
(4,27)
|
230
|
(19,20)
|
1300
|
(28,29)
|
240
|
(26,33)
|
1300
|
(21,23)
|
300
|
(32,33)
|
1300
|
(22,23)
|
300
|
(33,36)
|
1400
|
(28,31)
|
300
|
(41,42)
|
1500
|
(35,36)
|
300
|
(17,18)
|
2100
|
(4,7)
|
400
|
(25,26)
|
2100
|
(1,44)
|
400
|
(15,17)
|
2800
|
(21,27)
|
450
|
(40,42)
|
2800
|
(11,14)
|
500
|
(9,38)
|
2900
|
(38,39)
|
500
|
(33,42)
|
3100
|
(30,34)
|
550
|
(10,38)
|
3300
|
(36,37)
|
550
|
(40,43)
|
3600
|
(4,8)
|
600
|
(42,43)
|
5200
|
(27,28)
|
600
|
2)
Buat
graf G yang terdiri dari titik
3) Buat
tree (T) dari graf G tersebut dengan memasukkan 1 garis yang mempunyai bobot
minimum atau garis terpendek yang tidak membentuk sirkuit di T
4) Ulangi
langkah 3 sampai minimum spanning tree terbentuk, yaitu ketika
banyak garis T = (banyak titik G) – 1
Berdasarkan
langkah 4, telah didapat banyak garis T = (banyak titik G) – 1 dengan banyak
garis T = 43 dan diketahui banyak titik G = 44, sehingga banyak garis T =
(banyak titik G) – 1= 44-1 = 43
Adapun untuk
perbandingan pencarian minimum spanning
tree menggunakan algoritma solin dengan langkah-langkah sebagai berikut:
1)
Lakukan
pengurutan terhadap setiap garis dengan bobot terbesar sampai terkecil
Garis
|
Bobot (m)
|
Garis
|
Bobot (m)
|
(42,43)
|
5200
|
(4,8)
|
600
|
(40,43)
|
3600
|
(36,37)
|
550
|
(10,38)
|
3300
|
(30,34)
|
550
|
(33,42)
|
3100
|
(38,39)
|
500
|
(9,38)
|
2900
|
(11,14)
|
500
|
(40,42)
|
2800
|
(21,27)
|
450
|
(15,17)
|
2800
|
(1,44)
|
400
|
(25,26)
|
2100
|
(4,7)
|
400
|
(17,18)
|
2100
|
(35,36)
|
300
|
(41,42)
|
1500
|
(28,31)
|
300
|
(33,36)
|
1400
|
(22,23)
|
300
|
(32,33)
|
1300
|
(21,23)
|
300
|
(26,33)
|
1300
|
(28,29)
|
240
|
(19,20)
|
1300
|
(4,27)
|
230
|
(38,41)
|
1200
|
(10,11)
|
220
|
(20,21)
|
1200
|
(37,41)
|
210
|
(15,19)
|
1200
|
(3,4)
|
210
|
(16,17)
|
1200
|
(6,29)
|
200
|
(26,27)
|
1000
|
(6,7)
|
200
|
(12,13)
|
950
|
(14,15)
|
190
|
(31,35)
|
900
|
(38,40)
|
160
|
(22,25)
|
900
|
(4,5)
|
160
|
(34,36)
|
850
|
(5,6)
|
150
|
(24,25)
|
850
|
(18,19)
|
130
|
(11,12)
|
850
|
(8,9)
|
120
|
(12,14)
|
850
|
(21,22)
|
90
|
(34,37)
|
700
|
(2,3)
|
90
|
(9,10)
|
700
|
(29,30)
|
50
|
(7,8)
|
650
|
(23,24)
|
50
|
(31,34)
|
600
|
(20,44)
|
50
|
(31,32)
|
600
|
(1,2)
|
50
|
(27,28)
|
600
|
2)
Lakukan
penghapusan pada garis yang mempunyai bobot terbesar berdasarkan urutan yang
tidak menyebabkan graf G menjadi tidak terhubung atau garis yang membentuk
sirkuit pada graf G
Ataupun
pencarian minimum spanning tree menggunakan
algoritma greedy dengan langkah-langkah sebagai berikut:
1) Pilih
garis dengan bobot minimal dari graf G
2) Ulangi
langkah 1 sampai semua titik G terhubung dan tidak membentuk sikel
Jadi,
baik menggunakan algoritma kruskal, solin maupun greedy diperoleh minimum spanning
tree yang sama yaitu dengan total jarak 25000 m atau 25 km. Namun dapat
dilihat bahwa algoritma kruskal mempunyai kelebihan-kelebihan dibanding
algoritma solin dan greedy yaitu:
1) Pada
algoritma kruskal untuk menentukan garis minimum yang dipilih dari graf G
terlebih dahulu dilakukan pengurutan garis dengan bobot terkecil sampai
terbesar sehingga graf G yang mempunyai n titik atau garis yang berjumlah puluhan
akan lebih mudah dalam memilih garis minimum dibanding algoritma greedy
2) Didalam
algoritma kruskal dengan memilih 1 garis yang mempunyai bobot minimum dan
dilakukan berulang-ulang dengan tidak membuat sirkuit sampai diperoleh banyaknya
garis = (banyaknya titik G)-1, yaitu menambah garis demi garis pada graf G
dengan n titik atau garis yang berjumlah puluhan akan lebih efektif
dibandingkan dengan menghapus garis demi garis seperti algoritma solin
Adapun pencarian minimum spanning tree menggunakan salah satu softwere matematika
yaitu WINQS memperoleh hasil yang sama dapat dilihat tabel solusi sebagai
berikut:
Dan bentuk graf Spanning treenya dapat dilihat sebagai berikut:
Setelah
diperoleh minimum spanning tree maka
dilakukanlah pencarian lintasan terpendek dari kantor kecamatan warungpring ke
penerima surat dan kemudian kembali lagi ke kantor (lintasan tertutup) melewati
setiap penerima surat atau minimal satu kali tetapi harus memperhatikan
penerima surat mana yang harus dilalui
lebih dari 1 kali yang menghasilkan jarak minimum. Karena terdapat 2 pegawai yang bertugas
pengiriman surat maka graf minimum
spanning tree yang diperoleh akan dibagi 2 bagian sebagai berikut:
1.
Lintasan pertama
Rute
(lintasan tertutup) :
1-2-3-4-27-21-22-23-24-25-26-33-32-31-35-36-37-41-42-43-40-38-39-38-41-37-34-30-29-28-29-6-5-4-3-2-1
Jarak
: 25090 m (25,090 km)
Jadi, pegawai
dapat mengirim suratnya terlebih dahulu dengan urutan rutenya sebagai berikut:
1). KUA
Kecamatan Warungpring
2). Kh.
Mahmud
3).Mts dan
MA Nurul Huda Mereng, IPNU, IPPNU
|
4). Ust.
Muhlis
|
5).SMP
Islam Warungpring
|
6). Bpk.
Mahmud
|
7). Kantor
Desa Mereng
|
8). Bpk.
Ahmad Faizin
|
9). Bpk.
Warsito
10).Ust.
Mansyur
|
11). Ust.
Abdul Ckoliq
|
12). H.
Darsono
|
13).
Kantor Desa Cibuyur
14). Bpk.
Slamet Sodikin
15). K.
Sahari
16). Bpk.
Sulastro
17). UPPU
Wilayah 2 Randudongkal
18).Mts. Al-Maskuriyah
Datar
19).Kantor
Desa Datar
20). Bpk.
Fatkhurohman
21). H.
Suwarno
|
22). Bpk.
Suraji
|
23). Kantor Pos, BKK Warungpring
24).SMK Idaman Warungpring
25). Kantor Desa Warungpring
26).
Puskesmas, DHR 45, LVRI, Anwar Supadi, BRI
|
Lintasannya dapat digambarkan
sebagai berikut:
2. Lintasan kedua
Rute (lintasan
tertutup) :
1-2-3-4-7-8-9-10-11-12-13-12-14-15-17-16-17-18-19-20-44-1
Jarak : 15410 m (15,410
km)
Jadi, pegawai
dapat mengirim suratnya terlebih dahulu dengan urutan rutenya sebagai berikut:
1). Kantor Kec. Warungpring
a. Camat Warungpring
b. Kepala
UPKB Warungpring
c. Petugas
Kehutanan Lapangan
d. Petugas
Perikanan dan Peternakan
e. Mantri
Statistik
f. Mantri
Tani
g. Petugas
PBB
h. Koordinator
BPP
i.
Petugas Disdukcatpil
j.
PKK Kec.
k. Dharma
Wanita Kec.
|
2). SMPN 1 Warungpring
|
3). Bpk. Ahmad Sonhaji
|
4). Kepala Pasar Warungpring
|
5). Bpk. Saoji
|
6). Bpk. Jauhar Maknun
|
7). Kantor Desa Karangdawa
|
8). K. Rahmat, Bpk. Sugiyanto
|
9). PDAM Warungpring
|
12).Fatayat NU
|
13).SMPN 2 Warungpring
|
14). Mts. dan MA Salafiyah Karang Tengah, MNC NU
|
15). Kh. Abdul Aziz
16).Kh. Farikhin
17).Kantor Desa Pakembaran
|
18).Kh. Syamsudin
|
19). KNPI
|
20). Bpk. Syamsudin
|
21). Danposranmil Warungpring
|
22).Kapolsek Warungpring, Dharma Pertiwi, Bhayangkari
|
BAB V
PENUTUP
5.1
Kesimpulan
Berdasarkan hasil dari
pencarian lintasan terpendek dengan menggunakan algoritma kruskal pada
pengiriman surat serangkaian kegiatan peringatan proklamasi kemerdekaan RI di
Kecamatan Warungpring, dapat disimpulkan bahwa ada dua lintasan tertutup yang dilalui
untuk memperoleh jarak minimum. Pegawai pertama pengiriman surat dengan
lintasan surat yang akan dikirim dengan urutan sebagai berikut:
1). KUA
Kecamatan Warungpring
2). Kh.
Mahmud
3).Mts dan
MA Nurul Huda Mereng, IPNU, IPPNU
|
4). Ust.
Muhlis
|
5).SMP
Islam Warungpring
|
6). Bpk.
Mahmud
|
7). Kantor
Desa Mereng
|
8). Bpk.
Ahmad Faizin
|
9). Bpk.
Warsito
10).Ust.
Mansyur
|
11). Ust.
Abdul Ckoliq
|
12). H.
Darsono
|
13).
Kantor Desa Cibuyur
14). Bpk.
Slamet Sodikin
15). K.
Sahari
16). Bpk.
Sulastro
17). UPPU
Wilayah 2 Randudongkal
18).Mts. Al-Maskuriyah
Datar
19).Kantor
Desa Datar
20). Bpk.
Fatkhurohman
21). H.
Suwarno
|
22). Bpk.
Suraji
|
23). Kantor Pos, BKK Warungpring
24).SMK Idaman Warungpring
25). Kantor Desa Warungpring
26).
Puskesmas, DHR 45, LVRI, Anwar Supadi, BRI
|
Dengan jarak tempuh
25,09 km. Sedangkan Pegawai kedua pengiriman surat dengan lintasan surat yang
akan dikirim dengan urutan sebagai berikut:
1). Kantor Kec. Warungpring
a. Camat Warungpring
b. Kepala
UPKB Warungpring
c. Petugas
Kehutanan Lapangan
d. Petugas
Perikanan dan Peternakan
e. Mantri
Statistik
f. Mantri
Tani
g. Petugas
PBB
h. Koordinator
BPP
i.
Petugas Disdukcatpil
j.
PKK Kec.
k. Dharma
Wanita Kec.
|
2). SMPN 1 Warungpring
|
3). Bpk. Ahmad Sonhaji
|
4). Kepala Pasar Warungpring
|
5). Bpk. Saoji
|
6). Bpk. Jauhar Maknun
|
7). Kantor Desa Karangdawa
|
8). K. Rahmat, Bpk. Sugiyanto
|
9). PDAM Warungpring
|
12).Fatayat NU
|
13).SMPN 2 Warungpring
|
14). Mts. dan MA Salafiyah Karang Tengah, MNC NU
|
15). Kh. Abdul Aziz
16).Kh. Farikhin
17).Kantor Desa Pakembaran
|
18).Kh. Syamsudin
|
19). KNPI
|
20). Bpk. Syamsudin
|
21). Danposranmil Warungpring
|
22).Kapolsek Warungpring, Dharma Pertiwi, Bhayangkari
|
Dengan jarak tempuh
15,41 km.
5.2
Saran
Berdasarkan laporan Praktek Kerja
Lapangan ini, penulis berharap dengan solusi lintasan terpendek yang telah
dibahas diatas pegawai yang bertugas dalam pengiriman surat peringatan HUT RI
tidak lagi mengalami kesulitan dalam menentukan
tempat tujuan mana yang harus ditempuh terlebih dahulu sehingga kegiatan akan
berjalan dengan lancar tanpa kendala dalam proses pengiriman surat.
DAFTAR
PUSTAKA
[1]
Noviyasari, Citra. 2010 Matematika Diskret. Bandung: Manajemen
Informatika UNIKOM
[2]
Ratnasari, Lucia & Bayu Surarso. 2008. Buku
Ajar Teori Graf. Semarang: FMIPA
Universitas Diponegor
karena gambar rutenya terlalu banyak, jadi ndabisa terbaca di displaynya oleh karena itu teman-teman bisa mendownload file lengkapnya disini yaa
http://www.4shared.com/folder/fNWXMFlx/_online.htmlkarena gambar rutenya terlalu banyak, jadi ndabisa terbaca di displaynya oleh karena itu teman-teman bisa mendownload file lengkapnya disini yaa
Tidak ada komentar:
Posting Komentar