MAKALAH
GRAF DAN ANALISIS ALORITMA

 

Disusun Untuk Memenuhi Tugas Mata Kuliah  Graf dan Analisi Algoritma

 

Dosen Pengampu : Rukin Sudarwanto. S.Pd.,M.T.I

 

 

DISUSUN OLEH :

 

NAMA                   : M. HASAN UBAIDILLAH

NIM                        : 1957201045

SEMESTER          : 4 (Empat)

 

 

PROGAM STUDI SISTEM INFORMASI 

FAKULTAS SAINS DAN TEKNOLOGI

UNIVERSITAS NAHDLATUL ULAMA LAMPUNG

TAHUN 2021

KATA PENGANTAR
   

        Puji Syukur Kehadirat Tuhan Yang Maha Esa Atas Segala Rahmatnya Sehingga Makalah Ini Dapat Tersusun Hingga Selesai . Tidak Lupa Kami Juga Mengucapkan Banyak Terimakasih Atas Bantuan Dari Pihak Yang Telah Berkontribusi Dengan Memberikan Sumbangan Baik Materi Maupun Pikirannya.

        Dan Harapan Kami Semoga Makalah Ini Dapat Menambah Pengetahuan Dan Pengalaman Bagi Para Pembaca, Untuk Ke Depannya Dapat Memperbaiki Bentuk Maupun Menambah Isi Makalah Agar Menjadi Lebih Baik Lagi.

       Karena Keterbatasan Pengetahuan Maupun Pengalaman Kami, Kami Yakin Masih Banyak Kekurangan Dalam Makalah Ini, Oleh Karena Itu Kami Sangat Mengharapkan Saran Dan Kritik Yang Membangun Dari Pembaca Demi Kesempurnaan Makalah Ini.

 

 

Lampung Timur, 16 Maret 2021

 

 

M. Hasan ubaidillah

 

 

 

 

 

BAB I

PENDAHULUAN

1.1 LATAR BELAKANG

Dalam teori grafik, permasalahan penugasan bersyarat membahas bagaimana menemukan susunan pemberian tugas atau pekerjaan pada pekerja agar sebuah pekerjaan tersebut dapat dilakukan dengan seoptimal mingkin dengan beberapa konstrain permasalahan yang ada. Pemasalahan penugasan bersyarat yang diangkat dalam penelitian ini diambil dari persoalan SPOJ Klasik 6819 yang berjudul Yet Another Assignment Problem dengan kode soal ASSIGN5. Permasalahan tersebut akan diselesakan dengan pendekatan pencarian Maximum-size Matching pada sebuah birpartite graph.

   Pada permasalahan Yet Another Assignment Problem, terdapat beberapa pekerjaan dan beberapa orang pekerja yang akan mengerjakan pekerjaan tersebut. Setiap pekerjaan harus dilakukan oleh semua orang yang ada serta setiap orang memiliki waktu yang dibutuhkan tersendiri dalam menyelesaikan pekerjaan tersebut. Setiap orang hanya dapat mengerjakan sebuah pekerjaan dan sebuah pekerjaan hanya dapat dikerjakan oleh satu orang dalam satu waktu. Pekerjaan yang dimaksud juga bersifat independen dalam artian dapat dilakukan kapanpun oleh setiap orang. Semua orang juga dapat berhenti kapanpun untuk melakukan sebuah pekerjaan tersebut.

 

1.2 Rumusan Masalah

1.         Apa Pengertian Graf?

2.         Terminologi dasar graf?

1.3 Tujuan Penulisan

1.    Mengetahui Pengertian Graf?

2.    Terminologi dasar Graf?

 

 

BAB II

PEMBAHASAN

A.    PENGERTIAN GRAF

Algoritma Hopcroft-Karp adalah algoritma yang memerlukan bipartite graph sebagai masukannya dan menghasilkan maximum-size matching didalam grafik tersebut sebagai keluarannya. Algoritma  ini  ditemukan John  Hopcroft and Richard Karp pada tahun 1973.

