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)