KEGELISAHAN HATI - Puisi

Sengaja Begitu

Karya : Ni Made Ayu Astiti Wwekawati

Malam itu tak pernah datang sebelumnya

Dimana saat ingin beristirahat lebih cepat 

Mata mampu untuk terpejam namun pikiran tak mampu diam di satu tempat

Hai. . . Kau yang disana, apa kau memikirkan ku

Hingga malam berjalan sangat lambat

Kau begitu peduli 

Di tengah malam itu kau peduli

Namun aku tak menghiraukan

Maaf. . . karna sengaja aku begitu

KEGELISAHAN HATI - Puisi

SAKIT SEBELUM PERGI

Karya : Ni Made Ayu Astiti Wiwekawati

Sakit ini datang di saat jauh

Namun hilang saat akan kembali

Ingin kembali ke hari-hari biasa

Sesaat akan pergi, ia datang membawa sakit

Karna baik kau sakit

Jangan salahkan kebaikan karna dia tak bersalah

Mungkin dulu kau salah

Hingga kau tanggung saat baik

Materi MatDis (Matematika Diskrit) : Pohon Part 2

1. Pohon Berakar 

          adalah pohon yang sebuah simpulnya diperlukan sebagai akar dan sisi-sisinya diberi arah menjauh dari akar.

Terminologi pada pohon berakar

Anak(Child atau children) dan Orangtua (parent)

Misalkan Xx adalah sebuah simpul di dalam pohon berakar. Simpul y dkatakan anak simpul x jika ada sisi dari simpul x ke y. Dalam hal demikian, x disebut orangtua (parent)  y. Pada gambar dibawah, b, c dan d adalah anak-anak simpul a, dan a adalah orangtua dari anak-anak itu. e dan f adalah anak-anak simpul b dan b adalah orangtua dari e dan f. g adalah anak simpul d dan d adalah orangtua g. Simpul h,i, j, l dan m tidak mempunyai anak.

2. Pohon Berakar Terurut

    adalah pohon berakar yang urutan anak-anaknya penting.

3. Pohon Ekspresi
   adalah pohon biner dengan daun menyatakan operand dan simpul dalam (termasuk akar) menyatakan operator. Perhatikan bahwa tanda kurang tidak lagi diperlukan bila suatu ekspresi aritmetik diprsentasikan sebagai pohon biner.
