SAP RELASI

A.    Identitas

1.      Nama Mata Kuliah                  : Matematika Diskrit

2.      Jumlah SKS                            : 3 SKS

3.      Semester                                  : 5 (Ganjil)

4.      Kelompok Mata Kuliah          : Mata Kuliah Keahlian (MKK) Program Studi

B.     Tujuan

Setelah mengikuti mata kuliah ini, mahasiswa  memiliki  pengetahuan dan pemahaman tentang konsep-konsep yang terdapat dalam mata kuliah matematika diskrit.

C. Strategi Pembelajaran

1. Metode        : Diskusi dan  tanya jawab.

2. Evaluasi       : Tugas, quis, UTS, dan UAS.

3. Media          : Buku sumber, power point, komputer, dan LCD.

D.    Referensi

1.      Munir, R. (2005). Matematika Diskrit. Bandung: Informatika Bandung.

2.      Suryadi, D. (1994). Matematika Diskrit. Jakarta : Universitas Terbuka.

3.      Tremblay dkk (1988).Discrete Mathematical Structures With Application to Computer Science. Singapore : Chong Moh Offset

E.     KEGIATAN

Minggu ke	Pokok Bahasan dan TIU	Sub Pokok Bahasan dan Sasaran Belajar	Tugas
1	1.       Relasi TIU : 2.1. Memberi penjelasan tentang pengertian Relasi, macam-macam relasi, dan sifat-sifat relasi	Mahasiswa diharapkan dapat ·         Menyebutkan macam-macam  relasi ·         Menjelaskan sifat-sifat  suatu relasi ·         Membedakan relasi ekivalen dan relasi tolak parsial (poset) berdasarkan sifat-sifat relasi ·         Menjelaskan  defenisi relasi N-ary	Latihan soal dari lembar kerja

Pendahuluan

1.      Dosen menyampaikan judul materi pelajaran hari ini

2.      Memotivasi mahasiswa dengan mengajukan pertanyaan mengenai perkalian Cartesian

Penyajian

1.      Dosen menjelaskan macam-macam  relasi menggunakan power point

2.      Mahasiswa memperhatikan penjelasan dosen mengenai macam-macam relasi

3.      Dosen menjelaskan sifat-sifat relasi beserta contoh soalnya

4.      Mahasiswa memperhatikan penjelasan dan  mengajukan pertanyaan jika belum paham.

5.      Dosen memberikan beberapa contoh soal mengenai macam-macam relasi dan sifat-sifat  relasi

6.      Mahasiswa mengerjakan beberapa contoh soal mengenai macam-macam relasi dan sifat-sifat  relasi

7.      Mahasiswa bersama dosen  mengenai macam-macam relasi dan sifat-sifat  relasi

8.      Mahasiswa dan dosen menarik kesimpulan dari hasil diskusi macam-macam relasi dan sifat-sifat  relasi

Penutup

1.      Dosen memberikan soal evaluasi mengenai macam-macam relasi

2.      Mahasiswa mengerjakan soal evaluasi mengenai macam-macam relasi secara indifidu

3.      Dosen menyampaikan materi pertemuan berikutnya adalah poset

SAP Graf Euler dan Graf Hamilton

SATUAN ACARA PENGAJARAN (SAP)

A.         Identitas

1.      Nama Mata Kuliah                        : Matematika Diskrit

2.      Jumlah SKS                                  : 3 SKS

3.      Semester                                        : 5 (Ganjil)

4.      Kelompok Mata Kuliah                : Mata Kuliah Keahlian (MKK) Program Studi

 B.        Tujuan

Setelah mengikuti mata kuliah ini, mahasiswa  memiliki  pengetahuan dan pemahaman tentang konsep-konsep yang terdapat dalam mata kuliah matematika diskrit.

C.        Strategi Pembelajaran

1. Metode        : Diskusi dan  tanya jawab.

2. Evaluasi       : Tugas, quis, UTS, dan UAS.

3. Media          : Buku sumber, power point, komputer, dan LCD.

D.                 Referensi

