MATEMATIKA
BAB 1 LOGIKA
PENDAHULUAN
Logika adalah ilmu yang mempelajari tentang penalaran yang berhubumgan dengan pembuktian validitas suatu argumen.
Argument yang berisi pernyataan-pernyataan harus dirubah menjadi bentuk logika untuk dapat dibuktikan validitasnya.
Cara membuat ke bentuk logika, argument harus dirubah menjadi preposisi-preposisi selanjutnya preposisi dirubah menjadi variabel preposisi dengan huruf.
Setiap variabel preposisi ditentukan nilainyadan dimanipulasi dengan cara tertentu untuk mendapatkan nilaikebenarannya.
Contoh-contoh argument yang valid dan yang bisa dipakai adalah. Disjunctive Sillogism, Hypothecal Sillogism, Modus ponen, dan Modus Tollens.
Argument : permis & kesimpulan, preposisi / pernyataan semua berbentuk kal.
Preposisi dinotasikan dengan huruf abjad dan diberi nilai benar dan salah.
Eksprersi terdiri dari notasi dan perangkai ini juga disebut logika
PREPOSISI
Kalimat yang benar atau salah, ttp tidak keduanya
Preposisi atau kalimat dalam logika, preposisi bisa berupa
+ atom / kalimat sederhana
+ kalimat kompleks, komposisi kalimat menggunakan operator logika.
Kalimat sederhana bisa berupa
+ symbol konstanta : true dan false
+ symbol variabel proposisi : p,q,r,p1,q1
Literial adalah atom atau negasinya.
OPERATOR LOGIKA
(disusun berdasarkan hirarki)
Symbol Arti (dibaca) Bentuk
¬ Negasi / not / tidak Tidak …
Λ Konjungsi / and / dan …. Dan ….
v Disjungsi / or / atau …. Atau …
→ Implikasi Jika ….. maka ….
↔ Ekuivalensi / biimplikasi …. Jika hanya jika …
Definisi kalimat / preposisi
setiap konstanta logika true dan false adalah proposisi
variabel logika p,q,r,,p1,q1,…. Dalah proposisi
jika a dan b adalah proposisi maka a Λ b, a V b , a b dan -a adalah proposisi.
MEMPRESENTASIKAN FAKTA
proporsisi bisa mempresentasikan kalimat berita
p : saya malas belajar
q : saya lulus kuliah
p Λ q : saya malas belajar dan lulus kuliah
p ¬q : jika saya malas belajar maka saya tidak lulus kuliah
AMBIGUITY
Ambigu : mempunyai banyak arti
Contoh : p Λ q V r berarti p Λ(q V r) atau (p Λ q)V r
Untuk menghilangkan ambiguity bisa menggunakan notasi kurung buka dan tutup yaitu (dan) atau prioritas/hirarki operator (precedence)
Table kebenaran
Adalah table yang menunjukkan nilai kebenaran dan hasil kombinasi proposisi-proposisinya
Secara umum jika ada n variabel proposisi , maka tabel kebenarannya ada 2n baris.
Definisi masing-masing penghubung/operator sbb:
p q p P Λ q P V q P q P ↔ q
T T F T T T T
T F F F T F F
F T T F T T F
F F T F F T T
Keterangan tabel lihat halaman berikut
Keterangan tabel
Negasi
Proposisi ¬p memiliki nilai kebenaran yang berlawanan dengan aslinya
Misal jika p bernilai F maka ¬p bernilai T
Konjungsi
Proposisi p Λ q (di baca p dan q ) adalah bernilai benar bila nilai p dan q keduanya bernilai benar, sedangkan kombinasi yang lain bernilai salah
Disjungsi
Proposisi p q (dibaca p atau q ) adalah bernilai salah , bila nilai p dan q keduanya bernilai salah, sedangkan kombinasi yang lain bernilai benar
Implikasi
Proposisi p q (dibaca :# jika p maka q,# q apabila p,# p hanya bila q,# p sarat cukup q, # q syarat perlu p )adalah bernilai salah bila p benar dan q salah, sedangkan kombinasi lainya bernilai benar
Biimplikasi
Proposisi p↔ q ( dibaca p bila hanya bila q ) yang berarti juga (p → q)Λ(q→p) adalah bernilai benar bila p dan q mempunyai nilai kebenaran yang sama ( keduanya bernilai benar atau keduanya bernilai salah )
Contoh
Misal ; p = budi orang kaya
Q=budi berduka cita
Tulislah bentuk simbul logika kalimat-kalimat berikut :
Budi orang yang miskin tetapi bersuka cita.
Budi orang kaya atau ia sedih.
Budi tidak kaya ataupun bersuka cita.
Budi orang yang miskin atau ia kaya tetapi sedih.
Jawab : a). ¬p Λ q b). pV¬q
c).¬p Λ¬ q d). ¬pV (pΛ¬ q)
contoh 2
diketahui kalimat-kalimat yang sudah dalam bentuk symbol logika berikut dibawah ini,buatlah kebenarannya:
a). ¬(¬pV¬q) b).¬(¬p ↔q)
c). (p→q)Λ¬(pVq) d).(¬pΛ(¬qΛr)) V (qΛ r ) V (p Λr)
jawab :
p q r ¬p ¬q ¬qΛr qΛr pΛr
T T T F F F F T T T F
T T F F F F F F F F F
T F T F T T F F T T F
T F F F T F F F F F F
F T T T F F F T F T F
F T F T F F F F F F F
F F T T T T T F F T T
F F F T T F F F F F F
Contoh 3
Pada kondisi bagaimanakah agar kalimat berikut ini benar?”tidaklah benar bila rumah kuno selalu bersalju ataupun angker,dan tidak juga benar bila sebuah hotel selalu hangat atau rumah kuno selalu rusak”
Jawab
Membuat variabel proporsisi misal p=
Selanjutnya didapat bentuk logika sbb (¬(pVq)) Λ¬(rVs)).
Untuk menyelidiki kondisi kombinasinya dimana seluruh kalimat bernilai benar,harus dibuat tabel kebenaran ……………
Dari tabel diatas terlihat bahwa
Tidaklah benar bila rumah kuno selalu bersalju atau angker, dan tidak juga benar bila sebuah hotel selalu hangat atau rumah kuno selalu rusak adalah bernilai benar bila rumah kuno tersebut tidak selalu bersalju,tidak selalu angker,tidak selalu rusak, dan hotelpun tidak selalu hangat
EKUIVALEN (p q) atau p q
Adalah bila hanya bila ruas kiri dan ruas kanan memiliki nilai kebenaran yang sama untuk semua kombinasi nilai kebenaran dari masing-masing kalimat penyusunnya (kalimat pada ruas kiri dan kalimat pada ruas kanan )
Contoh :
Tentukan apakah pasangan bentuk logika p → q dengan ¬p Vq ekuivalen
Jawab :
Buat tabel kebenaran kedua bentuk logika sbb :
p Q P→ q ¬p ¬pVq
Oleh karena tiap-tiap baris nilai kebenaran sama, maka p→q ¬pVq
HUKUM-HUKUM EKUIVALEN LOGIKA
1). Hukum komunitatif ; p Λ q q Λ p ; p V q q V p
2). Hukum asosiatif ; pΛq )Λr pΛ(qΛr); (pΛq)Λr pΛ(qΛr)
3). Hk distributif; ; pΛ(q Vr) (pΛq)V(pΛr); pV(qΛr) (pΛq)V(pΛr);
4). Hk.identitas ; pΛT p; pVF=p
5). Hk. Ikatan ; pΛF p; pVT p
6). Hk. Negasi ; (pΛ¬p) F ; (pV ¬p) T ;
7). Hk.Negasi ganda ¬ ( ¬p) p ;
8). Hk. Idempoten ; (pΛp) p; (pVp p;
9). Hk. Demogran ; ¬ ( pΛq) pV ¬q, ¬(pVq) ¬pΛ¬q,
10). Hk.absorbsi ; pV (pΛq) p pΛ(pVq) p
11). Hk. Negasi T dan F ; ¬T F ¬F T
p ↔ q ( p → q )Λ ( q→p )
¬(p → q) p Λ¬q
P → q ¬ p V q
Catatan :
Manfaat hokum-hukum diatas adalah dapat digunakan untuk menyederhanakan kalimat-kalimat yang komplek
Contoh :
Sederhanakan bentuk , ¬(¬p Λ q) Λ (p V q)
Jawab :
(¬ ¬ pV¬q)Λ( pVq ) ; berubah jadi ini karena hk demorgan
(pV¬q)Λ(pVq) ; berubah jadi ini karena hk negasi ganda
pV(¬qΛq) ; berubah jadi ini karena hk distributive
pVF ; berubah jadi ini karena hk
p ; berubah jadi ini karena hk
Untuk membuktikan ekuivalensi dengan cara : biasanya bentuk yang lebih komplek diturunkan ke yang lebih sederhana , jika sama – sama komplek sama – sama diturunkan dg hk yang berbeda jika terdapat penghubung , dan , penghubung tersebut harus dirubah dulu dalam bentuk penghubung , V, Λ,
dan ¬
contoh buktikan ekuivalensi berikut tanpa tabel kebenaran
( q→p ) ↔ ( ¬ p→¬q)
Jawab
Ruas kanan tampaknya lebih komlpek, untuk itu yang disederhanakan ruas kanan
(¬p→¬q ) ↔ ¬ (¬p)V¬q (transformasi dari → ke V )
↔ pV¬q (negasi ganda )
↔ ¬qVp (komunikatif)
↔ q →p (transformasi dari V ke → )
Terbukti ruas kiri sama dengan ruas kanan yaitu (q→p) ↔ ( ¬p→¬q)
(p→(q→r)) ((pΛq)→r)
Jawab
Ruas kiri ; (p→(q→r)) ( ¬pV(q→r))
¬pV (¬qVr)
(¬ pV ¬q)Vr
¬( pΛq)Vr
(p Λ q)→r terbukti sama dengan ruas kanan
TAUTOLOGI DAN KONTRADIKSI
Tautologi adalah suatu kalimat yang selalu bernilai benar (T) , dan tak peduli nilai kebenaran kalimat penyusunnya.
Kontradiksi adalah suatu kalimat yang bernilai salah.
Misal diketahui implikasi adalah p→q maka :
Konversinya adalah q → p
Inversinya adalah ¬p→¬q
Kontraposisinya adalah ¬q →¬p
Catatan implikasi ikuivalensi dg kontraposisi jadi merupakan tautology
Contoh
Tentukan apakah kalimat dibawah
(pΛq)→q
q→(pVq)
tautologi atau kontradiksi dengan cara tabel kebenaran
jawab
a). dengan tabel kebenaran
P Q pΛq (pΛq)→q
Oleh karena semua baris pada kolom ( pΛq)→q bernilai T maka (pΛq)→q adalah tautologi
P Q pVq q→(pVq)
b).dengan tabel kebenaran
semua baris pada kolom q→(pVq) adalah T maka q→(pVq) merupakan tautologi
INFERENSI LOGIKA
Menentukan nilai kebenaran suatu kesimpulan berdasarkan sejumlahkalimat yang diketahui nilai kebenarannya
1).argumen valid : jika semua hipotesis / pernyataan benar dan kesimpulan juga benar.(kebenaran kesimpulan ini dikatakan turun dari hipotesis)
2).argumaen invalid : jika pernyataan benar dan kesimpulan salah
Cara menentukan argumen valid ada 2 cara yaitu dg tabel kebenaran metode inferensi
Langkah-langkah tabel kebenaran
#tentukan hipotesis dan kesimpulan
#buat tabel kebenaran (semua hipotesis juga kesimpulan)
#carilah baris kritis yaitu baris yang semua hipotesisnya bernilai benar
#perhatikan pada baris kritis jika semua nilai kesimpulan benar maka argumen valid, jika ada yang salah argumen tidak valid
Contoh tentukan apakah argument berikut
pV(qVr)…………… a)
¬ r …………… b)
Jadi pVr
Jawab
Ada 2 hipotesa pV(qVr) dan ¬ r, kesimpulan dengan tabel kebenaran sbb
Baris p q r qVr pV(qVr) ¬r pVr
1 T T T T T F T
2 T T F T T T T
3 T F T T T F T
4 T F F F T T T
5 F T T T T F T
6 F T F T T T F
7 F F T T T F F
8 F F F F F T F
Terlihat baris kritisnya pada baris 2,4,dan 6, pada baris tersebut kesimpulannya ada yang bernilai F. jadi argument tersebut adalah valid
P →(qV¬r)
q→qΛr)
p→ r
jawab :
perhatikan 2 hipotesa p →(qV¬r) dan q→(qΛr).sedang kesimpulannya p→r,dengan tabel kebenaran sbb
baris p q r ¬r qV¬r pΛr p→(qV¬r) q→(qΛr) p→r
T T T F T T T T T
T T F T T F T F F
T F T F F T F T T
T F F T T F T T F
F T T F T F T F T
F T F T T F T F T
F F T F F F T T T
F F F T T F T T T
METODE INFERENSI
Penurunan kesimpulanberdasarkan hipotesis yang ada
Dengan aturan – aturan sbb :
Modus ponen : p→q
P
Jadi q
Modus tollen : p →q
¬q
Jadi ¬p
Penambahan disjungtif p
Jadi pVq
Penyederhanaan konjungtif pΛq
Jadi p
Silogisme disjungtif pVq
¬p
Jadi q
Silogisme hipotesis
p→q
q→r
jadi p →r
dilemma :
pVq
p→r
q→r
jadi r
konjungsi p
q
jadi pΛq
contoh 1 tentang modus tollen
jika budi seorang manusia maka dia dapat mati
budi tidak dapat mati
jadi bukan seorang manusia
contoh 2 tentang silogisme hipotesis
jika 18486 habis dibagi 18 maka 18486 habis dibagi 9
jika 18486 habis dibagi 9 maka jumlah digitnya habis dibagi 9
jadi jika 18486 habis dibagi 18 maka jumlah digitnya habis dibagi 9
LATIHAN
1a. apakah jawabanmu ini sudah benar?
b. 4 adalah angka primap
c. pascal adalah bahasa pemrograman yang baik
2.buatlah tabel kebenaran ekspresi logika berikut
a. pV(¬pΛq)→q
b. (pV(¬pVq))Λ¬(qΛ¬r))
c. pΛ¬r↔qVr
3.nyatakan kalimat berikut dalam bentuk ekspresi logika
a. david sedang bermain di kolam atau ia ada dalam rumah
b. david sedang mendengarkan radio jika ia ada dalam rumah
c. david tidak bermain di kolam dan tidak sedang mengerjakan PR
4. sederhanakan logika berikut : (pΛq) V (pΛ¬q)
5. tentukan pakah pernyataan berikut ekuivalen
a. (pVq)Λ(¬pΛ(¬pΛq)) dengan ¬p Λq
b. ¬(pV¬q) V(¬pΛ¬q) dengan ¬p
6. tentukan manakah logika berikut merupakan tautology atau kontradiksi
a. (pΛq)V(¬pV(pΛ¬q)
b. ((¬pΛq)Λ(qΛr))Λ¬q
7. tulislah konvers, invers, dan kontraposisi kalimat berikut
a. jika bilangan rasional , maka angka desimalnya akan berulang
b. jika n adalah bilangan prima , maka n adalah bilangan ganjil atau n=2
c. jika p adalah bujursangkar , maka p adalah 4 persegi panjang
8. diketahui jika cairan X mendidih,maka temperaturnya paling sedikit 1000C,adalah benar manakah pernyataan berikut yang pasti benar
a. jika temperatur cairan X paling sedikit 1000C, maka cairan X akan mendidih
b. jika temperatur cairan X kurang dari 1000C, maka cairan X tidak akan mendidih
c. jika cairan X tidak mendidih, maka temperaturnya kurang dari 1000C
gunakan modus tollen atau modus ponen untuk mengisi soal 9-10
9. jika potongan program ini akan berulang dengan perintah while maka isi perulanagn tidak pernah dieksekusi
…………………………………………………………………………………
Jadi isi perulangan tidak pernah dieksekusi
10. jika logika adalah pelajaran yang muda maka pastilah saya seorang propesor
Saya bukan seorang propesor
Jadi …………………………………………………………………………………………………………………….
Beberapa inferen berikut ada yang valid juga ada yang tidak valid,untuk yang valid jelaskan aturan inferensi yang digunakan, jika tidak valid jelaskan kesalahan yang terjadi
11. bilangan riel ini merupakan bilangan rasional atau irrasional
Bilangan riel ini tidak rasional
Jadi bilangan riel ini adalah bilangan irrasional
2.jika saya pergi nonton, maka saya tidak bisa menyelesaikan PR
Jika saya tidak bisa menyelesaikan PR, maka saya tidak lulus
Jadi jika saya pergi nonton maka saya tidak lulus
13. gunakan tabel kebenaran untuk menentukan argumen berikut valid atau bukan
pΛ¬q→r
pVq
q→p
jadi r
14. gunakan prinsip inverensi untuk menurunkan ¬s dari hipotesis – hipotesis berikut
(sVq)→p
¬a
p→a
BAB 2 HIMPUNAN
Definisi :
1. Himpuan : Kumpulan obyek-obyek yang berbeda
2. Penyajian himpunan : mendaftar, simbul-simbul baku, notasi pembentuk himpunan(menulis syarat keanggotaan), dandiagram Venn.
contoh Nyatakan himp. Berikut dlm notasi himpunan
A= himp. Bil. Riel lebih besar satu
B= himp. Yg anggotanya adl. Kursi meja, TV, buku, air
3. Kardinalitas: jumlah anggota himpunan. Mis. Himp A notasi n(A) atau |A|
4. Himpunan Kosong: tdk memiliki elemen. Notasinya { } atau Ø
5. Definisi Himpuan Bagian:
Himp A dikatakan himp bagian dari himp B, Jika hanya jikan Setiap elemen A merupakan elemen dari B (B superset dari A) notasi A⊆ B
Catatan, sembarang himp A maka A ⊆ A dan Ø ⊆ A
himp {Ø} bukan merupakan himp bag dari himp {{Ø}} karena masing masing himp mempunyai satu elemen yang berbeda
6. Himpuan yang sama: NOTASI: A = B ↔ A ⊆ B dan B ⊆ A
7. Himpunan yang ekivalen Notasi: A~ B ↔ |A| = |B| yaitu kardinal dr kedua himp tsb sama (jumlah elemen sama)
8. Himp saling lepas: jika kedua himp. Tdk memiliki elemen yg sama Notasi: A // B
9. Himp Kuasa dari himp A adl Suatu himpunan yang elemen elemennya merupakan himpunan bagian dari A, termasuk himp kosong dan himp A sendiri (ingat elemen elemennya berupa himpunan sebanyak 2n ) dengan Notasi P(A)
Contoh misal A={teh, nasi} tentukan P(A)
Jawab P(A)= { { }, {teh}, {nasi}, {teh,nasi} }
10.OPERASI HIMPUNAN:
IRISAN dari himp A dan B adl himp yg elemennya ada pada himp A dan himp B. notasinya A∩B={x|xєA Λ xєB}
GABUNGAN dr himp A dan himp B adl Himp yg elemennya merupakan himp A atau himp B. Notasinya AUB={x|xєA V xєB}
KOMPLEMEN dr himp A terhadap himp semesta S adl himp yg elemennya merupakan himp semesta S tetapi bukan himp A. notasinya A’ = {x|xєU Λ x¢A}
SELISIH dari himp A dan himp B adalah himpunan yang elemennya merupakan elemen dari himp A dan bukan elemen himp B, dinotasikan A-B = AυB’
BEDA SETANGKUP dari himp B adalah himp yang elemennya merupakan elemen himp A atau elemen himp B tetapi tidak keduanya. Dinotasikan AӨB
PERKALIAN KARTESIAN dari himp A dan himp B adalah himp yang elemennya merupakan semua pasangan berurutan yang mungkin terbentuk dengan kompinen pertama dari himp A dan komponen kedua dari himp B
SIFAT-SIFAT OPERASI HIMPUNAN
Hukum identitas yaitu AØ=Ø, dan AӨA= Ø
Hukum nul yaitu A Ø=Ø, dan AӨA= Ø
Hukum komplemen yaitu AA’=U, AA’= Ø
Hukum Idempoten yaitu AA=A, A A=A
Hukum ivolusi yaitu (A’)=A
Hokum penyerapan yaitu A (AB)=A, A (AB)=A
Hukum komulatif
Hukum assosiatif
Hukum distributive
Hukum demorganyaitu (AB)’=
Hukum 0/I Yaitu
PRINSIP DUALITAS
Misal S adl kesamaan yg terbentuk dari himpunan dan operasi, jika operasi-operasi tsb diganti dengan , diganti , diganti U, dan U diganti , komplemen dan notasi himpunan yg ada ditetapkan seperti sebelumnya maka didapatkan kesamaan Q, maka Q disebut dual dari S.
Pembuktian Kalimat Himpunan diselesaikan dg cara : 1) tabel keanggotaan 2)sifat operasi, 3) definisi.
Contoh :
Buktikan bahwa jika A sembarang himpunan , maka A=
Jawab :
Cukup dibuktikan bahwa A tidak punya elemen, dg cara kontradiksi misalkan benar bahwa A mempunyai elemen yaitu x. Berarti x Є maka xЄA dan xЄ secara husus xЄ adalah tidak mungkin dengan kata lain A mempunyai elemen adalah SALAH. Jadi terbukti bahwa bahwa A tidak punya elemen
Latihan
Halaman 32-34(buku 1) dan 146-150(buku 2)
Contoh
Tentukan apakah pernyataan berikut benar/salah? Jelaskan
2 = {2}
2 € {2}
Misalkan S={x€Z | x=(-1)ⁿ, n adalah bilangan positip, Z adalah himp bil bulat} nyatakan himpunan S dengan cara mendaftar
Misalkan A={c, d, f, g}, B={f, j}, dan C={d, g}. Tentukan apakah pernyataan berikut benar atau salah?
B ⊆ A b) C ⊆ C c) C ⊆ C
Tentukan apakah pernyataan berikut benar atau salah? Jelaskan
1 € {{1}, 2} b) {3} € {1,2,{3}} c) {2} ⊆ {2,3,4}
Diketahui A= {x € bil riil | 0<x≤2}
B = {x € bil riil |1≤x<4}
S = semesta pembicaraan bil riil
Tentukan a) AB b) AB c) A’B’ d) A’B’
Misalkan A= {1,2}, B= {2,3}
Tentukan himpunan kuasa berikut a) P(AB) b) P(AB) c) P(AXB)
Tentukan a) P(Ø)= ?
b) P(P(Ø))=
c) P(P(P(Ø)))=
Buktikan bahwa a) AB ⊆ A
b) jika A⊆ B dan B ⊆ C maka A ⊆ C dengan cara definisi
Buktikan bahwa (AB)-C = (A-C) (A-B) dengan cara hukum-huku
BAB 3 KOMBINATORIKA
Dasar-dasar Perhitungan
1 ) Aturan Penjumlahan
Misal himpunan A adl gabungan dari himpunan-himpunan bagian yang tidak kosong dan saling asing maka jumlah elemen himpunan A sama dengan jumlah anggota semua himpunan bagian
Contoh
Dalam suatu kartu bridge lengkap berapa cara untuk mengambil
a) Sebuah kartu jantung atau sebuah daun
Jawab :
Kartu jantung dan kartu daun merupakan himpunan yang saling asing maka untuk mendapatkan salah satunya adalah JUMLAH cara pada masing-masing bagian(jantung dan daun), untuk mendpat satu kartu jantung adalah 13 cara (karena kartu jantung ada 13 buah), untuk mendapat kartu daun adalah 13 cara(karena kartu daun 13 buah ) jadi untuk mendapat satu kartu jantung atau satu kartu daun adalah 13+13=26 cara
b) Sebuah kartu jantung atau as
Jawab :
ingat jumalah kartu jantung 13 sudah termasuk as
Kartu as semua 4 buah (ada 3 kartu as selan jantung) maka banyak cara sebuah kartu jantung atau as adalah 13+3=16
Contoh 2
Misal dua dadu berbeda warna (merah dan putih) dilempar ada berapa macam cara untuk mendapatkan jumlah angka 4 atau 8.
Jawab :
Bentuk elemen (merah, putih)
Untuk mendapat jumlah 4 adalah 3 cara yaitu (1,3); (2,2); (3,1)
Untuk mendapat jumlah 8 adalah 5 cara yaitu……..
Jadi untuk mendapat jumlah 4 atau 8 adalah 3+5=8 cara
Contoh 3
Misal dua dadu warna sama dilempar ada berapa macam cara untuk mendapatkan jumlah angka 4 atau 8.
Jawab :
karena warna sama maka elemen (1,3) dg (3,1) dianggap satu elemen
Begitu juga elemen (2,6) dg (6,2) dan (3,5) dg (5,3) jadi kemungkinannya tinggal 5 cara
2) Aturan Perkalian
Misal suatu pekerjaan melibatkan k buah langkah dimana
Langkah ke-1 ada n1 cara (cara ke1,cara ke2, ….. Cara ke n1 )
Langkah ke-2 ada n2 cara (carake1,cara ke2, ….. Cara ke n2 )
Langkah ke-3 ada n3 cara (carake1,cara ke2, ….. Cara ke n3 )
…………………………………..
Langkah ke-k ada nk cara (cara ke1,cara ke2, ….. Cara ke nk ).
Dg demikain semua pekerjaan adalah sebanyak (n1 )(n2 )… (nk ) cara
(untuk membayangkan bentuk elemennya, ingat perkaian kartesian jika ada k-terorder identik dg titik pada Rk/ruang demensi k )
Contoh 1
Jika dua buah dadu berbeda dilontarkan ada berapa banyak cara angka yang muncul ?bagaimana jika 5 dadu, bagaimna jika n dadu ?
jawab adl (6)(6)= 62 cara; untuk 5 dadu adl 65; untuk n dadu adalah 6n cara
Contoh 2
Misalkan barang-barang disuatu pabrik diberi nomer kode yang terdiri dari 3 huruf dan 4 angka (misal BUD1234)
a)Jika baik huruf maupun angka boleh diulang penggunaannya ada berapa macam barang yg dat diberi kode yg berbeda?
b)Jika huruf saja yg dapat diulang
jawab
a)Jumlah huruf 26 dan jumlah angka 10, maka kode yg terdiri dari 3 huruf adalah 263cara ,sedang kode yg terdiri dari 4 angka adl (10)4cara, maka banyak kode dg kombinasi 3 huruf dan 4 angka adl (26)3(10)4cara.= …….. cara
b) kode yg terdiri dari 3 huruf adalah 263cara
kode yg terdiri dari 4 angka adalah (10)(9)(8)(7) cara
Maka banyak kode dengan 3 huruf dan 4 angka adalah (26)3(10)(9)(8)(7) cara
Contoh 3
berapa banyak bilangan yg terdiri dari 2digit atau 3 digit yang dapat dibentuk menggunakan angka-angka 1,2,3,4,5,6,7 jika perulangan tidak diperbolehkan.
Jawab
Banyak bilangan dari 2 digit adalah (7)(6) cara= 42 cara
Banyak bilangan dari 3 digit adalah (7)(6)(5) cara = 210 cara
Maka banyak bilangan terdiri dari 2 digit atau 3 digit adalah
(7)(6)+ (7)(6)(5) cara
KOMBINASI DAN PERMUTASI
Untuk perhitungan bagian ini yang perlu dipahami yaitu tentang Faktorial
Definisi
Besaran n faktorial (degan simbul n!)adalah sebagai hasil kali semua bilangan bulat antara 1 hingga n
Catatan
Untuk n=0 didefinisikan husus yaitu 0!=1
selanjutnya untuk bilangan bulat yang lain didapat sbb n!=1.2.3…….(n-1).n
Dari definisi faktorial didapat persamaan sbb n!= n(n-1)! (buktikan)
= sehingga didapat n!= n(n-1)!
Kombinasi ( hal yang diperhatikan obyek-obyek yg muncul)
Misal himpunan S memiliki n elemen
Ada himpunan bagian S memiliki r elemen dimana r≤n disebut kombinasi n obyek yang diambil sebanyak r obyek sekaligus, simbulnya adalah
atau ditulis C(n,r)
Banyaknya kombinasi yg dimaksud adl =
Catatan: urutan tidak diperhatikan maksudnya adalah elemen bentuk ab dengan elemen bentuk ba dianggap satu elemen(dianggap sama)
Contoh
seorang pelatih basket akan memilh komposisi pemain yg akan diturunkan dlm pertandingan , ada 12 orang pemain yg dapat dipilih. Berapa macam tim yg dapat dibentuk?
Jawab jumlah pemain basket dalam suatu tim ada 5 orang
Banyak tim yg dapat dibentuk adl
= = = 792
Contoh 2
Suatu perusahaan memiliki 5 karyawan laki-laki dan 7 karyawan wanita , lalu akan dipilih 5 orang untuk mengerjakan suatu proyak, ada berapa tim yg dapat dibentuk apabila dalam tim tersebut harus
a)Terdiri dari 3 karyawan laki dan 2 karyawan wanita
Jawab
Untuk laki-laki adl C(5,3))= = 10
Untuk wanita adl C(7,2) = =21
Jadi unt milih tim terdiri 3 laki dan 2 wanita adl , =210 cara
b) Terdiri dari paling sedikit terdapat 1 karyawan laki
jawab
Kasus ini ada 5 tim(setiap tim ada beberapa cara)
tim satu 1 laki dan 4 wanita banyak cara adl
5 7
1 4 cara=175
Tim dua 2 laki dan 3 wanita banyak cara adl
5 7
2 3 cara=350
Tim tiga 3 laki dan 2 wanita banyak cara adl
5 7
3 2 cara=210
Tim empat 4 laki dan 1 wanita banyak cara adl
5 7
4 1 cara=35
Tim lima 5 laki dan 0 wanita banyak cara adl 5 7
5 0 cara=1
Jadi cara memilih paling sedikit 1karyawan laki adl semua cara dijumlah=771
Permutasi (urutan diperhatikan artinya elemen ab beda dg elemen ba)
pengulangan elemen tidak diperbolehkanartinnya tdk bisa dplih lagi
Misalkan dalam kelas terdiri dari 30 mahasiswa coba perhatikan 2 kasus berikut; yaitu a) diambil 2 mahasiswa ada berapa cara
b) diambil 1 mahasiswa sbg ketua dan 1 mahasiswa lagi sebagai bendahara
Terlihat kasus ponit b) adalah permutasi karena ab dg ba adl beda sedangkan kasus a) terlihat ab dengan ba adalah sama (dihitung satu elemen )
Perhatikan gambar tentang 4 elemen diambil 2 elemen berikut;
{a,b,c,d} { a,b} a,b
b,a
{ a,c} a,c
c,a
{a,d}
{b,c}
{ b,d}
{c,d } dstnya ,dari sini didapat rumus
Rumus cecara umum untuk r obyek yg diambil dari n obyek adalah
P(n,r) = jika n=r disebut permutasi n obyek P(n,n)=n!
Contoh
Suatu undian dilakukan dg menggunakan angka yg terdidi dari 7 digit , jika digit digit dalam suatu angka diharuskan berbeda satu dg yang lain , ada berapa kemungkinan nomer undiannya?
Jawab
Dalam undian tsb jelas urutan angka diperhatikan (dihitung), maka banyaknya undian adlah
P(10, 7) = =10.9.8.7.6.5.4=604800 macam kmungkin
Contoh 2
Sebuah grup terdiri dari 7 wanita dan 3 pria . Ada berapa macam cara berbaris yg mungkin dibuat jika 3 pria tersebut selalu kumpul/bersebelahan
Jawab dalam hal ini ada dualangkah penyelesaiannya
Langkah 1 adalah permutasi dari 3 obyek adalah P(3,3)=3!=3.2.1=6
Langkah 2 adl permutasi dari 8 obyek P(8,8)=8!=40320
Jadi macamnya grup laki dan wanita adalah (6)(40320)=241920 macam
Rumus permutasi untuk susunan melingkar dengan n obyek yang beda adalah P(n,n)=(n-1)!
Berkurang karena posisi obyek yang pertama yang ditempatkan tidak begitu penting (yang dipentingkan kedudukan setiap obyek relatif dengan obyek yang lain
Kombinasi dan permutasi dengan elemen berulang(elemen nya sama/elemen ada yang lebih dari satu
Jika suatu himpunan terdiri dari n obyek tersusun dari
Jenis 1 sebanyak n1
Jenis 2 sebanyak n2
…………………….
Jenis k sebanyak nk , dimana n1+n2+…..+nk=n
Menggunakan rumus
P(n,n1,n2,….nk)= … =
contoh
Tentukan banyaknya macam cara untuk menyusun huruf-huruf dalam kata MISSISSIPPI
Jawab n=11, jenis huruf M =1 buah
jenis huruf I =4 buah
Jenis huruf S =4 buah
jenis huruf P =2 buah
jadi banyaknya cara adl = =34650
Contoh
Ada berapa macam cara agar 23 macam buku yang berbeda dapat diberikan pada 5 mahasiswa dengan aturan 2 mahasiswa memperoleh 4 buku dan 3 mahasiswa memperoleh 5 buku
Jawab
Ada dua langkah
Langkah pertama memilih 2 mahasiswa memperoleh 4 buku
Ada 5 = 5! =10 cara (rumus 2 sekat)
2 2! (5-2)!
Langkah kedua pendistribusian 23 buku dibagikan 5 mahasiswa, itu merupakan permutasi berulang yaitu
cara (rumus 5 sekat)
Jadi banyak cara pendistribusiannya adl
10 = …… macam cara
Aplikasi kombinatorika dalam ilmu Komputer
1. Pengenal (identifer) dalam Pascal
-harus dibuat(dideklarasikan) dulu sebelum identifer tsb dipakai
-identifer terdiri dari gabungan huruf, angka dan simbul-simbul husus
-karakter pertama harus huruf
-panjang identifer tentang kompiler yg dipakai
-identifer yang sudah dipakai oleh pascal sebagai kata kunci(reserved word) tdk boleh dipakai untuk keperluan lain seperti begin, end dll
Contoh
Misalkan dalam kompiler pascal, identifer tersusun dari 26 huruf,10 angka dan 3 simbul husus, panjang identifer yg diizinkan 8 karakter, jumlah kata kunci yang sudah dipakai 35, berapa identifer yg masih dapat digunakan?
Jawab
Panjang identifer maksimal 8 karakter
-Identifer dengan panjang 1 karakter =26 macam (karena pertama hrs huruf)
-Identifer dengan panjang 2 karakter= (26)(39) macam (karena karakter pertama harus huruf karakter kedua bisa berupa huruf,angka dan sibul husus)
-identifer dengan panjang 3 karakter=26(39)2
-identifer dengan panjang 4 karakter=26(39)(39)(39)=26(39)3
………………………………………………..
-identifer dengan panjang 8 karakter=26(39)(39)(39)(39)(39)(39)(39)=26(39)7
jadi jumlah identiber dengan panjang maksimal 8 adal = jumlah semua identifer dengan panjang 1 sampai 8 dijumlahkan yaitu
26+26(39)+26(39)2+26(39)3………..+26(39)7
Karena sudah dipakai 35 identifer sebagai kata kunci seingga identifer yang dapat dipakai adalah; (26+26(39)+26(39)2+26(39)3………..+26(39)7-35) macam
Jumlah iterasi dalam suatu loop(kalang)
-kebanyakan program menggunakan kalang
-statemen dalam kalang inilah yang sering dieksekusi sehingga lama waktu eksekusi tgt dari banyaknya kalang-kalang dalam yang dieksekusi
contoh
Perhatikan kalang FOR dibawah ini , berapa kali statemen didalamnya dieksekusi?
For i = 1 to n do
statemen – statemen dalam kalang. Tidak ada perintah di dalamnya yang menyebabkan eksekusi melompat keluar kalang.
{ end for – i}
Jawab
Misal x = statement dalam kalang, x tidak boleh keluar kalang sebelum kalang selesai dieksekusi
x akan dieksekusi untuk i =1,2,3,….n; jadi dieksekusi sebanyak n kali
For i = 1 to n Do
For j = 1 to m Do
Statemen – statemen dalam kalangan. Tidak ada perintah di dalamya yang menyebabkan eksekusi melompat keluar kalang.(jmlah=nilai+kuis)
{ End For – j }
{ End For – i}
Jawab
Eksekusi statemen dalam kalang dapat digambar sbb
i=1 j=1
j=2
j=3
….
j=m (dan seterusnya untuk i=2, ………i=n)
Ada tiap cabang keluar, statement selalu dieksekusi sekali menggunakan aturan perkalian, maka statement akan dieksekusi sebanyak mana kali
Contoh
Ada berapa banyak fungsi bool 3 variabel yg dapat dibuat, bila fungsi bool didefinisikan dg mengawankan masing-masing bil biner 3 digit 0 atau 1
Jawab
Salah satu nilai fungsi biner adl 10011000 jadi didapat 28 cara
1. Segitiga Pascal
Salah satu persamaan dlm kombinatorika dan dapat diguna untuk menghitung kombinasi suatu suku berdasarkan kombinasi suku-suku yg lebih rendah
identitas paskal dinyatakan dalam persamaan
= +
=
Secara geometris dapat digambar sbb
r
n 0 1 2 3 4……… r-1 r
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
….. ….. …. …. …
n ……………………..
n+1 ……………………………
Ada beberapa sifat penting dalam segi tiga Pascal
Kondisi batas
Nilai segitiga pascal dibagian ujung kiri kanan selalu = 1 karena, = = 1
Kondisi sekunder
Nilai segi tiga pascal pada baris ke n di kolom kedua dan kolom kedua sebelum terakhir selalu = n karena = = n
Simetris
Nilai pada setiap baris bersifat simetris karena =
Jumlah diagonal : + ……. + =
Jumlah baris + ……. + ……. + = 2n
Kuadrat penjumlahan baris 2 + 2 + 2 …. + …. + 2 =
Jumlah kolom : dg bil positif n dan r, n ≥ r berlaku : + + …. =
Menggunakan sifat-sifat koefisien binomial hitunglah
1 + 2 + 3 + ……….. + n
12 + 22 + …………. + n2
Jawab
k = maka 1+2+3 + ………+n = + + …. =
= = =
Catatan : ingat sifat penjumlahan kolom untuk r = 1
k2 = k(k-1) + k dalam hal ini r = 2
2 + maka 12 + 22 + ….. + n2 = ∑ 2 +
= ∑ 2 + ∑
= 2 + =
Contoh n, r bil bulat positif 2 ≤ r ≤ n, nyatakan dalam suku-suku
, dan
Jawab
= + ( identitas pascal )
= + + + = + 2 +
Teorema Binomial dan Multinomial
n
k
n
k=0
Misalkan x dan y adalah bilangan 2 riil dan n adalah bilangan bulat tak negative maka
(x + y)n = ∑ xn-k yk = xn + xn-1 y1 + xn-2 y2 + …. + yn
Contoh
Uraikan pernyataan: a) (2x + 5y)3 b) (x – 4y)4
Soal
Manakah yang lebih besar 101 atau 1,0110000
Teorema Multinomial
Multinomial jumlah suku berbeda sebanyak t buah yaitu, dalam hal ini jika jumlahan suku t = 2 disebut binomial dengan demikian berbentuk
(x1 + x2 + ….. + xt )n = ∑ x1n1 . x2n2 …. xtnt, dimana n1 + n2 + … +nt = n
Dan banyak suku (x1 + x2 + ….. + xt )n adalah sedangkan koefisien
Contoh
Hitunglah koefisien x12.x3.x43.x54 pada pernyataan (x1 + x2 + x3 + x4 + x5)10
Hitunglah koefisien dan banyak suku x3.y3.z2 pada pernyataan (2x – 3y + 5z)8
Jawab
Koefisien adalah = 12600
Koefisien adalah 23.(-3)3.52. = -3024000
Dan banyak sukunya adalah = = = 45
Latihan
1. Misalkan 2 dadu yg berbeda warna dilontarkan.Berapa macam cara untuk
mendapatkan jumlah mata dadu genap?Bagaimana jika kedua dadu berwarna
sama?
Berapa banyak kode barang yg dapat dibuat menggunakan 1 atau 3 huruf yg diikuti
oleh 4 buah angka?
Suatu kemeja merk tertentu memiliki 12 warna pilihan,memiliki versi untuk pria dan
wanita,serta 3 ukuran untuk tiap-tiap versi.Berapa banyak tipe kemeja yg dibuat?
Berapa banyak nomor telepon yg bisa dibuat,jika nomor tersebut terdiri dari 7 digit,
dua digit pertama antara 2 hingga 9,digit ketiga antara 1 hingga 9,dan digit sisanya
bebas?
Dalam suatu kelas akan dipilih seorang ketua,seorang bendahara,dan seorang
sekretaris di antara 4 calon (A, B, C, D).Berapa banyak cara yg mungkin dilakukan?
Suatu komite yg beranggotakan paling sedikit 5 orang akan dipilih dari 9 calon yg
ada.Berapa macam komite yg dapat dibuat?
Misalkan suatu departemen memiliki 10 staf pria dan wanita.Berapa banyak cara
untuk membentuk komite yg beranggotakan 6 orang jika jumlah wanita dalam
komite tersebut harus lebih banyak dari jumlah pria?
8. Sebuah ruang di kereta api memiliki 10 tempat duduk,5 di antaranya
menghadap mesin,dan 5 lainnya membelakangi mesin.Dari 10
penumpang,4 di antaranya senang duduk menghadap mesin,3
senang duduk membelakangi mesin,dan 3orang biasanya duduk di
mana saja.Dalam beberapa cara semua penumpang tersebut dapat
duduk sesuai keinginannya?
9. Dalam suatu bahasa pemrograman,suatu identifier adalah barisan
sejumlah karakter,di mana karakter pertama haruslah huruf dan
sisanya haruslah huruf atau angka
a. Berapa banyak identifier dengan panjang yg ada?
b. Secara khusus,dalam implementasinya dalam bahasa Pascal,
identifier adalah barisan 1 hingga 8 karakter dengan ketentuan
di atas.Berapa banyak jumlah identifier dalam Pascal?
10. Misalkan bahwa plat nomor kendaraan terdiri dari 3 huruf dan
diikuti dengan 3 angka.
a. Berapa banyak plat nomor yang mungkin ada?
b. Berapa banyak plat nomor yang di awali dengan A dan di akhiri
dengan 0?
c. Berapa banyak plat nomor yang diawali dengan PDQ?
11. Di propinsi tertentu, plat nomor kendaraan yang bisa dibuat dari:
a. 3 angka diikuti dengan 3 huruf atau 3 huruf diikuti 3 angka?
b. 2 huruf diikuti dengan 4 angka atau 2 angka diikuti dengan 4 huruf?
c. 3 huruf diikuti dengan 3 angka atau 4 huruf diikuti dengan 2 angka?
d. 2 atau 3 huruf diikuti dengan 2 atau 3 angka?
12. Berapa banyak plat nomor kendaraan yang bisa dibuat dari 2 huruf dan diikuti
dengan 4 angka?
13. Sebuah badan perwakilan mahasiswa (BPM) beranggotakan 15 mahasiswa.
a. Dalam berapa cara sebuah komite yang terdiri dari 6 orang dapat dipilih dari
anggota BPM tersebut?
b. Dalam berapa cara sebuah komite yang terdiri dari 6 orang dapat dipilih dari
anggota BPM tersebut jika ada dua orang anggota BPM kuliah di jurusan yang
sama sehingga tidak diperbolehkan duduk bersama dalam sebuah komite?
c. Misalkan anggota BPM terdiri dari 8 pria dan 7 wanita.
– Berapa macam komite yang terdiri dari 3 pria dan 3 wanita dapat dibentuk?
– Berapa macam komite yang beranggotakan 6 orang dapat di bentuk jika
paling sedikit harus beranggotakan 1 wanita.
d. Misalkan anggota BPM terdiri 3 mahasiswa tahun ke-1, 4 mahasiswa tahun
tahun ke-2,3 mahasiswa tahun ke-3, dan 5 mahasiswa tahun ke-4.
Berapa banyak komite dengan 8 anggota dapat di pilih sedemikian hingga
setiap angkatan diwakili oleh 2 orang?
14. Sebuah tim pembuatan software beranggotakan 14 orang
a. Berapa banyak cara dapat dilakukan untuk membentuk grup yang terdiri
dari 7 orang?
b. Misalkan 8 orang dalam tim tersebut adalah wanita dan 6 lainnya pria.
– Berapa macam grup yang terdiri dari 3 pria dan 4 wanita dapat dibentuk?
– Berapa macam grup yang beranggotakan 7 orang dan paling sedikit
1 orang diantaranya pria dapat di bentuk?
– Berapa macam grup yang beranggotakan 7 orang dan paling banyak
3 orang wanita di antaranya dapat dibentuk?
15. Seorang mahasiswa harus menjawab 12 dari 15 pertanyaan dalam suatu ujian.
Berapa banyak pilihan yang dimiliki mahasiswa tersebut.
a. Seluruhnya?
b. Jika ia harus menjawab 2 pertanyaan pertama?
c. Jika ia harus menjawab pertanyaan pertama atau pertanyaan kedua, tetapi
tidak keduanya.
d. Jika ia harus menjawab 3 dari 5 pertanyaan pertama?
e. Jika ia harus menjawab paling sedikit 3 dari 5 pertanyaan pertama?
16. Dalam berapa cara digit-digit 0,1,2,3,4,5,6,7,8, dan 9 disusun sehingga:
a. Digit 0 dan 1 bersebelahan
b. Digit 0 dan 1 bersebelahan dan dalam bentuk 01
c. 0,1,2 dan 3 bersebelahan.
17. Suatu bilangan yang terdiri dari 4 digit akan di bentuk dengan hanya
menggunakan digit 3,4,5,6, dan 7.
a. Dengan berapa cara pembentukan dapat dilakukan?
b. Dalam berapa cara bilangan pada (a) memiliki digit yang berulang?
c. Dalam beberapa cara bilangan pada (a) lebih besar dari 5000?
d. Dalam beberapa cara bilangan pada (a) genap?
18. Bilangan yang terdiri dari 4 digit akan di bentuk menggunakan digit-digit
1,2,3,4,5,6,7,8 ( tanpa perulangan)
a. Berapa banyak bilangan yang dapat di bentuk?
b. Berapa banyak diantaranya bilangan yang kurang dari 4000?
c. Berapa banyak di antaranya bilangan yang genap?
d. Berapa banyak di antaranya bilangan yang ganjil?
e. Berapa banyak di antaranya bilangan yang merupakan kelipatan dari 5?
f. Berapa banyak di antaranya bilangan yang memiliki digit 3 dan digit 5?
19. Dalam himpunan bilangan bulat {1, 2, 3, …100}
a. Berapa banyak bilangan genapnya?
b. Berapa banyak bilangan ganjilnya?
c. Berapa banyak cara untuk mengambil 2 bilangan dari himpunan tersebut
sehingga jumlahnya genap?
d. Berapa banyak cara untuk mengambil 2 bilangan dari himpunan tersebut
sehingga jumlahnya ganjil?
20. Berapa banyak bilangan
a. genap antara 1 hingga 1001?
b. bulat antara 1 hingga 1001 yg habis dibagi 3?
c. bulat 4 digit yg habis dibagi 5?
d. bulat digit yg merupakan kelipatan?
21. Anda diberi 8 buku berbahasa Inggris yg berbeda-beda,12 buku berbahasa
Jerman yg berbeda,dan 5 buku berbahasa Rusia yg berbeda.Tentukan
banyaknya cara untuk mengatur buku-buku tersebut dalam rak jika :
a. semua buku dg bahasa sama harus dikelompokkan menjadi satu
b. semua buku berbahasa Inggris harus terletak di sisi paling kiri
c. semua buku berbahasa Inggris harus terletak di sisi paling kiri dan semua
buku berbahasa Jerman harus terletak di sisi paling kanan.
22. Carilah banyaknya cara yg dapat dilakukan untuk mengatur tempat duduk 5
pria dan 5 wanita dalam satu baris :
a. tanpa syarat
b. jika mereka harus duduk berselang-seling
c. ulangi soal (b) jika pria A dan wanita B harus duduk bersebelahan
d. ulangi soal (b) jika pria A dan wanita B tidak boleh duduk bersebelahan
23. 6 orang menonton bioskop bersama-sama
a. berapa banyak cara yg dapat dilakukan untuk mengtur tempat duduk
mereka dalam satu baris
b. misalkan salah satu di antaranya harus duduk di ujung.berapa banyak
cara yg dapat dilakukan untuk mengatur tempat duduk mereka dalam
satu baris?
c. misalkan keenam orang tersebut terdiri dari 3 pasang suami-istri.setiap
pasangan ingin duduk bersebelahan,dg suami di kiri.berapa banyak
cara yg dapat dilakukan untuk mengatur tempat duduk mereka dalam
satu baris?
24. Dalam kata HULABALOO :
a. berapa macam berbeda untuk mengatur huruf-hurufnya?
b. berapa macam cara untuk mengatur huruf-hurufnya jika harus dimulai dengan huruf U dan berakhir dengan huruf L?
c. berapa macam cara berbeda untuk mengatur huruf-hurufnya jika dalam pengaturan tersebut harus memuat huruf HU bersebelahan satu sama lain?
25. a. k3 = k(k-1)(k-2) + 3k2 – 2k = k + 6 k + 6 k
1 2 3
b. gunakan hasil (a) untuk menghitung 13 + 23 + ….. + n3
26. Carilah koefisien :
a. x3 y7 dalam ekspresi (x + y)10
b. x3 y7 dalam ekspansi (2x – 3y)10
c. x100 y101 dalam ekspansi (2x + 5y)201
d. x5 y8 dalam ekspansi (x + y)13
27. Hitunglah menggunakan teorema binomial
a. (2,01)7
b. (0,9)5
28. Tentukan koefisien :
a. x3 x2 x2 x3 dalam ekspansi (x1 + x2 + x3 + x4 + x5)10
b. x5 y10 z5 w5 dalam (x – 7y + 3z – w)10
c. x5 dalam (a + bx + cx2)10
29. Perhatikan potongan algoritma berikut. Berapa kali statement di loop terdalam akan di iterasi jika program tersebut dijalankan?
For i : = 1 to 4
For j : = 1 to i
(statement yang ada dalam tubuh loop. Tidak ada statement melompat keluar loop)
Next j
Next j
For i : = 1 to n (n adalah bil. Bulat)
For j : = 1 to i
(statement yang ada dalam tubuh loop. Tidak ada statement melompat keluar loop)
Next j
Next i
BAB 4 GRAF
Graf adalah suatu diagram yg memuat informasi
Tujuan merepresentasikan obyek-obyek diskrit dan hubungan obyek2 tsb
Secara visual obyek dinyatakan dg bulatan kecil dan hubungan obyek dinyatakan dg garis, garis bisa berarah ataupun tdk berarah
Contoh
Strktur organisasi, peta rangkaian listrik dll
1. Dasar-Dasar GRAF
Definisi Graf
Suatu Graf G terdiri dari 2 himpunan yg berhingga yaitu himpunan titik tidak kosong dan himpunan garis
Suatu grs berhubungan dg satu titik atau dua titik (titik –titik tsb dsbut titik ujung), grs yg berhub. dg satu titik ujung disebut LOOP, dua grs yg beda menghubungkan ttk yg sama disebut Garis Paralel.
Dua titik dikatakan berhubungan jika ada garis yg menghubungkan keduanya
Titik yg tdk memiliki garis yg berhubungan dgnya dsbut Titik Terasing
Graf yg tidak memiliki titik (shingga tdk memiliki garis) dsbut Graf Kosong
Panjang garis , kelengkungan garis srta letak ttk tdk berpengaruh dlm suatu graf
Graf berarah jika semua garisnya berarah, dan sebaliknya
Contoh
Ada 7 kota yaitu A,B,C,D,E,F, dan G yang beberapa diantaranya dpt berhubungan langsung dg jalan darat , hubungan2 langsung yg dapat dilakukan sbb; A dg B dan D; B dg D; C dg B; E dg F . Buatlah graf nya
Jawab…
2. Diketahui graf (a) V(G)={ …………..}
E(G)={…………}
v6
Tentukan
Himpunan titik, himpunan garis, titik-titik ujung masing-masing garis, dan garis paralel
Loop dan titik terasing
Jawab…..
3. Gambarlah graf G dg titik V(G)= { v1, v2, v3, v4} dan garis E(G)= {e1, e2, e3, e4, e5} dg titik-titik ujung berikut
garis titik ujung
e1 { v1, v3}
e2 {v2, v4}
e3 {v1}
e4 {v2, v4}
e5 {v3 }
Jawab
Salah satu graf yg dapat dibentuk bila diketahui himpunan titik V(G)= { v1, v2, v3, v4} dan garis E(G)= {e1, e2, e3, e4, e5} adalah sbb
( A) v2 (B)
v1 v3
v4
Catatan: jika diketahui graf pasti himpunan titik, garis serta titik ujungnya adalah tunggal
4. Ada sebuah pulau yg penghuninya hanya terdiri dari dua macam yaitu pemakan orang dan pemakan sayuran dimana ada 2 orang pemakan orang dan 2 orang pemakan sayuran di sisi barat sungai. Di sisi barat sungai itu terdapat perahu kecil yg dapat menampung paling banyak 2 orang.
Pertanyaan bagaimana cara mengangkut 4 orang tsb kesisi timur sungan dg syarat jumlah pemakan manusia pada suatu sisi sungai tdk boleh lebih banyak dari pemakan sayuran ( sama boleh)
Jawab
Menggambarkan semua kemungkinan keadaan, dan kemudian menghilangkan keadaan yg tidak boleh terjadi
Misal s= pemakan sayuran
o=pemakan orang posisi berubah
p=perahu jml pemkan org timur(kanan)
/= sungi posisi tdk berubah
arah perjalanan tidak boleh pada pada satu sisi (warna sama)
Jadi didapat cara pengangkutan 0 1 2
Oossp/ ke ss/poo ke ossp/o ke
0/poss ke oop/ss ke /pssoo
0
jml pemakan sayur timur(kanan)
Graf Tak Berarah
Graf Bipartite
Graf sederhana adalah graf yang tidak memiliki loop ataupun garis paralel
Contoh
Ambarlah semua graf sederhanayang dibentuk dari 4 titikV(G) = {a, b, c, d) dan 2 garis
Jawab
Setiap garisselalu berhubungan dg 2 titik maka kemungkinan banyak garisnya adl
Yagn berbentuk E(G) = {a,b}, {a, c},{a, d},{b, c}, dan {c, d} dari 6 garis ini diambil = = 6
2 garis maka garis yg mungkin aalah sebanyak = = 15 macam graf
a b
c d Dan seterusnya cari sendiri yg 14 lainnya!!!!
Graf Lengkap dgn titik dinotasikan dg Kn
Adalah graf sederhana dg n titik dimana setiap 2 titik yg beda dihubungkan dgsuatu garis
Banyaknya garis pd graf lengkap dg n titik adalah buah garis
#suatu graf disebut graf bipartite apabila V(G) merupakan gabungan 2 himpunan yg tidak kosong V1 dan V2 dan setiap garis dalam G menghubungkan suatu titik dalamV1 dg titik dalam V2
# graf bipartite lengkap (Kmn) adalah graf bipartite setiap titik dalam V1 berhubungan dg setiap titik dalam V2
Contoh
Tentukan mana diantara graf-graf berikut yg merupakan graf bipartite dan graf bipartite lengkap
Jawab (a) adalah graf bipartite lengkap (K32) (b) adalahgraf bipartite
(c) adalah graf bipartite (d) grafnya sama dg point (a)
Catatan semua graf soal diatas titik-titiknya dapat dibagi menjadi 2 bagian
Komplemen Graf
Komplemen suatu graf G dinotasikan dg Ĝ dengan n titik adalah suatu graf sederhana dengan
Titik –titik Ĝ sama dg titik G jadi V(G)=V(Ĝ)
Garis –garis Ĝ adalah komplemen garis-garis G terhadap graf lengkapnya (Kn)
E(Ĝ)= Kn) – E(G)
berarti titi-titik yg dihubungkan dg garis dalam G tidak terhubung dalam Ĝ dan sebaliknya titik-titik yg terhubung dalam G menjadi tdk terhubung dalam Ĝ(dg kata laingaris yg ada pada G tidak ada pada Ĝ)
Contoh
Gambarlah komplemen graf G yg didefinisikan dalam gambar berikut
(a) (b) (c)
Jawab
(a) (b) (c)
Sub Graf
Misalkan G adalah suatu graf . Graf Hdikatakan subgraf G bila hanya bila
V(H)V(G)
E(H)E(G)
Setiap garis dalam H memiliki titik ujung yg sama dg garis tersebut dalam G
Contoh
v2
diketahui graf –graf dibawah, tentukan apakah H merupakan sub graf G ?
v2
a)
v3
v1
v3
G H
Jawab
V(H) = { v2, v3} dan V(G)= = { v 1, v2, v3} sehingga V(H)V(G)
E(H)= { e4} dan E(G)= { e 1, e2, e3, e4} sehingga V(H)V(G)
Garis e4 di H merupakan loop pada titik v2 dan garis e4 juga di G merupakan loop pada ttk v2 jadi H merupakan subgraf G
b) v1 v2 v1 v2
v3 v3
G H
Jawab
H bukan merupakan subgraf G krn meskipun V(H)=V(G)= { v 1, v2, v3} dan E(H)=E(G)= { e 1, e2, e3, e4} tetapi garis e4dalam H tdk menghubungkan ttk yg sama dg garis e4 dalam G yaitu dalam H garisnya merupakan loop di ttk v3 sedang dalam G garisnya merupakan loop di ttk v2
c)
Jawab
Karena graf H= graf G, maka H merupakan subgraf G
Derajat
Misalkan v adalah titik dalam suatu graf G. Derajat titik v yang disimbulkan d(v) = jumlah garis yg berhubungan dg titik v dan garis suatu loop dihitung dua kali. Derajat total G adalah jumlah derajat semua titik dalam G.
Contoh
Tentukan derajat tiap-tiap titik pada graf dibawah dan berapa derajat totalnya
Jawab
d(v1) = 4 , d(v2) = 2 , d(v3) = 1 , d(v4) = 1 , d(v5) = 2 , d(v6) = 0
i=1
Derajat total = ∑6 d(vi) = 10
#dalam sembarang graf, jumlah titik yg derajat ganjil adalah genap
Contoh
Gambarlah graf dg ketentuan sbb
Graf dg 4 titik dg derajat masing-masing 1, 1, 2, dan 3 (tdk dapat dibuat graf krn derajat total gaji)
Graf dg 4 titik dg derajat masing-masing 1, 1, 3, dan 3 (dapat dibuat antara lain coba sendiri)
Graf dg 4 titik dg derajat masing-masing 1, 1, 2, 2, 2, 4, 4, 4, dan 6 (tdk mungkin krn 3 titik derajat ganjil)
Graf dg 4 titik dg derajat masing-masing 1, 1, 3, dan 3 (tdk mungkin krn grafnya bentuk sederhana)
Path dan serkuit
Walk dari v kew adl barisan titik-titik yang berhubungan dan garis berselangselung diawali titik v dan diakhiri titik w
Walk dg panjang n dari v ke w
Ditulis sebagai :v= v0e1v1e2v2e3v3…………..envn= w dg vi=1 dan vi adl titik-titik ujung garis ei
Path dg panjang n dari v ke w adl walk dari v ke w dg semua garisnya berbeda
Ditulis sebagai :v= v0e1v1e2v2e3v3…………..envn= w dg ei≠ej
Path sedrhana dg panjang n dari v ke w adl path dari vke w (semua garisnya berbeda), titik-titiknya berbeda
Ditulis sebagai : v=v0e1v1e2v2e3v3…………..envn= w dg ei≠ej dan vk ≠ vm
Serkuit dg panjang n adl path (semua garisnya berbeda), dg titik awal dan titik akhir yang sama
Ditulis sebagai : v0e1v1e2v2e3v3…………..envn= v0
Serkuit sederhana dg panjang n adl serkuit yg semua titik-titiknya berbeda
Ditulis sebagai : v0e1v1e2v2e3v3…………..envn= v0 dg ei≠ej dan vk ≠ vm
Contoh
Contoh
Tentukan mana diantara baris titik dan garis pd gambar dibawah yg merupakan walk, path, path sederhana, sirkuit, dan sirkuit sederhana.
a) v1e1v2e3v3e4v3e5v4
b) v1e1v2e3v3e5v4e5v3e6v5
c)v2e3v3e5v4e10v5e6v3e7v6e8v2
d) V2e3v3e5v4e10v5e9v6e8v2 e) v1 jawab terlihat sirkuit sederhana krn …….
Jawab
a)Terlihat garisnya berbeda-beda yaitu e1,e3,e4,3e5 sedangkan titik ada yg sama maka dsbut PATH, dg panjang 4 dari v1 ke v4
b)Terlihat bahwa garisnya ada yg sama yaitu e5 berarti WALK dg panjang 5 dari V1 ke v5
c) Terlihat garisnya berbada yaitu e3e5e10e6e7e8sedangkan titiknya ada yg sama letaknya di tengah , titik awal dan akhir sama berarti serkuit saja dg panjang 6
d)Terlihat garisnya berbeda-beda, barisan, di awal dan akhir dg titik sama, semua titiknya berbeda berarti merupakan SIRKUIT SEDERHANA
Sirkuit Euler
Adalah sirkuit dimana setiap titik dlm graf muncul paling sedikit sekali , dan setiap garis dlm graf muncul satu kali.
Contoh
Kota Konigsberg terletak pada pertemuan 2 cabang sungai Prigel. Kota tersebut terdiri dari sebuah pulau ditengah-tengah ditengah-tengah dan ada 7 jembatan yg mengelilinginya menghubungkan 4 daerah . Masalahnya mungkinkah seorang berjalan mengunjung 4 kota tsb yg diawali dan diakhiri pada tempat yg sama, dg melintasi 7 jembatan masing-masing tepat satu kali? Apakah termasuk sirkuit Euler?
Jawab misal 4 daerah adalah 4 titik yaitu v1 ,v2 ,v3 ,v4
misal 7 jembatan adlah 7 garis yaitu e1e2e3e4e5e6e7
Dibuat graf sbb v1
v2 v3
jadi dpt disimpulkan bahwa berjalan mgunjngi 4 kota
tidak mungkin tepat satu kali melintasi jembatan.
V4
Graf terhubung dan tidak terhubung
Dua titik dalam graf dikatakan terhubung bila hanya bila ada walk antara dua titik tsb
Graf G dikatakan terhubung bila hanya bila setiap 2 titik dalam graf G terhubung.
Graf G dikatakan TDK terhubung bila hanya bila ADA 2 titik dlm graf G tdk terhubung.
Contoh
Diketahui graf G sbb
a b c
Jawab
Teorema
Graf G terhubung dikatakan Sirkuit Euler bila hanya bila semua titik dalam G mempunyai derajat genap.
Contoh
a)
b) # syarat graf G terhubung : tdk di penuhi krn ada 2 titik tdk terhubung
c) jawab merupakan sirkuit euler krn terhubung tiap ttk derajat genap
Contoh
Diketahui sebuah rumah beserta pintu dan ruangan-ruangannya sbb
A B C
H G D
F E
Mungkinkah seseorang keluar rumah (pintu 10) dan mengunci semua pintu dimulai dari pintu 1?, dg ketentuan pintu yg sdah dikunci sebelumnya tdk boleh dilewati
Jawab
Misal ruangan dinyatakan titik dan pintu dinyatakan dg garis dan ruangan A dg E dihubungkan
dg pintu semu sh g didapat graf sbb apakah graf tsb euler?
jawab kecuali titik A dan E , semua titik mempunyai derajat genap
dan grafnya terhubung jadi graf tsb adl graf Euler
Sirkuit Hamilton
Suatu graf terhubung disebut Sirkuit Hamilton bila ada sirkuit setiap titiknya dikunjungi sekali (kecuali titik awal yg sama dgtitik akhir) dan garisnya tdk semuanya harus dilalui.
Catatan
1)Sirkuit Euler setiap garisnya harus dilalui sekali , titiknya boleh dikunjungi lebih dari satu kali
2)Petunjuk untuk menentukan graf adl sirkuit hamilton adl memiliki sub graf H dg sifat
i) H terhubung
ii)H memuat semua titik G
iii) H memiliki jumlah garis yg sama dg jumlah titiknya
iv) setiap ttk dalam H mempunuai derajat 2
Contoh
Gambar berikut menyatakan peta beberapa kota (A…..G) beserta jalan yg menghubungkan kota-kota tsb seseorang salesmen hendak mengunjungi setiap kota masing2 sekali dimulai dr kota A . Carilah
Jalan yg dilalui jawab
C
B
F E
A D
G
terlihat graf H tsb sifat i) ii) iii) dan iv) dipenuhi jadi graf G tsb adlah sirkuit Hamilton
dg coba-coba didapat jalur yg mungkin adl ABFECDGA atau ABCFEDGA(buat grafnya)
Contoh
Buktikan graf berikut bukan sirkuit Hamilton
a b a c
e d c b
f g e d
Jawab
a) Syarat sirkuit hamilton bila graf G mempumyai sub graf H memiliki sifat
H memuat semua titik dalam dalam G
terpenuhi karena bisa diambil semua
ii) Jumlah garis dalam H sama dg jumlah titiknya tinggal menghilangkan tetapi ada kaitannya dg sarat iii)
iii) Semua titik dalam H berderajat 2 tidak terpenuhi karena titik B dan G derajat 3 salah satu garisnya harus dihilangkan padahal jml garis 8, dg menghilangkan dua maka jml garis dalam H menjadi 6 jadi tidak mungkin sub graf H memuat 7 garis
b) Ttk b derajat 4 maka 2 grs hrs dihilangkan, akan tetapi mengakibatkan titik lain derajatnya menjadi 1 jadi tidakmungkin terpenuhi terbukti bukan sirkuit hamilton
Suatu Graf berarah G terdiri dari
Himpunan titik-titik V(G) = {v1, v2, ….} , himpunan E(G) = {e1,e2} dan suatu fungsi Ψ yg mengawankan setiap garis dalam E(G) ke suatu pasangan berurutan titik (vi, vj)
# jika ek = (vi, vj) adalah suatu garis dalamG, maka vi disebut titik awal, dan vj disebut titik akhir, arah garis dari vi ke vj
# jumlah garis yg keluar dari titik vi disebut derajat keluar titik vi. dinotasikan d+ (vi) sedangkan garis yang masuk ke titik vi disebut derajat masuk titik vi. Dinotasikan d-(vi)
# titik terasing dalamG derajat masuk dan keluarnya adalah 0
# titik pendan dalam G jumlah derajat masuk dan keluarnya adalah 1
# dua garis berarah disebut paralel bila keduanya memiiki titik awal dan titik akhir yg sama
Contoh
Jawab
V(G) = {v1, v2, v3, v4, v5, v6}
E(G) = { e1, e2, e3, e4, e5, e6, e7, e8, e9}
Fungsi mengawankan garis-garis dg titik-titik adalah e1 dengan (v1, v2) dst….
Path berarah dan Sirkuit berarah
Path berarah dan sirkuit berarah sama saja dg path dan sirkuit tdk berarah hanya bedanya dalam graf perjalanan yg dilakukan harus mengikuti arah garis.
Suatu graf berarah tetapi tidak memuat sirkuit berarah disebut Asiklik
Contoh
Tentukan path terpendek dari titik E ke B pd graf berarah berikut
A E
C G
B F
D H jawab ada beberapa path berarah dari E ke B yg dapat dilakukan adalah EACDB dan EAB terlihat path terpendek adalah EAB dg panjang 2
Contoh
diketahui graf AB
apakah graf tsb sirkuit
A B
C
terlihat graf berarah tsbt tdk ada sirkuit berarah jadi graf Asiklik
Graf berarah terhubung
Graf G berarah disebut terhubung kuat jika ada paht untuk sembarang 2 titik dalam G
Graf G berarah disebut terhubung lemah jika tidak terhubung kuat, ttp graf tak berarah yg bersesuaian dg graf G terhubung
Contoh
Tentukan apakah graf G berikut terhubung kuat atau lemah
a) b)
jawab
Terlihat setiap 2 titik dapat dihubungkan dg path berarah jadi graf tsb adl graf terhubung kuat
Tidak ada path berarah yg menghubungkan titik v4 ke titik v3 , akan tetapi jika arah semua garis dihilangkan maka graf tsb merupakan graf terhubung, jadi graf tsb adl graf terhubung lemah
Reprentasi Graf dalam Matriks
Matriks dapat digunakan untuk menyatakan graf, hal ini dapat membantu pembuatan program komputer yg berkaitan dg graf, sehingga memudah kan dalam perhitungan .
Kesulian graf di buat dalam bentuk matrik adalah keterbatasan bentuk matriks dalam menyerap semua informasi akibatnya ada bermacam-macam matrik dalam nenyatakan graf tertentu
Representasi graf tak berarah dlm matriks
1. Matrik Terhubung
adalah digunakan menyatakan graf dg cara menyatakan jumlah garis yg menghubungkan titik titiknya, jumlah baris/kolom dalam matrik sama dg jumlah titik dalam graf
Definisi
G adl matrik tak berarah dg titik-titik v1 v2……vn, matriks hubung yg bersesuaian dg graf G adalah A=(aij) dimana aij= jumlah garis yg menghubungkan titik vi ke titik vj ; i,j=1,2,…..n
Graf tak berarah bentuk matriknya adalah matriks simetris
Contoh
Nyatakan graf berikut dalam matriks hubung
a) b)
jawab
A) b)
Ada beberapa hal yg dapat digunakan dalam matriks hubung
Loop pada titik v1 yg bersesuaian dg an = 1, graf tidak memiliki loop diagonal utamanya = 0
Dapat dipakai mendeteksi graf tidak terhubung secara mudah. Suatu graf tidak terhubung terdiri dari k komponen bila hanya bila matrik hubungnya berbentuk
Derajat titik v1 adalah jumlah komponen matriks kolom/ baris ke i. Elemen diagonal dikalikan 2
Dapat dipakai untuk mendeteksi graf bipartet (Kmn), bila matriks hubung berbentuk
Dimana O = matrik yg semua elemennya nol
Im = matriks ukuran m x n yg semua elemenya =1
In = matriks ukuran n x m yg semua elemennya = 1
Dapat dipakai untuk mendeteksi graf lengkap ini terjadi bila dan hanya bila semua elemennya diagonal utamanya nol, sedangkan elemen diluar diagonal = 1
Juga dapat menghitung banyaknya kemungkinan walk dg panjang n dari titik vi ketitik vj adalah elemen aij dari matriks hubung An
Contoh
Diketahui graf G sbb
v1
v2
v3 hitunglah jumlah walk dg panjang 2 dari titik v2 ke v1
jawab
matrik hubung A yang bersesuaian dengan graf G adalah
A = untuk menghitung walk dg panjang 2, hitung dulu A2
A2 = A x A = =
Jadi walk dari v2 ke v1 dg panjang 2 adalah elemen an pada A2 yaitu 6 buah cara. Walk tersebut didapat dengan coba-coba yaitu v1 e1 v1 e1 v1, v1 e2 v2 e2 v1,……….. teruskan
Matriks Biner
Matriks biner yg bersesuaian dg graf G tanpa loop dg n titik dan k garis adalah matriks A ukuran nxk yg elemennya adalah
aij= 1 jika titik vi berhubungan dg garis ej .
0 jika titik vi tidak berhubungan dg garis ej .
Contoh
Diketahui graf G sbb
tentukan matriks binernya dan derajat totalnya
Jawab
Ada 6 titik dan 8 garis dalam graf G, maka matriks A yg bersesuaian dg graf G tersebut berukuran 6×8 ( 6 baris dan 8 kolom)yaitu
d(v1)=1+0+0+0+0+1+0+0= 2 A=
d(v2)= 4, d(v3)=1, d(v4)=4
d(v5)=3, d(v6)=2
Jadi derajat totalnya adalah 16
Ada beberapa yg didapat pada matriks biner sbb
Ada korespodensi satu satu antara graf G dan matriks biner A
Setiap garis berhubungan dg dua titik (krn tdk memiliki loop), shingga setiap kolom ada 2 buah elemen 1 lainnya 0.
Jumlah elemen baris ke i adalah derajat titik vi , sedangkan derajat total graf G adalah jumlah semua elemen pd matriknya
Jika semua elemen pada baris ke-i adalah 0, maka titik vi, adalah titik terasing
Dua kolom elemennya sama menyatakan garis yg paralel.
3. Matrik Sirkuit
Matriks sirkuit A= (aij) yg bersesuaian dg graf G yg memuat q sirkuit sederhana dan e buah garis adalah matrik yg terdidri dari q baris dan e kolom dg elemen sbb
aij = 1 jika sirkuit ke i memuat garis ke j
0 jika sirkuit ke i tidak memuat garis ke j
Contoh
Tentukan matriks sirkuit yg sesuai dg graf diatas.
Jawab
Graf tsb ada 8 garis (e1 e1 e1 e1 e1 e1 e1 e1 ) dan 4 sirkuit ( s1 s1 s1 s1 s1 s1 ) sederhana masing masing s1 =e7 s8 , s2 = e3 e4 e5 ; s3 = e1 e4 e6 ; s4 = e1 e3 e5 e6
Selanjutnya didapat matriks sirkuit sbb
e1 e1 e1 e1 e1 e1 e1 e1
A = s1
s1
s1
s1
Representasi Graf Berarah Dalam Matriks
Hampis seperti graf tdk berarah , bedanya hanya terletak pada informasi tentang arah garisnya
1 Matriks hubung
Matriks hubung yg sesuai dg graf berarah G yg terdiri dari n titik tanpa garis paralel adl matriks bujur sangkar n x n , yaitu A = (aij )dengan
aij = 1 jika ada garis dari titik vi ke titik vj
0 jika tidak ada garis dari titik vi ke titik vj
Contoh
Nyatakan graf dibawah ke dalam matriks hubung
v1 v2
v3
v4 v5
Jawab graf terdiri dari 5 titik sehingga matrik hubungnya v1 v2 v3 v4 v5
adalah matriks bujur sangkar 5 x 5 A = v1
v2
v3
v4
v5
Ada beberapa hal yg dapat digunakan pada matriks hubung untuk graf berarah
Banyaknya garis yg keluar dari vi (derajat keluar) sama dg banyaknya elemen 1 pd baris ke i dan banyaknya garis yg mesuk dari vi (derajat masuk) sama dg banyaknya elemen 1 pd kolom ke i .banyak totalgaris pada G adl banyaknya elemen 1 pada matriks hubungnya.
Graf tdk memiliki loop semua elemen diagonalnya nol, jika ada loop pada ttk vi elemen aii =1.
Graf tdk terhubung yg terdiri dari k komponen matriks hubungnya berbentuk
dimana O=matrik semua elemennya 0
A= matriks hubung komponen ke i bent bjr sangkar
Pohon (Tree)
Pohon merupakan salah satu kasus husus graf, dan ini banyak dipakai dalam struktur data
Definisi
Pohon adalah graf sederhana G bila G terhubung dan tdk memuat sirkuit
Pohon semu adalah pohon yg terdiri dari satu titik
Hutan adalah graf sederhana G bila tdk terhubung dan tidak memuat sirkuit
Contoh
Tentukan apakah graf G berikut poho atau hutan
a) c)
jawab merupakan hutan krn graft dk trhubung
Jawab merupakan pohon krn grafnya terhubung dan tdk ada sirkuit
b)
Jawab bukan merupakan pohon karena ada sirkuit
Definisi
Daun (terminal vertex)adalah pohon T yg mempunyai derajat 1
Cabang (interval vertek) adalah pohon T yg mempunyai derajat lebih besar 1
Contoh
Tentukan daun dan cabang pada pohon T berikut
jawab mencari derajat masing masing titik dalam pohon T
d(v1)=2; d(v3)=2 ; d(v3)=3
d(v4)=1; d(v5)=1; d(v6)=1; d(v7)=1 ; d(v8)=1 d(v1)=2
berarti daunnya adalah v4, v5, v6 v7 v8
titik cabangnya adalah v1 ,v2 ,v3
Teorema : Pohon T dg n titik akan memiliki (n-1) garis
Misal T’ adalah pohon sprti T tetapi titik dan garisnya masing2 dikurangi 1
P(k) adalah pohon dg k titik berarti ada k-1 garis
Jumlah garis dalam T = jumlah garis dalam T’ + 1
= (k-1) + 1 = k
Jadi terbukti pohon Tadl pohon dg (k+1) titik memiliki k garis
Pohon Berakar dan Pohon Biner
Definisi
Pohon Berakar adalah suatu pohon dimana ada suatu titik dihususkan dari yg lain, titik husus itu disebut akar.
Tingkat suatu titik adalah banyaknya grs antara titik tersebut dg akar
Tinggi pohon adalah tingkat maksimum yg dimiliki titik-titik pada pohon
Anak dari titik v adalah semua titik yg berhubungan langsung dg titik v ttp yg memiliki tingkat yg lebih tinggi dari v, sedangkan v disebut orang tua
Dua titik memiliki orang tua yg sama disebut saudara(sibling).
Contoh
Perhatikan graf G berikut jawab
Dg v2 sbg akar a) tingkat v4adl jml grs antara v4dg akar =1
Tentukan tingkat v1=tingkat v6=tingkat v5=1
tingkat v3= 2, tingkat v7=tingkat v8=3
Tingkat tiap-tiap titik b)tinggi pohon(ttk terjauh dari akar) adl 3
Tinggi pohon
Anak, orang tua, saudara v1. c)anak v1 adalah v3, orang tua v1 adl v2
Pertanyaan a,b, c untuk akarnya v1 saudara v1adl v4, v5,dan v6
Definisi Pohon Biner
Pohon biner adl pohon berakar yg setiap titiknya memiliki paling banyak 2 anak
Pohon biner penuh adl pohon biner yg setiap titiknya memiliki 2 anak
Dapat digunakan untuk menyatakan ekspresi aljabar dal pohon biner dg cara sbb
Contoh
Ekspresi aljabar x/y kalau dibuat bentuk pohon biner adalah
Contoh
Nyatakan ekspresi aljabar berikut dalam pohon biner
Pohon Rentang
merupakan salah satu bentuk husus dari pohon
Definisi
Pohon rentang suatu graf terhubung G adl subgraf G yg merupakan pohon dan memuat semua titik dalam G
Dari definisi dapat dijelaskan bahwa garisnya bisa ada yg dihapus agar menjadi pohon, tetapi jika tidak ada sirkuit berarti graf G itu sendiri langsung menjadi pohon rentang
Suatu graf bisa memiliki pohon rentang yg berbeda tetapi yg jelas dari pohon rentang tsb memiliki jumlah garis yg sama yaitu (k-1) dimana k adalah jumlah titik pada graf.
Contoh diketahui graf berikut , buatlah pohon rentangnya
Jawab
Caranya menghilangkan garisnya satu persatu agar tidak ada sirkutnya ..
GRAF BERLABEL
Adalah graf yg setiap sisinya diberi bobot, Misal: bobot sisinya tentang jarak, biaya, waktu antar 2 kota, waktu tempuh pesan antar simpul komunikasi (dlm jaringan komputer) dsb.
contoh
Dalam suatu propinsi ada 8 kota (A,B,C,D,E,F,G,H)yg akan dihubungkan dg jaringan listrik yg mungkin dibuat antar dua kota sbb
garis Kota yang dihubungkan Biaya per satuan
e4
e4
e4
e4
e4
e4
e4
e4
e4
e4
e4 B ke C
D ke F
A ke G
C ke D
C ke E
A ke B
A ke D
F ke H
G ke H
E ke F
F ke G 3
4
5
5
5
15
15
15
15
15
18
Nyatan masalah tsb dalam graf berlabel
Buatlah matriks hubungnya
LINTASAN MINIMUM
Lintasa minimum dipilih dari simpul tertentu kesemua simpul yg lain.
Algoritma Dijktra
Misal: ada n buah simpul
dg matrik ketetanggan M = [ m ij ] dimana m ij= bobot sisi (i,j) pd graf tak berarah m ij = mji, , mii=0 , dan m ij = θ
Larik S = [si ] dimana si=1 temasuk lintasan terpendek
si=0 tdk masuk lin. Terpendek
larik/tabel D=[di] dimana di=panjang lin dr awal s ke simp. i
Langkah-langkah mencari lintasan terpendek
#Langkah 0 (inisialisasi)
-Inisialisasi si=0 dan di=mai ,unt. i=1,2,…..n nilai a sdh ada, untu mengisi baris selanjutnya
# langkah 1:
– isikan sa=1(krn simpul a adl simpul asal jadi sdh pasti terpilih)
isikan da=∞(tdk ada path terpendek dari a ke a )
Langkah 2,3,…(n-1)
– cari j sedemikian hingga sj=0 dan dj=min{ d1,……dn} didapat kolom yg diinginkan
– isi sj dgn 1 untuk mengisi baris selanjutnya
– perbarui di, unt. i=1,2,3,….n dgn ketentuan sbb
di(baru)=min{di (lama),dj+mji} nilai j sudah tertentu(ada)
contoh
Diketahui graf berarah yg menyatakan jarak antar kota di pulau jawa sbb
E
D
B C
F
A G Tentukan path minimumnya
H
jawab .
matriks hubungnya sbb
F
G
Simpul awal E, dengan tabulasi berikut
pilih lintasan S D
Simpul 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8
– – 0 0 0 0 0 0 0 0 – – – 1500 0 250 – –
5 5 0 0 0 0 1 0 0 0 – – – 1500 – 250 – –
6 5, 6, 0 0 0 0 1 1 0 0 – – – 250+1000 – 250 250+900 250+1400
7 5, 6, 7 0 0 0 0 1 1 1 0 – – – 1250 – 250 1150 1650
4 5, 6, 4 0 0 0 1 1 1 1 0 – – 1250+1200 1250 – 250 1150 1650
8 5, 6, 8 0 0 0 1 1 1 1 1 1650+1700 – 2450 1250 – 250 1150 1650
3 5, 6, 4, 3 0 0 1 1 1 1 1 1 3350 2450+800 2450 1250 – 250 1150 1650
2 5, 6, 4, 3, 2 0 1 1 1 1 1 1 1 3350 3250 2450 1250 – 250 1150 1650
1 5, 6, 8 , 1 1 1 1 1 1 1 1 1 3350 3250 2450 1250 – 250 1150 1650
Jadi path minimum dari
5 ke 6 adalah 5, 6 dengan panjang 250
5 ke 7 adalah 5, 6, 7 dengan panjang 1150
5 ke 4 adalah 5, 6, 4 dengan panjang 1250
5 ke 8 adalah 5, 6, 8 dengan panjang 1650
5 ke 3 adalah 5, 6, 4, 3 dengan panjang 2450
5 ke 2 adalah 5, 6, 4, 3, 2 dengan panjang 3250
5 ke 1 adalah 5, 6, 8, 1 dengan panjang 3350
BAB 6 FUNGSI
Fungsi merupakan kejadian husus dari relasi.
Definisi
Misalkan A dan B adalah Himpunan . Relasi biner f dari A ke B disebut suatu fungsi jika untuk setiap elemen a didalam A terdapat satu elemen tunggal b didalam B sedemikian hingga (a,b) Є f. ditulis f(a)=b. Jika f adalah fungsi dari A ke B , ditulis f: AB yang artinya f memetakan A ke B.
Jika f adalah fungsi dari A ke B , A disebut daerah asal (domain) dari f, dan B disebut daerah hasil (kodomain/range) dari f
Jika f(a)=b , maka a dinamakan prabayangan dari b, b dinamakan bayangan dari a
A B
a f b
contoh gambar fungsi f memetakan A ke B
contoh
1. Diketahui f={(1,u), (2,v), (3,w)} dari A={1,2,3} ke B={u, v, w}
2. Diketahui f={(1,u), (2,v), (3,w)} dari A={1,2,3, 4} ke B={u, v, w}
3. Diketahui f={(1,u), (1,v),(2,v), (3,w)} dari A={1,2,3, 4} ke B={u, v, w}
4. Diketahui f={(1,u), (2,u), (3,v)} dari A={1,2,3, 4} ke B={u, v, w}
Tentukan apakah f merupakan fungsi
Jawab
1. f adalah fungsi dari A ke B, karena daerah asal f adalah A dan daerah hasil B
2. f adalah bukan fungsi dari A ke B, karena daerah asal f adalah {1,2,3} tidak sama dengan A
3. f adalah bukan fungsi dari A ke B, karena 1 dalam A dipetakan ke dua buah elemen dalam B
4. f adalah fungsi dari A ke B , meskipun u didalam B merupakan bayangan dari dua elemen dalam A.
Fungsi Injektif (satu-satu), surjektif (pada/onto), bijektif (berkoresponden sau-satu)
A. Fungsi f disebut injektif jika tidak ada dua elemen dari himpunan A yang memiliki bayangan yang
Sama. Dengan kata lain , jika a dan b anggota dari himpunan A, maka f(a)f(b)
Gambar fungsi satu-satu
Contoh
1. Diketahui f={(1,w), (2,u), (3,v)} dari A={1,2,3} ke B={u, v, w,x}. tentukan apakah fungsi satu-satu?
2. Diketahui f={(1,w), (2,u), (3,v)} dari A={1,2,3} ke B={u, v, w}. tentukan apakah fungsi satu-satu?
3.Diketahui f={(1,u), (2,u), (3,v)} dari A={1,2,3} ke B={u, v, w}. tentukan apakah fungsi satu-satu?
Jawab
1. f adalah fungsi satu-satu
2. f adalah fungsi satu-satu
3. f adalah bukan fungsi satu-satu karena f(1)=f(2)=u
B. Fungsi f disebut surjektif (pada/onto) , jika setiap elemen himpunan B merupakan bayangan dari
Satu atau lebih dari elemen himpunan A. Dengan kata lain fungsi f adalah surjektif
Bila semua elemen B merupakan daerah hasil dari f
A B
Contoh
1.Diketahui f={(1,u), (2,u), (3,v)} dari A={1,2,3} ke B={u, v, w}. apakah f fungsi surjektif/pada?
2. Diketahui f={(1,w), (2,u), (3,v)} dari A={1,2,3} ke B={u, v, w}. apakah f fungsi surjektif?
Jawab
1. f adalah bukan fungsi surjektif karena w tidak ada dalam daerah hasil
2. f adalah fungsi surjektif.
C. Fungsi disebut bijektif(berkoresponden satu-satu), jika fungsinya injektif dan surjektif
Contoh
Diketahui f={(1,u), (2,v), (3,w)} dari A={1,2,3} ke B={u, v, w}
Jawab
F adalah fungsi bijektif karena f tersebut injektif (satu-satu)dan surjektif (pada).
Fungsi Invers
Misalkan f: A B adalah suatu fungsi , jika f fungsi bijektif (korespodensi satu-satu) , maka dapat menemukan inversnya dari f yang dilambangkan dengan notasi f-1. Misalkan a dalah elemen dari himpunan A dan b adalah elemen dari himpunan B, maka f-1(b)= a jika f(a)= b
Contoh
Diketahui f={(1,u), (2,v), (3,w)} dari A={1,2,3} ke B={u, v, w}. Tentukan f-1
Jawab
f-1 ={(u, 1), (v, 2), (w, 3)}
contoh
diketahui f: A A dengan f(a)=a+2 .Tentukan f-1
jawab
b=f(a) = a+2
a= b-2
f-1(b)= a = b-2, selanjutnya variabelnya ditukar sehingga didapat f-1(a)=a-2
Fungsi Komposisi
Jika ada beberapa fungsi , fungsi-fungsi tersebut bisa dikomposisikan untuk menghasilkan fungsi yang baru. Misalakan g adalah fugnsi dari himpunan A ke himpunan B , dan f adalah fungsi dari himpunan B ke himpunan C . Komposisi f dan g, dinotasikan dengan ( f0 g ) adalah fungsi dari A ke C yang didefinisikan oleh
(fog)(a)= f(g(a))
A B C
g f
f0g gambar fungsi komposisi
contoh
Diberikan fungsi g= {(1, u), (2, u), (3, v)} yang memetakan dari A={1, 2, 3} ke B={ u, v , w}
Dan fungsi f ={(u, y), (v, x), (w, z)} yang memetakan dari B={ u, v , w} ke C ={ x, y, z}
Tentuka fungsi (f0g)
Jawab
(f0g) = {(1, y), (2, y), (3, x)}
Contoh 2
Diketahui fungsi g(x)=x+1 dan f(x)= x2
a. tentukan (f0g)(x) b. tentukan (f0f)(x) c. tentukan apakah (f0g)(x) = (g0f)(x)
jawab
a) (f0g)(x) = f(g(x))= f(x+1)2
b) (f0f)(x) =f(f(x))= f(x+1)= (x+1) + 1 = x+2
c) (g0f)(x) = g(f(x))=g(x2)= x2+1 terlihat bahwa (f0g)(x) (g0f)(x)
Latihan
Soalinjektif dan invers belum
1. Diketahui diagram panah berikut;
a) b)
c) d)
Tentukan apakah diagram tersebut fungsi atau bukan, kalau bukan jelaskan.
2. Misalkan A={1,3,5} dan B= {s, t, u, v} dan diketahui fungsi f: A B yang dinyatakan dengan
Diagram berikut;
A B
s
3
1
t
5
u
v
a) Tentukan daerah asal dan kodomain f
b) carilah f(1), f(3), dan f(5) c) tentukan range(daerah hasil) f
3. Misalkan A={1, 5, 9} dan B= {3, 4, 7}
a) Diketahui f: A B dengan f(1)=4, f(5)= 7 dan f(9)= 4 . Apakah injektif, surjektif, bijektif ?
b) Diketahui g: A B dengan g(1)=7, g(5)=3 dan g(9)= 4. Apakah injektif, surjektif, bijektif ?
4. Misalkan A adalah himpunan asli, diketahui f: (AXA) A yang didefinisikan f(x,y)= x+y
Apakah fungsi f injektif ?
5. Misalkan f adalah fungsi dari A={0, 1, 2, 3, 4, 5} ke A yang didefinisikan oleh f(x)=4x mod 6. Tentukan f sebagai himpunan pasangan terurut. Apakah f satu-satu
6. Untuk semua bilangan riil a, didefinisikan f dan g yaitu f(a)=a3 , g(a)=a – 1
Carilah f0g dan g0f
7. Diberikan fungsi g= {(1, b), (2, c), (3, a)} yang memetakan dari A={1, 2, 3} ke B={ a, b ,c, d}
Dan fungsi f ={(a,x), (b,x), (c, z),(d, w)} yang memetakan dari B={ a, b , c, d} ke C ={ w,x, y, z}
Tentuka fungsi (f0g)sebagai himpunan pasangan berurutan.
8. Fungsi f: R R didefinisikan f(x) = x3-2 . apakah fungsi tersebut mempunyai invers ?
9. Diketahui A={a, b, c}, B={x, y, z}. Didefinisikan f:AB, dan g: BC dengan diagram panah berikut
A B C
Carilah : g0f , : ( g0f)-1 , g-1; f-1, dan (f-10g-1). Apakah relasi antara : ( g0f)-1 dengan (f-10g-1).
************************
wisnuria 