POHON 

Definisi Pohon dan Hutan 
Pohon (tree) telah digunakan sejak tahun 1857 oleh matematikawan Inggris yang bernama Arthur Cayley untuk menghitung jumlah senyawa kimia. Silsilah keluarga biasanya juga digambarkan dengan bentuk pohon.

Pohon (tree) adalah  graf yang tak berarah terhubung yang tidak memuat sirkuit sederhana. Diagram pohon dapat digunakan sebagai alat untuk memecahkan masalah dengan menggambarkan semua alternative  pemecahan.

Jadi, dapat disimpulkan bahwa pohon adalah suatu graph yang banyak vertexnya sama dengan n (n>1), jika :

~ Graph tersebut tidak mempunyai lingkar (cycle free) dan banyaknya rusuk (n-1).

~ Graph tersebut terhubung .

Contoh   : 

 

Hutan ( forest ) merupakan kumpulan pohon yang saling lepas. Dengan kata lain, hutan merupakan graf tidak terhubung yang tidak mengandung sirkuit.

Ciri – ciri hutan :

banyaknya titik = n

banyaknya pohon = k

banyaknya rusuk = n-k 

   

Berikut adalah beberapa sifat pohon :

1. Misalkan G merupakan suatu graf dengan n buah simpul dan tepat n – 1 buah sisi.

2. Jika G tidak mempunyai sirkuit maka G merupakan pohon.

3. Suatu pohon dengan n buah simpul mempunyai n – 1 buah sisi.

4. Setiap pasang simpul di dalam suatu pohon terhubung dengan lintasan tunggal.

5.Misalkan G adalah graf sederhana dengan jumlah simpul n, jika G tidakmengandung sirkuit maka penambahan satu sisi pada graf hanya akan membuatsatu sirkuit. 

Spanning Tree

Spanning Tree adalah subgraph G merupakan pohon dan mencakup semua titik dari G.Pohon merentang di peroleh dengan cara menghilangkan sirkuit didalam graf trsbt. 

Contoh :

T₁, T₂, T₃, T₄ ® merupakan spanning tree dari G

Minimal spanning tree dari labeled graph  Adalah spanning tree dari graph yang mempunyai jumlah panjang edge minimum.

Contoh   :

2.3  Rooted Tree ( Pohon Berakar )

Rooted tree adalah suatu tree yang mempunyai akar . Istilah-istilah / unsur - unsur yang ada pada pohon berakar :

1.  Akar :dinyatakan dengan lingkar-aN

2. Daun

3.  Cabang

4.  Tinggi / level / dept / dalamnya suatu vertex

Contoh   :

 

Sifat utama Pohon Berakar

1.      Jika Pohon mempunyai Simpul sebanyak n, maka banyaknya ruas atau edge adalah (n-1).

2.      Mempunyai Simpul Khusus yang disebut Root, jika Simpul tersebut memiliki derajat keluar >= 0, dan derajat masuk = 0.

3.      Mempunyai Simpul yang disebut sebagai Daun / Leaf, jika Simpul tersebut berderajat keluar = 0, dan berderajat masuk = 1.

4.      Setiap Simpul mempunyai Tingkatan / Level yang dimulai dari Root yang Levelnya = 1 sampai dengan Level ke - n pada daun paling bawah. Simpul yang mempunyai Level sama disebut Bersaudara atau Brother atau Stribling

5.      Pohon mempunyai Ketinggian atau Kedalaman atau Height, yang merupakan Level tertinggi

6.      Pohon mempunyai Weight atau Berat atau Bobot, yang banyaknya daun (leaf) pada Pohon.

7.      Banyaknya Simpul Maksimum sampai Level N adalah :

2 (N) - 1

8.      Banyaknya Simpul untuk setiap Level I adalah

N              ∑ 2 (I -1)              (I-1)

 

Pohon Berurut Berakar (Ordered Rooted Tree) adalah  pohon berakar yang diberi label berurut secara sistematis. Sistem itu disebut Universal Adress System.