1.      Munir, R. (2005). Matematika Diskrit. Bandung: Informatika Bandung.

2.      Suryadi, D. (1994). Matematika Diskrit. Jakarta : Universitas Terbuka.

3.      Tremblay dkk (1988).Discrete Mathematical Structures With Application to Computer Science. Singapore : Chong Moh Offset

4.      KEGIATAN

Minggu ke	Pokok Bahasan dan TIU	Sub Pokok Bahasan dan Sasaran Belajar	Tugas
9.	Graf Euler dan Graf Hamilton	Setelah mengikuti perkuliahan mahasiswa diharapkan dapat : ·         Membedakan graf Euler dan graf Hamilton. ·         Membedakan lintasan Euler dan lintasan Hamilton dari gambar. ·         Membedakan sirkuit Euler dan sirkuit Hamilton dari gambar. ·         Menentukan graf dapat ditelusuri atau tidak dari sebuah gambar ·         Menentukan jalur terpendek dari sebuah graf	Latihan soal dari lembar kerja

Pendahuluan (2’)

1.                  Dosen manuliskan judul pelajaran hari ini di papan tulis

Penyajian (35’)

1.       Menjelaskan  lintasan euler dan sirkuit euler dari gambar. 

2.             Mahasiswa memperhatikan penjelasan lintasan euler dan sirkuit euler  dan mengajukan pertanyaan jika belum memahami penjelasan dosen.

3.             Memberikan soal-soal tentang lintasan euler dan sirkuit euler.

4.             Mahasiswa mengerjakan soal lintasn euler dan sirkuit euler, kemudian soal dibahas bersama dosen.

5.             Menjelaskan graf Hamilton dari gambar.

6.             Mahasiswa memperhatikan penjelasan graf Hamilthon dan  mengajukan pertanyaan jika belum memahami penjelasan dosen

7.             Memberikan soal-soal tentang graf Hamilton.

8.             Mahasiswa mengerjakan soal-soal graf Hamilton

9.             Menjelaskan lintasan terpendek dalam sebuah graf.

10.         Mahasiswa memperhatikan penjelasan mengenai lintasan terpendek dalam sebuah graf.

11.         Mahasiswa mengerjakan soal-soal lintasan terpendek.

12.         Dosen meminta beberapa mahasiswa untuk menuliskan jawaban soal-soal graf Hamilton dan lintasan terpendek di papan tulis.

13.         Mahasiswa yang lain memberikan argument atas jawaban soal graf hamilthon dan lintasan terpendek yang ada di papan tulis.

14.         Mahasiswa dan dosen menarik kesimpulan

Penutup (13’)

1.             Dosen memberikan soal evaluasi mengenai graf.

2.             Dosen menyampaikan materi pertemuan berikutnya adalah UAS.

Graf Euler, Graf Hamilthon, dan Lintasan Terpendek

Graf Euler, Graf Hamilthon, dan Lintasan Terpendek

Lintasan Euler ialah lintasan yang melalui masing-masing sisi di dalam graf tepat satu kali.

Sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali..

Graf yang mempunyai sirkuit Euler disebut graf Euler (Eulerian graph). Graf yang mempunyai lintasan Euler dinamakan juga graf semi-Euler (semi-Eulerian graph).

Contoh 6.31. Lintasan Euler pada graf Gambar 6.42(a) : 3, 1, 2, 3, 4, 1

Lintasan Euler pada graf Gambar 5.42(b) : 1, 2, 4, 6, 2, 3, 6, 5, 1, 3

Sirkuit Euler pada graf Gambar 6.42(c)    : 1, 2, 3, 4, 7, 3, 5, 7, 6, 5, 2, 6, 1

Sirkuit Euler pada graf Gambar 6.42(d)    : a, c, f,  e, c, b, d, e, a, d, f, b, a

Graf (e) dan (f) tidak mempunyai lintasan maupun sirkuit Euler

 

 

              Gambar 6.42   (a) dan (b) graf semi-Euler

                                           (c) dan (d) graf Euler

                                         (e) dan (f) bukan graf semi-Euler atau graf Euler

