BAB PENDAHULUAN
1.1.
Latar Belakang Teori graf
merupakan pokok bahasan yang sudah sangat tua usianya namun memiliki banyak sekali terapan sampai saat ini. Graf
dipakai untuk merepresentasikanobjek – objek
diskrit dan hubungan antara objek– objek tersebut. Representasi visual dari
graf adalah dengan menyatakan objek–
objek sebagai sebuah titik atau bulatan yang juga sering disebut dengan verteks dan biasanya
diberi lambang v, sedangkan hubungan antara
objek– objek tersebut dilambangkan dengan sebuah garis atau rk yang juga sering disebut dengan edge dan biasa diberi
lambang e.
Ada banyak jenis graf yang dapat
digolongkan berdasarkan jenis rknya, ataupun
dapat juga digolongkan berdasarkan ada atau tidaknya arah pada rk dari graf tersebut. Berdasarkan jenis rknya maka
graf dibagi kepada 2 jenis yaitu graf sederhana
(simple graph) dan graf tak sederhana (unsimple graph). Adapun graf sederhana adalah graf yang tidak mengandung
gelang (loop) maupun rk ganda (multiple
edge). Sedangkan graf tak sederhana adalah graf yang mengandung rk ganda dan dapat saja juga mengandung gelang.
Adapun graf tak sederhana dapat dibagi 2
yaitu graf ganda (multi graph) dan graf semu (pseudo graph). Graf ganda adalah graf yang memiliki rk ganda tanpa memiliki
gelang. Sedangkan graf semu adalah graf
yang memiliki gelang dan bisa juga sekalian memiliki rk ganda atau hanya memiliki gelang tanpa rk ganda.
Selanjutnya berdasarkan ada atau tidaknya arah pada rk, maka graf dapat terbagi 2 yaitu
graf tak berarah (undirected graph) dan
graf berarah (directed graph) yang biasa disebut juga digraf. Graf tak berarah adalah graf yang setiap rknya tidak memiliki
arah sehingga setiap rknya hanya digambarkan
berupa garis saja tanpa ada penunjuk
arah. Sedangkan graf berarah adalah graf
yang setiap rknya memiliki arah tertentu sehingga rk – rknya digambarkan
berupa garis beserta tanda panah sebagai penunjuk arah tertentu.
1.3.
Pembatasan Masalah Permasalahan
yang dibahas dalam penulisan ini adalah untuk sembarang graf yaitu untuk semua model graf tanpa terkecuali baik
dari graf sederhana maupun graf tak sederhana.
1.4. Tujuan Penelitian Penelitian ini bertujuan
untuk mencari dan menemukan suatu rumus yang tepat untuk mencari dan menghitung banyaknya jumlah
seluruh subgraf dari graf.
1.5. Manfaat Penelitian Karena penelitian ini bertujuan untuk mencari
suatu rumus yang tepat untuk menghitung
banyaknya subgraf dari graf sembarang, maka penulis mengharapkan rumus yang berhasil ditemukan ini nantinya
dapat berguna untuk menemukan dan memetakan
semua subgraf dari graf sembarang sehingga pada akhirnya akan lebih memudahkan dalam penghitungan jumlah subgraf dari
graf sembarang.
Selain itu penulis juga berharap
bahwa pada masa mendatang rumus ini dapat dipakai untuk melahirkan rumus – rumus baru
lainnya yang berguna untuk menemukan
suatu pola tertentu dari subgraf– subgraf yang bersifat khs dari suatu graf dan akhirnya dapat juga ditemukan suatu
rumus untuk menghitung jumlah subgraf – subgraf khs tersebut. Misalkan untuk
menghitung banyaknya subgraf yang
berbentuk graf terhubung (connected graph) dari suatu graf, subgraf yang berbentuk graf teratur (regular graph),
subgraf yang berbentuk bipartit (bipartite graph), subgraf – subgraf yang isomorfik,
subgraf – subgraf yang planar, maupun juga untuk menemukan rumus untuk menghitung
banyaknya subgraf – subgraf yang memiliki
lintasan Euler maupun lintasan Hamilton, dan lain– lain.
1.6.
Metodologi Penelitian Penelitianini merupakan penelitian literatur atau
kepustakaan. Penelitian ini dilakukan dengan
pertama kali melakukan kajian terhadap buku –
buku mengenai teori graf maupun
buku – buku matematika diskrit yang di
dalamnya memuat topik – topik mengenai
kombinatorika dan teori graf. Secara garis besar metodologi penelitian ini adalah sebagai berikut : 1.
Mengumpulkan berbagai literatur yang berhubungan dengan kombinatorika dan teori graf.
2. Mempelajari literatur – literatur yang telah
dikumpulkan.
3. Mengamati dan meneliti berbagai macam contoh
graf kemudian membuat subgraf – subgraf
yang memungkinkan dari graf – graf tersebut.
4. Menyn dan mengelompokkan subgraf – subgraf
secara baik dan teratur dengan tujuan
untuk mencari dan menemukan suatu pola tertentu mengenai pembentukan subgraf ini.
5. Membuat dugaan – dugaan dari pola – pola
yang telah didapat untuk selanjutnya
dijadikan acuan dasar dalam membuat rumus yang tepat untuk menghitung jumlah subgraf dari suatu graf.
n, kepX H a p�b (Wc yle='mso-spacerun:yes'> sekarang adalah xndan keputusan optimal dibuat
sesudahnya.
fn * (sn) = fn(sn, xn * ) Hubungan rekursif akan selalu memiliki bentuk
: fn * (sn) = maxxn {fn(sn, xn)} atau fn
* (sn) = minxn {fn(sn, xn)} dimana fn(sn, xn) akan dinyatakan dalam sn, xn, f *
n+1(sn+1) dan mungkin beberapa ukuran
tentang keefektifan (atau ketidakefektifan) tahap pertama dari xn.
Hubungan rekursif dinamakan
demikian karena hubungan tersebut selalu berulang setiap bergerak ke belakang tahap
demi tahap. Bila tahap sekarang bernomor n diturunkan satu tahap, maka fungsi f * (sn)
baru akan diturunkan menggunakan f * n+1(sn+1)
yang baru saja diturunkan dalam iterasi sebelumnya, proses ini berulang terus.
Perhitungan maju dilaksanakan
dalam urutan f1
f2 f3, metode perhitungan ini dikenal sebagai prosedur maju
( forward procedure) karena perhitungan
maju dari tahap pertama ke tahap akhir. Sedangkan metode untuk perhitungan mulai dari tahap akhir dan
kemudian berlanjut ke tahap satu dinamakan prosedur mundur ( backward procedure).
Perbedaan utama antara prosedur maju dan prosedur mundur adalah dalam mengidentifikasi
keadaan sistem.
1.5. Tujuan Penelitian 1. Mengetahui jumlah tenaga kerja pada setiap
shift dengan menggunakan Program Dinamik
2. Mengetahui perbandingan jumlah
perawat yang bekerja antara real worlddan metode Program Dinamik 1.6. Manfaat Penelitian Manfaat dari penelitian ini adalah dapat
membantu pihak rumah sakit sebagai alternatif
kebijakan bagi para pengambil keputusan di RSJ Daerah Provinsi Sumatera Utara 1.7. Metode Penelitian Metode yang digunakan dalam penelitian adalah
langsung ke lapangan untuk mengambil
data yang diperlukan. Data yang dipergunakan adalah banyaknya tenaga perawat pada rumah sakit, data ini akan
digunakan untuk menentukan berapa jumlah tenaga perawat yang bekerja pada setiap
shiftnya. Data tentang jumlah shift dimana jumlah shifnya ada tiga yaitu pagi dari pukul
08.00 sampai pukul 14.30, siang dari pukul
14.30 sampai pukul 21.00, dan malam dari pukul 21.00 sampai pukul 08.00.
Skripsi Mathematics:Jumlah Subgraf Dari Graf
Download lengkap Versi PDF
 | ||
| ||
| ||
| ||
|