Contoh : dengan memberi nomor urutan; NOL pada akar, kemudian memberikan nomor atas n gugus pada setiap titik simpul yang berjarak n dari akar.

 

Gambar pohon berurut berakar di atas disebut Lexicographic order.

Pernyataan arimetika (a-b) / [(cxd)+e] dapat digambar dalam Lexicographic.

Contoh Soal Pohon

1.      Spanning Tree

Perhatikan gambar suatu graf berikut :

Penyelesaian dengan Spanning Tree adalah

2.      Rooted Tree

Diketahui suatu bentuk Pohon Berakar T sebagai berikut :

Pohon diatas mempunyai :

a.       Simpul sebanyak = 8 dan edge = n - 1 = 8 – 1 = 7

b.      Root pada Pohon T diatas adalah Simpul P

c.       Mempunyai daun (Leaf) = 4, yaitu = R, S, V dan W

d.      Level (tingkatan) Pohon = 4 yaitu :

Level 1 = Simpul P 

Level 2 = Simpul Q dan T

Level 3 = Simpul R, S dan U

Level 4 = Simpul V dan W

e.       Ketinggian atau kedalaman = jumlah level = 4

f.       Weight atau berat atau bobot = jumlah daun = 4

Dalam gambar Pohon T diatas dapat dibentuk 2 buah hutan (forest), bila simpul P dihilangkan, yaitu :

Hutan 1 : Q,R,S

Hutan 2 : T,U,V,W

g.      Banyaknya Simpul Maksimum yang dapat terbentuk sampai Level 4 (bila simpul pada pohon dianggap penuh) adalah

2(N) – 1

2(4) – 1 = 16 – 1 = 15

h.      Banyaknya Simpul maksimum untuk setiap Level I(bila simpul pada pohondianggap penuh) adalah :

Maksimum Simpul pada level 2 = 2 ( I – 1)=

 2 ( 2 - 1 )  = 2

Maksimum Simpul pada level 3 = 2 (3-1)= 4

Maksimum Simpul pada level 4 = 2 (4-1)= 2

 

3. Terdapat sebuah permainan sederhana sebagai berikut: Seseorang memikirkan

sebuah angka antara 1 sampai 31. Anda harus menebak angka dengan benar.

Anda bertanya, ”Apakah angkanya x?” kemudian orang tersebut menjawab

dengan ”Ya”,”Lebih kecil dari x”, atau ”Lebih besar dari x”. Tunjukkan bahwa Anda

mampu menebak angka tersebut tidak lebih dari 5 kali tebakan.

Penyelesaian :

Petunjuknya adalah dengan selalu menebak angka yang menjadi titik tengah dari

jangkauan angka yang tersisa. Kemudian, jika tebakan salah akan mengurangi

separuh angka, hingga akhirnya akan tersisa satu angka. Gambar 11.6

memperlihatkan bagaimana proses tebakan berlangsung,mulai dari 16.

Setiap verteks adalah titik yang memutuskan nilai benar atau salah, jika salah maka nilai

tersebut berada di salah satu subtree dari dua subtree. Subtree pada sisi kiri berisi

nilai yang lebih kecil, dan subtree pada sisi kanan berisi nilai yang lebih besar.

Tree yang terbentuk hanya empat level, maka diperlukan tidak lebih dari 5 kali

tebakan.

Gerbang Logika

Gerbang Logika (Logic Gates) adalah sebuah entitas untuk melakukan pengolahan input-input yang berupa bilangan biner (hanya terdapat 2 kode bilangan biner yaitu, angka 1 dan 0) dengan menggunakan Teori Matematika Boolean sehingga dihasilkan sebuah sinyal output yang dapat digunakan untuk proses berikutnya.

Pengertian Gerbang Logika (Logic Gates) berdasarkan wikipedia adalah :