TEOREMA 6.2. Graf tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali.

TEOREMA 6.3. Graf tidak berarah G adalah graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap.

(Catatlah bahwa graf yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya)

TEOREMA 6.4.  Graf berarah G memiliki sirkuit Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.

 

Gambar 6.43   (a) Graf  berarah Euler (a, g, c, b, g, e, d, f, a)

                          (b) Graf berarah semi-Euler (d, a, b, d, c, b)

                           (c) Graf berarah bukan Euler maupun semi-Euler

 

 

Gambar 6.44   Bulan sabit Muhammad

Lintasan dan Sirkuit Hamilton

Lintasan Hamilton ialah lintasan yang melalui tiap simpul di dalam graf tepat satu kali.

Sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

Graf yang memiliki sirkuit Hamilton dinamakan graf Hamilton, sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.

 

                                (a)                                    (b)                      (c)     

           

Gambar 6.45  (a) graf yang memiliki lintasan Hamilton (misal: 3, 2, 1, 4)

                         (b) graf yang memiliki lintasan Hamilton (1, 2, 3, 4, 1)

                       (c) graf yang tidak memiliki lintasan maupun sirkuit Hamilton

 

                                                (a)                                            (b)

Gambar 6.46   (a) Dodecahedron Hamilton, dan (b) graf yang mengandung sirkuit Hamilton

TEOREMA 6.5.  Syarat cukup (jadi bukan syarat perlu) supaya graf sederhana G dengan n (³ 3) buah simpul adalah graf Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) ³ n/2 untuk setiap simpul v di  G).

TEOREMA 6.6.  Setiap graf lengkap adalah graf Hamilton.