Sebagian besar ide dasar dari algoritma ini hampir sama dengan teknik inverting augmenting path dalam mencari maximum-size matching, hanya saja algoritma ini mencari beberapa augmenting path sekaligus dalam sekali iterasi dengan meggunakan himpunan maksimal dari augmenting path terpendek. (Izzuddin et al., 2016)

 

Graf digunakan untuk menggambarkan hubungan antara titik atau simpul dengan tepi atau garis yang saling berhubungan. Jurnal tentang graf pertama kali ditulis oleh matematikawan Swiss Leonhard Euler (1707-1783) dengan karya yang terkenal yaitu Kӧnigsberg Bridge Problem, dimana kota Kӧnigsberg (sekarang bernama Kaliningrad) yang berada di Prussia Timur merupakan wilayah yang terdiri dari dua pulau dan dikelilingi oleh sungai, dimana antarkota dihubungkan denga tujuh jembatan. (Sholikhatin et al., 2020)

 

Teori Graf merupakan salah satu kajian dalam matematika diskrit yang digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek diskrit tersebut. Teori Graf banyak diterapkan dalam berbagai bidang keilmuan diantaranya : optimalisasi jaringan (baik itu jaringan transmisi nasional, jaringan listrik PLN, saluran air PDAM maupun jaringan komunikasi), ekonomi, psikologi genetika dan riset operasi. Tulisan ini membahas tentang pohon merentang minimum (minimum spanning tree), khususnya algoritma prim, dan penerapannya dalam jaringan transmisi khususnya jaringan transmisi nasional provinsi Sulawesi Selatan, sehingga jaringan transmisi tersebut dapat optimal (minimum). (Kementerian Kesehatan Republik Indonesia, 2016)

 
B.     Terminologi Dasar Graf

Berikut ini adalah beberapa terminologi atau istilah-istilah yang sering digunakan dalam graf.

1.      Bertetangga (adjacent)

Dua buah simpul dikatakan bertetangga jika kedua simpul tersebut terhubung oleh suatu sisi.

Pada Gambar 1, simpul 1 dan 2 dikatakan bertetangga karena dihubungkan oleh sisi e₁, sedangakan  simpul 1 dan 4 tidak bertetangga karena tidak ada sisi yang menghubungkan keduanya.

2.      Bersisian (incidency)

Suatu sisi e dikatakan bersisian dengan simpul v₁ dan v₂ jika e menghubungkan kedua simpul tersebut.

3.      Simpul terpencil (isolated vertex)

Jika suatu simpul tidak memiliki sisi yang bersisian dengannya maka disebut simpul terpencil.

4.      Derajat (degree)

Derajat suatu simpul menyatakan jumlah sisi yang bersisian dengan simpul tersebut.

5.      Lintasan (path)

Lintasan yang panjangnya n dari simpul awal v₀ ke simpul tujuan v_n dalam sebuah graf ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v₀, v₁, v₂, v₃, ..., v_n.

 

BAB III

KESIMPULAN

 

 

Berdasarkan hasil penelitian yang dilakukan dapat disimpulkan bahwa dengan  penggunaan Algoritma Prim ini penghematan kabel dapat dilakukan sepanjang 222 km.

 

DAFTAR PUSTAKA

Izzuddin, M., Wijaya, A. Y., & Soelaiman, R. (2016). Desain dan Analisis Algoritma Penyelesaian Permasalahan Penugasan Bersyarat dengan Representasi Bipartite Graph. Jurnal Teknik ITS, 5(2), 2–4. https://doi.org/10.12962/j23373539.v5i2.16858

Kementerian Kesehatan Republik Indonesia. (2016). No 主観的健康感を中心とした在宅高齢者における 健康関連指標に関する共分散構造分析Title. 07(June), 50–61.

Sholikhatin, S. A., Prasetyo, A. B., Nurhopipah, A., Komputer, F. I., & Purwokerto, U. A. (2020). Aplikasi Berbasis Desktop Untuk Penyelesaian Graph Dengan. 3(2), 89–93.