"Gerbang logika atau gerbang logik adalah suatu entitas dalam elektronika dan matematika Boolean yang mengubah satu atau beberapa masukan logik menjadi sebuah sinyal keluaran logik. Gerbang logika terutama diimplementasikan secara elektronis menggunakan diode atau transistor, akan tetapi dapat pula dibangun menggunakan susunan komponen-komponen yang memanfaatkan sifat-sifat elektromagnetik (relay), cairan, optik dan bahkan mekanik."

                   Gambar diatas merupakan Simbul gerbang AND, OR, INVERTER, NAND, dan NOR yang digunakan oleh American National Standard Institute (ANSI) dan Institute of Electrical and Electronic Engineers (IEEE) (a) lama dan (b) baru.

Jenis - Jenis Gerbang Logika:

Ada 7 jenis gerbang logika, yaitu:

1. Gerbang AND : Apabila semua / salah satu input merupakan bilangan biner (berlogika)          0, maka output akan menjadi 0. Sedangkan jika semua input adalah                bilangan biner (berlogika) 1, maka output akan berlogika 1.

2. Gerbang OR  : Apabila semua / salah satu input merupakan bilangan biner (berlogika) 1,       maka output akan menjadi 1. Sedangkan jika semua input adalah                    bilangan  biner (berlogika) 0, maka output akan berlogika 0.

3. Gerbang NOT : Fungsi Gerbang NOT adalah sebagai Inverter (pembalik). Nilai output             akan berlawanan dengan inputnya.

4. Gerbang NAND : Apabila semua / salah satu input bilangan biner (berlogika) 0, maka                outputnya akan berlogika 1. Sedangkan jika semua input adalah                      bilangan biner (berlogika) 1, maka output akan berlogika 0.

5. Gerbang NOR : Apabila semua / salah satu input bilangan biner (berlogika) 1, maka                outputnya akan berlogika 0. Sedangkan jika semua input adalah                       bilangan  biner (berlogika) 0, maka output akan berlogika 1.

6. Gerbang XOR : Apabila input berbeda (contoh : input A=1, input B=0) maka output akan         berlogika 1. Sedangakan jika input adalah sama, maka output akan                 berlogika 0.

7. Gerbang XNOR : Apabila input berbeda (contoh : input A=1, input B=0) maka output                 akan  berlogika 0. Sedangakan jika input adalah sama, maka output                akan berlogika 1. 

Untuk lebih jelasnya, dapat dilihat pada tabel berikut ini:

PENGERTIAN DAN HUKUM ALJABAR BOOLEAN

Pengertian

 Aljabar Boolean atau dalam bahasa Inggris disebut dengan Boolean Algebra adalah matematika yang digunakan untuk menganalisis dan menyederhanakan Gerbang Logika pada Rangkaian-rangkaian Digital Elektronika. Boolean pada dasarnya merupakan Tipe data yang hanya terdiri dari dua nilai yaitu “True” dan “False” atau “Tinggi” dan “Rendah” yang biasanya dilambangkan dengan angka “1” dan “0” pada Gerbang Logika ataupun bahasa pemrograman komputer. Aljabar Boolean ini pertama kali diperkenalkan oleh seorang Matematikawan yang berasal dari Inggris pada tahun 1854. Nama Boolean sendiri diambil dari nama penemunya yaitu George Boole.

Hukum Aljabar Boolean

Dengan menggunakan Hukum Aljabar Boolean ini, kita dapat mengurangi dan menyederhanakan Ekspresi Boolean yang kompleks sehingga dapat mengurangi jumlah Gerbang Logika yang diperlukan dalam sebuah rangkaian Digital Elektronika.

Dibawah ini terdapat 6 tipe Hukum yang berkaitan dengan Hukum Aljabar Boolean

Hukum Komutatif (Commutative Law)

Hukum Komutatif menyatakan bahwa penukaran urutan variabel atau sinyal Input tidak akan berpengaruh terhadap Output Rangkaian Logika.

Contoh :

Perkalian (Gerbang Logika AND)

X.Y = Y.X

Penjumlahan (Gerbang Logika OR)

X+Y = Y+X