TEOREMA 6.7. Di dalam graf lengkap G dengan n buah simpul (n ³ 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.

TEOREMA 6.8. Di dalam graf lengkap G dengan n buah simpul (n ³ 3 dan n ganjil), terdapat (n - 1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n  ³ 4, maka di dalam G terdapat (n - 2)/2 buah sirkuit Hamilton yang saling lepas.

Contoh 6.33. (Persoalan pengaturan tempat duduk). Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan?

Jumlah pengaturan tempat duduk yang berbeda adalah (9 - 1)/2 = 4.

 

Gambar 6.47  Graf yang merepresentasikan persoalan pengaturan tempat duduk.

Beberapa graf dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, mengandung sirkuit Euler dan lintasan Hamilton, mengandung lintsan Euler maupun lintasan Hamilton, tidak mengandung lintasan Euler namun mengandung sirkuit Hamilton, dan sebagainya. Graf pada Gambar (a) mengandung sirkuit Hamilton maunpun sirkuit Euler, sedangkan graf pada Gambar 6.48(b) mengandung sirkuit Hamilton dan lintasan Euler (periksa!).

                                                    (a)                            (b)

Gambar 6.48 (a) Graf Hamilton sekaligus graf Euler

                                                     (b) Graf Hamilton sekaligus graf semi-Euler

POSET

POSET

            Poset adalah suatu relasi yang memenuhi tiga sifat yaitu reflektif, anti simetri dan transitif.

Contoh soal :

1.             A = { -4, -3, -2, -1} dan R = {(x,y) │x,y є A,  x ≤ y }

Periksa apakah R poset atau tidak ?

Peny :

A x A     = {(-4,-4), (-4,-3), (-4,-2), (-4,-1), (-3,-4), (-3,-3), (-3,-2), (-3,-1), (-2,-4), (-2,-3)

                    (-2,-2), (-2,-1), (-1,-4), (-1,-3), (-1,-2), (-1,-1)}

R            = {(-4,-4), (-4,-3), (-4,-2), (-4,-1), (-3,-3), (-3,-2), (-3,-1),(-2,-2), (-2,-1), (-1,-1)}

·                     Reflektif            : Karena setiap x  є A berlaku {(x,x   є R)} maka sifat reflektif terpenuhi. R = {(-4,-4), (-3,-3), (-2,-2), (-1,-1)}

·                     Transitif : Karena untuk setiap x, y, z є A berlaku xRy dan yRz berlaku xRz, maka sifat transitif terpenuhi. Bukti (-4,-2) є R, (-2,-1) ) є R  dan  (-4,-1).

·                     Antisimetris       : Karena untuk setiap x, y є A berlaku xRy dan yRx berlaku       x = y, maka sifat antisimetris  terpenuhi.

Karena ketiga sifat   dipenuhi maka R adalah poset.

2.             A = { -4, -3, -2, -1} dan R = {(x,y) │x,y є A,  x <  y }

Periksa apakah R poset atau tidak ?

Peny :

A x A     = {(-4,-4), (-4,-3), (-4,-2), (-4,-1), (-3,-4), (-3,-3), (-3,-2), (-3,-1), (-2,-4), (-2,-3)

                    (-2,-2), (-2,-1), (-1,-4), (-1,-3), (-1,-2), (-1,-1)}

R            =  {(-4,-3), (-4,-2), (-4,-1), (-3,-2), (-3,-1), (-2,-1)}

·                     Reflektif            : Karena setiap x  є A tidak berlaku {(x,x   є R)} maka sifat reflektif tidak terpenuhi. R = {(-4,-3), (-4,-2), (-4,-1), (-3,-2), (-3,-1), (-2,-1)}

Karena sifat reflektif      tidak dipenuhi maka R bukan poset.

3.             A = {1, 3, 5, 7,9} dan R = {(1,1), (1,5), (5,1), (2,2), (2,3), (3,2), (3,3), (4,1), (1,4), (5,5) }

Periksa apakah R poset atau tidak ?

Diagram Hasse

            Jika suatu relasi adalah sebuah poset maka relasi tersebut dapat dinyatakan dalam bentuk diagram. Diagram ini dikenal dengan diagram Hasse. Pada diagram Hasse tiap elemen diwakili oleh sebuah lingkaran kecil atau titik. Jika x < y maka x digambar dibawah lingkaran yang mewakili y.

Contoh Soal :

1.             Misalkan A = {1,2,3,4,5}. Relasi ≤ didefenisikan sebagai x ≤ y. Gambarkan diagram Hasse dari (A, ≤)

Peny

2.             Misalkan B = {1, 2, 3, 4, 6, 12}. Didefnisikan sebagai x ≤ y dan y habis dibagi oleh x, gambarkan diagram Hassenya 

·                Jika A adalah poset dan a,b є A. Maka c ɛ A disebut batas atas {a,b} jika a ≤ c dan        b ≤ c.

·                Jika A adalah poset dan a,b є A. Maka d ɛ A disebut batas bawah {a,b} jika d  ≤ a dan           d ≤ b.

3.             Misalkan B = {2,7,14,28, 56, 84}. Didefnisikan sebagai x ≤  y dan y habis dibagi oleh x, Tentukan :

a.       Gambarkan diagram Hassenya ?

b.      Tentuka batas atas dari {2, 7}

c.       Tentukan batas bawah dari {56, 84}

Peny 

a.         Batas atas dari {2,7} adalah 14, 28, 56, 84

b.         Batas bawah dari {56,84} adalah 28, 14, 7, 2

4.             Misalkan B = {2,3,4,6,12,18,24,36}. Didefnisikan sebagai x ≤  y dan y habis dibagi oleh x, Tentukan :

a.         Gambarkan diagram Hassenya ?

b.        Tentuka batas atas dari {2,3}

c.         Tentukan batas bawah dari {24,36}

·                Jika A adalah poset dan a,b ɛ A. Jika c adalah batas atas dari {a,b} dan untuk setiap batas dari d dari {a,b} berlaku c ≤ d. Maka c dinamkan batas atas terkecil atau supremum dari {a,b} dan dilambangkan c = a + b.

·                Jika A adalah poset dan a,b ɛ A. Jika c adalah batas bawah dari {a,b} dan untuk setiap batas d dari {a,b} berlaku d ≤ c. Maka c dinamakan batas bawah terbesar atau infimum dari {a,b} dan dilambangkan c = a * b.