contoh :
(a+b) * c/(d+e) Infix
Prefix : *+ ab/c + de
Posfix : ab + cde +/*


INFIX, POSTFIX dan PREFIX

1. Infix
    Digunakan manusia sebagai input di komputer
2. Postfix
    Digunakan komputer sebagai proses
3. Prefix
    Sama Seperti Postfix yaitu digunakan komputer sebagai proses.

• Konversi Infix ke Postfix

ada 3 cara yaitu :
1. Cara Manual
    Caranya adalah dengan menyederhanakan  notasi menjadi dua operand (variabel) da satu operator, seperti A + B

2. Cara Stack
    Stack adalah tumpukan (jadi, memori diibaratkan dengan tumpukan) yang memiliki cara kerja yang pertama masuk ke kotak, maka akan terakhir kali diambil kembali atau first in last out atau sebaliknya, yang terakhir masuk ke kotak akan diambil yang pertama kali, atau last in first out.

3. Cara Binary Tree

• Konversi Infix ke Prefix

Ada 2 cara :
1. Cara Manual
    Sama seperti mengonversi notasi infix ke prefix
2. Cara Binary Tree
    Sama seperti mengonversi notasi infix ke prefix

• Konversi Prefix ke Infix dan/atau Postfix

Bisa dilakukan melalui bantuan manual dan pohon binar.

• Konversi Postfix ke Infix dan/atau Prefix

Sama seperti Konversi Prefix ke Infix dan/atau Postfix

Materi MatDis (Matematika Diskrit) : Pohon

DEFINISI POHON

Pohon adalah graf tak berarah terhubung yang tidak mengandung sirkuit.
Beberapa pohon dapat membentuk hutan. Hutan adalah kumpulan pohon yang saling lepas. Atau hutan adalah graf tak terhubung yang tidak mengandung sirkuit, dalam hal ini setiap komponen graf terhubung adalah pohon.
Pohon juga seringkali didefinisikan sebagai graf tak berarah dengan sifat bahwa hanya terdapat sebuah lintasan unik antara setiap pasang simpul.


POHON MERENTANG

adalah semua simpul pada pohon T sama dengan semua simpul pada graf G.
Pohon merentang didefinisikan hanya untuk graf terhubung, karena pohon selalu terhubung. Pada graf terhubung terdapat setidaknya satu buah pohon merentang.Graf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri. Pada graf yang mengandung sirkuit, pohon merentangnya diperoleh dengan cara memutuskan sirkuit yang ada.
Sisi pada pohon merentang disebut cabang. Sedangkan sisi dari graf yang tidak terdapat di dalam pohon merentang disebut tali hubung.Himpunan tali hubung beserta simpul yang bersisian disebut komplemen pohon. Rumus menghitung jumlah cabang dan jumlah tali hubung :

                                Jumlah cabang = n - 1
                                Jumlah tali hubung = m - n + 1

dan pada graf tidak terhubung dengan k komponen, m buah sisi dan n buah simpul,

                                Jumlah cabang = n - k
                                Jumlah tali hubung = m - n + k

Sirkuit yang terbentuk dengan penambahan sebuah tali hubung pada pohon merentang disebut sirkuit fundamental.


POHON MERENTANG MINIMUM

adalah pohon merentang yang berbobot minimum dimana pohon merentang ini merupakan pohon merentang yang paling penting karena mempunyai terapan yang luas dalam praktik.
Terdapat dua buah algoritma dalam membuat pohon merentang minimum :

1. Algoritma Prim

          Algoritma Prim membentuk pohon merentang minimum langkah per langkah. 

          1. Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T

          2. Pilih sisi e yang mempunyai bobot minimum dan bersisian dengan simpul di T, tetapi e                        tidak  membentuk sirkuit di T. Masukkan e ke dalam T

          3. Ulangi langkah 2 sebanyak n - 2 kali

         Jumlah langkah seluruhnya di dalam algoritma prim adalah 1 + (n - 2) = n - 1, yaitu sebanyak             jumlah sisi di dalam pohon merentang dengan n buah simpul.

     2. Algoritma Kruskal

         Pada algoritma kruskal, sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari           kecil ke besar. Perbedaan prinsip antara algoritma prim dan algoritma kruskal adalah : jika pada           algoritma prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T,               maka pada algoritma kruskal sisi yang dipilih tidak perlu bersisian dengan sebuah simpul di T             asalkan penambahan sisi tersebut tidak membentuk sirkuit.

         

         Algoritma Kruskal :

1. T Masih Kosong
2. Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T. Masukkan e ke dalam T
3. Ulangi langkah 2 sebanyak n - 1 kali

Materi MatDis (Matematika Diskrit) : Graf Part 2

GRAF PLANAR dan GRAF BIDANG

Graf planar adalah graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling memotong. Reprsentasi dari graf planar disebut dengan graf bidang. Sisi-sisi pada graf graf bidang membagi bidang datar menjadi beberapa wilayah atau muka.

RUMUS EULER

Rumus euler sebagai berikut:

             n - e + f = 2
atau
            f = e - n + 2
keterangan:
e = jumlah sisi
n = jumlah simpul



TEOREMA KURATOWSKI

Sifat graf kuratowski :

1. Kedua graf kuratowski adalah graf teratur
2. Kedua graf kuratowski adalah graf tidak planar
3. Penghapusan sisi atau simpul dari graf kuratowski menyebabkannya menjadi graf planar
4. Graf kuratowski pertama adalah graf tidak planar dengan jumlah simpul minimum dan graf kuratowski kedua adalah graf tidak planar dengan jumlah sisi minimum. Keduanya adalah graf tidak planar paling sederhana

HOMEOMORFIK

adalah jika salah satu dari kedua graf dapat diperoleh dari graf yang lain dengan cara menyisipkan dan/atau membuang secara berulang-ulang simpul berderajat 2.

LINTASAN dan SIRKUIT EULER

Lintasan euler adalah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit euler.

Graf yang mempunyai sirkuit euler disebut graf euler. Graf yang mempunyai lintasan euler dinamakan graf semi euler.

LINTASAN dan SIRKUIT HAMILTON

Lintasan hamilton adalah lintasan yang melalui tiap simpul di dalam graf tepat satu kali. Jika kembali ke simpul asal membentuk lintasan tertutup disebut sirkuit hamilton.

Graf yang memiliki sirkuit hamilton disebut graf hamilton sedangkan graf yang hanya memiliki lintasan hamilton disbeut graf semi hamilton.

Materi MatDis (Matematika Diskrit) : Graf

1. Definisi Graf
    Graf adalah tidak adanya sisi satu buah pun namun memiliki simpul, minimal adanya simpul satu.

2. Jenis-jenis Graf
    Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara urutan graf dapat          digolongkan menjadi dua jenis :

•      Graf Sederhana

               adalah graf yang tidak mengandung gelang maupun sisi-ganda. Pada graf sederhana, sisi                     adalah pasangan terurut. Jadi menuliskan sisi (u, v) sama saja dengan (v, u). Graf sederhana                 dapat juga diartikan himpunan tidak kosong simpul-simpul dan himpunan pasangan tak                       terurut yang disebut sebagai sisi.

• Graf Tak Sederhana

           adalah graf yang mengandung sisi ganda atau gelang. Ada dua macam graf tak sederhana,                   yaitu

1.          Graf Ganda

                   adalah graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang                           simpul bisa lebih dari dua buah. Sisi ganda dapat diasosiasikan sebagai pasangan tak                           terurut yang sama. Serta dapat juga diartikan yang terdiri dari himpunan tidak kosong                           simpul-simpul dan himpunan ganda yang mengandung sisi ganda. Setiap graf sederhana                       juga adalah graf ganda tetapi tidak setiap graf ganda merupakan graf sederhana.

     

       2.         Graf Semu

               

                   adalah graf yang mengandung gelang. Graf semu lebih umum daripada graf ganda                               karena  sisi pada graf semu dapat terhubung ke dirinya sendiri.

Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis :

1. Graf Tak Berarah 

          adalah graf yang sisinya tidak mempunyai orientasi arah. Pada graf tak berarah, urutan                        pasangan simpul yang dihubungkan oleh sisi tidak diperhatikan. Jadi (u, v) = (v, u) adalah sisi              yang sama.

  

       2. Graf Berarah

           adalah graf yang setiap sisinya diberikan orientasi arah. Sisi berarah disebut dengan busur.                 Pada graf berarah, (u, v) dan (v, u) menyatakan dua buah busur yang berbeda. Untuk busur (u,             v), simpul v dinamakan simpul asal dan simpul v dinamakan simpul terminal.

TERMINOLOGI DASAR

1. Bertetangga

          Duah buah simpul dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah                  sisi.

       2. Bersisian

           Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u dan simpul v.

       3. Simpul Terpencil

           adalah simpul yang tidak mempunyai sisi yang bersisian dengannya ataupun tidak satupun                   bertetangga dengan simpul-simpul lainnya.

        4. Graf Kosong

            adalah graf yang himpunan sisinya merupakan himpunan kosong.

         5. Derajat

             Derajat suatu simpul pada graf tak berarah adalah jumlah sisi yang bersisian dengan simpul                 tersebut.

             Notasi : d(v) menyatakan derajat simpul v
             Simpul yang berderajat satu disebut anting-anting. Dengan kata lain, anting-anting hanya                     bertetangga dengan sebuah simpul.

         6. Lintasan

             adalah barisan berselang-seling simpul-simpul dan sisi-sisi. Istilah lain untuk lintasan adalah               jalur. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan                           dikatakan lintasan sederhana jika semua simpulnya berbeda. Lintasan yang berawal dan                     berakhir pada simpul yang sama disebut lintasan tertutup sedangkan lintasan yang tidak                     berawal dan berakhir pada simpul yang sama disebut lintasan terbuka. Panjang lintasan                     adalah jumlah sisi dalam lintasan tersebut.

       7. Siklus atau Sirkuit

            adalah lintasan yang berawal dan berakhir pada lintasan yang sama. Panjang sirkuit adalah                  jumlah sisi di dalam sirkuit tersebut.

        8. Terhubung

             Dikatakan terhubung jika terdapat lintasan dari u ke v diantara dua buah simpul u dan simpul               v. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai dari simpul               yang kedua. Jika setiap pasang simpul di dalam graf terhubung maka graf tersebut dikatakan               graf terhubung.

          9. Upagraf dan Komplemen Upagraf

          10. Upagraf Merentang

          11. Cut-Set

                Cut-Set atau jembatan adalah himpunan sisi yang apabila dibuang dari graf menyebabkan                    graf tersebut tidak terhubung.

          12. Graf Berbobot

                adalah graf yang setiap sisinya diberi sebuah harga (bobot).

             
BEBERAPA GRAF SEDERHANA KHUSUS

1. Graf Lengkap

          adalah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya.

       2. Graf Lingkaran

           adalah graf sederhana yang setiap simpulnya berderajat dua.

       3. Graf Teratur

            adalah graf yang setiap simpulnya mempunyai derajat yang sama.

        4. Graf Bipartit

            adalah himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian.


REPRESENTASI GRAF

1. Matriks Ketetanggaan

          Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan matriks              nol-satu. Selain dengan angka 0 dan , elemen matriks dapat juga dinyatakan dengan nilai false            (menyatakan 0) dan true (menyatakan 1). Matriks ketetanggaan untuk graf sederhana dan tidak            berarah selalu simetri sedangkan untuk graf berarah matriks ketetanggaannya belum tentu                    simetri. Selain itu, diagonal utamanya selalu nol karena tidak ada sisi gelang.

      2. Matriks Bersisian

          Matriks bersisian menyatakan kebersisian simpul dengan sisi. Baris menunjukkan label simpul sedangkan kolom menunjukkan label sisinya. Matriks bersisian dapat digunakan untuk mempresentasikan graf yang mengandung sisi ganda atau sisi gelang.

      3. Senarai Ketetanggaan

          Senarai ketetanggaan menganumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam graf.


GRAF ISOMORFIK

adalah dua buah graf yang sama tetapi secara geometri berbeda. Syarat-syarat dua buah graf isomorfik :

1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama.
3. Mempunyai jumlah simpul yang sama berderajat tertentu.

           

Materi MatDis (Matematika Diskrit) : Aljabar Boolean

1. Definisi Aljabar Boolean
    Yang disebut aljabar boolean adalah <B, +, ., ',  0, 1>

• Identitas

         (i) a + 0 = a
         (ii) a + 1 = a

• Komutatif

          (i) a + b = b + a
          (ii) a . b = b . a

• Distributif

          (i) a . (b +c) = (a . b) + (a . c)
          (ii) a + (b . c) = (a + b) . (a + c)

• Komplemen

          (i) a + a' = 1
          (ii) a . a' = 0


2. Prinsip Dualitas
    Misalkan S adalah kesamaan (identify) di dalam aljabar boolean yang melibatkan operator +, ., dan komplemen, maka jika pernyataan S* diperoleh dari S dengan cara mengganti
   
     . dengan +
     + dengan .
     0 dengan 1
     1 dengan 0
dan membiarkan operator komplemen tetap apa adanya, maka kesamaan S* juga benar. S* disebut sebagai dual dari S


Hukum-hukum Aljabar Boolean
1. Hukum Identitas:
    (i) a + 0 = a
    (ii) a . 1 = a

2. Hukum Idempoten:
    (i) a + a = a
    (ii) a . a = a

3. Hukum Komplemen:
    (i) a + a' = 1
    (ii) aa' = 0

4. Hukum Dominansi:
    (i) a . 0 = 0
    (ii) a + 1 = 1

5. Hukum Involusi:
    (i) (a')' = a

6. Hukum Penyerapan:
    (i) a + ab = a
    (ii) a(a + b) = a

7. Hukum Komutatif:
    (i) a + b = b + a
    (ii) ab = ba

8. Hukum Asosiatif
    (i) a + (b + c) = (a + b) + c
    (ii) a (b c) = (a b) c

9. Hukum Distributif:
    (i) a + (b c) = (a + b)(a + c)
    (ii) a (b + c) = a b + a c

10. Hukum De Morgan
      (i) (a + b)' = a'b'
      (ii) (ab)' = a' + b'

11. Hukum 0/1
      (i) 0' = 1
      (ii) 1' = 0


Contoh Soal :
1. Bentuk baku SOP dan POS dari f (x, y, z) = xy + x'z

    SOP:
    xy = xy(z + z')
         = xyz + xyz'
    dan
    x'z = x'z (y +y')
          = x'yz + x'y'z
    Jadi f(x, y, z) = xy + x'z
                          = xyz + xyz' + x'yz + x'y'z
   Atau f(x, y, z) = m7 + m6 + m3 + m1
                          = (1, 3, 6, 7)

    POS:
    f(x, y, z) = xy +x'z
                   = (xy + x')(xy + z)
                  = (x + x')(y + x')(x + z)(y + z)
                   = (x' + y)(x + z)(y + z)
   
     x' + y = x' + y + zz' = (x' + y + z)(x' + y + z')
     x + z  = x + z + yy'  = (x + y + z)(x + y' + z)
     y + z   = xx' + y + z  = (x + y +z)(x' + y + z)

     Jadi f(x, y, z) = (x + y + z)(x + y' + z)(x' + y + z)(x' + y + z')

     Atau f(x, y, z) = M0 M2 M4 M5
                            = (0, 2, 4, 5)

2. Bentuk Baku SOP dan POS dari f(x, y, z) = x + yz'
   
     SOP:
     x = x(y + y')
        = xy + xy'
        = xy (z + z') + xy' (z + z')
        = xyz + xyz' + xy'z + xy'z'
    dan
    yz' = yz' (x + x')
          = yz'x + yz'x' = xyz' + x'yz'
 
     Jadi f(x, y, z) = x + yz'
                           = xyz + xyz' + xy'z + xy'z' + x'yz'
                           = x'yz' + xy'z' + xy'z + xyz' + xyz
     
     Atau f(x, y, z) = m2 + m4 + m5 + m6 + m7
                            = (2, 4, 5, 6, 7)


    POS:
    f(x, y, z) = x + yz'
                   = (x + y)(x + z')
 
    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) = M0 M1 M3
                          = (0, 1, 3)