matematika diskrit siap print
Post on 07-Apr-2018
368 Views
Preview:
TRANSCRIPT
-
8/4/2019 Matematika Diskrit Siap Print
1/253
-
8/4/2019 Matematika Diskrit Siap Print
2/253
2
Tujuan Pembelajaran
Mahasiswa mampu memahami konsep
logika, metode pembuktian, himpunan,
fungsi, induksi matematis & rekursi, relasidan dapat mengaplikasikannya pada
permasalahan nyata.
-
8/4/2019 Matematika Diskrit Siap Print
3/253
3
Kompetensi
Mahasiswa mampu menjelaskan dengan benar konsep
logika dan dapat mengambil kesimpulan yang benar,
Mahasiswa mampu mengaplikasikan metode-metode
pembuktian yang efesien,
Mahasiswa mampu menjelaskan & mengaplikasikan
konsep himpunan dan fungsi,
Mahasiswa menjelaskan induksi matematis dan rekursi
& mengaplikasikan pada permasalahan nyata
Mahasiswa menjelaskan konsep relasi &mengaplikasikan pada permasalahan nyata.
-
8/4/2019 Matematika Diskrit Siap Print
4/253
Cara Belajar
Perhatikan ketika dosen mengajar
Kerjakan latihan seluruhnya
4
-
8/4/2019 Matematika Diskrit Siap Print
5/253
Bab dari Buku
Bab 1 Logic and Proof
Bab 2 Sets, function, sequence and sums
Bab 4 Induction and recursion
Bab 7 Advance Counting Technique
Bab 8
Relation
5
-
8/4/2019 Matematika Diskrit Siap Print
6/253
PERTEMUAN I
LOGIKA
6
-
8/4/2019 Matematika Diskrit Siap Print
7/253
Logika
Mempelajari penalaran/pemikiran (reasoning)
secara benar
Logicmempelajari bgm cara mengambilkesimpulan yang benar menurut aturan yang ada ,ex:or,and,not,dll
Fokus pada relasi antar pernyataan (statement) /
kalimat (sentence).
7
-
8/4/2019 Matematika Diskrit Siap Print
8/253
Logika Matematika Logika merupakan studi penalaran; yang secara khusus
membahas apakah suatu penalaran benar atau tidak. Dasar dari teori logika adalah proposisi.
Proposisi atau kalimat terbuka adalah kalimat yang bisabernilai benar atau salah, tetapi tidak sekaligus
keduanya. Proposisi biasanya dinyatakan sebagai kalimat berita
(bukan kalimat tanya, kalimat perintah dansebagainya).
Dalam logika tidak disyaratkan adanya hubunganantara kedua kalimat penyusunnya hanya tergantungpada nilai kebenaran kalimat penyusunnya
8
-
8/4/2019 Matematika Diskrit Siap Print
9/253
Contoh LogikaNyatakan apakah setiap kalimat yang diberikan
adalah proposisi atau bukan. Jika proposisi,
bagaimana nilai kebenarannya?
1. Matahari terbit dari Utara
2. 1+2 = 3
3. Kerjakan latihan soal di rumah!
4. Apakah anda merasa senang kuliah di UPN ?
5. Bumi adalah satu-satunya planet di jagat raya yang mempunyaikehidupan
6. N adalah bilangan ganjil.7. Gajah lebih besar daripada kucing.
8. 1089 < 101
9. y > 15
10. x < y jika dan hanya jika y > x 9
-
8/4/2019 Matematika Diskrit Siap Print
10/253
Proposisi Huruf kecil, misal p, q, dan r, digunakan untuk
menyatakan kalimat proposisi.
Contoh: Notasi p: 1 + 1 = 3
untuk mendefinisikan p sebagai proposisi 1+1 =
3. Nilai kebenaran suatu proposisi ditentukan oleh
kebenaran kalimat yang menyatakannya. Misal,proposisi 1+1 = 3 bernilai salah, sedangkan
proposisi ,Paris ibu kota Perancis bernilai benar. Selanjutnya kita akan menulis B untuk
menyatakan benar dan S untuk menyatakansalah.
10
-
8/4/2019 Matematika Diskrit Siap Print
11/253
Konjungsi, Disjungsi, & Negasi
Misalkan p dan q adalah proposisi. Konjungsi p dan q, dinyatakan dengan
, adalah proposisi p dan q.
Disjungsi p dan q, dinyatakan dengan
, adalah proposisi p atau q
Negasi dari p, dinyatakan dengan atau ~p,
adalah proposisi bukan p
11
qp
qp
p
-
8/4/2019 Matematika Diskrit Siap Print
12/253
Tabel Kebenaran
disjungsi (inclusive or)
Contoh: p = Joni seorang mahasiswa
q = Mira seorang sarjana hukum
p v q = Joni seorang mahasiswa atau Mira seorang
sarjana hukum
12
p q p v q
S S S
S B B
B S B
B B B
P ^ q bernilai salah jika p dan q salah
-
8/4/2019 Matematika Diskrit Siap Print
13/253
Tabel Kebenaran(truth table)
Konjungsi (inclusive and)
13
p q p q
S S S
S B S
B S S
B B B
P ^ q bernilai benar jika p dan q benar
-
8/4/2019 Matematika Diskrit Siap Print
14/253
Konjungsi, Disjungsi, & Negasi (2)
Catatan :
Kata atau pada disjungsi digunakan dalam
makna inklusif; yakni, dinyatakan benarapabila baik p, atau q, atau keduanya bernilai benar
dan salah hanya jika kedua p dan q salah
Sedangkan makna eksklusif-atau, dinyatakan p XOR
q, bernilai benar apabila baik p atau q benar, tetapitidak keduanya.
qp
qp
14
-
8/4/2019 Matematika Diskrit Siap Print
15/253
Contoh
1. Untuk proposisi2 berikut:
p: 1+1 = 3
q: Satu tahun sama dengan 12 bulanTentukanlah Konjungsi, Disjungsi, Negasi
beserta nilai kebenarannya
15
-
8/4/2019 Matematika Diskrit Siap Print
16/253
Contoh (2)
Jawab:
a. : 1+1 = 3 dan satu tahun sama dengan 12bulan
p salah dan q benar, maka nilainya SALAH
b. : 1+1 = 3 atau satu tahun sama dengan12 bulan
p salah atau q benar, maka nilainyaBENAR
c. : 1+1 3
Karena p salah, maka nilainyaBENAR
qp
qp
16
p
p
-
8/4/2019 Matematika Diskrit Siap Print
17/253
Contoh (3)
2. Untuk proposisi2 berikut:
p: 1+1 = 3
q: Satu tahun sama dengan 12 bulanr: Tugu Pahlawan terletak di Surabaya
Nyatakan proposisi simbolik dengan
kata-kata dan kemudian evaluasi nilaikebenarannya.
17
r)qp(
-
8/4/2019 Matematika Diskrit Siap Print
18/253
Kalimat majemuk
compound statements
p, q, r merupakan kalimat / pernyataan sederhana
(simple statements) Beberapa contoh bentukan compound statements,
seperti:
(p q) r p (q r) (p) (q) (p q) (r) dll
18
-
8/4/2019 Matematika Diskrit Siap Print
19/253
Tabel Kebenaran (p r)q
19
p q r (p r)qS S S (S B) S= SS S B (S S) S = SS B S (S B) B = BS B B (S S B = BB S S (B B) S = BB S B (B S) S = SB B S (B B) B = BB B B (B S) B = B
-
8/4/2019 Matematika Diskrit Siap Print
20/253
Implikasi
Disebut juga proposisi kondisional (conditionalproposition) dan berbentuk
jika p maka q
Notasi simboliknya : p q Contoh:
p = " John rajin belajar"
q = " John dapat hadiah "
p q = If John rajin belajar then John dapat hadiah "
20
-
8/4/2019 Matematika Diskrit Siap Print
21/253
Tabel Kebenaran
21
p q p qS S B
S B BB S S
B B B
P q benar jika p dan q benar atau p salah
-
8/4/2019 Matematika Diskrit Siap Print
22/253
Hipotesa dan konklusi
Dalam implikasi p qp disebut anteseden, hipotesa, premis
(antecedent, hypothesis, premise)
q disebut konsekuensi atau konklusi(consequence,conclusion)
22
-
8/4/2019 Matematika Diskrit Siap Print
23/253
Cara menyebut p qjika p maka q if p then q
jika p, q if p, q
q jika p q if pp hanya jika q p only if q
p mengimplikasikan q p implies q
23
-
8/4/2019 Matematika Diskrit Siap Print
24/253
Eksklusif-Or, Implikasi, Bikondisional
P Q PQtrue true false
true false truefalse true true
false false false
P Q PQtrue true true
true false false
false true false
false false true 24
falsefalsetrue
truetruefalsetruefalsefalse
truetruetrue
PQQP
-
8/4/2019 Matematika Diskrit Siap Print
25/253
Kesamaan Logika
Dua proposisi majemuk P dan Q disebut ekuivalen
secara logika, ditulis sebagai bila keduanya
mempunyai nilai kebenaran yang sama, tidak peduli
nilai kebenaran yang dimiliki oleh proposisi unsur-unsurnya.
Contoh: hukum De Morgan I
dan II untuk logika, msg2 adalah
ekuivalen secara logika.
25
QP
qpqp
qpqp
-
8/4/2019 Matematika Diskrit Siap Print
26/253
Kesamaan Logika (2)
Untuk menunjukkan dua proposisi majemukekuivalen secara logika dapat dilakukandengan mengecek nilai kebenaran kedua
proposisi. Contoh:
Tunjukkan hukum De Morgan yang pertama
adalah ekuivalen secara logika.
26
qpqp
-
8/4/2019 Matematika Diskrit Siap Print
27/253
Contoh Kesamaan Logika
Tabel kebenaran untuk kesamaan tersebut adalah:
Dari tabel di atas terlihat bahwa untuk nilai sembarang yang
diberikan dari p dan q, dan mempunyai nilai
kebenaran yang sama, sehingga dapat ditulis:
27
qp qp
qpqp
-
8/4/2019 Matematika Diskrit Siap Print
28/253
Tabel Kesamaan Logika
28
-
8/4/2019 Matematika Diskrit Siap Print
29/253
Tabel Kesamaan Logika
untuk Kondisional & Bikondisional
29
p)
-
8/4/2019 Matematika Diskrit Siap Print
30/253
Kesamaan Logika
Keterangan:
T : Pernyataan yang selalu bernilai BENAR
(Tautologi)
F : Pernyataan yang selalu bernilai SALAH
(Kontradiksi)
30
-
8/4/2019 Matematika Diskrit Siap Print
31/253
Contoh Pembuktian
Kesamaan Logika
1. Tunjukkan bahwa ~(pV(~pq)) dan ~p~q adalahekivalen secara logika TANPA menggunakan tabelkebenaran!
2. Tunjukkan bahwa (pq) (pVq) adalah sebuah
Tautologi TANPA menggunakan tabel kebenaran!Petunjuk: Untuk menunjukkan bahwa pernyataandiatas adalah sebuah Tautologi, gunakan daftarkesamaan logika untuk menunjukkan bahwapernyataan tersebut ekivalen dengan T
31
-
8/4/2019 Matematika Diskrit Siap Print
32/253
Solusi Contoh 1
ekivalenbenarqp
qp
qpT
qpppqpp
qpqpp
32
-
8/4/2019 Matematika Diskrit Siap Print
33/253
Solusi Contoh 2
33
TTT
qqpp
qpqp
qpqp
BABANB
qpqp
BA
)()(
:
-
8/4/2019 Matematika Diskrit Siap Print
34/253
Latihan
1. Jika p dan q bernilai benar (T); r dan s bernilai salah (F).
Tentukan nilai kebenaran kalimat berikut :
2. Tentukan apakah kalimat berikut ekivalen TANPA
menggunakan tabel kebenaran :
srqprqpbrqpa
.
.
pqpqppb
pqpqpa
.
.
34
-
8/4/2019 Matematika Diskrit Siap Print
35/253
Latihan
3. Buktikan apakah kalimat berikut merupakan tautologi atau
kontradiksi!
35
qpqbqqpa
.
.
-
8/4/2019 Matematika Diskrit Siap Print
36/253
Proposisi Bersyarat
Definisi:
Misal p dan q adalah proposisi, proposisi majemuk
jika p maka q disebut proposisi bersyarat dan
dinotasikan sebagai p q Proposisi p disebut hipotesis (anteseden) dan
proposisi q disebut konklusi (konsekuen)
36
-
8/4/2019 Matematika Diskrit Siap Print
37/253
Proposisi Bersyarat
Nilai kebenaran dari proposisi bersyarat
diberikan oleh tabel kebenaran berikut:
37
-
8/4/2019 Matematika Diskrit Siap Print
38/253
Implikasi p q
Jika p, maka q
Jika p, q
p mengakibatkan q
p hanya jika q
p cukup untuk q
Syarat perlu untuk p
adalah q
q jika p
q ketika p
q diakibatkan p
q setiap kali p
q perlu untuk p
Syarat cukup untuk q
adalah p
38
-
8/4/2019 Matematika Diskrit Siap Print
39/253
Proposisi Bersyarat
Dalam percakapan sehari-hari, hipotesis dan konklusi dalamproposisi bersyarat biasanya berhubungan, tetapi dalamlogika, hipotesis dan konklusi dalam proposisi bersyarat tidakharus merujuk pada permasalahan yang sama.
Logika memperhatikan bentuk proposisi dan hubungan antarproposisi tetapi tidak memperhatikan pokok permasalahandari proposisi itu sendiri.
Perhatikan bahwa proposisi bersyarat yang benar berbedadengan proposisi bersyarat dengan konklusi yang benar.
39
-
8/4/2019 Matematika Diskrit Siap Print
40/253
Proposisi Bersyarat
Contoh:1. Misal: p = 1 > 2
q = Satu meter sama dengan 100 cm
Tentukan nilai kebenaran dari proposisi bersyarat p q
(Jika 1 > 2 maka satu meter sama dengan 100 cm)Jawab:
p: salah q: benar
Maka menurut tabel kebenaran 2.1, proposisi diatas bernilaiBENAR
40
-
8/4/2019 Matematika Diskrit Siap Print
41/253
Proposisi Bersyarat
2. Tunjukkan bahwa pq ekivalen secara logika dengan ~pVq.
Jawab:
Tabel kebenaran untuk pq dan ~pVq:
Kesimpulan: pq ekivalen scr logika dgn ~pVq
pq ~pVq
41
-
8/4/2019 Matematika Diskrit Siap Print
42/253
Proposisi Bersyarat
3. Bagaimana nilai kebenaran proposisi berikut:
If today is Friday, then 2x3=5
Jawab:
p : today is Friday
q : 2 x 3 = 5
Proposisi di atas akan selalu bernilai BENARkecualipada hari Jumat
42
-
8/4/2019 Matematika Diskrit Siap Print
43/253
Proposisi Bersyarat
4. Bagaimana nilai kebenaran proposisi berikut: Jika mhs ikut ujian, makaia harus membawa kartu ujian
Jawab:
p: Mhs ikut ujian
q: mhs membawa kartu ujian
43
-
8/4/2019 Matematika Diskrit Siap Print
44/253
Bikondisional
Misal p dan q adalah proposisi, proposisimajemukp jika dan hanya jika q disebut proposisibikondisional (dwisyarat) dan dinotasikan sebagai
p q. Nilai kebenaran p q sebagai berikut:
44
-
8/4/2019 Matematika Diskrit Siap Print
45/253
Bikondisional
Catatan : Cara lain menyatakan p jika dan hanya jika q adalah:
p adalah syarat perlu dan cukup untuk q
Jika p maka q, dan sebaliknya
Contoh:
1. p: You can take the flightq: You buy a ticket
pq: You can take the flight if and only if you
buy a ticket
Pernyataan diatas benar jika p dan q keduanya benarataukeduanya salah. Pernyataan di atas salah jika hanya salahsatu dari p dan q yang benar.
45
-
8/4/2019 Matematika Diskrit Siap Print
46/253
Bikondisional
3. Tunjukkan dgn tabel kebenaran bahwa:p q (pq) (qp)
Jawab:Tabel kebenarannya sbb:
Karena nilai kebenaran pq sama dengan nilai kebenaran(pq) (qp), maka keduanya ekivalen.
46
-
8/4/2019 Matematika Diskrit Siap Print
47/253
Konvers, Kontrapositif, Invers
Misal sebuah kondisi bersyarat p q Konvers-nya : q p
Kontrapositif-nya : ~q ~p
Invers-nya : ~p ~q
Contoh:
Tentukan Konvers, Kontrapositif, dan Invers dari: Jika adapencuri masuk rumah, maka pintu dalam keadaan terbuka
p: Ada pencuri masuk rumah
q: Pintu dalam keadaan terbuka
47
-
8/4/2019 Matematika Diskrit Siap Print
48/253
Konvers, Kontrapositif, Invers
Konvers (q p):
Jika pintu dalam keadaan terbuka, maka ada pencurimasuk rumah
Kontrapositif (~q
~p):Jika pintu dalam keadaan tertutup, maka tidak adapencuri masuk rumah
Invers (~p ~q):
Jika tidak ada pencuri masuk rumah, maka pintudalam keadaan tertutup
48
-
8/4/2019 Matematika Diskrit Siap Print
49/253
Ekspresi Logika
Contoh 4. Ubah ke dalam ekspresi logika:
Anda mempunyai akses internet hanya jika anda mahasiswa
Matematika ITB atau anda bukan mahasiswa TPB
Solusi. Misal a : Anda punya akses internetm: Anda mhs Matematika ITB
f : Anda mhs TPB
a (m f)
49
-
8/4/2019 Matematika Diskrit Siap Print
50/253
Ekspresi Logika (2)
Soal 1. Ubah kedalam ekspresi logika.
Anda tidak boleh naik roller coaster jika tinggi anda
kurang dari 100 cm, kecuali usia anda sudah
melebihi 16 th.
Saya akan ingat tentang kuliah besok hanya jika
kamu mengirim sms.
Pantai akan erosi ketika ada badai
50
-
8/4/2019 Matematika Diskrit Siap Print
51/253
Logika Inferensi
Modus Ponen
Modus Tollen
q
p
qp
p
q
qp
51
Penambahan Disjungtif
qpqp
qp
Penyederhanaan Konjungtif
qpqpqp
-
8/4/2019 Matematika Diskrit Siap Print
52/253
Logika Inferensi (2)
Silogisme Disjungtif
Silogisme Hipotesispq
qp
qpqp
rp
rq
qp
52
Dilema
Konjungsi
rrq
rp
qp
qp
q
p
-
8/4/2019 Matematika Diskrit Siap Print
53/253
Contoh
Pada suatu hari, Anda hendak pergi ke kampus dan baru sadar bahwaAnda tidak memakai kacamata. Setelah mengingat-ingat, ada beberapafakta yang Anda pastikan kebenarannya :
a. Jika kacamataku ada di meja dapur, maka aku pasti sudah melihatnya ketikasarapan pagi.
b. Aku membaca koran di ruang tamu atau aku membacanya di dapur.
c. Jika aku membaca koran di ruang tamu, maka pastilah kacamata kuletakkan dimeja depan.
d. Aku tidak melihat kacamataku pada waktu sarapan pagi.
e. Jika aku membaca buku di ranjang, maka kacamata kuletakkan di meja sampingranjang.
f. Jika aku membaca koran di dapur, maka kacamataku ada di meja dapur.
Berdasarkan fakta-fakta tersebut, tentukan di mana letak kacamata
tersebut !
53
-
8/4/2019 Matematika Diskrit Siap Print
54/253
-
8/4/2019 Matematika Diskrit Siap Print
55/253
Inferensi yang dapat dilakukan adalah sbb :
PonenModusdengant
(3)darikesimpulanr(c)faktatr4.
DisjungtifSilogismedenganr
(2)darikesimpulans
(b)faktasr3.TollenModusdengans
(1)darikesimpulanp
(f)faktaps2.
TollenModusdenganp(d)faktaq
(a)faktaqp1.
55
Kesimpulan kacamata ada di meja tamu
-
8/4/2019 Matematika Diskrit Siap Print
56/253
Latihan
1. Show that the hypotheses It is not sunny this afternoon and it iscolder than yesterday, We will go swimming only if it is sunny, Ifwe do not go swimming, then we will take a canoe trip, If we takea canoe trip, then we will be home by sunset lead to the conclusionWe will be home by sunset.
2. Show that hypotheses If you send me an email message, then I will
finish writing the program, If you do not send me an emailmessage, then I will go to sleep early, If I go to sleep early, then Iwill wake up feeling refreshed lead to the conclusion If I do notfinish writing the program then I will wake up feeling refreshed.
56
-
8/4/2019 Matematika Diskrit Siap Print
57/253
Predikat
Pernyataan yg melibatkan variabel, seperti x>3,x=y+3, dan x+y=z sering ditemukan dalam ilmumatematika dan komputer.
Pernyataan tsb blm memiliki nilai kebenaran jika nilai
dari variabelnya belum didefinisikan.
Pernyataan x lebih besar dari 3 memiliki 2 bagian:
Bag. 1: variabel x itu sendiri, yg merupakan subjek daripernyataan
Bag 2: predikat, lebih besar dari 3, yg mengacu pada sifatyg dapat dimiliki oleh subjek pernyataan
57
-
8/4/2019 Matematika Diskrit Siap Print
58/253
Propotional Function
Pernyataan x lebih besar dari 3 dapat dinyatakandgn P(x), dimana P merupakan predikat lebih besardari 3 dan x adalah variabel.
P(x) juga dapat dikatakan sebagai propotional
function P pada x. Jika x sudah diberikan sebuah nilai, maka P(x)
menjadi sebuah proposisi dan memiliki nilaikebenaran.
x dapat juga merupakan anggota dari sebuahhimpunan domain (daerah asal) D.
58
-
8/4/2019 Matematika Diskrit Siap Print
59/253
Propotional Function
Contoh:
Misal P(x) menyatakan x >3. Bagaimana nilai
kebenaran untuk P(4) dan P(2)?
Jawab:
P(4) x = 4 shg pernyataannya menjadi 4 >3, nilai
kebenarannya adalah BENAR
P(2) x = 2 shg pernyataannya menjadi 2>3, nilaikebenarannya adalah SALAH
59
-
8/4/2019 Matematika Diskrit Siap Print
60/253
Propotional Function
Propotional function juga dapat melibatkan lebih dari 1
variabel.
Contoh: pernyataan x = y + 3 dapat dinyatakan dengan
Q(x,y) dimana x dan y adalah variabel dan Q adalah
predikat.
Nilai kebenaran dari Q(1,2) adalah SALAH dan nilai
kebenaran dari Q(3,0) adalah BENAR
60
Propotional Function
-
8/4/2019 Matematika Diskrit Siap Print
61/253
Propotional Function
dengan daerah Domain
Contoh:
P(x): x adalah bilangan ganjil; x D
D = himpunan bilangan bulat positif
Jika x = 1, maka P(1) bernilai BENAR
Jika x = 2, maka P(2) bernilai SALAH
Jika x = 3, maka P(3) bernilai BENAR
dst.
61
-
8/4/2019 Matematika Diskrit Siap Print
62/253
Universal Quantor
Misalkan P adalah fungsi proposisi dengan daerah asal D.
dibaca untuk setiap x, P(x)
merupakan kuantor universal, dan dibaca untuk setiapatau untuk semua
Pernyataan bernilai BENAR jika berlaku untuk semuax pada domain D.
Pernyataan bernilai SALAH jika berlaku hanya padasebagian x pada domain D.
)x(P,x
)x(P,x
62
)x(P,x
-
8/4/2019 Matematika Diskrit Siap Print
63/253
Universal Quantor
Contoh 1:
Tulislah pernyataan berikut dengan simbol
universal quantor: Untuk setiap x, x2 0
Jawab:
P(x) : x2 0, maka:
63
0x,x 2
-
8/4/2019 Matematika Diskrit Siap Print
64/253
Universal Quantor
Contoh 2:
Tulislah pernyataan berikut dengan simbol
universal quantor: Untuk semua x, jika x > 1,
maka x2> 1
Jawab:
P(x): x > 1 x2 > 1, maka:
64
1x1x,x 2
-
8/4/2019 Matematika Diskrit Siap Print
65/253
Universal Quantor
Contoh 3:
Misal P(x): x + 1 > x
Bagaimana nilai kebenaran dari
dimana domainnya adalah semua bilangan real?Jawab:
D = himp. Bil real. Karena P(x) benar untuk semuabilangan real x, maka
bernilai BENAR
)x(P,x
)x(P,x
65
-
8/4/2019 Matematika Diskrit Siap Print
66/253
Universal Quantor
Contoh 4:
Misal P(x): x < 2. Bagaimana nilai kebenaran dari
untuk domain semua bilangan real?
Jawab:P(x) tidak benar untuk setiap bilangan real x, karena
(misal) untuk x=3, maka P(x) SALAH. Sehingga
bernilai SALAH
)x(P,x
)x(P,x
66
-
8/4/2019 Matematika Diskrit Siap Print
67/253
Existential Quantor
Misalkan P adalah fungsi proposisi dengan daerah asalD.
dibaca untuk beberapa x, P(x)
merupakan kuantor eksistensial, dan dibaca untukbeberapa, ada, atau setidaknya ada.
Pernyataan bernilai BENAR jika berlaku untuksetidaknya salah satu x dari domain D.
Pernyataan bernilai SALAH jika tidak ada ygberlaku dari domain D.
)x(P,x
)x(P,x
67
)x(P,x
-
8/4/2019 Matematika Diskrit Siap Print
68/253
Existential Quantor
Contoh 1:
Tuliskan pernyataan berikut dengan simbol
kuantor eksistensial: Untuk beberapa x, x2
0
Jawab:
P(x): x2 0, maka
68
0x,x 2
-
8/4/2019 Matematika Diskrit Siap Print
69/253
Existential Quantor
Contoh 2:
Tuliskan pernyataan berikut dengan simbol
kuantor eksistensial: Untuk setidaknya satu x,
jika x>1, maka x2>1
Jawab:
P(x): x>1 x2>1, maka:
69
1x1x,x 2
-
8/4/2019 Matematika Diskrit Siap Print
70/253
Existential Quantor
Contoh 3:
Misal P(x): x > 3. Bagaimana nilai kebenaranpada domain semua bilangan real?
Jawab:P(x) bernilai benar untuk beberapa nilai x,misal 4 dan 5. Sehingga bernilai
BENAR
)x(P,x
)x(P,x
70
l
-
8/4/2019 Matematika Diskrit Siap Print
71/253
Existential Quantor
Contoh 4:
Misal P(x): x2 < 0. Bagaimana nilai kebenaran
untuk domain semua bilangan real?
JAWAB:Pernyataan tersebut SALAH, karena untuk semua x,
adalah salah bahwa kuadrat x bernilai negatif.
)x(P,x
71
-
8/4/2019 Matematika Diskrit Siap Print
72/253
Negasi dari Quantor
~( )
~( )
Contoh:
Tentukan negasi dari: Semua manusia memiliki
orangtua Tentukan negasi dari:Ada orang Indonesia yang tidak
suka gado-gado
)x(P,x
)x(P,x
72
)(~, xPx
)(~, xPx
K G d
-
8/4/2019 Matematika Diskrit Siap Print
73/253
Kuantor Ganda
Contoh :
Untuk setiap orang x, terdapat seorang y sedemikian
hingga y adalah ibu dari x.
Jawab :
x"dariibuadalahy":y)P(x,y),P(x,y)x)((
73
K G d
-
8/4/2019 Matematika Diskrit Siap Print
74/253
Kuantor Ganda
Contoh :
Terdapat seorang y sehingga untuk semua orang x, y
adalah ibu dari x.
Jawab :
x"dariibuadalahy":y)P(x,dimanay),P(x,x)y)((
74
-
8/4/2019 Matematika Diskrit Siap Print
75/253
y)P(x,y)x)((y)P(x,y)x)((
y)P(x,y)x)((y)P(x,y)x)((
:Ingkaran
y)P(x,x)y)((y)P(x,y)x)((
y)P(x,x)y)((y)P(x,y)x)((
y)P(x,))((y)P(x,y)x)((
:gandakuantorantarHubungan
xy
75
C h
-
8/4/2019 Matematika Diskrit Siap Print
76/253
Contoh
Apakah ingkaran kalimat berikut :
a.
b.
P.kanmenyelesaidapat
tidakCC)komputerprogramP)(masalah(
2knkbulatbilangannbulatbilangan
P.kanmenyelesai
dapatCC)komputerprogramP)(masalah(b.
2knkbulatbilangannbulatbilangana.
:Jawab
76
-
8/4/2019 Matematika Diskrit Siap Print
77/253
Latihan
1. Ubahlah ke ekspresi logika predikata.Setiap mhs dalam kelas ini telah mengambilKalkulus I.
b.Semua orang Indonesia makan pecel lele.
c.x+y = y+x berlaku untuk semua bilangan real x dan y.
d.Untuk setiap x ada nilai y sehingga x+y = 0.
e.Untuk setiap x, y dan z berlaku hukum asosiatif x+(y+z) =(x+y)+z.
2. Cari negasi dari ekspresi logika predikat hasil no.1lalu ubahlah kedalam kalimat.
77
-
8/4/2019 Matematika Diskrit Siap Print
78/253
Latihan
3.Artikan kalimat ini dalam bhs Indonesia:bila C(x) : x mempunyai komputer,
F(x,y): x dan y berteman,
dan domainnya adalah semua mhs di kampus.
a. x (C(x) y ( C(y) F(x,y))),
b. xy z((F(x,y) F(x,z) (y z) F(y,z))
c. x y (xy=1)
78
-
8/4/2019 Matematika Diskrit Siap Print
79/253
ARGUMEN & METODE PEMBUKTIAN
Argumen adalah suatu deret proposisi yang dituliskansebagai :
p1
p2
p3
.
pn----------
p1, p2, , pn disebut hipotesis (premis) dan p disebutkonklusi.
79
p
-
8/4/2019 Matematika Diskrit Siap Print
80/253
Inference Rule
Universal
Instantiation
UniversalGeneralization
Existensial
Instantiation
Existential
Generalization
celementsomeforcP
xPx
)(
)(
)(
)(
xPx
carbitraryanforcP
)(
)(
xPx
carbitrarysomeforcP
80
)(
)(
cP
xPx
C h
-
8/4/2019 Matematika Diskrit Siap Print
81/253
Contoh
Diketahui premis Everyone in this discrete
mathematics class has taken a course in
computer science and Marla is a student in
this class Apakah benar konklusinya adalahMarla has taken a course in computer
science
81
S l i
-
8/4/2019 Matematika Diskrit Siap Print
82/253
Solusi
Misal :
P(x) : x is in this discrete mathematics class
Q(x) : x has taken a course in computer science
Maka logika kuantor dari premis diatas :
)(?
)(
))()((
MarlaQkonklusi
MarlaP
xQxPx
82
I f R l
-
8/4/2019 Matematika Diskrit Siap Print
83/253
Inference Rule
)(
)(
)()(.2)()(
))()((.1
MarlaQ
MarlaP
MarlaQMarlaPMarlaQMarlaP
xQxPx
83
Premise
Universal InstantiationHasil (1)Premise
Modus Ponen
-
8/4/2019 Matematika Diskrit Siap Print
84/253
III. METODE PEMBUKTIAN
84
I d k i ik
-
8/4/2019 Matematika Diskrit Siap Print
85/253
Induksi matematika
merupakan teknik pembuktian yang sangat penting
dipergunakan secara luas untuk membuktikan
pernyataan yang berkaitan dengan obyek diskrit.
(kompleksitas algoritma, teorema mengenai graf,identitas dan ketidaksamaan yang melibatkan
bilangan bulat, dsb).
tidak dapat digunakan untuk menemukan rumus
atau teorema, tetapi hanya untuk melakukan
pembuktian.
85
Berapakah jumlah dari n bilangan ganjil positif
-
8/4/2019 Matematika Diskrit Siap Print
86/253
Berapakah jumlah dari n bilangan ganjil positif
pertama?
1 = 1
1 + 3 = 4
1 + 3 + 5 = 9
1 + 3 + 5 + 7 = 16
1 + 3 + 5 + 7 + 9 = 25
Tebakan:
Jumlah dari n bilangan ganjil positif pertama adalah n2.
Metoda apa yang dapat dipakai untuk membuktikan bahwa
tebakan ini benar, jika memang pada kenyataannya benar?
86
Induksi matematika
-
8/4/2019 Matematika Diskrit Siap Print
87/253
Induksi matematika
Suatu bukti dengan menggunakan induksi matematika bahwa P(n) benaruntuk setiap n bilangan bulat positif
terdiri dari tiga langkah:
1. Langkah basis:
Tunjukkan bahwa P(1) benar.
2. Langkah induktif:
Tunjukkan bahwa P(k) P(k + 1) benar untuk setiap k.P(k) untuk suatu k tertentu disebut hipotesa induksi.
3. Konklusi:n P(n) bernilai benar.
87
Teknik untuk membuktikan proposisi dalam bentukn P(n),
dengan semesta pembicaraan adalah himpunan bilangan bulatpositif.
Berapakah jumlah dari n bilangan ganjil positifpertama?
-
8/4/2019 Matematika Diskrit Siap Print
88/253
pertama?
Tebakan:
Jumlah dari n bilangan ganjil positif pertama adalah n2
.
88
Bukti:
Misalkan P(n): proposisi Jumlah dari n bilangan ganjil positif
pertama adalah n2.
1. Langkah basis:
P(1) benar, karena 1 = 12.
2. Langkah induktif:
Asumsikan bahwa P(k) benar untuk semua k, yaitu
1 +3 + 5 + + (2k-1) = k2.Kita perlu menunjukkan bahwa P(k + 1) benar, yaitu
1 +3 + 5 + + (2k-1) + (2k+1) = (k+1)2.
1 +3 + 5 + + (2k-1) + (2k+1) = k2 + (2k+1)
= (k+1)2
Berapakah jumlah dari n bilangan ganjil positif
-
8/4/2019 Matematika Diskrit Siap Print
89/253
p j g g j p
pertama?
3. Konklusi:
Jumlah dari n bilangan ganjil positif pertama adalahn2.
Akhir dari bukti.
89
ContohGauss 1 + 2 + + n = n (n + 1)/2
-
8/4/2019 Matematika Diskrit Siap Print
90/253
Gauss. 1 + 2 + + n = n (n + 1)/2
Bukti.
Misalkan P(n): proposisi 1 + 2 + + n = n (n + 1)/2
1. Langkah basis:Untuk n = 1 diperoleh peroleh 1 = 1. Jadi, P(1) benar.
2. Langkah induktif:
Asumsikan bahwa P(k) benar untuk semua k, yaitu
1 + 2 + + n = n (n + 1)/2
Akan ditunjukkan bahwa P(k + 1) benar, yaitu1 + 2 + + k + (k + 1) = (k + 1) ((k + 1) + 1)/2
Dari 1 + 2 + + k = k (k + 1)/2, diperoleh
1 + 2 + + k + (k + 1) = k (k + 1)/2 + (k + 1)
= (2k + 2 + k (k + 1))/2
= (2k + 2 + k2 + k)/2= (2 + 3k + k2 )/2
= (k + 1) (k + 2)/2
= (k + 1) ((k + 1) + 1)/2
90
Contoh
-
8/4/2019 Matematika Diskrit Siap Print
91/253
3. Konklusi:
Jadi 1 + 2 + + n = n (n + 1)/2 benar untuk setiap
nN.Akhir dari bukti.
91
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
92/253
Latihan
1.Buktikan bahwa n3-n dapat dibagi 3 untuk n bilanganbulat positif.
2.Buktikan :
1+2+22
++2n
=2n+1
-1untuk semua bilangan bulat positif.
3. Buktikan 22n-1 habis dibagi 3 untuk semua bil.bulat
n1
4.
n
i
ni
riilbilrbulatbilsemuauntukr
rr
0
1
1.0.1
1
92
Metode Pembuktian
-
8/4/2019 Matematika Diskrit Siap Print
93/253
Contoh Penyangkal (Counter Example).
Tunjukkan bahwa pernyataan
setiap bilangan bulat positif adalah hasil tambah dari tigabilangan kuadrat
adalah salah.
Solusi. Pernyataan ini benar untuk beberapa nilai, mis.
1=02+02+12; 2=02+12+12 ; 3=12+12+12 ; 4=02+02+22 ;5=02+12+22 ; 6=12+12+22 .
Tapi kita tidak dapat mengekspresikan seperti di atas untukbilangan 7.
Jadi bilangan 7 merupakan contoh penyangkal daripernyataan di atas.
93
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
94/253
Latihan
Tunjukkan bahwa jika segitiga siku-siku RSTdengan sisi tegak r, s, dan sisi miring tmempunyai luas t2/4, maka segitiga tersebutsama kaki.
Buktikan bahwa jika n bulat dan tidak habisdibagi oleh 2 atau 3 maka n2 1 habis dibagi24.
Tunjukkan bhw tidak ada solusi bulat x dany yang memenuhi x2 + 3y2 =8.
94
-
8/4/2019 Matematika Diskrit Siap Print
95/253
IV. PERMUTASI DAN
KOMBINASI
95
Prinsip Perkalian
-
8/4/2019 Matematika Diskrit Siap Print
96/253
Prinsip Perkalian
Jika sebuah aktivitas bisa dibentuk dalam tlangkah berurutan dan langkah 1 bisa
dilakukan dalam n1 cara; langkah kedua bisa
dilakukan dalam n2cara; .; langkah tbisadilakukan dalam nt cara, maka banyaknya
aktivitas berbeda yang mungkin adalah
n1.n2.nt.
96
Prinsip Perkalian
-
8/4/2019 Matematika Diskrit Siap Print
97/253
Prinsip Perkalian
Contoh 1:Sebuah panitia yang terdiri dari enam orang terdiri dari Ali,Budi, Cokro, Dewi, Edi, dan Franky akan memilih seorangketua, sekretaris, dan bendahara. Ada berapa banyak carapemilihan ini bisa dilaksanakan ?
Jawab:Pemilihan dilakukan dgn 3 langkah berurutan:
1. Memilih ketua (ada 6 cara) n12. Memilih sekretaris (ada 5 cara) n23. Memilih bendahara (ada 4 cara) n
3
Total ada n1 x n2 x n3 = 6 x 5 x 4 = 120 cara
97
Prinsip Perkalian
-
8/4/2019 Matematika Diskrit Siap Print
98/253
Prinsip Perkalian
Contoh 2:Kursi di sebuah auditorium akan diberi nomor yangterdiri dari 1 huruf dan sebuah bil integer positif ygtidak melebihi 100. Ada berapa kursi yang dapat
dilabeli dgn nomor yg berbeda?Jawab:
1. Memilih huruf (ada 26 cara)
2. Memilih angka (ada 100 cara)
Total ada 26 x 100 = 2600 nomor berbeda yg dapatdigunakan untuk melabeli kursi
98
Prinsip Perkalian
-
8/4/2019 Matematika Diskrit Siap Print
99/253
Prinsip Perkalian
Contoh 3:Ada berapa banyak plat nomor kendaraan bermotor di Surabaya yg dapatdibuat jika nomor terdiri dari huruf L, diikuti dgn 4 digit angka, dan 2 hurufbelakang?
Jawab:
1. Memilih huruf pertama L (1 cara)
2. Memilih digit angka I (9 cara)3. Memilih digit angka II (10 cara)
4. Memilih digit angka III (10 cara)
5. Memilih digit angka IV (10 cara)
6. Memilih huruf belakang I (26 cara)
7. Memilih huruf belakang II (26 cara)Total ada 26.26.9.10.10.10 = 6.084.000 plat nomor
99
-
8/4/2019 Matematika Diskrit Siap Print
100/253
Prinsip Penjumlahan
-
8/4/2019 Matematika Diskrit Siap Print
101/253
Prinsip Penjumlahan
Jika aktivitas pertama dapat dilakukan dalamn1 cara, aktivitas kedua dengan n2cara, , dan
aktivitas ke-t dengan nt cara, dan jika aktivitas2
ini tidak dapat dilakukan pada waktu ygbersamaan, maka ada n1 + n2+ + nt cara
untuk melakukan aktivitas tersebut
101
Prinsip Penjumlahan
-
8/4/2019 Matematika Diskrit Siap Print
102/253
Prinsip Penjumlahan
Contoh 1:Mengacu pada Contoh 1 sebelumnya, ada berapa banyak carapemilihan ini bisa dilaksanakan apabila Ali atau Budi harus menjadiketua ?
Jawab:
Jika Ali sebagai ketua, maka sekretaris bisa dipilih dalam 5 cara.
Setelah pemilihan ketua dan sekretaris, bendahara bisa dipilih dalam4 cara. Oleh karena, apabila Ali sebagai ketua jumlah total darikemungkinan untuk memilih pengurus yang lain adalah 5.4 = 20 cara.
Jika Budi sebagai ketua jumlah total dari kemungkinan untuk memilihpengurus yang lain adalah 5.4 = 20 cara
Karena kedua kasus saling lepas, menurut prinsip penjumlahan,terdapat 20 + 20 = 40 cara pemilihan pengurus bisa dilaksanakanapabila Ali atau Budi harus menjadi ketua.
102
Prinsip Penjumlahan
-
8/4/2019 Matematika Diskrit Siap Print
103/253
Prinsip Penjumlahan
Contoh 2:Misal akan dipilih satu orang perwakilan anggotapengurus himajur dari 15 laki-laki dan 17perempuan untuk menghadiri rapat di fakultas.
Ada berapa macam cara untuk memilih perwakilantersebut?
Jawab:
1. Memilih anggota dari 15 laki-laki 15 cara
2. Memilih anggota dari 17 perempuan 17 caraMaka ada 15 + 17 = 32 cara untuk memilih
perwakilan
103
Prinsip Penjumlahan
-
8/4/2019 Matematika Diskrit Siap Print
104/253
Prinsip Penjumlahan
Contoh 3:Seorang mhs dapat memilih sebuah topik tugas akhirdari salah satu daftar dari 3 daftar judul ygdisediakan. Ketiga daftar tsb masing2 memiliki 23,
15, dan 19 topik tugas akhir. Ada berapa banyak topikyg dapat dipilih?
Jawab:
Dari daftar I dapat dipilih 23 topik
Dari daftar II dapat dipilih 15 topikDari daftar III dapat dipilih 19 topik
Maka ada 23 + 15 + 19 = 57 topik yg dapat dipilih
104
Contoh Perkalian & Penjumlahan
-
8/4/2019 Matematika Diskrit Siap Print
105/253
Contoh Perkalian & Penjumlahan
Contoh 4:Sebuah password komputer terdiri dari 6 s.d. 7 karakter, dimana tiapkarakter dapat berupa huruf besar atau sebuah digit angka. Password tsbminimal memiliki 1 digit angka. Ada berapa banyak kombinasi password?
Jawab:
Misal: P6 = jumlah total pwd yg terdiri dr 6 kar
P7 = jumlah total pwd yg terdiri dr 7 karP: jumlah total pwd yg terdiri dari 6 atau 7 kar = P6 + P7Utk P6 & P7: jumlah pwd yg terdiri dari huruf dan setidaknya 1 digit angka =
jumlah pwd keseluruhan jumlah pwd tanpa digit angka
P6 = (26+10)6 266 = 1.867.866.560
P7 = (26+10)7 267 = 70.332.353.920
P = P6 + P7 = 72.200.220.480 kemungkinan password
105
Contoh Perkalian & Penjumlahan
-
8/4/2019 Matematika Diskrit Siap Print
106/253
Contoh Perkalian & Penjumlahan
Contoh 5:
Misal dalam sebuah rak ada 4 buku
Matematika yg berbeda, 3 buku Biologi yg
berbeda, & 2 buku Fisika yg berbeda. Berapabanyak cara 2 buku dengan bidang yg berbeda
bisa dipilih dari rak tersebut?
106
Permutasi
-
8/4/2019 Matematika Diskrit Siap Print
107/253
Permutasi
Permutasi menggunakan prinsip perkalian Permutasi dari n unsur yang berbeda x1, x2, ,
xn adalah sebuah pengurutan dari n unsur x1,
x2, , xn. Permutasi MEMPERHATIKAN urutan objek yg
disusun
Banyaknya permutasi dari n unsur = n!
107
Permutasi
-
8/4/2019 Matematika Diskrit Siap Print
108/253
Permutasi
Contoh:
Hitung banyaknya permutasi dari 3 huruf A, B,
C
Tuliskan semua permutasi A, B, C
Jawab:
- n =3, maka permutasi = n! = 3! = 6
- ABC, ACB, BAC, BCA, CAB, CBA
108
Permutasi r dari n unsur
-
8/4/2019 Matematika Diskrit Siap Print
109/253
Permutasi r dari n unsur
Contoh di atas mengasumsikan bahwa yg dipermutasikanadalah seluruh n.
Permutasi r dari n mempermutasikan r
(r n) dari n unsur yang ada.
P(n,r) = Banyaknya permutasi-r dari sebuah himpunan dariobjek-objek yang berbeda
109
)!(
!
),( rn
n
rnP
Permutasi r dari n unsur
-
8/4/2019 Matematika Diskrit Siap Print
110/253
Permutasi r dari n unsur
Contoh 1:
Ada berapa cara untuk memilih juara I, II, dan
III dari 100 orang yg mengikuti sebuah lomba?
Jawab:
n = 100 r = 3
P(100,3) = 100.99.98 = 970.200 cara
110
Permutasi r dari n unsur
-
8/4/2019 Matematika Diskrit Siap Print
111/253
Permutasi r dari n unsur
Contoh 2:Misal seorang sales akan mengunjungi 8 kota ygberbeda satu-persatu. Ia harus mulai dari 1 kotatertentu, tetapi setelah itu bebas untuk memilih rute
ke 7 kota lainnya. Ada berapa kemungkinan rute?Jawab:
Jumlah kota yg dipermutasikan = 7
Jumlah rute = 7! = 5040 rute
111
Permutasi r dari n unsur
-
8/4/2019 Matematika Diskrit Siap Print
112/253
Permutasi r dari n unsur
Contoh 3:
Ada berapa banyak permutasi dari huruf ABCDEFGH
yang terdiri dari substring ABC?
Jawab:Krn ABC harus muncul sebagai 1 kesatuan, maka
jumlah yg dipermutasikan = 6 (ABC, D, E, F, G, H)
Jumlah permutasi = 6! = 720 permutasi
112
Generalisasi Permutasi
-
8/4/2019 Matematika Diskrit Siap Print
113/253
Generalisasi Permutasi
Teorema: Misal X adalah barisan yg memiliki nunsur, dimana ada n1 unsur yg sama untuk
jenis 1, n2 unsur yg sama untuk jenis 2, dst
sampai ntunsur yg sama utk jenis t.Banyaknya permutasi dari X:
113
!!...!!
21 tnnnn
Generalisasi Permutasi
-
8/4/2019 Matematika Diskrit Siap Print
114/253
Generalisasi Permutasi
Contoh:Ada berapa permutasi dari kata MASSACHUSETTS?
Jawab:
Jumlah huruf: 13
Jumlah M: n1 = 1 Permutasi
Jumlah A: n2
= 2
Jumlah S: n3 = 4
Jumlah C: n4 = 1
Jumlah H: n5 = 1
Jumlah U: n6 = 1
Jumlah E: n7 = 1
Jumlah T: n8 = 2
114
64.864.800
96
8006.227.020.!2!1!1!1!1!4!2!1
!13
-
8/4/2019 Matematika Diskrit Siap Print
115/253
Kombinasi
-
8/4/2019 Matematika Diskrit Siap Print
116/253
Kombinasi
Contoh 1:a. Hitunglah banyaknya kombinasi 2 dari tiga huruf
A, B, dan C.
b. Daftarlah kombinasi 2 dari tiga huruf A, B, dan C.Jawab:
a. n = 3 r = 2
C(3,2) = 3!/(3-2)!2! = 3b. AB, AC, BC
116
Kombinasi
-
8/4/2019 Matematika Diskrit Siap Print
117/253
Kombinasi
Contoh 2:Ada berapa cara untuk memilih 5 pemain dari10 orang pemain tenis untuk mengikuti
lomba?Jawab:
n = 10 r = 5
C(10,5) = 10!/5!5! = 252Ada 252 cara untuk memilih 5 pemain
117
Kombinasi
-
8/4/2019 Matematika Diskrit Siap Print
118/253
Kombinasi
Contoh 3:Ada berapa banyak cara untuk membentuk suatu kelompokbelajar Mat Diskrit jika anggota kelompok tsb terdiri dari 3mhs jur TF dan 4 mhs jur SI, jika ada 9 mhs TF dan 11 mhs SI?
Jawab:
Langkah 1: Memilih 3 mhs TF dari 9 C(9,3)Langkah 2: Memilih 4 mhs SI dari 11C(11,4)
118
caraTotal
xTotal
CxCTotal
LangkahxLangkahTotal
720.27
!7!4
!11
!6!3
!9
)4,11()3,9(
21
Generalisasi Kombinasi
-
8/4/2019 Matematika Diskrit Siap Print
119/253
Generalisasi Kombinasi
Merupakan perluasan dari kombinasi ygmembolehkan pengulangan suatu unsur.
Teorema: Jika X merupakan sebuah himpunan
yg mempunyai tjenis unsur dimanapengulangan dibolehkan, maka banyaknya
seleksi kunsur tak berurut dari X adalah:
C(k+t-1, t-1) = C(k+t-1, k)
119
Generalisasi Kombinasi
-
8/4/2019 Matematika Diskrit Siap Print
120/253
Generalisasi Kombinasi
Contoh 1:
Ada berapa cara untuk memilih 4 kelereng dari
sebuah kantong yg berisi sedikitnya 4 kelereng
dari 3 jenis warna merah, biru, dan kuning?Jawab:
jenis warna kelereng: t = 3
banyaknya kelereng yg dipilih: k = 4Banyaknya cara: C(4+3-1, 4-1) = C(6,3) = 20
120
Generalisasi Kombinasi
-
8/4/2019 Matematika Diskrit Siap Print
121/253
Generalisasi Kombinasi
Contoh 2:Sebuah toko kue memiliki 4 jenis kue ygberbeda. Ada berapa cara kita bisa megambil
6 buah kue?Jawab:
Jenis kue: t = 4
Banyaknya kue yg diambil: k = 6Banyaknya cara = C(6+4-1, 4-1) = 84
121
Pigeonhole
-
8/4/2019 Matematika Diskrit Siap Print
122/253
Pigeonhole
Prinsip Pigeonhole: Jika ada m ekor merpatidan n buah sarang, dan m > n, maka
setidaknya ada sarang yang berisi lebih dari 1
merpati Secara umum:
Jika ada k+1 atau lebih objek yang diletakkan
dalam kkotak, maka setidaknya ada 1 kotakyang berisi 2 atau lebih objek
122
Prinsip Pigeonhole
-
8/4/2019 Matematika Diskrit Siap Print
123/253
p g
Dari 8 orang, setidaknya ada 2 orang yangmemiliki hari lahir yg sama
Dari 13 orang, setidaknya ada 2 orang yg
memiliki bulan lahir yg sama Dari 367 orang, setidaknya ada 2 orang yg
lahir pada tgl & bulan yg sama
123
Prinsip Pigeonhole Umum
-
8/4/2019 Matematika Diskrit Siap Print
124/253
p g
Jika N objek ditempatkan pada k kotak, makaada setidaknya 1 kotak yang berisi setidaknya
objek
Contoh 1:Dari 100 orang, setidaknya ada
yang lahir di bulan yang sama
124
kN/
912/100
Prinsip Pigeonhole Umum
-
8/4/2019 Matematika Diskrit Siap Print
125/253
p g
Contoh 2:Berapa jumlah mhs dlm kelas Mat Diskrit ygdibutuhkan untuk memastikan bahwa setidaknya 6mhs mendapat nilai yg sama, jika ada 5 kemungkinan
nilai yaitu A, B, C, D, dan E?Jawab:
k = 5 y = 6
N = 26, dibutuhkan 26 mhs agar adaminimal 6 mhs dengan nilai yang sama
125
ykN /
Prinsip Pigeonhole Umum
-
8/4/2019 Matematika Diskrit Siap Print
126/253
p g
Contoh 3:Tunjukkan bahwa jika 30 kamus dalam sebuahperpustakaan memiliki total jumlah halaman 61.327,maka salah satu kamus paling tidak memiliki 2045halaman.
Jawab:
pigeon: halaman N = 61.327
pigeonhole: kamus k = 30
Maka sebuah kamus setidaknya memilikiatau 2045 halaman
126
30/327.61
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
127/253
1. Dalam sebuah kartu bridge lengkap, berapa macamcara untuk mengambil :
a. sebuah jantung atau sebuah daun
b. sebuah jantung atau kartu AS
c. sebuah AS atau sebuah king
d. sebuah kartu bernomor 2 hingga 10
2. Misalkan 2 buah dadu yang berbeda warna (merah
dan putih). Ada berapa macam cara untukmendapatkan jumlah angka 4 atau 8 ?
127
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
128/253
3. Jika dua dadu yang berbeda dilontarkan, adaberapa banyak kemungkinan angka yangmuncul? Bagaimana jika 5 dadu ? Bagaimanajika n dadu ?
4. Berapa banyak bilangan yang terdiri dari 2atau 3 digit yang dapat dibentuk denganmenggunakan angka-angka 1, 3, 4, 5, 6, 8 dan
9, jika perulangan tidak dibolehkan.
128
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
129/253
5. Suatu perusahaan mempunyai 5 orang karyawanlaki-laki dan 7 karyawan perempuan. Pimpinan
perusahaan akan memilih 5 orang diantaranya untuk
bersama-sama mengerjakan suatu proyek. Berapa
banyak tim yang dapat ia bentuk apabila di dalamtim tersebut harus terdiri dari:
a. 3 laki-laki dan 2 perempuan
b. paling sedikit ada 1 karyawan laki-lakic. paling banyak ada 1 karyawan laki-laki
129
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
130/253
6. Sebuah grup terdiri dari 7 wanita dan 3 pria.Ada berapa macam cara berbaris yang
mungkin dilakukan jika ketiga pria tersebut
harus berdiri bersebelahan satu dengan yanglain.
7. Berapa macam penyusunan berbeda yang
dapat dilakukan pada huruf a,a,b,c?
130
-
8/4/2019 Matematika Diskrit Siap Print
131/253
I. HIMPUNAN
131
HIMPUNAN (SETS)
-
8/4/2019 Matematika Diskrit Siap Print
132/253
( )
Himpunan: Sekumpulan obyek yangdisebut elemen/anggota himpunan
Cara pendefinisian himpunan: { }
Contoh: Himpunan mhs TF UPNV: A={Ani, Budi, Citra}
Himp. Bil asli < 5: B = {1, 2, 3, 4}
C = {x|x adalah integer positif atau nol}
C= {0, 1, 2, 3, }
132
NOTASI HIMPUNAN
-
8/4/2019 Matematika Diskrit Siap Print
133/253
anggota himpunanContoh: Ani A, 2 B
himpunan bagian
Contoh: D = {Budi, Citra}; D A { } atau himpunan kosong
Ingat!!:
133
2}2{}{
AAdanA
Operasi pada Himpunan
-
8/4/2019 Matematika Diskrit Siap Print
134/253
UNION (U)Diketahui himpunan :
A={a, b};
B={d, e};
A U B = {a, b, d, e}
BA
BxAxSxBA |
134
Operasi pada Himpunan (2)
-
8/4/2019 Matematika Diskrit Siap Print
135/253
INTERSECTION ()Diketahui himpunan :
A={a, b, c};
B={b, g, i}
A B = {b}
BA
BxAxSxBA |
135
Operasi pada Himpunan (3)
-
8/4/2019 Matematika Diskrit Siap Print
136/253
SELISIH(-)Diketahui himpunan :
A={a, b, c};
B={b, c, d, e}
A-B={a}B-A={d, e}
BA
}|{ BxAxSxBA
136
Operasi pada Himpunan (4)
-
8/4/2019 Matematika Diskrit Siap Print
137/253
SYMMETRIC DIFFERENCE ( )
Diketahui himpunan :
A={a, b, c, d};B={a, c, e, f, g}
A B={b, d, e, f, g}
BA
137
Operasi pada Himpunan (5)
-
8/4/2019 Matematika Diskrit Siap Print
138/253
}|{ AxSxAc
138
KOMPLEMEN
Diketahui himpunan :
S={a, b, c, d, e, f, g};
A={a, c, e, g}
Ac={b, d, f}
A
S
Properti Aljabar (Teorema 1)
-
8/4/2019 Matematika Diskrit Siap Print
139/253
Komutatif1. A U B = B U A
2. A B = B A
Asosiatif
3. A U (B U C) = (A U B) U C
4. A (B C) = (A B) C
139
Properti Aljabar (2)
-
8/4/2019 Matematika Diskrit Siap Print
140/253
Distributif5. A (B U C) = (A B) U (A C)
6. A U (B C) = (A U B) (A U C)
Idempotent
7. A U A = A
8. A A = A
140
Properti Aljabar (3)
-
8/4/2019 Matematika Diskrit Siap Print
141/253
Komplemen - Universal Set
16. A U S = S
17. A S = A
- Empty Set
18. A U = A
19. A =
BABA
BABA
S
S
AA
SAA
AA
.15
.14
.13
.12
.11
)(.10
)(.9
141
Himpunan Kuasa (Power Set)
-
8/4/2019 Matematika Diskrit Siap Print
142/253
Misal A adalah sembarang himpunan. Power Set dariA (P(A)) adalah himpunan yang anggota2nya adalahsemua himpunan bagian dari A. Jika A memiliki nanggota, maka P(A) memiliki 2n anggota.
Contoh:A = {x, y}. Carilah P(A)
Himp2. bagian A adalah , {x}, {y}, {x, y}
Maka P(A) = {, {x}, {y}, {x, y}}
142
Prinsip Inklusi dan Eksklusi
-
8/4/2019 Matematika Diskrit Siap Print
143/253
Misal A adalah sebuah himpunan.|A| = Jumlah elemen pada himpunan A
Teorema 2: |A U B| = |A| + |B| - |A B|
Teorema 3:
|AUBUC| = |A| + |B| + |C| - |AB| -
|AC| - |BC| + |ABC|
143
Contoh
Prinsip Inklusi dan Eksklusi
-
8/4/2019 Matematika Diskrit Siap Print
144/253
Prinsip Inklusi dan Eksklusi
1. A computer company wants to hire 25programmers to handle desktop applicationprogramming jobs and 40 programmers forweb application programming. Of those hired,
10 will be expected to perform jobs of bothtypes. How many programmers must behired?
144
Contoh
Prinsip Inklusi dan Eksklusi (2)
-
8/4/2019 Matematika Diskrit Siap Print
145/253
Prinsip Inklusi dan Eksklusi (2)
Jawab: Mis. A = himp. desktop programmer |A| = 25
B = himp. web programmer
|B| = 40
|A B| = 10
Maka jumlah programmer yang harus
dipekerjakan: |AUB|=25+40-10 = 55
145
Contoh
Prinsip Inklusi dan Eksklusi (3)
-
8/4/2019 Matematika Diskrit Siap Print
146/253
Prinsip Inklusi dan Eksklusi (3)
2. Pada Jur. TF, didapat informasi tentang jumlah mahasiswayang mengambil mata kuliah sebagai berikut:
260 mahasiswa mengambil MK Statistik, 208 mengambilMK Kalkulus II, dan 160 mengambil MK Grafika. 76 mhsmengambil Statistik dan Kalkulus II; 48 mhs mengambil
Statistik dan Grafika, 62 mengambil Kalkulus II dan Grafika.Ada 30 mhs yg mengambil ketiga MK tsb dan jumlah
seluruh mahasiswa 622.
a. Berapa mhs yg tidak mengambil ketiga MK tsb?
b. Berapa mhs yg mengambil Statistik dan Kalkulus II,tetapi tidak mengambila Grafika?
146
Jawab :
-
8/4/2019 Matematika Diskrit Siap Print
147/253
463076
CBABACBAb.
150472622CBA
CBA472622
CBA30624876160208260622
CBA|CBA||CB|-|CA|-|BA|-|C||B||A|S
CBACBASa.
622||30,|CBA|62,|CB|48,|CA|76,|BA|
160|C|Grafika,MKmhshimpC
208|B|II,KalkulusMKmhshimpB
260|A|Statistik,MKmhshimpA
S
147
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
148/253
1. Nyatakan himpunan di bawah ini dalam notasi himpunana. A=himp bil bulat antara 1 dan 5
b. B=himp yg anggotanya kucing, meja, buku, air
c. himp bil riil yang lebih besar 1
2. Tentukan apakah pernyataan berikut benar?
1,2,32d.1,2,31,2,3g.1,2,32c.2,12f.1,2,32b.
2,12e.1,2,32a.
148
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
149/253
3. Misalkan diantara 400 tamu-tamu yang datang, 200diantaranya bisa berbahasa Perancis dan 50 orang dapat
berbahasa Belanda. Tamu yang bisa berbicara dalam kedua
bahasa tersebut hanya 20 orang. Berapa banyak tamu yang
tidak bisa berbicara dalam kedua bahasa tersebut?
149
-
8/4/2019 Matematika Diskrit Siap Print
150/253
V. RELASI DAN FUNGSI
150
Hasil Kali Kartesian
-
8/4/2019 Matematika Diskrit Siap Print
151/253
Adalah himpunan semua pasangan berurutan (a,b) dengan
Simbol : A x B
Contoh :
Misalkan himpunan A={a,b,c}; B={,,}; C={1,2,3}.Hitunglah A x B dan (A x B) x C !
Penyelesaian :
A x B = {(a,),(a,),(a, ),(b, ),(b, ),(b, ),(c, ),(c, ),(c, )}
(A x B) x C = {((a,),1),((a,),1),((a, ),1),((b, ),1),((b, ),1),((b, ),1),((c, ),1),((c, ),1),((c, ),1), ((a,),2),((a,),2),((a, ),2),((b, ),2),((b, ),2),((b, ),2),((c, ),2),((c, ),2),((c, ),2), ((a,),3),((a,),3),((a, ),3),((b, ),3),((b, ),3),((b, ),3),((c, ),3),((c, ),3),((c, ),3)}
BbdanAa
BbA,aba,BxA
151
Relasi
-
8/4/2019 Matematika Diskrit Siap Print
152/253
Hubungan antara anggota-anggota himpunan direpresentasikandengan menggunakan struktur yang disebut relasi.
Untuk mendeskripsikan relasi antara anggota-anggota dua himpunan Adan B, dapat digunakan pasangan terurut dengan anggotapertamanya diambil dari A dan anggota keduanya diambil dari B.
Karena ini merupakan relasi antara dua himpunan, maka disebutrelasi biner.
Definisi.
Misalkan A dan B himpunan.
Suatu relasi binerdari A ke B adalah subhimpunan (subset) dari AB.
Untuk relasi biner R berlaku R AB.
Digunakan notasi aRb untuk menyatakan (a,b)R dan aRb untukmenyatakan (a,b)R.
Jika (a, b) merupakan anggota R, a dikatakan berelasi dengan b olehR.
152
Contoh 1
-
8/4/2019 Matematika Diskrit Siap Print
153/253
Misalkan O himpunan orang,
A himpunan angkutan kota, danN relasi yang mendeskripsikan siapa yangmenaiki angkot tertentu.
O = {Aang, Bida, Charlie, Dina},
A = {Cicaheum-Ledeng (CL), Kelapa-Dago (KD), Stasiun-
Sadang Serang (SS)}N = {(Aang, CL), (Bida, CL), (Bida, KD), (Charlie, SS)}
Artinya Aang naik Cicaheum-Ledeng,
Bida naik Cicaheum-Ledeng dan Kelapa-Dago,Charlie naik Stasiun-Sadang Serang, dan
Dina tidak menaiki salah satu dari angkot tersebut.
153
Relasi pada Himpunan
-
8/4/2019 Matematika Diskrit Siap Print
154/253
Definisi.
Suatu relasipada himpunan A adalah relasi dari A ke A.
Relasi pada himpunan A adalah subhimpunan (subset)
dari AA.
Contoh 2.
Misalkan A = {1, 2, 3, 4}.
Himpunan terurut manakah yang terdapat dalam relasi
R = {(a, b) | a < b} ?
Solusi.
R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
154
Matriks Relasi
-
8/4/2019 Matematika Diskrit Siap Print
155/253
Disebut juga matriks nol-satu
Jika ,
masing-masing terdiri dari m dan n elemen, dan R
adalah relasi dari A ke B, maka R dapat ditulis dalam
matriks mxn dimana :
n21m21 b,,b,bBdana,,a,aA
][M ijR m
155
Rbajika
Rbajika
m ji
ji
ij ),(,0
),(,1
Contoh 1
-
8/4/2019 Matematika Diskrit Siap Print
156/253
156
R 1 2 3 4
1
2
3
4
1 1
2
3
4
2
3
4
1 1 1
1 1
1
R = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}
-
8/4/2019 Matematika Diskrit Siap Print
157/253
Contoh 3
-
8/4/2019 Matematika Diskrit Siap Print
158/253
0101
0110
1001
RM 321 ,, aaaA
4321 ,,, bbbbB
331332224111 ,,,,,,,,,,,
sehingga,1jikahanyadanjika,
babababababaR
mRba ijji
158
Misal matriks relasi R :
Karena ordo matriks 3x4, maka
dan
Digraph Relasi
-
8/4/2019 Matematika Diskrit Siap Print
159/253
Digraph (directed graph), terdiri dari vertex dan edge.
Vertex melambangkan elemen pada himpunan Edge melambangkan relasi antara elemen yang satu dengan yang
lainnya
Contoh : Misal,
maka digraph :
1,4,4,3,4,2,3,2,2,2,1,2,2,1,1,14,3,2,1
R
A
159
1
2
3
4
Sifat Relasi - Refleksif
-
8/4/2019 Matematika Diskrit Siap Print
160/253
Definisi.
Relasi R pada himpunan A disebut refleksifjika(a,a)R untuk setiap anggota aA.
Apakah relasi berikut pada {1, 2, 3, 4} refleksif?
160
R = {(1, 1), (1, 2), (2, 3), (3, 3), (4, 4)} Tidak.
R = {(1, 1), (2, 2), (2, 3), (3, 3), (4, 4)} Ya.
R = {(1, 1), (2, 2), (3, 3)} Tidak.
Sifat Relasi - Simetris & Antisimetris
Definisi.
-
8/4/2019 Matematika Diskrit Siap Print
161/253
Apakah relasi berikut pada {1, 2, 3, 4} simetris atauantisimetris?
161
R = {(1, 1), (1, 2), (2, 1), (3, 3), (4, 4)} simetris
R = {(1, 1)} simetris &
antisimetris
R = {(1, 3), (3, 2), (2, 1)} antisimetris
R = {(4, 4), (3, 3), (1, 4)} antisimetris
Definisi.
Relasi R pada himpunan A disebut simetris jika (b,a)Rsetiap kali (a,b)R untuk setiap a,bA.
Relasi R pada himpunan A disebut antisimetris jika(a,b)R dan tidak ada (b,a)R, kecuali a = b.
Sifat Relasi - Transitif
-
8/4/2019 Matematika Diskrit Siap Print
162/253
Definisi.
Relasi R pada himpunan A disebut transitifjika setiap kali(a,b)R dan (b,c)R, maka (a,c)R untuk a,b,cA.
Apakah relasi berikut pada {1, 2, 3, 4} transitif?
162
R = {(1, 1), (1, 2), (2, 2), (2, 1), (3, 3)} Ya.
R = {(1, 3), (3, 2), (2, 1)} Tidak.
R = {(2, 4), (4, 3), (2, 3), (4, 1)} Tidak.
Sifat Matriks Representasi RelasiMatriks yang merepresentasikan relasi refleksif ?
-
8/4/2019 Matematika Diskrit Siap Print
163/253
Matriks yang merepresentasikan relasi refleksif ?
Setiap elemen diagonal dari matriks Mrefharuslah 1.
163
1
.
.
.
1
1
refM
Matriks yang merepresentasikan relasi simetris?
Matriksnya juga simetri, yaitu MR = (MR)t.
1101
10010010
1101
RM
matriks simetri,
relasi simetris.
0011
00110011
0011
RM
matriks tak-simetri,
relasi tak-simetris.
Komposisi RelasiD fi i i
-
8/4/2019 Matematika Diskrit Siap Print
164/253
Definisi.
Misalkan R relasi dari A ke B dan S relasi dari Bke C. Komposisi dari R dan S adalah relasi yangmemuat himpunan terurut (a,c), dengan aA,cC, di mana terdapat anggota bB sehingga(a,b)R dan (b,c)S. Komposisi dari R dan Sdinotasikan oleh SR.Jika relasi R memuat pasangan (a, b) dan relasi
S memuat pasangan (b,c), maka SR memuatpasangan (a,c).
164
Contoh 4
Contoh
-
8/4/2019 Matematika Diskrit Siap Print
165/253
Contoh.
Misalkan D dan S relasi pada A = {1, 2, 3, 4}.D = {(a, b) | b = 5 - a} b sama dengan (5 a)
S = {(a, b) | a < b} a lebih kecil dari b
D = {(1, 4), (2, 3), (3, 2), (4, 1)}
S = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}
SD = {(2, 4), (3, 3), (3, 4), (4, 2), (4, 3), (4, 4)}
165
D memetakan suatu anggota a ke anggota (5 a), dan setelah
itu S memetakan (5 a) pada semua anggota yang lebih besardari (5 a), yang menghasilkan
SD = {(a,b) | b > 5 a} atau SD = {(a,b) | a + b > 5}.
Kuasa dari Relasi
-
8/4/2019 Matematika Diskrit Siap Print
166/253
Definisi.
Misalkan R relasi pada himpunan A.
Kuasa Rn, n = 1, 2, 3, , didefinisikan secara induktif
R1 = R
Rn+1 = RnR
Dengan kata lain:
Rn = RR R (sebanyak n kali)
Teorema.Relasi R pada A transitif jika dan hanya jika Rn R untuk setiapbilangan bulat positif n.
166
Contoh
-
8/4/2019 Matematika Diskrit Siap Print
167/253
Misalkan A={a,b,c,d} dan R={(a,b),(b,c),(c,d)}.
Maka kuasa dari R :
R2= R o R = {(a,c),(b,d)}
R3= R2 o R ={(a,d)}
R4= R3 o R = { }
NB TF-E : Adi (IK), Teguh, Bagus, Prasetyo Adhi
167
Irisan dan Gabungan
-
8/4/2019 Matematika Diskrit Siap Print
168/253
Hakikatnya relasi merupakan himpunan.
Contoh :
Misal A={-1,0,1} dan B{0,1}. Relasi R dan S:
Maka,
{(-1,1)}SR
(1,1)}(0,0),(0,1),(-1,1),{(-1,0),SR
(-1,1)}(1,1),{(0,0),S
(0,1)}(-1,1),{(-1,0),R
168
Misalkan relasi R dan S direpresentasikan
-
8/4/2019 Matematika Diskrit Siap Print
169/253
Misalkan relasi R dan S direpresentasikan
oleh matriks
169
011
111
101
SRSR MMM
001
110
101
SM
Apakah matriks yang merepresentasikan RS andRS?Solusi: Matriks-matriks tersebut adalah
000
000
101
SRSR MMM
010
001
101
RM
Transitif Closure
-
8/4/2019 Matematika Diskrit Siap Print
170/253
Merupakan relasi yang diperoleh dengan caramenambahkan anggota agar suatu relasi yang tidaktransitif menjadi transitif.
1. Menggunakan kuasa relasiR+ = R u R2 u R3 u
2. Algoritma Warshall
170
Contoh
Misalkan A={a b c d} dan R={(a b) (b c) (c d)}
-
8/4/2019 Matematika Diskrit Siap Print
171/253
Misalkan A={a,b,c,d} dan R={(a,b),(b,c),(c,d)}
Maka kuasa dari R :R2= R o R = {(a,c),(b,d)}
R3= R2 o R ={(a,d)}
R4= R3 o R = { }
R+ = R u R2 u R3 u R4
= {(a,b),(b,c),(c,d)} u {(a,c),(b,d)} u {(a,d)} u { }= {(a,b),(a,c),(a,d),(b,d),(b,c),(c,d)}
171
Algoritma Warshall
-
8/4/2019 Matematika Diskrit Siap Print
172/253
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
172
Baris-1 (k) : {b}Kolom-1 (b) : {}A(b,k)={}
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
Baris-2 (k) : {c}Kolom-2 (b) : {a}A(b,k)={(a,c)}
0 1 1 0
0 0 1 0
0 0 0 1
0 0 0 0
0 1 1 1
0 0 1 1
0 0 0 1
0 0 0 0
Baris-3 (k) : {d}
Kolom-3 (b) : {a,b}A(b,k)={(a,d),(b,d)}
Baris-4 (k) : {}
Kolom-4 (b) : {a,b,c}A(b,k)={}
R = {(a,b),(a,c),(a,d),(b,c),(b,d),(c,d)}
Fungsi
-
8/4/2019 Matematika Diskrit Siap Print
173/253
Jika suatu relasi menghubungkan suatu himpunan Ake himpunan B dimana tiap anggota A memiliki
TEPAT satu relasi dengan sembarang anggota B.
Fungsi dari A ke B ditulis
BbdanAauntukbaf ,)(
173
A B A B A B
Contoh fungsi :
-
8/4/2019 Matematika Diskrit Siap Print
174/253
174
A B A B
Contoh relasi yang bukan fungsi :
A disebut DOMAIN, dan B disebut KODOMAIN. Elemen-elemen B yangberelasi dengan elemen A disebut RANGE (himpunan penyelesaian)
Jenis fungsi - Injective
-
8/4/2019 Matematika Diskrit Siap Print
175/253
INJECTIVE (one to one function)
Jika tiap anggota dari domain memiliki range yang
UNIK satu sama lain.
Contoh injective : Contoh bukan injective :
175
A B A B
Jenis fungsi - Surjective
-
8/4/2019 Matematika Diskrit Siap Print
176/253
SURJECTIVE (Onto function)jika kodomain = range
Contoh onto : Contoh bukan onto :
176
A BA B
Jenis fungsi - Bijection
-
8/4/2019 Matematika Diskrit Siap Print
177/253
BIJECTION (one to one correspondence)
jika mempunyai sifat one to one dan onto
Contoh :
177
A B
-
8/4/2019 Matematika Diskrit Siap Print
178/253
VI. RELASI REKURENSI
178
-
8/4/2019 Matematika Diskrit Siap Print
179/253
INGAT !!!
KONSEP REKURSIF
179
Konsep
-
8/4/2019 Matematika Diskrit Siap Print
180/253
Suatu barisan yang didefinisikan secara rekursif jika kondisi
awal barisan ditentukan, dan suku-suku barisan selanjutnya
dinyatakan dalam hubungan dengan sejumlah suku-suku
sebelumnya.
Contoh :
Barisan 3, 5, 7, 9, dapat dinyatakan sbb :
)(2
)(3
1
0
rensirelasirekuaa
lkondisiawaa
kk
180
Contoh 1
-
8/4/2019 Matematika Diskrit Siap Print
181/253
Suatu barisan co, c1, c2, didefiniskan secara rekursif.
Untuk semua bilangan
dengan kondisi awal c0=1 dan c1=2. Hitunglah c5 ?
Solusi
,2k1. 21 kkk ckcc
18194112.5331.5
3315.4121.4
1212.351.3
511.221.2
345
234
123
012
ccc
ccc
ccc
ccc
Contoh 2Menara Hanoi
A B CA B
-
8/4/2019 Matematika Diskrit Siap Print
182/253
Cara memindahkan k cakram dari tiang A ke C adalah sbb :1. pindahkan (k-1) cakram dari tiang A ke B
2. pindahkan cakram paling bawah dari tiang A ke C
3. pindahkan (k-1) cakram dari tiang B ke C
Misalkan mn adalah jumlah minimal untuk memindahkan n cakram dari satu tiang
ke tiang yang lain. Langkah 1 memerlukan mk-1 perpindahan, langkah 2
memerlukan 1 perpindahan, dan langkah 3 memerlukan mk-1 perpindahan. Jadi
jumlah keseluruhan perpindahan minimal :
mk=mk-1+1+mk-1=2mk-1+1Sehingga didapatkan persamaan rekursif :
m1=1 (kondisi awal)
mk=2mk-1+1 (relasi rekurensi)
182
A B C
m1=1 (kondisi awal)
mk=2mk-1+1 (relasi rekurensi)
-
8/4/2019 Matematika Diskrit Siap Print
183/253
Maka untuk memindahkan :
- 2 cakram, dibutuhkan m2=2m1+1=2.1+1= 3
- 3 cakram, dibutuhkan m3=2m2+1=2.3+1=7- 4 cakram, dibutuhkan m4=2m3+1=2.7+1=15
183A B CA
Penyelesaian relasi rekurensi
-
8/4/2019 Matematika Diskrit Siap Print
184/253
Perhitungan dengan rekursif sangat memakanwaktu.
Waktu running yang dibutuhkan akan jauhlebih lama dibandingkan dengan program
non-rekursif.
Menyelesaikan relasi rekurensi, ada 2 :
Cara iterasi
Melalui persamaan karakteristik
184
Metode 1 - Cara Iterasi
-
8/4/2019 Matematika Diskrit Siap Print
185/253
Prinsip : hitung suku-suku barisan secaraberurutan terus menerus hingga diperoleh
pola tertentu sebagai dasar pembuatan
rumus eksplisit.
185
Pola Deret (barisan)
-
8/4/2019 Matematika Diskrit Siap Print
186/253
)(1,1
1.. .1
3
)2)(1()1(...4.33.22.1
6)12)(1(...32
2
)1(...321
12
2222
geometrideretruntukr
rrrr
nnnnn
nnnna
nnn
nn
186
U-Ubdimana1)b,(naU
AritmatikaDeret
1
-
8/4/2019 Matematika Diskrit Siap Print
187/253
1r;r)-(1
)r-a(1Sn
1r;
1)-(r
1)-a(rSn
UUrdimana,arU
GeometriDeret
)U(a2
nS
UUbdimana1)b,(naU
n
n
1
n1-nn
nn
n1-nn
n
187
Contoh 1
-
8/4/2019 Matematika Diskrit Siap Print
188/253
Carilah rumus eksplisit, untuk semua bilangan bulat k1,
Penyelesaian
Berdasarkan pola yang ada, diperoleh rumus eksplisit :
)(2
)(1
1
0
rekurensirelasiaa
awalkondisia
kk
kkaa
aaaaaa
aaaaa
aaaaaa
k 212.
2.4222)2(22)2(2)2(2
2.322)2(2)2(2
2.22)2(22
0
001234
00123
0012
01
188
Contoh 2
Carilah rumus eksplisit yang menyatakan masalah Hanoi.
-
8/4/2019 Matematika Diskrit Siap Print
189/253
p y g y
Penyelesaian.
mk merupakan deret geometri dengan r=2 sehinggadiperoleh rumus eksplisit :
1
212
1
1
m
kbulatbilanganuntukmmkk
1222...222
12221)1)12(2(21)12(2121221)12(212
1211.212
123321
123
1234
12
123
1
12
kkkkm
mmmmmmm
mm
189
1212
12 1)1(
k
k
km
Metode 2 Persamaan Karakteristik
-
8/4/2019 Matematika Diskrit Siap Print
190/253
Sebuah relasi rekurensi linier berkoefisienkonstan, secara umum ditulis sebagai berikut
C0 an + C1 an-1 + C2 an-2+ + Ck an-k = f(n)
dimana Ci, untuk i = 0,1,2,,k adalah
konstanta dan f(n) adalah sebuah fungsinumerik dengan variabel n.
Relasi rekurensi tersebut dikatakan relasi
rekurensi linier berderajat k , jika C0 dan Ckkeduanya tidak bernilai 0 (nol).
190
Contoh :
-
8/4/2019 Matematika Diskrit Siap Print
191/253
2 an + 2 an-1 = 3n
adalah sebuah relasi rekurensi linier berderajat 1
tn = 7 tn-1
adalah sebuah relasi rekurensi linier berderajat 1
an an-1 an-2 = 0
adalah sebuah relasi rekurensi linier berderajat 2
bn-3 3bn = n+3adalah sebuah relasi rekurensi linier berderajat 3
191
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
192/253
Tentukan apakah persamaan di bawah inimerupakan relasi linier dengan koefisien konstan
an 7an-1 + 10an-2 = 0 YA
bk = bk-1 + bk-2 + bk-3 YA
ck = 2ck-2 YA dk = d
2k-1 + dk-2 BUKAN
ek = ek-1.ek-2 BUKAN f
k 2f
k-1+ 1 = 0 YA
hk = -hk-1 +(k-1)hk-2 YA
192
Relasi rekurensi linier homogen dengan
koefisien konstan
-
8/4/2019 Matematika Diskrit Siap Print
193/253
Sebuah relasi rekurensi linier berkoefisien konstandapat dinyatakan dalam bentuk
C0 an + C1 an-1+ + Ck an-k = f(n).
Bila nilai f(n) = 0, maka diperoleh relasi rekurensi
yang memenuhiC0 an + C1 an-1 + C2 an-2+ + Ck an-k = 0.
Relasi rekurensi demikian disebut dengan relasirekurensi homogen dan solusi dari relasi rekurensi
homogen ini dinamakan solusi homogen atau jawabhomogen.
193
Misalkan suatu relasi rekurensi homogen linier dengan koefisienkonstan :
C0an + C1an-1 + C2an-2+ + Ckan-k = 0 dengan ck0 dan nk
Persamaan karakteristik :
tk tk 1 0
-
8/4/2019 Matematika Diskrit Siap Print
194/253
tk + c1tk-1+ + ck =0
Misalkan 1, 2, , k adalah akar-akar persamaan karakteristik. Ada 2kemungkinan akar :
1. Semua akar berbeda
an = c11n + c22
n+ + ckkn
dengan c1, c2, , ck adalah konstanta yang nilainya ditentukan
berdasarkan kondisi awal.
2. Ada akar kembar
1=2=p, p+1, , kMaka penyelesaiannya :
an = (c1 + c2n + + cpnp-1) 1n + cp+1p+1n, + + ckkndengan c1, c2, , ck adalah konstanta yang nilainya ditentukanberdasarkan kondisi awal
194
Contoh
-
8/4/2019 Matematika Diskrit Siap Print
195/253
1. an = 3an-1 + 4an-2untuk n2 dengan kondisiawal a0=1 dan a1=3
2. an 3an-1 + 3an-2 an-3= 0 untuk n3 dengankondisi awal a0=1, a1=2, a2=4
3. an 7an-1 + 16an-2 12an-3= 0 untuk n3dengan kondisi awal a0=1, a1=4, a2=8
195
an = 3an-1 + 4an-2untuk n2 dengan kondisi
awal a0=1 dan a1=3
R l i 3 4 0 k l i k i h li i d
-
8/4/2019 Matematika Diskrit Siap Print
196/253
Relasi an - 3an-1 - 4an-2 = 0 merupakan relasi rekurensi homogen linier dengan
koefisien konstan c1=-3, c2=-4, derajat k=2. Persamaan karakteristik yang sesuaiadalah
t2 3t 4 = 0
(t-4)(t+1) = 0
akar-akar pers. karakteristik 1=4, 2=-1. Karena semua akar berbeda, makapenyelesaiannya :
an = c11n + c22n= c14n + c2(-1)n
a0 =1 sehingga 1 = c140 + c2(-1)
0
1 = c1 + c2a1 =3 sehingga 3 = c14
1 + c2(-1)1
3 = 4c1 - c2
Dari 2 persamaan tersebut dapat diperoleh c1=4
/5 dan c2=1
/5.Maka penyelesaian relasi rekurensi an - 3an-1 - 4an-2 = 0 adalah
an =4/5 (4)
n + 1/5 (-1)n
196
an 3an-1 + 3an-2 an-3= 0 untuk n3
dengan kondisi awal a0=1, a1=2, a2=4
R l i 3 3 0 k l i k i h li i
-
8/4/2019 Matematika Diskrit Siap Print
197/253
Relasi an - 3an-1 + 3an-2 an-3 = 0 merupakan relasi rekurensi homogen linier
dengan koefisien konstan c1=-3, c2=3, c3=-1, derajat k=3. Persamaankarakteristik yang sesuai adalah
t3 - 3t2 + 3t 1 = 0
(t -1)3 = 0
akar-akar pers. karakteristik 1=2=3=1. Karena semua akar sama, makapenyelesaiannya :
an = (c1 + c2n + + cpnp-1) 1n =(c1 + c2n + c3n2).1n = c1 + c2n + c3n2a0 =1 sehingga 1 = c1 + c2.0 + c3.0
2
1 = c1
a1 =2 sehingga 2 = c1 + c2.1 + c3.12
2 = c1 + c2 + c3
a2 =4 sehingga 4 = c1 + c2.2 + c3.224 = c1 + 2c2 + 4c3
Dari 3 persamaan tersebut dapat diperoleh c1=1, c2=1/2 dan c3=
1/2
Maka penyelesaian relasi rekurensi an - 3an-1 + 3an-2 an-3 = 0 adalah
an = 1 +1/2n +
1/2n2 197
Penyelesain relasi rekurensi linier
tidak-homogen (penyelesaian total)
-
8/4/2019 Matematika Diskrit Siap Print
198/253
penyelesaian homogen+
penyelesaian khusus
Untuk f(n) 0
Kesulitan : tidak ada metode yang pasti sehingga
menggunakan perkiraan bentuk umumnya(undetermined coeeficients)
198
Beberapa pola perkiran untuk fungsi f(n)f(n)
(D,a :
konstan)Sifat pers. karakteristik c(t)
Bentuk penyelesaian
khusus
-
8/4/2019 Matematika Diskrit Siap Print
199/253
konstan)
Dan a bukan akar pers.karakteristik c(t) (c(a)0) Pan
Dan a adalah akar pers.karakteristik c(t) kelipatan
m
Pnman
Dnsan a bukan akar pers.karakteristik c(t) (c(a)0) (P0+P1n++Psns)an
Dnsan a adalah akar pers.karakteristik c(t) kelipatanm
(P0+P1n++Psns)nman
Dns 1 bukan akar pers.karakteristik c(t) (c(1)0) P0+P1n++Psns
Dns 1 adalah akar pers.karakteristik c(t) kelipatan
m
(P0+P1n++Psns)nm
199
Contoh 1 : an-7an-1+10an-2=4nuntuk n2
dengan kondisi awal a0=8 dan a1=36
1/ P RRLH 7 + 10 0
-
8/4/2019 Matematika Diskrit Siap Print
200/253
1/ Pers. RRLH : an - 7an-1 + 10an-2 = 0
2/ Pers.karakteristik : t2 - 7t + 10 = (t-5)(t-2) = 0
3/ Akar karakteristik : 1=5, 2=2
4/ Penyelesaian homogen : an = c15n + c22
n
5/ Karena f(n)=4n dan 4 bukan akar karakteristik, maka bentuk
penyelesaian khusus an=P(4)n
. Kemudian substitusikan kerelasi rekurensi mula-mula :
P(4)n 7 (P(4)n-1)+10(P(4)n-2) = 4n
P(4)n-2(42-7.4+10) = 4n
-2 P (4)n-2 = 4n
-2 P = 16P = -8
Sehingga penyelesaian khususnya adalah an = -8(4)n.
200
6/ Penyelesaian total = homogen + khususan = c15
n + c22n - 8(4)n
7/ Substitusi kondisi awal0 0 0
-
8/4/2019 Matematika Diskrit Siap Print
201/253
a0=8 shg 8 = c15
0
+ c22
0
- 8(4)
0
8 = c1+ c2
8
16 = c1+ c2
a1=36 shg 36 = c151 + c22
1 - 8(4)1
36 = 5c1+ 2c2 32
68 = 5c1+ 2c2
Dengan substitusi diperoleh c1=12 dan c2=4.
8/ Rumus eksplisit :an = 12.5
n + 4.2n - 8(4)n
201
Contoh 2 : an-7an-1+10an-2=7.3n+4nuntuk n2
1/ Penyelesaian homogen sama seperti contoh 1 : an = c15n + c22
n
2/ Karena f(n)=7.3n+4n, maka penyelesaian khususnya adalah jumlah dari penyelesaiankhusus relasi :
-
8/4/2019 Matematika Diskrit Siap Print
202/253
khusus relasi :
an-7an-1+10an-2=7.3n
an-7an-1+10an-2=4
n (contoh 1)
Penyelesaian khusus untuk f(n)=4n adalah an = -8(4)n.
Penyelesaian khusus f(n)=7.3n, karena 3 bukan akar karakteristik, maka digunakanbentuk an=P(3)n. Jika disubstitusikan ke relasi mula2 :
P(3)n-7P(3)n-1+10P(3)n-2 = 7.3n
P(3)n-2
(32
-7.3+10) = 7.3n
-2P(3)n-2 = 7.3n
-2P(3)n-2 = 7.3n
-2P = 7.32
P = -63/2Sehingga an= -(
63/2)3n.
Jadi penyelesaian khusus yang sesuai untuk f(n)= 7.3n+4n, adalah :an = -8(4)
n - (63/2)3n
Sehingga penyelesaian totalnya :
an = c15n + c22
n - 8(4)n - (63/2)3n
202
Contoh 3 : an 4an-1 + 4an-2 = 2n untuk n2
1/ Pers RRLH : a 4a + 4a = 0
-
8/4/2019 Matematika Diskrit Siap Print
203/253
1/ Pers. RRLH : an 4an-1 + 4an-2 = 0
2/ Pers.karakteristik : t2 - 4t + 4 = (t-2)(t-2) = 03/ Akar karakteristik : 1=2=2
4/ Penyelesaian homogen : an = (c1+ c2n) 2n
5/ Karena f(n)=2n dan 2 adalah akar karakteristik kelipatan 2 (2 akar kembar),maka bentuk penyelesaian khusus an=Pn
22n. Kemudian substitusikan kerelasi rekurensi mula-mula :
Pn22n 4(P(n-1)22n-1) + 4(P(n-2)22n-2) = 2n
P2n-2(n2.22 - 4(n-1)2.2 + 4(n-2)2) = 2n
P(4n2 - 8(n2-2n+1) + 4(n2-4n+4)) = 22
8P = 4
P = 1/2Sehingga penyelesaian khususnya adalah an = -1/2n22n.
6/ Penyelesaian total :
an = (c1+ c2n) 2n -1/2n
22n
203
Latihan
-
8/4/2019 Matematika Diskrit Siap Print
204/253
Carilah penyelesaian total relasi rekurensiberikut :
an - 5an-1 + 6an-2 = n24nuntuk n2
an
- 2an-1
+ an-2
= 5+3n untuk n2
204
-
8/4/2019 Matematika Diskrit Siap Print
205/253
VII. GRAPH
205
Konsep
-
8/4/2019 Matematika Diskrit Siap Print
206/253
Graph adalah suatu diagram yang memuatinformasi tertentu.
Contoh :
Struktur organisasi, Bagan alir pengambilan mata kuliah,
Peta, dll.
206
Dasar-dasar Graph
Suatu graph terdiri dari 2 himpunan berhingga, yaitu
-
8/4/2019 Matematika Diskrit Siap Print
207/253
g p p gg , y
himpunan titik (V(G)) dan himpunan garis (E(G)). Graf yang tidak mempunyai titik (sehingga tidak
mempunyai garis) disebut graf kosong.
Jika semua garisnya berarah maka disebut graph berarah(directed graph)
Jika semua garisnya tidak berarah disebut graph takberarah (undirected graph)
Setiap garis berhubungan dengan satu atau 2 titik, yangdisebut titik ujung.
Garis yang berhubungan dengan satu titik ujung disebutloop.
207
Dasar-dasar Graph (2)
Dua garis berbeda yang menghubungkan titik ujung yang
-
8/4/2019 Matematika Diskrit Siap Print
208/253
sama disebut garis pararel. Dua titik dikatakan berhubungan (adjacent) jika ada garis
yang menghubungkan keduanya.
Titik yang tidak mempunyai garis yang berhubungan
dengannya disebut titik terasing. Sebuah graf yang tidak mempunyai loop dan tidak
mempunyai rusuk-rusuk yang sejajar disebut graf sederhana.
Jika terdapat sebuah edge e yang menghubungkan verteks v
dan w, kita tulis e = (v,w). Dalam konteks ini, (v,w)menyatakan sebuah edge antara v dan w dalam sebuahgraph.
208
Graph Berarah Sebuah graf terarah atau digraf G terdiri dari
-
8/4/2019 Matematika Diskrit Siap Print
209/253
suatu himpunan V dari verteks dan suatuhimpunan E dari edge sedemikian rupasehingga setiap rusuk e E menghubungkanpasangan verteks terurut.
himpunan verteks-verteks
V = {v1, v2, v3, v4, v5}
dan himpunan rusuk-rusuk
E = {e1, e2, e3, e4, e5, e6}
209
v1 v2 v3
v4 v5
e2 e1
e3
e4
e5
e6
Weighted Graph
-
8/4/2019 Matematika Diskrit Siap Print
210/253
Sebuah graf dengan bilangan-bilangan padaedge-nya disebut graf berbobot(weighted
graph). Dalam sebuah graf berbobot, panjang
lintasan adalah jumlah bobot edge dalam
lintasan.
210
a bc
de
8
4
4
9
62
1253
Derajat Suatu Titik
Derajat titik v adalah jumlah garis yang berhubungan
-
8/4/2019 Matematika Diskrit Siap Print
211/253
Derajat titik v adalah jumlah garis yang berhubungandengan titik v dan garis suatu loop dihitung 2 kali.
Derajat total G adalah jumlah derajat semua titikdalam G
211
v1 v2
v3
v5
v4
v6
e1
e2
e5
e4e3 D(v1)=4 D(v4)=2
D(v2)=2 D(v5)=1
D(v3)=1 D(v6)=0
Derajat total = 4+2+1+2+1+0 = 10
Walk
Misalkan v0 dan vn adalah verteks-verteks dalam
-
8/4/2019 Matematika Diskrit Siap Print
212/253
sebuah graf. Sebuah walk dari v0 ke vn denganpanjang n adalah sebuah barisan berselang-seling dari n+1 verteks dan n edge yang berawaldengan verteks v0 dan berakhir dengan verteks
vn,(v0, e1, v1, e2, , vn-1, en, vn)
dengan ei insiden pada verteks vi-1 dan vi untuk
i = 1,2, , n.
212
Path dan Sirkuit
-
8/4/2019 Matematika Diskrit Siap Print
213/253
Path adalah walk dari v ke w yang semua garisnyaberbeda.
Path sederhana adalah path dari v ke w yang semuatitiknya berbeda.
Sirkuit/cycleadalah path yang dimulai dan diakhiri padatitik yang sama.
Sirkuit sederhana adalah sirkuit yang semua titiknyaberbeda.
213
Contoh
v3 v4e2
e5
e4
-
8/4/2019 Matematika Diskrit Siap Print
214/253
214
v1
v2
v6 v5
e1
e2
e8
e3
e7
e9
e6 e10
a. v1 e1 v2 e3 v3 e4 v3 e5 v4 Path dari v1 ke v4
b. v1 e1 v2 e3 v3 e5 v4 e5 v3 e6 v5 Walk dari v1 ke v5
c. v2 e3 v3 e5 v4 e10 v5 e6 v3 e7 v6 e8 v2 Sirkuit
d. v2 e3 v3 e5 v4 e10 v5 e9 v6 e8 v2 Sirkuit sederhana
Dari graph diatas tentukan barisan titik dan garis berikut apakahWalk, path, path sederhana, sirkuit, sirkuit sederhana.
Graph terhubung dan Tidak Terhubun Dua titik v dan w dalam G dikatakan terhubung bila dan
-
8/4/2019 Matematika Diskrit Siap Print
215/253
hanya bila ada walk dari v ke w. Graf G dikatakan terhubung (connected) bila dan hanya
bila setiap 2 titik terhubung.
Graf G dikatakan tidak terhubung (unconnected) bila
dan hanya bila ada 2 titik yang tidak terhubung.
215
Connected Graph Unconnected graph
Euler Path dan Cycle
Euler path adalah sebuah path pada graph
-
8/4/2019 Matematika Diskrit Siap Print
216/253
Euler path adalah sebuah path pada graph
G yang melewati setiap edge/garis tepat 1
kali dan melewati setiap vertex/titik paling
sedikit sekali.
Euler cycle/sirkuit adalah euler path yang
kembali ke vertex awal.
216
Permasalahan 7 JembatanKonigsberg
A
-
8/4/2019 Matematika Diskrit Siap Print
217/253
Masalah : mungkinkah seseorang berjalan mengelilingi
kota yang dimulai dan diakhiri pada tempat yang sama,
dengan melintasi ketujuh jembatan masing-masing tepat
1 kali ?
Apakah graph tersebut merupakan sirkuit EULER ?
217
B
A
D
C B C
D
Teorema Euler
Jika graph G memiliki vertex berderajat ganjil maka
-
8/4/2019 Matematika Diskrit Siap Print
218/253
Jika graph G memiliki vertex berderajat ganjil, makatidak ada euler cycle dalam G.
Jika G adalah sebuah connected graph dan setiapvertexnya berderajat genap, maka terdapat EULERCYCLE dalam G.
Jika graph G memiliki lebih dari 2 vertex berderajatganjil, maka tidak ada euler path.
Jika G connected graph dan memiliki tepat 2 vertex
berderajat ganjil, maka ada EULER PATH yangberawal di satu vertex berderajat ganjil dan berakhirdi vertex berderajat ganjil lainnya.
218
Contoh
E
-
8/4/2019 Matematika Diskrit Siap Print
219/253
219
A
B C
D Euler path :EDBACD
1
2
3
4
5
Euler cycle :
1345321
Algoritma Fleury
Algoritma untuk mencari EULER CYCLE dalam
-
8/4/2019 Matematika Diskrit Siap Print
220/253
g
sebuah connected graph yang tidak memilikivertex berderajat ganjil.
Langkah-langkah :
Pilih sembarang vertex (v). Dari v, pilih sebuah edge yang bukan merupakan cut
edge (bridge). Beri tanda pada edge tersebut.
Melalui edge tersebut, telusuri vertex lainnya.
Ulangi langkah 2 dan 3 hingga semua edge terlewatidan berakhir di vertex awal (v).
220
ContohA B
C D
E FA B A B A B
-
8/4/2019 Matematika Diskrit Siap Print
221/253
221
C D
E F
A B
C D
E F
A B
C D
E F
A B
C D
E F
C D
E F
A B
C D
E F
A B
C D
E F
A B
C D
E F
A B
C D
E F
Hamilton Path dan Cycle
-
8/4/2019 Matematika Diskrit Siap Print
222/253
Hamilton path adalah path dalam sebuah graph
yang melewati tiap vertex tepat 1 kali dan tidak
harus melalui semua garis.
Hamilton cycle adalah hamilton path yang
kembali ke titik awal
Graph yang mengandung hamilton cycle tidak
memiliki loop dan multiple edge
222
Contoh
-
8/4/2019 Matematika Diskrit Siap Print
223/253
223
A
B C
DE
Hamilton cycle : A-B-C
top related