Catatan : Pada penjumlahan dan perkalian, kita dapat menukarkan posisi variabel atau dalam hal ini adalah sinyal Input, hasilnya akan tetap sama atau tidak akan mengubah keluarannya.

Hukum Asosiatif (Associative Law)

Hukum Asosiatif menyatakan bahwa urutan operasi logika tidak akan berpengaruh terhadap Output Rangkaian Logika.

Contoh :

Perkalian (Gerbang Logika AND)

W . (X . Y) = (W . X) . Y

Penjumlahan (Gerbang Logika OR)

W + (X + Y) = (W + X) + Y

Catatan : Pada penjumlahan dan perkalian, kita dapat mengelompokan posisi variabel dalam hal ini adalah urutan operasi logikanya, hasilnya akan tetap sama atau tidak akan mengubah keluarannya. Tidak peduli yang mana dihitung terlebih dahulu, hasilnya tetap akan sama. Tanda kurung hanya sekedar untuk mempermudah mengingat yang mana akan dihitung terlebih dahulu.

Hukum Distributif

Hukum Distributif menyatakan bahwa variabel-variabel atau sinyal Input dapat disebarkan tempatnya atau diubah urutan sinyalnya, perubahan tersebut tidak akan mempengaruhi Output Keluarannya.

Hukum AND (AND Law)

Disebut dengan Hukum AND karena pada hukum ini menggunakan Operasi Logika AND atau perkalian. Berikut ini contohnya :

Hukum OR (OR Law)

Hukum OR menggunakn Operasi Logika OR atau Penjumlahan. Berikut ini adalah Contohnya :

Hukum Inversi (Inversion Law)

Hukum Inversi menggunakan Operasi Logika NOT. Hukum Inversi ini menyatakan jika terjadi Inversi ganda (kebalikan 2 kali) maka hasilnya akan kembali ke nilai aslinya.

Jadi, jika suatu Input (masukan) diinversi (dibalik) maka hasilnya akan berlawanan. Namun jika diinversi sekali lagi, hasilnya akan kembali ke semula.

contoh soal hukum Boolean:

Nyatakan fungsi Boolean f(x, y, z) = x + y’z dalam bentuk kanonik SOP dan POS !
f(x, y, z) = x + y’z
(a) SOP
x  = x(y + y’)
    = xy + xy’
    = xy (z + z’) + xy’(z + z’)
    = xyz + xyz’ + xy’z + xy’z’
y’z = y’z (x + x’)
      = xy’z + x’y’z
Jadi,
f(x, y, z)   = x + y’z
                 = xyz + xyz’ + xy’z + xy’z’ + xy’z + x’y’z
                 = x’y’z + xy’z’ + xy’z + xyz’ + xyz
atau  
f(x, y, z)   = m1 + m4 + m5 + m6 + m7
                 = S (1,4,5,6,7)
(b) POS
f(x, y, z) = x + y’z
               = (x + y’)(x + z)
                 (Hk Distributif)
x + y’ = x + y’ + zz’
           = (x + y’ + z)(x + y’ + z’)
x + z   = x + z + yy’
           = (x + y + z)(x + y’ + z)
Jadi,
f(x,y,z)  =  (x +y’+ z) (x +y’+ z’) (x + y + z) (x + y’ + z)
              =  (x +y+ z) (x +y’ + z) (x + y’ + z’)
atau
f(x, y, z) = M0M2M3
               = Õ(0, 2, 3)

SOAL DAN PEMBAHASAN MATERI KOMBINAS DAN PERMUTASI

1. Berapa banyak string yang dapat dibentuk dari huruf-huruf kata “WEAKNESS” sedemikian sehingga 2    buah huruf “S” tidak terletak berdampingan?

          Penyelesaian:

2. Carilah jumlah himpunan bagian dari A = {a,b,c,d,e} bila diletakkan ke himpunan B dengan 2 elemen?

           Penyelesaian:

3. Sebuah kelompok terdiri dari 7 orang wanita dan 4 orang pria. Berapa banyak perwakilan 4 orang yang dapat dibentuk dari kelompok itu jika paling sedikit harus ada 2 orang wanita didalamnya?

           Penyelesaian:

      

