tugas matematika informatika lengkap
TRANSCRIPT
TUGAS MATEMATIKA INFORMATIKA
BAB I
PENDAHULUAN
I.1 Relasi Rekurensi
Persamaan rekurensi adalah persamaaan yang menentukan nilai suku n
dalam fungsi dari suku-suku sebelumnya yaitu n-1, n-2, ….. . Relasi Rekurensi yang
paling terkenal dan sering digunakan yaitu barisan fibonacci. Relasi ini adalah relasi
rekurensi yang paling tua di dunia, dibahas dalam buku Liber Abacci (thn. 1202) yang
ditulis oleh Leonardo of Pisa yang lebih dikenal dengan Fibonacci. Pada Saat itu
dicoba untuk menghitung jumlah pasangan kelinci yang ada, jika setiap pasangan
kelinci setiap bulan dapat menghasilkan sepasang anak kelinci baru.Bila syarat awal
diberikan a0 = 1 dan a1 = 1 maka bilangan yang diperoleh dengan menggunakan
rumus rekursi di atas untuk n = 2, 3, 4, ..... disebut Barisan Fibonacci dan suku a0
disebut bilangan fibbonacci, jadi barisan fibbonacci sebagai beikut ;
1,1,2,3,5,8,13,21,34,55,89,144,233,…..
I.2 Relasi Rekursi
Relasi Rekursi adalah sebuah formula rekursif di mana setiap bagian dari
suatu barisan dapat ditentukan menggunakan satu atau lebih bagian sebelumnya. Jika
ak adalah banyak cara untuk menjalankan prosedur dengan objek,
untuk k = 0, 1, 2,….., maka Relasi Rekursi adalah sebuah persamaan yang
menyatakan an sebagai sebuah fungsi dari ak untuk k < n. Bentuk umum relasi rekursi
adalah
C0ar + C2ar-2 + … + Ckar-k = f(r)
Dimana ;
Setiap Ci adalah konstanta (tidak tergantung pada r)
Disebut relasi rekursi derajat ke k
C0 dan Ck tidak bernilai 0
I.3 Graf
Suatu graf adalah himpunan benda-benda yang disebut verteks (atau node)
yang terhubung oleh edge-edge (atau arc). Biasanya graf digambarkan sebagai
kumpulan titik-titik (melambangkan verteks) yang dihubungkan oleh garis-garis
(melambangkan edge). Secara fataumal, definisi dari graf sebagaimana yang terlihat
pada definisi dibawah ini.
Suatu graf tak berarah (Undirected graf) G adalah suatu pasangan terurut (V,E)
dengan V merupakan himpunan verteks (node) dan E adalah himpunan dari
multisetya yang terdiri dari dua elemen di V, elemen dari E dinamakan edge atau arc.
Graf tak berarah ini biasa disimbolkan dengan G=(V,E).
Himpunan vertex V biasa dituliskan dengan V = { V1, V2, ….., Vn} dalam hal ini V,
mempunyai n buah elemen yaitu V1, V2, ….., Vn. Begitu juga dengan himpunan E
bisa dituliskan dengan E= {e1, e2,….., em } dimana e1 = {vj , vk} Verteks u dan v
dikatakan adjacent jika ada sebuah edgee = {u, v }. Dalam hal ini, vertex u dan v
disebut titik ujung dari e, dan e dikatakan menghubungkan vertex u dan v . Atau
edgee dikatakan incident dengan vertek u dan v .
Suatu graf berarah (Directed graf) G adalah suatu pasangan terurut (V, E) dengan V
merupakan himpunan verteks (node) danE adalah relasi biner pada V atau E:V→V.
Elemen dari E dinamakan edge atau arc (busur). Graf berarah ini biasa disimbolkan
dengan G=(V,E)
Sebagaimana pada graf tak berarah, himpunan vertex V biasa dituliskan dengan;
V = { V1, V2, ….., Vn} dalam hal ini V, mempunyai n buah elemen yaitu
V1, V2, ….., Vn. Begitu juga dengan himpunan E bisa dituliskan dengan
E= {e1, e2,….., em } dimana e1 = {vj , vk} merupakan pasangan terurut vertex.
Ingat bahwa (vj , vk) ≠ (vk , vj).
Verteks u dan v dikatakan adjacent jika ada sebuah edgee = (u, v) atau e = (v, u).
Dalam hal e = (u, v), vertex u disebut verteks awal dari e dan vertex v disebut verteks
akhir dari e, dan e dikatakan menghubungkan dari (incident from) vertex u dan
menghubungkan ke (incedentto) verteks v.
BAB II
PEMBAHASAN
II.1 RELASI REKURENSI Kuliah Ke-1
Definisi
Relasi rekursi yang tergantung pada harga n adalah barisan bilangan a0, a1, a2, ..., an,
dengan an dapat dinyatakan sebagai fungsi dari n harga ai sebelumnya.
Contoh 1 :
Contoh relasi rekurensi yang diperoleh dari pengacakan suatu bilangan bulat
{1, 2, ..., n} yaitu :
Dn = (n-1) (Dn-2 + Dn-1) ....................(1. 1)
Atau :
Dn = n Dn-1 + (-1)n ....................(1. 2) n = 2, 3, 4, ...dst.
Pada relasi rekurensi (1. 1) bila ditentukan syarat awal D1 = 0 dan D2 = 1 maka
bilangan D3, D4, ..., Dn dapat dihitung.
Sedangkan pada relasi rekurensi (1. 2) harga Dn dapat dihitung bila harga Dn-1
diketahui. Sehingga hanya dibutuhkan 1 syarat awal D1 = 0.
Berdasarkan harga awal tersebut dapat dihitung barisan bilangan pengacakan
yang nilainya sama dengan yang dihitung dari persamaan (1. 1)
Contoh 2 :
Contoh relasi rekurensi an = n an-1 , n = 2, 3, 4, ....... dst
Syarat awal a1 = 1 dan dengan menggunakan iterasi didapat :
an = n an-1
= n(n-1) an-2
= n(n-1) (n-2) an-3
= n(n-1) (n-2) (n-3) ....... 3x2x1 = n!
Dari sini diperoleh an = n! adalah banyaknya permutasi himpunan yang terdiri
dari n bilangan bulat {1, 2, ..., n}
Contoh 3 :
Contoh relasi rekurensi dari barisan Fibonacci
an = an-1 + an-2 , n = 3, 4, ...... dst
Relasi ini adalah relasi rekurensi yang paling tua di dunia, dibahas dalam buku
Liber Abacci (thn. 1202) yang ditulis oleh Leonardo of Pisa yang lebih dikenal
dengan Fibonacci.
Definisi : Bila syarat awal diberikan a0 = 1 dan a1 = 1 maka bilangan yang
diperoleh dengan menggunakan rumus rekursi di atas untuk n = 2, 3, 4, .....
disebut Barisan Fibonacci
Dari perhitungan diperoleh barisan Fibonacci sebagai berikut :
1, 1, 2, 3, 5, 8, 13, 34, 55, 89, 144, 233, 377, 610, ........
Sifat barisan Fibonacci dapat ditulis :
a0 + a1 + a2 + .......... + an = an+2 – 1
Buktikan dengan induksi lengkap !
Sifat bilangan Fibonacci memenuhi :
an = n - n
II.2 RELASI REKURSI Kuliah Ke-2
1. Relasi Rekurensi Linier Berkoefisien Konstan
Bentuk Umum
C0ar + C2ar-2 + … + Ckar-k = f(r)
Setiap Ci adalah konstanta (tidak tergantung pada r)
Disebut relasi rekursi derajat ke k
C0 dan Ck tidak bernilai 0
Contoh 1 :
Relasi Rekursi linier derajat 1 berkoefisien konstan :
2ar + 2ar-1 = 2r atau 3ar – 5ar-1 = 4r
Relasi Rekursi linier derajat 2 berkoefisien konstan :
3ar – 5ar-1 + 2ar-2 = r2 + 5 atau ar + 7ar-2 = 0
Relasi Rekursi linier derajat 3 berkoefisien konstan :
2ar – 2ar-1 – 5ar-2 + 6ar-3 = r2 + 1
Contoh 2 :
Perhatikan relasi rekursi 3ar – 5ar-1 + 2ar-2 = r2 + 5, yang berlaku untuk setiap
harga r = 2, 3, 4, … ; bila diberikan harga a3 = 3 dan a4 = 6
Maka dapat dihitung harga a5 sebagai ;
a5 = ( -5 x 6 + 2 x 3 – (52 + 5) ) = 18
a6 = ( -5 x 18 + 2 x 6 – (62 + 5) ) = dst
Dapat dihitung harga a2, a1, a0 sebagai ;
a2 = ( 3 x 6 – 5 x 3 – (42 + 5) ) =
a1 = ( 3 x 3 – 5 x 9 – (32 + 5) ) = 33
a0 = ( 3 x 9 – 5 x 25 – (22 + 5) ) =
Kesimpulan :
Bila diketahui relasi rekursi derajat ke-2 dan diketahui dua harga a3 = 3 dan
a4 = 6, maka dapat diperoleh hanya satu barisan bilangan yang memenuhi
relasi rekursi tersbut.
Secara Umum :
Untuk suatu relasi rekursi derajat ke k berkoefisien k harga ai yang berurutan
am-k, am-k-1, … , am-1, untuk suatu harga yang tertentu, maka setiap harga yang
lain pasti dapat ditentukan dengan rumus
am = ( C1am-1 + C2am-2 + … + ckam-k – f(m) )
Selanjutnya harga am+1 dapat dihitung sebagai ;
am+1 = ( C1 am + C2 am-1 + … + C2 am-k – f(m+1) )
Demikian pula untuk harga am+2, am+3 dan seterusnya
Dilain fihak harga am-k-1 dapat dihitung sebagai ;
am-k-1 = ( C0 am-1 + C1 am-2 + … + Ck-1 am-k – f(m-1) )
Dan harga amk-2 adalah ;
am-k-2 = (C0 am-1 + C2 am-3 + … + C2 am-k+1 – f(m-2) )
Analog untuk menghitung am-k-3 dan seterusnya
Untuk setiap relasi rekursi linier derajat ke – k berkoefisien konstan, bila
diketahui harga-harga k buah ai yang berurutan maka dapat ditentukan harga-
harga ai lainnya secara unik
Dengan perkataan lain, k buah harga-harga ai, yang diberikan merupakan
himpunan syarat batas yang harus dipenuhi oleh relasi rekursi tersbut untuk
dapat memperoleh harga-harga yang unik
Catatan :
1. Relasi rekursi linier derajat ke k berkoefisien konstan, dengan syarat batas
kurang dari k buah ai yang berurutan, maka hal ini tidak dapat menetukan
fungsi yang memenuhi relasi tersbut secara unik.
Perhatikan ar + ar-1 + ar-2 = 4 relasi rekursi derajat 2 koefisien konstan,
hanya diberikan satu syarat batas a0 = 2 maka aka nada banyak fungsi
numeric yang akan memenuhi relasi rekursi tersebut.
Berikut adalah contoh barisan bilang yang memenuhi kedua syarat tersbut
yaitu ar + ar-1 + ar-2 = 4 dengan a0 = 2
2,0,2,2,0,2,2,0,2,2,0,……
2,2,0,2,2,0,2,2,0,2,2,……
2,5,-3,2,5,-3,2,5,-3,2,……
2. Relasi rekursi linier derajat ke k berkoefisien konstan, paling banyak hanya
daoat ditentukan sejumlah k syarat batas
Pada relasi rekursi linier derajat 2 koefisien konstan berikut ;
ar + ar-1 + ar-2 = 4 bila diberikan syarat batas a0 = 2, a1 = 1 dan a3 = 2, maka
ketiga harga tadi tidak memenuhi relasi rekursi tersebut
2. Jawab Dari Relasi Rekursi
Terdiri atas
Jawab homogen dari relasi rekursi dengan mengambil f(r) = o dan
Jawab Khusus yang memnuhi relasi rekursi yang sebenarnya
Misal jawab homogen a(h) = (a0(h), a1
(h), …) dan
Jawab khusus a(k) = (a0(k), a1
(k), …) maka
Jawab umum a= a(h) + a(k)
3. Jawab Homogen dari Relasi Rekursi
Definisi Relasi Rekursi Homogen : C0ar + c2ar-2 + …+ Ckar-k = 0
Jawab homogeny dari suatu persmaan diferensi linier berkoefisien konstan
dapat ditulis dalam bentuk A r
akar karakteristik dan A adalah konstan yang akan ditentukan kemudian
untuk memnuhi syarat batas yang diberikan
Substitusi kepersamaan relasi rekursi homogeny diperoleh ;
C0 A r + C1 A r + … + Ck A r-k = 0
Atau :
C0 r + C1 r-1 + … + Ck r-k = 0
Bila 1 akar karakteristik dari persamaan tersebut, maka A 1r akan memenuhi
persamaan homogen
Jadi jawab homogen yang dicari berbentuk A 1r
Persamaan karakteristik ke- k akan mempunyai k buah akar karakteristik
Jika semua akar karakteristik berbeda, maka jawab homogen dari relasi rekursi
yang diberikan dapat ditulis dalam bentuk ;
Ar(h) = A1 1
r + A2 2r
+ … + Ak kr
Contoh 3 :
Diberikan relasi rekursi Fibonacci ar = ar-1 + ar-2
Persamaan karakteristik yang diperoleh adalah ;
2 - -1 = 0 dengan akar-akar 1 = ; 2 =
Jadi jawab homogen dari relasi rekursi Fibonacci adalah ;
Ar(h) = A1
r + A2 r
Konstanta A1 dan A2, ditentukan kemudian untuk memenuhi syarat batas
a0 = 1 dan a1 = 1
Sifat :
Misalakan adalah suatu bilang riil atau kompleks yang tidak nol
Maka an = n adalah jawab dari relasi rekursi C0ar + C1ar-1 + … + Ckar-k = 0 jika
dan hanya jika akar karakteristik dari polynomial C0Xr + C1Xr-1 + … +
CkXr-k = 0
4. Jawab Umum Persamaan Relasi Rekursi Homogen
Bila 1, 2, … , k k buah akar karakteristik yang berbeda dari persamaan
karakteristik C0ar + C2ar-2 + … + Ckar-k = 0 serta d1, d2, … , dk konstanta
sebarang, maka umum relasi rekursi homogen adalah ;
An = d1 1n + d2 2
n + … + dk kn Konstanta d1, d2, … , dk dapat ditentukan bila
syarat batas dari relasi rekursi diberikan.
Contoh 4 :
Diberikan relasi rekursi berikut ;
An – 2an-1 – an-2 + 2an-3 = 0
Persamaan karakteristik yang bersangkutan dengan relasi rekursi ini ;
x3 – 2x2 – x + 2 = 0
Akar karakteristik dari persamaan ini ;
1 = 1, 2 = -1, dan 3 = 2
Jawab umum dari relasi rekursi homogen di atas adalah ;
an = d11n + d2(-1)n + d3(2)n
5. Persamaan Karakteristik Berakar Ganda
Jawab Homogen dari relasi rekursi homogen berakar ganda
Bila persamaan karakteristik dari relasi rekursi yang diberikan mempunyai i
sebagai akar ganda m maka bentuk berikut merupakan jawab homogen dari
relasi rekursi
C0ar + C1ar-1 + … + Ckar-k = 0 ;
ar = (A1rm-1 + A2rm-2 + … + Am-2r2 + A m-1r + Am) 1r
Konstanta A1, A2, … , Am akan ditentukan oleh syarat batas yang diberikan
Contoh 5 :
Diberikan relasi rekursi ar + 6ar-1 + 12ar-2 + 8ar-3 = 0
Persamaan karakteristiknya 3 + 6 2 + 12 + 8 = 0
Didapat akar-akar karakteristik yaitu 1 = 2 = 3 = -2 atau harga kelipatan
akar ganda adalah m = 3
Jadi bentuk umum dari jawab homogen adalah ;
ar (h) = (A1r2 + A2r + A3)(-2)r
Conoh 6 :
Diberikan relasi rekursi 4ar - 20ar-1 + 17ar-2 - 4ar-3 = 0
Persamaan karakteristiknya 3 - 20 2 + 17 - 4 = 0
Diperoleh akar karakteristik , , dan 4 berarti 4 akar tunggal, sedangkan
adalah akar ganda 2
Jadi jawab uum relasi rekursi homogeny dapat ditulis ;
ar (h) = (A1r + A2) ar
(h) r + A3(4)r
II. 3 RELASI REKURSI Kuliah Ke-3
1. Jawab Khusus Relasi Rekursi
Tidak ada metode yang dapat menentukan jawab khusus relasi rekursi yang
non homogeny (relasi rekursi dengan f ( (r)≠0 )
Untuk masalah yang sederhana, dapat diterka hanya dengan melihat rekursi
relasi tersebut
Untuk memenetukan jawab khusus relasi rekursi tersebut, diberikan beberapa
model jawab tertentu, diberikan beberapa model jawab tertentu yang
disesuaikan dengan f(r) itu sendiri
Model yang sering diguankan adalah model polinom & model eksponen
2. Jawab Khusus Relasi Rekursi Dengan Model Polinom
Bila suatu relasi rekursi mempunyai f(r) yang berbentuk polynomial derajat t :
F1 rt + f2 rt-1 +……+ Ftr + Ft+1
Maka jawab khusus relasi rekursi ;
P1rt + P2rt-1 +…...+ Ptr + Pt+1
Contoh 1 :
Diberikan relasi rekursi ar + 5ar-1 + 6ar-2 = 3r2
Jawab khusus yang akan di coba adalah bentuk polinomial derajat 2, karena
f(r) berbentuk polynomial derajat 2 juga
Misalkan polynomial tersebut P1r2 + P2r + P3 , P1, P2, P3 akan ditentukan
Subtitusi polynomial ke dalam relasi rekursi, akan diperoleh ;
P1r2 + P2r + P3
5P1(r-1)2 + 5P2(r-1) + 5P3
6P1(r-2)2 + 6P2(R-2) + 6P3
Secara sederhana dapat ditulis dalam bentuk :
12 P1r2 – ( 34P1 – 12P2 )r + ( 29P1 – 17P2 + 12P3)
Bentuk terakhir merupakan polynomial derajat 2 yang besarnya 3r2 maka
dapat ditulis;
12 P1r2 – ( 34P1 – 12P2 )r + (29P1 – 17P2 + 12P3) = 3r2
Sehingga diperoleh :
12P1 = 3
34P1 – 12P2 = 0
29P1 – 17P2 + 12P3 = 0
Yang menghasilkan P1 = 1/4, P2 = 17/ 4 dan P3 = 115/228
Jadi bentuk khusus yang memenuhi relasi rekursi homegen adalah :
ar(k) = 1/4 r2 + 17/24 r + 115/228
3. Jawab Khusus Relasi Rekursi Dengan model Eksponen
Bila suatu relasi rekursi nonhomogen mampunyai f(r) yang berbentuk βr, maka
jawab khusus akan berbentuk P βr, β bukan akar karakteristik
Bila f(r) berbentuk ;
(F1 rt + F2 rt-1 +…..+ Ftr + Ft+1) βr
Maka jawab khusus relasi rekursi ini adalah :
(P1 rt + P2 rt-1 +…..+ Ptr + Pt+1) βr
Bila β bukan akar karakteristik dari persamaan diferensi yang terbentuk
Contoh 2 :
Diberikan relasi rekursi ar + 5ar-1 + 6 ar-2 = 42 x 4r
Jawab khusus persamaan diferensi nonhomogen akan dicoba dengan bentuk
eksponen P4r
subtitusikan P4r ke dalam relasi rekursi
Diperoleh P4r + 5P4r+1 + 6P4r-2 = 42 x 4r atau
21/8 P4r = 42 x 4r
21/8 P = 42
P = 16
Jadi jawab khusus relasi rekursi adalah : ar(k) = 16 x 4r
4. Jawab Keseluruhan Relasi Rekursi
Misalkan relasi rekursi yang diberikan merupakan relasi rekursi derajat t, dan
akar persamaan karakteristik semuanya mempunyai sejumlah t buah harga
yang berbeda
Maka jawab keseluruhan dari relasi rekursi tersebut dapat ditulis sebagai
ar = A1 1r + A2 2
r +…+ At tr + p(r)
p(r) adalah jawab khusus persamaan nonhomogen
untuk menentukan t buah konstanta A1, A2….At perlu diberi t buah syarat
batas
Contoh 4 :
rhatika relasi rekursi ar + 5ar-1 1 + 6ar-2 = 42 x 4r
Jawab keseluruhan akan berbentuk :
ar = A1(-2)r + A2(-3)r + 16 x 4r
Bila selanjutnya diberikan 2 buah syarat batas yang berbentuk a2 = 278 dan
a3 = 962 maka persamaan linier diperoleh :
278 = 4A1 + 9A2 + 256
962 = -8A1 – 27A2 + 1024
A1 = 1, A2 = 2
Jadi jawab keseluruhan relasi rekursi :
ar = (-2) + 2(-3) + 16 x 4r
II.4 RELASI REKURSI Kuliah Ke-4
1. Penyelesaiian Relasi Rekursi dengan Iterasi dan Induksi
Contoh 1 :
→ Perhatikan Relasi Rekursi an = 2 an-1 + 1 dengan syarat batas a0 = 0
jawab :
→ Selesaikan dengan cara iterasi :
an = 2 an-1 + 1
= 2(2an-2 + 1) + 1 = 22 an-2 + 2 + 1
= 22 (2n-3 + 1) + 2 + 1 = 2 an-3 + 2 + 1
= …...........
→ Dengan cara induksi :
n = 0, rumus benar a0 = 20 – 1 = 0,
asumsikan rumus benar untuk n = k, ak = 2k – 1
akan dibuktikan rumus benar untuk n = k + 1
Dari relasi rekursi ak+1 = 2 ak + 1
= 2(2k - 1) + 1
ak+1 = 2k+1 - 1 (rumus berlaku untuk semua n)
jadi an = 2n - 1 adalah solusi relasi rekursi an = 2 an-1 + 1 dengan syarat batas
a0 = 0
Contoh 2 :
Diketahui relasi rekursi an = an-1 + 3
Kondisi awal (syarat batas) a1 = 2
Jawab :
Dengan iterasi, ganti n dengan n-1, didapat :
an-1 = an-2 + 3
Bila an-1 di atas disubtitusi :
an = an-1 + 3
= an-2 + 3 + 3
= an-2 + 2 . 3
Ganti n dengan an-2 :
an-2 = an-3 + 3
Subtitusi an-2 :
an = an-2 + 2 . 3
= an-3 + 3 + 2 . 3
= an-3 + 3 . 3
Secara umum :
an = an-k + k . 3
Bila k = n – 1; an = a1 + (n – 1) . 3
karena a1 = 2, akan di dapat formula an = 2 + 3(n – 1) yang merupakan
solusi iterasi dari relasi rekursi
Selanjutnya harus dibuktikan dengan induksi matematika untuk n = 1,
rumus benar
a1 = 2 + 3(1 – 1) = 2
- Asumsikan formula benar untuk n = k
ak = 2 + 3(k – 1)
- Akan dibuktikan formula benar untuk n = k + 1
Dari relasi rekursi ak+1 = ak + 3
= 2 + 3(k – 1) + 3
ak+1 = 2 + 3(k+1 – 1)
= 2 + 3(k+1) – 3
= 3(k+1) – 1
ak+1 = 2 + 3k (formula berlaku untuk semua n)
Jadi an = 2 + 3(n – 1) adalah solusi relasi rekursi dengan syarat batas a1 = 2
2. Tabel diferensi
Kegunaan Tabel Diferensi
Untuk menyatakan suatu bentuk xk, dengan k adalah bilangan bulat positif
yang merupakan suatu perluasan dari bentuk koefisien binomial
Cara penulisan yang demikian ini dapat digunakan untuk melakukan
perhitungan jumlah pangkat k dari n buah bilangan asli pertama
Contoh 3 :
Perhatikan suatu fungsi p(x) yang didedinisikan pada bilangan riil x sebagai
p(x) = 2x2 + 3x + 1
Akan dihitung p(x) untuk x = 0,1,2,....
Bila harga ini ditulis dalam baris ke 0 maka akan diperoleh: 0 : 1 6 15 28
45 66 91 …
Pada baris berikutnya, yaitu baris ke 1, tuliskan diferensi dari suku-suku yang
berurutan pada baris 0
Didefinisikan fungsi baru Δp sbb. ;
Δp(x) = p(x + 1) – p(x)
Maka diferensi yang diperoleh adalah harga Δp(x) untuk x = 0, 1, 2,... Dan
seterusnya
Beda ini disebut dengan beda derajat pertama dari p
Maka baris 0 dan 1 dapat ditulis sebagai berikut :
0 : 1 6 15 28 45 66 91 …
1 : 5 9 13 17 21 25 …
Pada baris ke 2 dituliskan diferensi dari suku yang berurutan pada baris 1
Beda ini adalah diferensi yang diperoleh dari fungsi Δp(x), atau ditulis dengan
Δp2(x)
untuk harga x = 0,1,...
Jadi Δp2(x) didefinisikan sebagai :
Δp2(x) = Δ (Δp)(x) = Δp(x + 1) - Δp(x)
= p (x + 2) – p(x + 1) – (p(x + 1) - p(x))
= p(x + 2) – 2p(x + 1) – p(x)
Dari hasil perhitungan ini dapat dieroleh baris kedua yang berisi:
0 : 1 6 15 28 45 66 91 ...
1 : 5 9 13 17 21 25 …
2 : 4 4 4 4 4 …
Proses dapat dilanjutkan sehingga dari suatu baris yang telah ada akan
diperoleh baris berikutnya yang merupakan diferensi dari bilangan baris
sebelumnya
Secara umum table diferensi untuk fungsi p didefinisikan sebagai :
Δpk(x) = Δpk-1(x + 1) – Δpk-1(x)
Nilai-nilai Δpk(x) untuk x = 0,1,2,... disebut diferensi derajat ke k dari p(x)
Didefinisikan pula Δ0p = p disebut diferensi derajat 0 dari p
Catatan, bila dalam proses perhitungan baris ke -k diperoleh seluruh harga
baris ke k tersebut adalah 0 baris-baris selanjutnya pasti akan 0, jadi tidak
perlu dilanjutkan
Pada contoh 3, p(x) polinom derajat 2, maka diferensi derajat 3 dari p(x) akan
mempunyai baris dengan bilangan 0 semua
Misal diberikan polynomial p(x) derajat n dan sisi kiri dari tabel diferensi p(x)
adalah bilangan C0, C1, C2, ..., Cn. Maka diperoleh :
p(x) = C0 p0(x) + C1 p1(x) + C2 p2(x) ........ + Cn pn(x)
Atau :
p(x) = C0 + C1 + C2 + ..... + Cn
Contoh 4 :
Tuliskan polinomial p(x) = x4 sebagai penjumlahan dari polinomial p0(x),
p1(x), p2(x), ... pn(x)
Diperoleh Tabel diferensi polinomial p(x)
0 1 16 81 256 625 ...
1 15 65 175 369 ...
14 50 110 194 …
36 60 84 ….
24 24 ….
0
x4 = p(x) = C0 p0(x) + C1 p1(x) + C2 p2(x) ........ + Cn pn(x)
x4 = 0 + 1 + 14 + 36 + 24
II.5 GRAPH (GRAF) Kuliah Ke-5
1. Kelahiran Graph
Teori graph ditemukan pertama kali pada tahun 1736 oleh seorang
matematikawan berkebangsaan Swiss bernama Leonhard Euler. Leonard Euler
berhasil mengungkapkan misteri jembatan Konigsberg di kota konisberg( sekaran
CC CC
Kalilingard), Rusia. Di kota tersebut mengalir sungai Pregel, yang di tengah
sungai tersebut terdapat dua buah pulau. Diantara kedua pulau dan kedua tepian
sungai terdapat jembatan (lihat gambar 5.1).
A
A & B : tepi sungai
C & D : pulau
B
(gambar 5.1 jembatan konisberg)
Konon katanya, penduduk kota tersebut yang pada saat libur sering
berjalan – jalan, menginginkan bagaimana caranya melewati jembatan masing –
masing hanya satu kali, dimulai dari sembarang tempat (A,B,C,D) dan kembali
ketempat semula. Karena itulah penduduk sekitar mengirimkan surat kepada
Euler. Akhirnya masalah tersebut dapat di pecahkan Euler, yaitu bahwa perjalanan
serupa itu tidak mungkin dilakukan diatas jembatan konisberg.Euler menyajikan
situasi jembatan konisberg tersebut dalam bentuk graf (lihat gambar 5.2).
CC DD
AA
(gambar 5.2 situasi jembatan konisberg dalam bentuk graf)
Suatu graf terdiri atas titik (simpul, vertex atau node) dan ruas ( rusuk, sisi, edge).
Setiap ruas menghubungkan 2 simpul. Ruas menandakan adanya relasi antara 2
simpul yang bersangkutan. Pada permasalahan diatas, daratan (tepian A dan B
serta pulau C dan D) dinyatakan sebagai simpul, dan jembatan sebagai ruas. Euler
mengemukakan teoremanya, bahwa perjalanan seperti itu aka nada apabila graf
tersebut terhubung, dan banyaknya ruas yang datang pada setiap simpul adalah
genap. Teorema tersebut dikenal sebagai perjalanan Euler.
2. Graph Secara Formal
Definisi Graf
Suatu graf G, ditulis G(V,E) adalah koleksi atau pasangan; (1) himpunan V
yangelemennya disebut simpul (titik, vertex point, node). (2) himpunan E
yang merupakan pasangan tak terurut dari simpul, disebut ruas.
Order dan kuran Graf
Banyaknya simpul (anggota V) disebut order graf G, sedangkan banyaknya
ruas (anggota E) disebut ukuran Graf G.
Simpul Berdampingan
Simpul u dan v disebut berdampingan, bila terdapat ruas(u,v). Graf dapat
dinyatakan secara geometri. Sebuah simpul dinyatakan sebuah titik, sedangkan
sebuah ruas dinyatakan sebagai sebuah garis yang menghubungkan 2 simpul.
Ruas Berganda atau Ruas Sejajar
Dua ruas r1 dab r2 yang mempunyai kedua simpul ujung yang sama, yakni r1
=(u,v) dan r2 = (u,v), disebut ruas berganda atau ruas sejajar.
Gelung atau Self Loop
Sebuah ruas r1 yang keedua simpul ujungnya sama, yakni r1 =(u,u) disebut
sebuah gelung atau self-loop.
Definisi Sub Graf
G’(V’,E’) disebut Subgraf dari G(V,E) bila E’ himpunan bagian dari E dan V’
himpunan bagian dari V. Jika E’ mengandung semua ruas di E yang kedua
BB
ujung di V’, dikatakan G’ adalah subgraf yang direntang oleh V’, atau disebut
juga Spanning Subgraph.
Definisi Graf Hingga
Suatu graf G disebut hingga apablia G mempunyai sejumlah hingga simpul
dan sejumlah hingga ruas.
3. Derajat Graf
Definisi Derajat Simpul
Derajat simpul suatu simpul v pada graf G, ditulis d(v) adalah banyaknya ruas
yang menghubungi atau insidensi v. Jumlah derajat semua simpul Graf G
disebut derajat graf G.
Simpul Bergantung & Simpul Terpencil
Simpul berderajat satu disebut simpul bergantung (simpul akhir). Simpul
berderajat nol disebut simpul terpencil (simpul terisolasi). Jumlah derajat
semua simpul graf (derajat graf) = 2 kali banyaknya ruas graf (ukuran graf).
Simpul Genap atau Ganjil
Suatu simpul disebut simpul genap atau ganjil tergantung apakah derajat
simpul tersebut genap atau ganjil. Bila pada simpul v terdapat gelung, maka
satu gelung dihitung dua kali pada derajat simpul v.
4. Keterhubungan
Perjalanan atau Walk
Perjalanan atau walk pada suatu graf G adalah barisan simpul dan ruas
berganti – ganti; v1, e1, v2,e2,…….en-1, vn ruas ei menghubungkan vi dan vi+1.
Perjalanan dapat ditulis sebagai barisan ruas e1,e2,…….en-1 atau barisan simpul
v1, v2, ………, vn-1,vn. v1 disebut simpul akhir dari perjalanan. Banyaknya ruas
dalam barisan disebut panjang perjalanan.
Perjalanan Tertutup & Perjalanan Terbuka
Disebut perjalanan terutup bila v1 = vn. Dalam hal lain disebut perjalanan
terbuka yang menghubungkan v1 dan vn.
Lintasan atau Trail
Adalah walk dengan semua ruas dalam barisan berbeda.
Jalur atau Patha
Adalah perjalanan yang semua simpul dalam barisan adalah berbeda. Jalur
pasti lintasan. Suatu jalur adalah suatu lintasan terbuka dengan derajat setiap
simpul dua, keculi simpul awal v1 dan simpul akhir vn berderajat satu. Jalur
dengan panjang k disebut jalur k atau k path.
Definisi Sirkuit atau Cycle
Adalah suatu lintasan tertutup dengan derajat setiap simpul dua. Sirkuit
dengan panjang k disebut sirkuit k ata k cycle.
Definisi ACYCLIC
Graf yang tidak mengandung sirkuit.
Teorema
Antara simpul u dan v, pada graf G terdapat jalur jika dan hanya jika terdapat
perjalanan antar simpul u dan v tersebut.
Definisi graf terhubung
Suatu graf G di katakana terhubung jika setiap dua simpul dari Graf G, selalu
terdapat jalur yang menghubungkan antara simpul tersebut.
Definisi komponen dari graf
Suatu terhubung K, dari suatu graf G, disebut Komponen dari G, bila subgraf
K tersebut tidak terkandung dalam subgraf terhubung lain yang lebih besar.
Definisi Jarak Antara Dua Simpul u dan v
Dimana yang dituliskan d(u,v) , Adalah panjang jalur terpendek antara kedua
simpul u dan v terebut.
Definisi diameter
Diameter suatu graf terhubung G adalah maksimum jarak antara simpul G.
Definisi Rank & Nullity
Jika Order dari G = n, ukuran dari G = e, dan banyaknya komponen = k, maka
dedefinisikan:> Rank(G) = n-k, Nullity(G) = e-(n-k)
5. Operasi Pada GRAF
Definisi
Pandang dua graf G1 = (E1,V1), dan G2 = (E2,V2)
Gabungan G1 G2 adalah graf dengan himpunan ruas E1UE2
Irisan G1 G2 adalah graf dengan himpunan ruas E1 E2
Selisih G1-G2 adalah graf dengan himpuna ruas E1-E2
Penjumlahan ring G1 G2 adalah graf dengan himpunan ruas ;
(E1 E2) – (E1 E2) atau (E1-E2)-(E2-E1)
Definisi Didekomposisi
Suatu graf G dikatakan didekomposisi menjadi subgraf K dan L bila G = KuL
& K
Definisi pemendekan (shorting)
Merupakan simpul yang dihubungi oleh dua ruas (simpul berderajat = 2) yang
saling terhubungan.
Definisi Matrik Ruas
Yaitu matriks ukuran (2xM) atau (Mx2) yang menunjukkan ruas dari graf.
Definisi matrik ajasensi
Matrik ajasensi graf G tanpa Ruas sejajar adalah A=aij , berukuran (N,N)
dengan ; aij [1 bila ruas (vi,Vj)] dan [0 dalam hal lain]
Merupakan matrik simetris
Untuk graf dengan ruas sejajar, matrik ajasensi didefiniskan sebagai berikut :
aij = p , bila ada p ruas ,menghubungkan (vi , V j)
Definisi matrik insidensi
Merupakan matrik M berukuran (N,M) yaitu mij = [ 1 bila ruas ej ,
menghubungi simpul vi ] dan [ 0 dalam hal lain
II.6 GRAPH (GRAF) Kuliah ke-6
1. Definisi Graf Berlabel
Suatu Graf G disebut graf berlabel(berbobot) jika ruas atau simpulnya
dikaitkan dengan suatu besaran tertentu.
Khususnya, G disebut graf terbobit jika setiap ruas e dari G dikaitkan dengan
suatu bilangan non negative disebut bobot atau panjang ruas e
Pada graf ini simpul
menyatakan kota dan label d(e) menyatakan jarak antar kedua kota.
Problema yang biasa ditanyakan adalah menghitung jarak terpendek antar dua
kota, yang berarti lintasan yang ditempuh memiliki nilai minimum dan harus
memiliki nilai.
Misalnya gambar diatas antar kota P dan kota Q , maka hasil yang diperoleh
adalah (P,A1,A2,A5,A3,A6,Q) = 3+3+3+1+2+1 = 14.
2. Graf Eurelian dan Transversebel
Suatu multigraf dikatakan traversable jika dapat digambarkan tanpa satu
patahanpun pada kurva dan dapat mengulang sisi manapun, yang berarti jika
ada suatu lintasan yang mengandung semua simpul dan menggunakan setiap
ruas tepat hanya satu kali. Lintasan merupakan suatu jejak traversal karena
tidak ada ruas yang dugunakan dua kali.
Misalkan suatu multigraf adalah traversable dan bahwa suatu jejak traversable
tidak dimulai atau diakhiri pada suatu simpul P. Asumsikan bahwa P suatu
simpul genap karena setiap kali jejak traversable memasuki P melalui suatu
ruas, pasti selalu ada ruas yg belum digunakan sebelumnyadan dapat
digunakan untuk meninggalkan simpul P. Jadi ruas-ruas dalam trail yang
insidensi dengan P harus muncul sebagai pasang-pasangan, sehingga P suatu
simpul genap
Dengan demikian Jika simpul Q adalah janjil, traversable trailnya harus
berawal dan berakhir pada simpul Q. Oleh karena itu, suatu multigraf dengan
lebih dari dua simpul ganjil tidak bisa menjadi traversable.
Suatu graf G disebut sebagai Graf Eulerian apabila ada suatu jejak
traversable tertutup yang disebut dengan jejak eulerian.
Berikut ini suatu algoritma salah satu lintasan (perjalanan) euler pada suatu graf.
Dengan catatan telah dipastikan bahwa graf tersebut memliki perjalan serupa itu,
yakni bahwa derajat setiap simpul graf adalah genap.
Algoritma perjalanan euler terdiri dari beberapa langkah yaitu :
Langkah 0 : Dimulai dengan suatu simpul awal perjalanan.
Langkah 1 : Kita tentukan suatu perjalanan berbentuk sirkuit dari simpul awal
tersebut dengan meneliti pasangan simpul berikutnya.
Langkah 2 : Mencari sirkuit selanjutnya , dengan sirkuit sebelumnya.Simpul
persekutuan tersebut selalu di letakkan pada simpul awal,dengan
merotasikan penulisan sirkuit , lalu menggabunggkan sirkuit-
sirkuit tersebut. Langkah ini diulangin sampai semua ruas selesai
membentuk perjalanan.
Contoh 1 :
1 2
3
4 5
Gambar 6.2
Perhatikan Graf { (1,2),(1,3),(2,3),(3,4),(3,5),(4,5) }
Jadi langkah graf terdiri dari beberapa yaitu :
Langkah 0 : ambil simpul awal, misalnya simpul 1
Langkah 1 : bentuk sirkuit { (1,2),(2,3),(3,1) }
Langkah 2 :
- Untuk sirkuit berikutnya hanya simpul 3 yang merupakan simpul persekutuan
dengan sirkuit sebelumnya
- rotasikan penulisan sirkuit diatas menjadi { (1,2),(2,3),(3,1) }
- Sirkuit berikutnya yang bersimpul awal di simpul 3 adalah : { (3,4),(4,5),(5,3) }
- Gabung kedua sirkuit diatas menjadi : { (3,1,),(1,2),(2,3),(3,4),(4,5),(5,3) }
Karena semua ruas garis telah di jalani, maka proses kita hentikan
Gabungkan sirkuit diatas adalah salah satu perjalanan Euler yang di cari.
3. Graf Halmilton
Nama sirkuit Hamiltonian diambil dari nama ahli matematika Irlandia yang hidup di
abad Sembilan belas William Hamilton (1803-1865)
Sirkuit Hamiltonian adalah suatu lintasan tertutup yang mengunjugi setiap simpul
dalam G tepat hanya 1 kali saja
Lintasan tertutup demikian pastilah merupakan suatu siklus.
Jika G memiliki sirkuit Hamilton , maka G disebut graf Hamiltonian
Teorema Graf Halmilton
Misal G suatu graf dengan n simpul
Jika jumlah derajat setiap pasang simpul-simpul dalam G adalah n-1 atau lebih besar,
maka terdapat lintasan Hamiltonian dalam G.
Contoh 2 :
Gambar 6.3 , Graf Hamilton dan bukan Euleri
Gambar 6.3 Graf Hamilton dan bukan Eulerian
Contoh: 3
Gambar 6.4 : Graf Eulerian dan bukan Hamiltonian
Gambar 6.4 Graf Hamilton dan bukan Eulerian
II.7 GRAPH (GRAF) Kuliah Ke-7
1. Graf Planar
Definisi Graf Planar
Suatu Graf yang digambarkan tanpa adanya ruas yang berpotongan disebut Graf
Planar.
Contoh 1 :
Graf lengkap K4 yang digambarkan dengan ruas yang berpotongan dapat
digambarkan tanpa ruas yang berpotongan (lihat Gbr.7.1 b)
Jadi K4 merupakan Graf Planar
Gbr. 7. 1 Contoh Graf lengkap K4 dan Graf Planar
Definisi Map atau Peta
Graf Planar hingga tanpa adanya ruas berpotongan disebut Representasi
(Penyajian) Planar, atau Map atau Peta.
Contoh :
Gambar 7. 1a bukan Map, sedangkan gambar 7.1b adalah Map
Definisi Region atau daerah
Sebuah Map disebut Terhubung, jika Graf yang bersangkutan Terhubung. Map
akan membagi-bagi bidang rata atas beberapa Region atau Daerah.Definisi
Derajat Region Derajat dari suatu Region adalah panjang Rerjalanan batas dari
Region tersebut.
Contoh 2 :
Perhatikan Graf Planar pada Gambar 7. 2
Gambar 7.2 Contoh Graf Planar terdiri atas 6 simpul dan 9 ruas
Gambar 7.2 suatu Graf Planar yang terdiri atas 6 simpul dan 9 ruas
Merupakan Map dengan 5 buah Refgon : yaitu r1, r2, r3, r4, dan r5
4 Region adalah terbatas, sedangkan region kelima r5 tidak terbatas
Pada unmumnya batas dari Region adalah suatu Sirkuit
Pengecualian untuk Region r3 dibatasi oleh walk (C,D,F,E,F,C)
Teorema Graf Planar
Jumlah derajat dari semua Region suatu Map sama dengan 2 kali jumlah ruas Graf
yang bersangkutan.
Derajat Region d(r1)=3 ; d(r2)= 3, d(r3)= 5, d(r4)= 4, d(r5)= 3
Jumlah Derajat Region di atas = 3+3+5+4+3 = 18
Formula Euler Untuk Graf Planar
Hubungan antara jumlah simpul V, jumlah ruas E serta jumlah region R suatu
Map terhubung dinyatakan oleh Formula Euler berikut :
V – E + R = 2
Pada Gambar 7.2 V = 6 , E = 9 , dan R = 5
2. Graf Non Planar
Gambar 7.3 contoh graf non planar
Gambar 7.3(a) disebut Graf Utilitas, menyatakan 3 rumah A1, A2, A3 yang
masing-masing dihubungkan dengan sumber gas, sumber air, serta listrik
Gambar 7.3(a) disebut Graf Utilitas, menyatakan 3 rumah A1, A2, A3 yang
masing-masing dihubungkan dengan sumber gas, sumber air, serta listrik B1,
B2, B3
Gambar 7.3(b) disebut Graf Bintang, yang merupakan Graf Lengkap dengan 5
simpul, K5
3. Pewarnaan Graf
Definisi Pewarnaan Simpul
Pewarnaan simpul (vertex coloring) atau graf pewarnaan (coloring), suatu Graf
adalah pemberian warna terhadap simpul sedemikian sehingga 2 simpul yang
berdampingan mempunyai warna yang berlainan.
Definisi Warna n
G berwarna n, bila terdapat perwarnaan dengan menggunakan n warna.
Definifi Bilangan Kromatis
Jumlah minimum warna yang dibutuhkan disebut bilangan kromatis dari G.
Ditulis : K(G)
Algoritma Welch-Powell
Digunakan untuk mewarnai sesuatu graf dengan banyak warna minimal.
Algoritmanya :
Mula-mula urutkan semua simpul berdasarkan derajatnya, dari derajat besar ke
derajat kecil
Ambil warna pertama, warna simpul pertama (dalam urutan)
Kemudian simpul berikutnya yang tidak berdampingan, terus menerus,
berdasarkan urutan
Kemudian lanjutkan dengan warna kedua dan seterusnya sampai semua
simpul telah diberi warna
Contoh 3 :
Mewarnai Graf pada gambar 7.4 mengukan algoritma Welch-Powel :
Gbr.7.4 Contoh Graf Planar terdiri dari 6 simpul dan 9 ruas
Kemudian urutkan simpul berdasarkan derajatnya: E, G, C, A, B, D, F, H
Ambil warna pertama, miasal warna hijau. Beri warna hijau simpul E
Kemudian warnai simpul A, karna A tidak berdampingan dengan simpul E
Urutkan simpul yang belum di beri warna : G, C, B, D, F, H
Kemudian ambil warna kedua, misal warna merah, beri warna merah simpul
G,B dan F
Urutkan simpul yang belum diberi nama C, D, H
Warna ketiga misalnya putih, beri warna putih simpul C, D, dan H
Pewarnaan telah selesai, Graf merupakan Graf berwarna 3. Jadi K(G)=3
4. Pewarnaan Map
Definisi Pewarnaan Map :
Yang dimaksud pewarnaan Map adalah pemberian warna Region sehingga region
yang berdampingan mempunyai warna yang berbeda.
Catatan :
Perhatikan suatu Map M. Dua Region dari M dikatakan berdampingan jika
mereka mempunyai suatu ruas persekutuan.
Suatu Map M berwarna n jika terdapat suatu pewarnaan dari M dengan
menggunakan n warna.
Contoh : 4
Graf pada gambar 7.5 berwarna 3, karena Region dapat diberi warna sebagai berikut
ini :
r1 merah, r2 putih, r3 merah, r4 putih, r5 merah, r6 biru
Definisi Dual Map :
Andaikan digambarkan sebuah simpul baru pada masing-masing Region suatu map
M. Kemudian dibuat sebuah ruas menghubungkan simpul 2 Region yang
berdampingan memotong setiap ruas batas atau persekutuan kedua region. Tanpa
adanya ruas baru yang berpotongan, maka akan terbentuk suatu Map M* yang disebut
dual dari Map M.
Contoh 5 :
Gbr.7.6 Map M dan M* yang disebut dual dari Map M
KET :
Map M
Map M*
Dapat dilihat bahwa masing-masding Region dari M* mengandung tepat satu
simpul dari M
Setiap ruas dari M memotong tepat satu ruas dari M*
Dapat pula dikatakan M adalah dual dari M*
Relasi dual adalah relasi simetris
Pewarnaan dari M sama artinya dengan pewarnaan simpul dari M*
Suatu Map M berwarna n jika dan hanya jika dualnya M* berwarna (simpul) n.
Teorema Map Bewarna 5 :
Suatu Map M adalah berwarna 5. Tetapi ada map yang dijumpai membutuhkan 5
warna pada setiap pewarnaan.
Teorema Map Bewarna 4 :
Setiap Map adalah berwarna (Region) 4 dan setiap Graf Planar adalah berwarna
(simpul) 4.
II.8 GRAPH (GRAF) Kuliah Ke-8
1. Pohon (Tree)
Definisi Pohon / Tree
Suatu Graf T disebut Pohon (Tree) jika T terhubung dan T tidak mengandung Sirkuit. Graf itu sendiri adalah Pohon jika dan hanya jika terdapat satu dan hany satu jalur di antara setiap pasang simpul dari G. Pohon yang mengandung suatu simpul tunggal tanpa ruas disebut Pohon Degenerasi.
Hutan / Forest
Suatu Hutan G adalah suatu graf tanpa Sirkuit.
Catatan :
Komponen-komponen terhubung dari suatu hutan G adalah pohon-pohon
Teorema Pohon / Tree
Misalkan G suatu graf dengan n > 1 simpul, maka G adalah suatu pohon G bebas Sirkuit dan memiliki n-1 ruas G terhubung dan memiliki n-1 ruas.
Contoh : 1
Gbr.8.1 Contoh Pohon
Gambar 8.1(a) pohon memiliki 9 simpul dan 8 ruas
Gambar 8.1(b) pohon memiliki 13 simpul dan 12 ruas
2. Pohon Rentangan (Spanning Tree)
Definisi Pohon Rentangan (Spanning Tree)
Suatu subgraf dari suatu graf G disebut sebagai pohon rentangan (spanning tree) dari G jika S adalah suatu pohon dan S mengandung semua simpul dari G.
Jika G mempunyai n simpul maka Pohon Rentangan S juga mempunyai n simpul, karena S adalah pohon, maka S mempunyai n-1 ruas.
Ruas dari Pohon Rentangan disebut sebagai Cabang (Branch). Banyak Cabang adalah n-1
Ruas dari G yang tidak memrupakan ruas dari Pohon Rentangan disebut Chord dari Pohon. Jika banyaknya ruas dari G adalah e, maka G-S mempunyai e-(n-1) ruas yang adalah banyak Chord dari pohon.
Contoh 2 :
Gambar 8.2 Suatu Graf terhubung G dan pohon – pohon rentangan S1, S2, S3.
3. Pohon Rentang Minilmal
Definisi Pohon Rentang Minimal
Apabila G suatu Graf terbobot (suatu Network), maka Pohon Rentangan Minimal dari G adalah Pohon Rentangan dengan jumlah bobot terkecil.
Cara Mendapatkan Pohon Rentang Minimal
1) Algoritma Solin
Urutkan ruas G dalam urutan bobot dari besar ke kecil
Lakukan berturut-turut penghapusan, masing-masing ruas yang tidak menyebabkan Graf menjadi tidak terhubung sampai tersisa n-1 ruas yang membentuk Pohon Rentangan Minimal
2) Algoritma Kruskal
Mula-mula buat Graf G hanya terdiri dari simpul saja
Urutkan ruas dari bobot kecil ke besar
Kemudian, berdasarkan urutan tersebut, tambahkan ruas dengan mencegah terjadi Sirkuit pada setiap penambahan ruas
Setelah n-1 penambahan, diperoleh Pohon Rentangan Minimal yang ditanyakan
Contoh 3 :
Tentukan Pohon Rentangan Minimal dari Graf terbobot G pada gambar 8.3 berikut ini :
a) Gunakan Algoritma Solin
b) Gunakan Algoritma Kruskal
Gbr.8.3 Graf terbobot G
Jawab :
a) Menggunakan Algoritma Solin
Ruas : BC AF AC BE CE BF AE DF BDBobot : 8 7 7 7 6 5 4 4 3Hapus : ya ya ya tidak tidak ya
Jadi Pohon Rentangan Minimal G yang diperoleh mengandung ruas : BE, CE, AE, DF, BD dengan bobot 24.
b) Menggunakan Algoritma Kruskal
Ruas : BD AE DF BF CE AC AF BF BCBobot : 3 4 4 5 6 7 7 7 8Menambah : ya ya ya tidak ya tidak ya
Jadi Pohon Rentangan Minimal G yang diperoleh mengandung ruas : BD, AE, DF, CE, AF dengan bobot 24.
II.9 GRAPH (GRAF) Kuliah Ke-9
1. Pohon Berakar (Rooted Tree)
Pohon Berakar
Suatu pohon berakar R adalah suatu pohon dengan suatu simpul tertentu
dirancang atau ditunjuk sebagai apa yang di sebut Akar atau Root dari R.
Suatu pohon dapat dijadikan pohon berakar cukup dengan mengangkat salah
satu simpul sebagai akar.
Definisi Level, Daun, Cabang
Panjang jalur antara akar R dengan simpul V disebut Level atau kedalaman
simpul V
Simpul bukan akar, yang berderaat 1 disebut daun
Jalur antara suatu simpul dengan suatu daun disebut cabang (branch)
Definisi Mendahului & mendahului langsung
Simpul U dikatakan mendahului simpul V, jika jalur dari akar R ke V melalui
U
U mendahului langsung V, bila U mendahului V, dan mereka berdampingan
Contoh 1
Pada gambar 9.1 a mendahului d, e, dan h, a mendahului langsung d dan e. Suatu
pohon berakar dapat digunakan untuk menelusuri semua kemungkinan dari
kejadian, dengan masing-masing dapat muncul dalam sejumlah hingga cara.
R
a b c
d e f g
h i j
gambar 9.1
2. Pohon Biner (Binary Tree)
Definisi Pohon Biner
Sebuah pohon biner T didefinisikan terdiri atas sebuah himpunan hingga simpul
sedemikian sehingga secara rekrusif :
a) T adalah hampa (disebut pohon nol)
b) T mengandung simpul R yang dipilih (dibedakan dari yang lain), disebut Akar
dari T, dan simpul sisanya membentuk 2 pohon binar (sub pohon kiri dan sub
pohon kanan dari R), T1 dan T2 yang saling lepas. Jika T1 (tidak hampa), maka
simpul akarnya disebut suksesor kiri dari R. Hal yang sama untuk akar dari
T2 (tidak hampa) disebut suksesor kanan dari R. Kembalikan suksesor adalah
predesesor.
Contoh 3:
gambar 9.1
Keterangan :
Pohon biner tersebut mempunyai 11 simpul yang diberi huruf A sampai L
tidak termasuk I
Simpul akar adalah simpul yang digambar pada bagian paling atas
Suksesor kiri dari A adalah B dan suksesr kanan dari A adalah C
Subpohon kiri dari A mengandung smpul D,E dan F
I
F
B C
A
G
J
E
H
K
D
Subpohon kanan dari A mengandung simpul C,G,H,J,K dan L
Jika N adalah sembarang simpul dari pohon biner T, maka N mempunyai 0,1
atau 2 buah suksesor
Suksesor sering disebut anak (child)
Simpul N tersebut dapat disebut ayah atau orang tua (perent) dari suksesornya
Pada contoh, simpul A,B,C, dan H mempunyai 2 anak
Sedang simpul E dan J mempunyai 1 anak
Simpul D, F, G, L dan K tidak mempunyai satu anakpun
Simpul yang tidak memepunyai anak disebut daun atau terminal
Jika simpul N adalah daun maka kedua subpohon kiri dan kanannya adalah
hampa
Dua pohon biner T dan U dikatakan serupa (similar) jika mereka memiliki
struktur atau bentuk yang sama
Bila pohon biner similar juga mempunyai elemen(isi) yang sama pada simpul
yang bersesuaian, maka pohon biner di sebut salinan (copy)
Contoh 4
A E A E
B F B F
C D G H C D G H
(1) (2) (3) (4)
Gambar 9.4
Pohon-pohon (1), (3), (4) serupa
Pohon-pohon (1), (3) salinan
Pohon (2) tidak serupa juga bukan salinan pohon (4)
3. Terminologi Pada Pohon Biner
Definisi Kedalaman / Ketinggian (Depth / Height)
Dari pohon T adalah banyak maksimum simpul dari cabang di T
Atau panjang maksimum jalur di T tambah 1
Gambar 9.5
Keterangan :
Pada gambar 9.5, simpul K adalah keturunan kanan dari D, tetapi bukan
keturunan dari F, E ataupun M
Simpul G adalah ayah dari K, dan L, K & L adalah bersaudara, masing-
masing anak kanan dan kiri dari G
Garis AD, ataupun GL adalah contoh luas
Barisan ruas (AD, DG, GL) adalah jalur dari simpul A ke simpul L
F
D D
A
G M
K L
Jalur ini sekaligus merupakan cabang, karena berakhir di simpul terminal
(daun) L
Jalur (AD, DG) bukan sebuah cabang
Simpul A mempunyai tingkat nol
Simpul D dan E berada pada generasi dengan tingkat = q
Generasi berikutnya F,G,M dengan tingkat = 2
Generasi terahir, simpul K dengan tingkat = 3
Pohon pada gambar 9.5 di atas mempunyai ketinggian = 4 (tingkat
tertinggi dari simpul ditambah 1 )
Cabang (AD, DG, GK) dan (AD, DG, GL) mengandung simpul dengan
jumlah maksimum yaitu = 4
Cabang(AE, EM) dan (AD, DF) hanya mengandung 3 simpul
I.10 Graph (Graf) Kuliah Ke-10
1. Graf Berarah
Definisi Graf berarah
Suatu graf berarah (directed graph atau diagraf) D terdiri atas 2 himpunan
Himpunan V, anggotanya disebut simpul.
Himpunan A merupakan himpunan pasangan terurut, yang disebut ruas
berarah atau arkus.
Ditulis D(V,A)
Graf berarah dapat digambarkan pada suatu bidang datar.
Simpul anggota V, digambarkan sebagai titik (lingkaran kecil)
Arkus a=(u,v), digambarkan sebagai garis dilengkapi dengan tanda panah
mengarah dari simpul u ke simpul v.
Simpul u disebut titik terminal dari arkus a tersebut.
Contoh 1:
Sebuah graf berarah D(V,A) lihat gambar 10.1
1 4
3
Gambar 10.1
Keterangan :
2
V mengandung 4 simpul, yakni 1, 2, 3, dan 4
A mengandung 7 arkus, yakni (1,4), (2,1). (2,1) (4,2), (2,3), (4,3) dan (2,2)
Arkus (2,2) disebut gelung (self-loop)
Arkus (2,1) muncul lebih dari satu kali, disebut arkus sejajar (arkus berganda)
Definisi Jaringan (Network)
Apabila arkus dan/atau simpul suatu Graf berarah menyatakan suatu bobot,
maka digraph tersebut dinamakan suatu jaringan atau Network
Graf semacam ini untuk menggambarkan situasi yang dinamis
Definisi Graf Berarah Hingga
Misalkan D(V,A) suatu Graf berarah.
D disebut hingga(finite|) bila baik V maupun A merupakan himpunan
hingga
Definisi Graf Bagian/Subgraf
Bila V’ himpunan bagian dari V serta A’ himpunan bagian dari A, dengan titik
ujung anggota A’ terletak di dalam V’, maka dikatakan bahwa D’(V’,A’)
adalah Graf Bagian/Subgraf
2. Beberapa Definisi Graf Berarah
Definisi Arkus
Misalkan D suatu Graf berarah
Arkus a = (u,v) adalah mulai pada titik awal u, dan berahir pada titik
terminal V
Definisi Derajat Ke Luar
Derajat ke luar (out degree) suatu simpul adalah banyaknya arkus yang mulai /
keluar dari simpul tersebut
Definisi Derajat Ke Dalam
Derajat ke dalam (in degree) suatu simpul adalah banyaknya arkus yang
berahir / masuk ke simpul tersebut
Definisi Sumber
Sumber berderajat ke dalam = 0 disebut sumber (source), dan bila berderajat
ke luar = 0 disebut muara (Sink)
Definisi Semi Perjalanan
Pada Graf berarah, D adalah suatu perjalanan tanpa memperhatikan arah dari
arkus
Pengertian yang serupa diberikan untuk semi jalur dan semi lintasan
3. Graf Berarah dan Matriks
Pandang D(V,A) suatu graf berarah tanpa ruas sejajar, maka A
adalah himpunan bagian dari V x V (produk Cartesis himpunan), jadi
merupakan Relasi pada V. Sebaliknya bila R adalah Relasi pada
suatu himpunan V, maka D(V,R) merupakan graf berarah tanpa ruas
sejajar. Jadi konsep Relasi dan konsep graf berarah tanpa ruas
sejajar adalah satu dan sama.
Misalkan D(V,A) suatu graf berarah dengan simpul v1, v2, … , vm.
Matriks M berukuran (mxm) merupakan matriks (matriks adjacency)
dari D, dengan mendefinisikan sebagai berikut :
M = (Mij), dengan mij banyaknya ruas yang mulai di vi dan
berakhir di vj
Bila D tidak mengandung ruas berganda, maka elemen M adalah 0
dan 1. Kalau Graf berarah mengandung ruas berganda, elemen M
merupakan bilangan bulat non negatif.
Jadi suatu matriks berukuran (mxm) yang elemennya bilangan bulat
non negatif menyatakan secara tunggal suatu graf berarah dengan
m simpul.
Contoh :
Teorema :
M adalah Matriks dari sutau graf berarah D, maka elemen baris ke i
kolom ke j dari Matriks Mn menyatakan banyaknya walk dengan
panjang n dari simpul vi ke simpul vj.
Problem Jalur Terpendek
Pandang D suatu Graf berarah yang hingga dengan tiap-tiap
ruas mempunyai bobot. Jadi D merupakan suatu Network. Kita
hendak menentukan Jalur Terpendek antara simpul u dan v.
Misalkan D tidak mengandung sirkuit.
Sebagai contoh, gambar berikut merupakan suatu Network. Kita
hendak menghitung Jalur terpendek dari simpul u ke v.
Simpul u disebut Sumber (Source).
Simpul v disebut Muara (Sink).
Untuk menentukan Jalur Terpendek tersebut, cara berikut dapat
digunakan :
• Buat tabel jarak :
u x y z a b c v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb =
2
yc =
1
zy =
2
zc =
5
ab =
2
av =
3
bv
= 3
cv =
3
Kita mulai dengan simpul u sebagai simpul awal. Beri harga = 0. Ambil simpul
dengan jarak terdekat dari u (dalam hal ini z = 2), kemudian lingkari uz. Semua ruas
lain yang berakhir di z kita hapus (dalam hal ini tidak ada ruas lain yang berakhir di z.
Beri nilai = 2 di belakang z. Simpul yang telah diberi harga ditandai dengan *.
u*(0) x y z*(2) a b c v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb = 2
yc = 1
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3 cv = 3
Dari simpul u dan z (yang telah ditandai *), dicari simpul lain yang jarknya terdekat
dihitung dari u. Jadi harus diperhitungkan nilai yang tertulis di simpul (0 untuk u dan
2 untuk z). Disini ux = 4 dan uzy = 2 + 2 = 4 merupakan nilai minimal. Boleh dipilih
salah satu, misalnya uzy. Beri nilai = 4 pada y. Lingkari zy dan hapus ruas yang lain
yang menuju y, yaitu uy dan xy.
u*(0) x y z*(2) a b c v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb = 2
yc = 1
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv = 3 cv = 3
Demikian proses dilanjutkan berturut-turut :
u*(0) x*(4) y*(4) z*(2) a b c v
ux = 4
uy = 6
uz = 2
xy = 3
xa =
3(7)
yb =
2(6)
yc =
1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv =
3
cv =
3
u*(0) x*(4) y*(4) z*(2) a b c*(5) v
ux = 4
uy = 6
uz = 2
xy = 3
xa =
3(7)
yb =
2(6)
yc = 1(5)
zy =
2(4)
zc =
5(7)
ab = 2
av = 3
bv = 3 cv =
3(8)
u*(0) x*(4) y*(4) z*(2) a b*(6) c*(5) v
ux = 4
uy = 6
xy = 3
xa =
yb =
2(6)
zy =
2(4)
ab = 2
av = 3
bv =
3(9)
cv =
3(8)
u*(0) x y*(4) z*(2) a b c v
ux = 4
uy = 6
uz = 2
xy = 3
xa = 3
yb = 2(6)
yc = 1(5)
zy = 2(4)
zc = 5(7)
ab = 2
av = 3
bv =
3
cv =
3
uz = 2 3(7) yc = 1(5) zc =
5(7)
u*(0) x*(4) y*(4) z*(2) a*(7) b*(6) c*(5) v
ux = 4
uy = 6
uz = 2
xy = 3
xa =
3(7)
yb =
2(6)
yc = 1(5)
zy =
2(4)
zc =
5(7)
ab = 2
av =
3(10)
bv =
3(9)
cv =
3(8)
u*(0) x*(4) y*(4) z*(2) a*(7) b*(6) c*(5) v*(8)
ux = 4
uy = 6
uz = 2
xy = 3
xa =
3(7)
yb =
2(6)
yc = 1(5)
zy =
2(4)
zc =
5(7)
ab = 2
av =
3(10)
bv =
3(9)
cv =
3(8)
Maka, Diperoleh jalur minimal dari simpul u ke simpul v yang
panjangnya = 8 dengan urutan v ← c ← y ← z ← u
Algoritma diatas dapat pula dikenakan untuk Graf tidak
berarah.
BAB III
SIMPULAN
Berdasarkan materi yang telah diberikan oleh Ibu Marama Namora pada mata kuliah
Matematika Informatika 4 sudah sesuai dengan SAP. Dimana Matematika Informatika
merupakan disiplin ilmu yang mempelajari transformasi fakta berlambang berupa data
maupun informasi pada mesin berbasis komputasi yang mencakup kajian matematika. Ruang
lingkup pembahasan Matematika Informatika 4 adalah : Relasi Rekurensi, Relasi Rekursi dan
Graph (Graf). Berikut adalah simpulan dari pembahasan tersebut.
Relasi rekurensi untuk deretan {an} adalah persamaan yang menyatakan an kedalam
satu atau lebih suku sebelumnya, yaitu a0, a1, …, an-1, untuk seluruh bilangan bulat n, dengan
n ≥ n0, dimana n0 adalah bilangan bulat tak negatif. Suatu deretan disebut sebagai jawaban
dari relasi rekurensi jika suku-sukunya memenuhi relasi rekurensi. Dengan kata lain, relasi
rekurensi mirip dengan deretan yang didefinisikan secara rekursif, tetapi tanpa menyebutkan
nilai (kondisi) awalnya. Maka, relasi rekurensi bisa (dan biasanya) memiliki jawaban ganda
(multiple solution). Jika kondisi awal dan relasi rekurensi disebutkan dua-duanya, maka
deretan dapat ditentukan secara unik.
Relasi rekursi untuk suatu barisan real ( ) n x dikatakan barisan kontraktif jika terdapat
konstanta C, dengan 0 < C < 1 sehingga berlaku, n n n n x − x ≤ C x − x +2 +1 +1 , ∀n ∈ N .
Untuk menentukan nilai limit suatu barisan kontraktif dapat menggunakan relasi rekursif.
Relasi rekursif linier dengan koefisien konstanta order k dapat ditulis dalam bentuk ... ( ) 0 1 1 2
2 c x c x c x c x f n n n n k n k + + + + = − − − , dimana k c ,c ,c ,...,c 0 1 2 konstanta dan ≠ 0 k c , n
x fungsi diskret dan f (n) suatu fungsi terhadap n, ∀n ≥ 0 . Jika f (n) = 0 maka disebut relasi
rekursif homogen order k dan jika f (n) ≠ 0 disebut relasi rekursif tak homogen order k Nilai
limit barisan kontraktif dapat ditetukan dengan metode relasi rekursif yang mana solusi
umum dari relasi rekursif merupakan rumus umum suku ke-n barisan kontraktif.
Dalam himpunan edge untuk di graf, urutan pasangan verteks menentukan arah dari
edge tersebut. Dalam sebuah graph memungkinkan terdapat lebih dari satu resolving set.
Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas
terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan
dengan teori graf :
Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada
node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path
Cycle siklus ? path yang kembali melalui titik asal 2 kembali ke
2.
Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a
dalam digraf diatas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge
dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex
Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected
graph) jika setiap sisinya tidak berarah. Dengan kata lain (vi,vj)=(vj,vi)
Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika
setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex)
sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada
graf adalah sisi yang verteks awal dan verteks akhirnya sama.
Daftar pustaka
http://dcenter.it-kosongsatu.com/?file_id=5
http://radar.ee.itb.ac.id/~suksmono/Lectures/el2009/ppt/6.%20Pencacahan%20Lanjut.pdf
http://data.artofproblemsolving.com/aops20/latex/texer/
936efc63466efd05bcbeb972192b6e09fac70c6c.pdf
tambah”in la ya bang jek, dari buku digital yg dr kampus k nada matif nya tuh