INDUKSI MATEMATIKA

Induksi matematika adalah metode pembuktian untuk proposisi perihal bilangan bulat. Induksi matematika merupakan teknik pembuktian yang baku didalam matematika. Induksi metamtika dapat mengurangi lagkah-langkah pembuktian bahwa semua bilangan bulat termasuk kedalma suatu himpunan kebenaran dengan hanya sejumlah langkah terbatas.  

         Contoh:

 

Jumlah bilangan bulat positif dari 1 sampai n adalah n(n+1)/2

Bukti :

Misalkan n = 6 à p(6) adalah “Jumlah bilangan bulat positif dari 1 sampai 6 adalah 6(6+1)/2” terlihat bahwa :

  1 + 2 + 3 + 4 + 5 + 6 = 21 è 6(7)/2 = 21

Sehingga proposisi (pernyataan) tersebut benar

Contoh:

Jumlah n buah bilangan ganjil positif pertama adalah n2.

Bukti:

Misalkan n = 6 buah (n = 1,2,3,4,5,6) maka :

nn = 1 à 1 = 1  è (1)2 = 1

nn = 2 à 1+3 = 4  è (2)2 = 4

nn = 3 à 1+3+5 = 9  è (3)2 = 9

nn = 4 à 1+3+5+7 = 16  è (4)2 = 16

nn = 5 à 1+3+5+7+9 = 25  è (5)2 = 25

nn = 6 à 1+3+5+7+9+11 = 36 è (6)2 = 36

         Sehingga proposisi (pernyataan) tersebut benar

PRINSIP INDUKSI SEDERHANA

Misalkan p(n) adalah proposisi bilangan bulat positif dan ingin dibuktikan bahwa p(n) adalah benar untuk semua bilangan bulat positif n. Maka langkah-langkahnya adalah sebagai berikut :

1. p(n) benar
2. Jika p(n) benar, maka p(n+1) juga benar untuk setiap n ³ 1 

         Sehingga p(n) benar untuk semua bilangan bulat positif n

       

          Basis Induksi:  

•         Digunakan untuk memperlihatkan bahwa pernyataan benar bila n diganti dengan 1, yang merupakan bilangan bulat positif terkecil
•         Buat implikasi untuk fungsi berikutnya benar untuk setiap bilangan bulat positif \

           Langkah Induksi:

•         Berisi asumsi (andaian) yang menyatakan bahwa p(n) benar.
•         Asumsi tersebut dinamakan hipotesis induksi.

           Bila kedua langkah tersebut benar maka pembuktian bahwa p(n) benar untuk semua  bilangan positif n.

 

      

          CONTOH:

          Tunjukkan bahwa untuk n ³ 1, 1+2+3+…+n = n(n+1)/2 melalui induksi matematika

•           Basis induksi

                    p(1) benar ➜ n = 1 diperoleh dari :

                                           

                          1 = 1(1+1)/2

                             

                              = 1(2)/2

           

                              = 2/2

                              

                              =1

•           Langkah induksi

                    Misalkan p(n) benar à asumsi bahwa :

                    1+2+3+…+n = n(n+1)/2

                    Adalah benar (hipotesis induksi). Perlihatkan bahwa p(n+1) juga benar yaitu 

                    1+2+3+…+n+(n+1) = (n+1)[(n+1)+1]/2

                      

                1+2+3+…+n+(n+1) = (1+2+3+…+n)+(n+1)

  = [n(n+1)/2]+(n+1)

  = [(n2+n)/2]+(n+1)

  = [(n2+n)/2]+[(2n+2)/2]

  = (n2+3n+2)/2

  = (n+1)(n+2)/2

  = (n+1)[(n+1)+1]/2

Langkah (i) dan (ii) dibuktikan benar, maka untuk semua bilangan bulat positif n, terbukti bahwa untuk semua n ³ 1, 1+2+3+…+n = n(n+1)/2