pedoman kuliah

H P H

A

K

A

I

A

N

S R

I

L P

Anything you're good at contributes to happiness – Apapun kebisaan yang saya miliki adalah sumber kebahagiaan (BERTRAND RUSSELL, 1872 – 1970)

SEKOLAH TINGGI MATEMATIKA – IN THE SECOND YEAR

HPUTUTHMARET 2012

MATEMATIKA DISKRIT

PANDUAN KULIAH

STM – To Make Each Day Count

Ad

ap

t Tru

th In

You21

DAFTAR ISI1. Matematika Diskrit.................................................................................2

2. SILABUS..................................................................................................2

A. Penjelasan Umum...............................................................................2

B. Kemajuan Kuliah.................................................................................3

C. Uji coba soal ujian...............................................................................3

D. Ujian Tertulis.......................................................................................3

E. Penjelasan Materi Kuliah.....................................................................3

3. Kalender.................................................................................................6

A. Kuliah..................................................................................................6

B. Tugas..................................................................................................7

4. Pedoman Tugas......................................................................................9

A. Desain.................................................................................................9

i. Kover................................................................................................9

ii. Kata Penyemangat.........................................................................10

iii. Fakta Objektif.................................................................................10

iv. Peta Pikiran....................................................................................11

v. Soal Biasa.......................................................................................11

vi. Soal Pembuktian............................................................................12

vii. Jawaban Ringkas............................................................................12

viii. Jawaban Runtut..............................................................................12

ix. Esai Sederhana..............................................................................13

x. Esai Lengkap..................................................................................14

B. Bacaan..............................................................................................16

C. Video.................................................................................................17

5. Penilaian...............................................................................................17

i. Nilai Akhir.......................................................................................17

ii. Nilai Tugas.....................................................................................18

iii. Denda.............................................................................................19

iv. Kehadiran.......................................................................................19

6. Permainan............................................................................................19

Ad

ap

t Tru

th In

You21

1. MATEMATIKA DISKRIT

Matematika Diskrit (MDT) adalah kuliah mengenai struktur matematika yang pondasinya adalah diskrit, yang maknanya tidak mendukung atau memerlukan notasi kontinu. Objek yang dipelajari adalah himpunan terhitung (countable set), seperti bilangan bulat (integer), graph terbatas (finite graphs), dan bahasa formal (formal languages) (Wikipedia, 2011). MDT adalah kuliah tentang sistem terbatas (finite systems) (Lipschutz, 2007). Subjek utama kuliah MDT adalah matematika kombinatorial (combinatorial mathematics) (Grimaldi, 2004). Lima tema utama yang saling rajut membentuk pemahaman MDT adalah (1) logika matematika (mathematical reasoning), (2) analisis kombinatorial (combinatorial analysis), (3) struktur diskrit (discrete structures), (4) berpikir algoritma (algorithmic thinking), dan (5) aplikasi dan pemodelan (applications and modeling). Kuliah MDT yang sukses mestinya secara hati-hati mencampur dan menyeimbangkan kelima tema tersebut (Rosen, 2007).

2. SILABUS

Kuliah diberikan dalam 16 (enam belas) kali jumpa dengan konten sebagai berikut:

Penjelasan umum dan kemajuan kuliah 2 kali Uji coba soal ujian 2 kali Ujian tertulis 2 kali Penjelasan materi kuliah 10 kali

A. PENJELASAN UMUM

Penjelasan umum diberikan di jumpa ke-1 untuk memberikan pemahaman tentang konten kuliah, pembuatan tugas mingguan, tujuan yang ingin dicapai, metode evaluasi, dan bacaan yang digunakan.Bacaan yang wajib dipelajari adalah:

Burger - The Heart of Mathematics, An Invitation to Effective Thinking (2010)

Grimaldi - Discrete and Combinatorial Mathematics, An Applied Introduction, Ed. 5 (2003)

Grimaldi - Discrete and Combinatorial Mathematics, Instructor's Solution Manual, Ed. 5 (2004)

Ad

ap

t Tru

th In

You21

B. KEMAJUAN KULIAH

Kemajuan kuliah diberikan pada jumpa ke-9 untuk memberikan penjelasan tentang jalannya kuliah tahap pertama (sampai dengan tengah semester) meliputi proses pembuatan soal ujian tengah semester (UTS), hasil uji coba soal UTS, penggantian soal UTS, dan statistik tentang nilai uji coba UTS, ujian UTS, dan tugas mingguan pra UTS. Kemajuan kuliah disampaikan untuk memberikan penjelasan tentang:

Apakah ada perbedaan yang signifikan antara uji coba dengan ujian tertulis?

Apakah ada pengaruh tugas mingguan pra UTS terhadap hasil ujian tertulis (UTS)?

C. UJI COBA SOAL UJIAN

Pada tugas mingguan yang diberikan, siswa diwajibkan membuat satu soal dan jawaban. Kumpulan seluruh soal dan jawaban ini kemudian dipilih disesuaikan dengan topik yang sedang dibahas dan tingkat kesulitannya. Dari soal yang terkumpul kemudian diseleksi 10 (sepuluh) soal yang kemudian diuji-cobakan dalam yang 100 menit. Usai uji coba kemudian diberikan penjelasan singkat mengenai cara menjawab soal tanpa memberikan solusi akhir yang tuntas. Penjelasan hanya untuk mengarahkan siswa agar mampu menemukan solusinya secara mandiri.

D. UJIAN TERTULIS

Ada dua jenis ujian yaitu ujian tengah semester (UTS) dan ujian akhir semester (UAS). Ujian UTS diberikan pada jumpa ke-8 dan UAS pada jumpa ke-16. Materi ujian diciptakan berdasarkan kumpulan soal dan jawab yang dihimpun dari tugas mingguan setelah mempertimbangkan hasil uji coba soal ujian UTS. Ujian terdiri dari 10 (sepuluh) soal dengan bobot merata. Waktu ujian ditentukan sekitar 100 menit, dengan demikian waktu untuk menyelesaikan soal sekitar 10 menit per soal.

E. PENJELASAN MATERI KULIAH

Kuliah MDT merupakan kuliah berbobot 4 (empat) satuan kredit semester (SKS) atau setara dengan 200 menit. Kuliah dimulai pukul

Ad

ap

t Tru

th In

You21

09.50 sampai dengan pukul 13.30 dengan jeda 10 menit untuk istirahat. Kuliah disampaikan dalam 10 kali jumpa. Setiap jumpa diisi dengan diskusi tentang tugas yang telah disampaikan. Jumpa akan diawali dengan penjelasan ringkas mengenai materi tugas mingguan kemudian dilanjutkan dengan penayangan tugas mingguan salah satu siswa menggunakan fasilitas komputer dan layar LCD yang tersedia di ruang kelas. Selain fasilitas komputer dan LCD, kuliah juga disampaikan menggunakan papan tulis, spidol, dan penghapus.Kesepuluh materi kuliah MDT bertumpu pada lima tema utama yaitu:

1. Logika Matematika (Mathematical Reasoning)Topik ini terdiri dari:

1.1 Logika Matematika1.1.1 Koneksi dan Tabel Kebenaran1.1.2 Ekuivalensi Logis1.1.3 Implikasi Logis1.1.4 Kuantor

1.2 Himpunan dan Induksi Matematika1.2.1 Set dan Subset1.2.2 Operasi Set dan Hukum Teori Set1.2.3 Induksi Matematika

2. Analisis Kombinatorial (Combinatorial Analysis)Topik ini terdiri dari:

2.1 Permutasi dan Kombinasi2.1.1 Aturan Penjumlahan dan Perkalian2.1.2 Permutasi2.1.3 Teorema Binomial2.1.4 Kombinasi dengan Repetisi2.1.5 Menghitung dan Diagram Venn

2.2 Teknik Menghitung2.2.1 Menghitung2.2.2 Prinsip Sangkar Merpati2.2.3 Prinsip Inklusi dan Eksklusi2.2.4 Generalisasi Prinsip

3. Struktur Diskrit (Discrete Structures)Topik ini terdiri dari:

3.1. Graph3.1.1. Contoh dan Definisi3.1.2. Subgraph, Komplemen, dan Graph Isomorfisme3.1.3. Euler Trail dan Sirkuit3.1.4. Graph Palanr3.1.5. Hamiltonian Path dan Siklus3.1.6. Pewarnaan Graph dan Polinomial Kromatik

Ad

ap

t Tru

th In

You21

3.2. Tree3.2.1. Definisi, Sifat, dan Contoh3.2.2. Akar Tree3.2.3. Tree dan Sorting3.2.4. Tree Berbobot dan Kode Prefiks3.2.5. Komponen Biconnected dan Titik Artikulasi

4. Berpikir Algoritma (Algorithmic Thinking)Topik ini terdiri dari:

4.1. Relasi4.1.1. Sifat Relasi4.1.2. Matriks Satu-Kosong dan Graph Berarah4.1.3. Diagram Hasse4.1.4. Relasi Ekuivalensi dan Partisi

4.2. Rekursif4.2.1. Definisi Rekursif4.2.2. Relasi Recurrence Linear Orde Pertama4.2.3. Relasi Recurrence Linear Homogen Orde Kedua4.2.4. Relasi Recurrence Non Homogen

5. Aplikasi Dan Pemodelan (Applications And Modeling)Topik ini terdiri dari:

5.1. Fungsi Pembangkit5.1.1. Contoh Perkenalan5.1.2. Teknik Kalkulasi5.1.3. Partisi Bilangan Bulat5.1.4. Fungsi Pembangkit Eksponensial5.1.5. Operator Jumlahan5.1.6. Metode Fungsi Pembangkit

5.2. Mesin Finite State5.2.1. Teori Set dan String5.2.2. Perjumpaan Pertama5.2.3. Perjumpaan Kedua5.2.4. Proses Minimisasi

Ad

ap

t Tru

th In

You21

3. KALENDER

A. KULIAHJumpa Topik Diskusi Sumber Tanggal

1 Penjelasan Umum 24 Mar 12

2 Logika Matematika Grimaldi (2003) 31 Mar 12

3 Himpunan dan Induksi Matematika Grimaldi (2003) 07 Apr 12

4 Permutasi dan Kombinasi Grimaldi (2003) 14 Apr 12

5 Teknik Menghitung (Counting Techniques) Grimaldi (2003) & Burger (2010)

21 Apr 12

6 Graph Grimaldi (2003) 28 Apr 12

7 Uji Coba Ujian UTS Tugas Mingguan 05 Mei 12

8 Ujian Tengah Semester (UTS) Tugas Mingguan 12 Mei 12

9 Penjelasan Kemajuan Kuliah Ujian UTS 26 Mei 12

10 Tree Grimaldi (2003) 02 Jun 12

11 Relasi Grimaldi (2003) 09 Jun 12

12 Rekursif Grimaldi (2003) 16 Jun 12

13 Fungsi Pembangkit Grimaldi (2003) 23 Jun 12

14 Mesin Finite State Grimaldi (2003) 30 Jun 12

15 Uji Coba Ujian UAS Tugas Mingguan 07 Jul 12

16 Ujian Akhir Semester (UAS) Tugas Mingguan 21 Jul 12

Ad

ap

t Tru

th In

You21

B. TUGASTemu Topik Diskusi Sumber Tugas

1 Penjelasan Umum

2 Logika Matematika:2.1 Basic Connectives and Truth Tables 2.2 Logical Equivalence: The Laws of Logic 2.3 Logical Implication: Rules of Inference 2.4 The Use of Quantifiers

Grimaldi (2003) Esai MDT 1

3 Himpunan dan Induksi Matematika:3.1 Sets and Subsets 3.2 Set Operations and the Laws of Set Theory 4.1 The Well-Ordering Principle: Mathematical Induction


4 Permutasi dan Kombinasi:1.1 The Rules of Sum and Product 1.2 Permutations 1.3 Combinations: The Binomial Theorem 1.4 Combinations with Repetition 3.3 Counting and Venn Diagrams


5 Teknik Menghitung (Counting Techniques):2.1 Counting5.5 The Pigeonhole Principle 8.1 The Principle of Inclusion and Exclusion 8.2 Generalizations of the Principle

Grimaldi (2003) & Burger (2010)

Esai MDT 4

6 Graph:11.1 Definitions and Examples 11.2 Subgraphs, Complements, and Graph Isomorphism 11.3 Vertex Degree: Euler Trails and Circuits 11.4 Planar Graphs 11.5 Hamilton Paths and Cycles 11.6 Graph Coloring and Chromatic Polynomials


7 Uji Coba Ujian UTS Tugas Mingguan

8 Ujian Tengah Semester (UTS) Tugas Mingguan

9 Penjelasan Kemajuan Kuliah Hasil UTS

10 Tree: Grimaldi (2003) Esai

Ad

ap

t Tru

th In

You21

12.1 Definitions, Properties, and Examples 12.2 Rooted Trees 12.3 Trees and Sorting 12.4 Weighted Trees and Prefix Codes 12.5 Biconnected Components and Articulation Points

MDT 6

11 Relasi:7.1 Relations Revisited: Properties of Relations 7.2 Computer Recognition: Zero-One Matrices and Directed Graphs 7.3 Partial Orders: Hasse Diagrams 7.4 Equivalence Relations and Partitions


12 Rekursif:4.2 Recursive Definitions 10.1 The First-Order Linear Recurrence Relation 10.2 The Second-Order Linear Homogeneous Recurrence Relation with Constant Coefficients 10.3 The Nonhomogeneous Recurrence Relation


13 Generating Function:9.1 Introductory Examples 9.2 Definition and Examples: Calculational Techniques 9.3 Partitions of Integers 9.4 The Exponential Generating Function 9. 5 The Summation Operator 10.4 The Method of Generating Functions


14 Mesin Finite State:6.1 Language: The Set Theory of Strings 6.2 Finite State Machines: A First Encounter 6.3 Finite State Machines: A Second Encounter 7.5 Finite State Machines: The Minimization Process


15 Uji Coba Ujian UAS Tugas Mingguan

16 Ujian Akhir Semester (UAS) Tugas Mingguan

Ad

ap

t Tru

th In

You21

4. PEDOMAN TUGAS

A. DESAIN

I. KOVER

Jangan menilai isi buku dari kovernya tetapi nilailah dari isinya. Kover sangat penting karena menunjukkan identitas pengarang. Sosok penulis tidak dihadirkan sebagai foto diri namun secara kreatif diwakilkan oleh simbol grafis, tulisan, dan gambar. Kover dinilai karena ada proses kreatif dalam pembuatannya.

Contoh:

Ad

ap

t Tru

th In

You21

II. KATA PENYEMANGAT

Mencari ilmu adalah perjuangan! Upaya ini memerlukan semangat tinggi untuk bertahan sampai selesai mengikuti ujian UAS. Ada beberapa kendala yang mengintai proses pencarian ini. Gangguan yang berkaitan dengan kesehatan dan emosi atau gangguan yang berkaitan dengan ekonomi. Kurang tidur, terserang flu, atau kurang tidur adalah contoh yang pertama sedangkan kurang jajan dan telat bayar kuliah adalah contoh gangguan kedua.

Untuk mempertahankan semangat mencari ilmu agar selalu dalam kondisi puncak, salah satunya adalah mencari kata-kata yang dapat menggugah dari tokoh-tokoh terkenal di bidang sains atau matematika.

Contoh:

Logic will get you from A to B. Imagination will take you everywhere.

III. FAKTA OBJEKTIF

Fakta objektif merupakan data yang dikumpulkan dari hasil membaca teks buku dan merupakan potongan yang menarik minat dan layak dikumpulkan untuk dirangkai menjadi suatu pengertian. Fakta objektif merupakan kutipan langsung yang direkam secara apa adanya. Teknik yang digunakan adalah menggunakan printscreen-paste melalui paint, kemudian setelah di-cut sesuai bagian yang diinginkan di-paste di lembar word. Dari setiap tugas mingguan yang diberikan, diperlukan sebanyak 5 (lima) lembar kutipan langsung. Setiap kutipan perlu diberi label yang diikuti dengan nomor halaman sebagai penanda untuk memudahkan referensi apabila ada tulisan yang perlu detil penjelasan.

Contoh:

Prinsip dasar menghitung, hal. 3

Ad

ap

t Tru

th In

You21

IV. PETA PIKIRAN

Seluruh label fakta objektif kemudian dikategori sesuai plot tulisan yang ingin disampaikan penulis. Pengkategorian menggunakan hubungan logis antar fakta yang membentuk suatu pemahaman. Agar memudahkan alur pikir, dapat menggunakan aplikasi xmind.

Contoh:

V. SOAL BIASA

Soal biasa adalah pernyataan yang dimulai dengan kata, “Hitunglah, Selesaikan, Carilah, atau kalimat perintah semisal lainnya.” Gunakan bahasa Indonesia sebagai bahasa ilmiah. Soal wajib ditulis dalam bahasa Indonesia sekalipun sumbernya dari bahasa Inggris. Unsur yang dinilai adalah kemahiran siswa memilih kata dalam merumuskan gagasannya.

Contoh:

Tentukan fungsi pembangkit (generating function) dan tunjukkan koefiesien suku dari fungsi yang diperlukan untuk mendapatkan solusi bulat persamaan:

Ad

ap

t Tru

th In

You21

c1+c2+c3+c4=20 , dengan pembatasan 0≤ck≤6 untuk setiap 1≤k≤4 .

VI. SOAL PEMBUKTIAN

Soal pembuktian adalah pernyataan yang dimulai dengan kata, “Buktikan, Tunjukkan, Ceritakan, atau kalimat perintah semisal lainnya.” Gunakan bahasa Indonesia sebagai bahasa ilmiah. Soal wajib ditulis dalam bahasa Indonesia sekalipun sumbernya dari bahasa Inggris. Unsur yang dinilai adalah kemahiran siswa memilih kata dalam merumuskan gagasannya.

Contoh:

Gagasan John Nash tentang governing dynamics muncul pada saat bersama ke-empat temannya membicarakan pesona seorang gadis pirang dan ke-empat teman gadis itu. Coba ceritakan secara singkat alur algoritmanya. Adakah diantara ke-empat teman John yang berhasil memikat si gadis pirang?

VII. JAWABAN RINGKAS

Jawaban singkat adalah pernyataan yang langsung menunjukkan hasil akhir dari soal. Jawaban singkat merupakan kesimpulan akhir dari algoritma (langkah-langkah) pengerjaan soal. Unsur yang dinilai adalah kemahiran siswa memilih kata dalam merumuskan gagasannya.

Contoh:

Koefiesien suku dari fungsi yang diperlukan untuk mendapatkan solusi bulat persamaan:

c1+c2+c3+c4=20 , dengan pembatasan 0≤ck≤6 untuk setiap 1≤k≤4, adalah

35.

VIII. JAWABAN RUNTUT

Jawaban runtut adalah pernyataan yang selain menyampaikan hasil akhir dari soal namun juga menguraikan algoritma (langkah-langkah) pengerjaan soal. Unsur yang dinilai adalah kemahiran siswa memilih kata dalam merumuskan gagasannya.

Contoh:

Fungsi pembangkit f ( x ) adalah,

Ad

ap

t Tru

th In

You21

f ( x )=( x0+x1+ x2+…+x5+x6 ) (x0+ x1+x2+…+x5+x6 ) (x0+x1+x2+…+x5+x6 ) (x0+x1+x2+…+x5+x6 )=(x0+x1+ x2+…+ x5+x6 )4

Solusi c1+c2+c3+c4=20 adalah yang koefisien dari ekspresi x20 .

Ini adalah permutasi multi n – objek. Ini terjadi apabila,

x2 x6 x6 x6 ada sebanyak ( 41,3)= 4 !1 !3!

=4

x3 x5 x6 x6 ada sebanyak ( 41,1,2)= 4 !

1!1 !2 !=12

x4 x5 x5 x6 ada sebanyak ( 41,2,1)= 4 !

1!2 !1 !=12

x4 x4 x6 x6 ada sebanyak ( 42,2)= 4 !!2 !2!

=6

x5 x5 x5 x5 ada sebanyak 1

Jadi koefisien dari ekspresi x20 adalah 35.

IX. ESAI SEDERHANA

Tujuan pembuatan tugas mingguan adalah melatih siswa untuk mampu menyampaikan pengetahuan (knowledge) yang diperoleh setelah (1) membaca; (2) mengumpulkan fakta objektif; (3) membuat peta pikiran; (4) memahami soal dan jawaban, menjadi sebuah esai. Esai sederhana adalah tulisan yang berisi tentang ringkasan atau komentar tentang fakta objektif yang disampaikan semata-mata untuk memenuhi target mengisi penuh satu halaman A4. Esai dinilai berdasarkan kreatifitas siswa menemukan kata yang tepat untuk menyampaikan gagasannya.

Contoh:

Definisi graf secara bahaasa yaitu jalur yang dapt dibuat dari beberapa vertex(titik) yang mana hanya dapat dilalui satu kali. Sedangkan pada multigraf sedikit berbeda karena dapat melalui/melewati vertex (indeg/outdeg) lebih dari 1 kali.

Sebuah graf G terdiri dari dua hal:

(I) V = V (G) elemen yang disebut simpul, set poin, atau node G.

(Ii) Satu set E = E (G) unordered pasangan simpul yang berbeda disebut tepi G.

Ad

ap

t Tru

th In

You21

Kita menyatakan seperti grafik dengan G (V, E) ketika kita ingin menekankan dua bagian G.disebut endpoint e, dan e dikatakan dapat terhubung u dan v. Juga, e tepi

dikatakan insiden pada masing-masing titik ujungnya u dan v.

Degree of a Vertex Yaitu Derajat dari simpul v dalam graf G, ditulis deg (v), sama dengan jumlah sisi di G yang mengandung v, yaitu, yang insiden pada v. Karena setiap tepi dihitung dua kali dalam menghitung derajat simpul dari G,

Teorema 8.1: Jumlah dari derajat simpul dari graf G adalah sama dengan dua kali jumlah edge di G.Perhatikan, misalnya, grafik pada Gambar. 8-5 (a). Kami memiliki

deg (A) = 2, deg (B) deg = 3, (C) = 3, deg (D) = 2.

Jenis-jenis graph1. Subgraphs2. Isomorphic Graphs3. Homeomorphic Graphs4. Hamiltonian Graphs5. Complete Graphs6. Regular Graphs7. Tree Graphs8. Eulerian graphs

Bilangan kromatik dan pewarnann graph

Definisi 1: Suatu pewarnaan grafik sederhana adalah penugasan warna untuk setiap simpul dari graf sehingga tidak ada dua titik yang berdekatan yang ditugaskan warna yang sama.

Definisi 2: Jumlah kromatis dari graf adalah sedikitnya jumlah warna diperlukan untuk mewarnai grafik ini. Jumlah kromatis dari graf G dinotasikan dengan X (G). (Di sini X adalah huruf Yunani chi.) (Ipul, 2011)

X. ESAI LENGKAP

Esai lengkap adalah penghalusan (refinement) dari esai sederhana. Esai lengkap selain memuat ringkasan atau komentar tentang fakta objektif, namun juga memperhatikan urutan logis pemaparan sehingga menjadi tulisan yang enak dibaca dan mudah dipahami gagasannya. Esai dinilai berdasarkan kreatifitas siswa menemukan kata yang tepat untuk menyampaikan gagasannya.

Contoh:

Seperti yang sudah kita bahas pada tugas 4 , Pengertian dari Graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang

Ad

ap

t Tru

th In

You21

terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop). Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut, sedangkan Graf Planar, Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graf planar, jika tidak, ia disebut graf tak-planar. Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan disebut graf bidang (plane graph).

Jenis - jenis graf yang dibahas dalam bab ini yaitu : Graph bagian (subgraph) yaitu Sebuah graph H disebut graph bagian (subgraph) dari graph G. Graph Trivial yaitu Graph yang tidak memiliki sisi disebut graph kosong atau graph nol. Graph nol dengan n titik dilambangkan dengan Nn , graph yang hanya mempunyai satu buah titik tanpa sebuah sisi dinamakan graph trivial. Graph Bipartisi yaitu Sebuah graph G disebut graph bipartisi jika V(G) (himpunan titik graph G) dapat dipartisi menjadi dua himpunan bagian X dan Y sedemikian sehingga setiap sisi dari G menghubungkan sebuah titik di X dan sebuah titik di Y. Complete graf yaitu Sebuah graph komplit (graph lengkap) dengan n titik, dilambangkan dengan Kn , adalah graph sederhana dengan n titik dan setiap dua titik berbeda dihubungkan dengan sebuah sisi, sebuah graph lengkap sering juga disebut sebagai graph universal. Graph berbobot Sebuah graph G disebut graph berbobot jika setiap sisinya diberi sebuah harga. Isomorfik Graf yaitu Dua graph G dan H dikatakan isomorfik ditulis , jika Terdapat korespondensi satu-satu antara V(G) dan E(G), dan banyaknya sisi yang menghubungkan dua titik u dan v di G, sama dengan banyaknya sisi yang menghubungkan dua titik di H yang korespondensi dengan titik u dan titik v. Selanjutnya masih banyak lagi jenis jenis graf yang lainnya seperti homeomorphic graf ,tree graf, dan regular graf.

Yang akan dibahas mengenai bilangan kromatik dalam bab ini adalah pengertian dari bilangan kromatik sendiri, yaitu bilangan terkecil dari banyaknya warna yang digunakan dalam perwarnaan graph, sedangkan Pewarnaan dari simple graph adalah pemberian warna pada setiap vertex dari graph sehingga tidak ada vertex yang bertetangga mempunyai warna yang sama.

Terakhir yaitu mengenai pewarnaan Graf (Graph Coloring). Pewarnaan graf adalah kasus khusus dari pelabelan graf. Pelabelan disini maksudnya, yaitu memberikan warna pada titik-titik pada batas tertentu. Ada tiga macam pewarnaan graf. Pertama, pewarnaan titik (vertex coloring) yaitu memeberikan warna berbeda pada setiap titik yang bertetangga sehingga tidak ada dua titik yang bertengga dengan warna yang sama. Kedua, pewarnna sisi (edge coloring), yaitu memberikan warna berbeda pada sisi yang bertetangga sehingga tidak ada dua sisi yang bertetangga

Ad

ap

t Tru

th In

You21

memepunya warna yang sama. Ketiga, pewarnaan bidang, yaitu memberikan warna pada bidang sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama.

Perhatikan grafik G. pewarnaan vertex, pewarnaan sederhana G adalah penyerahan warna untuk simpul dari G sedemikian rupa sehingga simpul yang bersebelahan memiliki warna yang berbeda. Kami mengatakan bahwa G adalah n-yg dpt diwarnai jika terdapat pewarnaan G yang menggunakan warna n. Jumlah warna minimum yang diperlukan untuk cat G disebut sebagai bilangan kromatik dari G dan dinotasikan dengan χ (G). (Budi, 2011)

B. BACAAN

Buku wajib baca adalah Grimaldi (2004) dan Burger (2010). Buku lain merupakan koleksi yang dapat digunakan untuk memperkaya pemahaman secara mandiri. Seluruhnya ada sebanyak 23 (dua puluh) tiga buku yang mengulas langsung atau tidak langsung topik dalam MDT.

1. Anderson - A First Course in Discrete Mathematics (2002)

2. Benjamin - Discrete Mathematics Parts I and II (2009)

3. Burger - The Heart of Mathematics, An Invitation to Effective Thinking (2010)

4. Chen - Discrete Mathematics (1982)

5. Erickson - Pearls Of Discrete Mathematics (2010)

6. Garnier - Discrete Mathematics for New Technology, Ed. 2 (2002)

7. Grimaldi - Discrete and Combinatorial Mathematics, An Applied Introduction, Ed. 5 (2003)

8. Grimaldi - Discrete and Combinatorial Mathematics, Instructor's Solution Manual, Ed. 5 (2004)

9. Gunawan - Matematika dan Indonesia (2007)

10. Habib - Probabilistic Methods for Algorithmic Discrete Mathematics (1998)

11. Knuth - Selected Papers on Discrete Mathematics (2003)

12. Lipschutz - Discrete Mathematics, Ed. 3 (2007)

13. Lovász - Discrete Mathematics (2003)

14. Matousek - An Invitation to Discrete Mathematics, Ed. 2 (2008)

15. Mott - Discrete Mathematics, Ed. 2 (2008)

16. PBDBN - Kamus Bahasa Indonesia (2008)

17. Rosen - Discrete Mathematics and Its Applications, Ed. 6 (2007)

18. Rosen - Handbook of Discrete and Combinatorial Mathematics (1999)

19. Rosen - Handbook of Discrete and Combinatorial Mathematics (2000)

Ad

ap

t Tru

th In

You21

20. Rosen - Student's Solutions Guide for Use with Discrete Mathematics and Its Applications, Ed. 5 (2003)

21. Ross - Topics in Finite and Discrete Mathematics (2000)

22. Saxl - Discrete Mathematics (1995)

23. Scheinerman - Mathematics, A Discrete Introduction, Ed. 2 (2006)

C. VIDEO

Sumber pemahaman juga dapat diperoleh dari hasil menyimak The Teaching Company (TTC) oleh Arthur T. Benjamin yang dikemas dalam 24 (dua puluh empat) video ajar. Koleksi video berikut dapat digunakan untuk memperkaya pemahaman tentang topik dalam MDT.

1. What Is Discrete Mathematics?

2. Basic Concepts of Combinatorics.

3. The 12-Fold Way of Combinatorics.

4. Pascal's Triangle and the Binomial Theorem.

5. Advanced Combinatorics—Multichoosing.

6. The Principle of Inclusion-Exclusion.

7. Proofs—Inductive, Geometric, Combinatorial.

8. Linear Recurrences and Fibonacci Numbers.

9. Gateway to Number Theory—Divisibility.

10. The Structure of Numbers.

11. Two Principles—Pigeonholes and Parity.

12. Modular Arithmetic—The Math of Remainders.

13. Enormous Exponents and Card Shuffling.

14. Fermat's ''Little'' Theorem and Prime Testing.

15. Open Secrets—Public Key Cryptography.

16. The Birth of Graph Theory.

17. Ways to Walk—Matrices and Markov Chains.

18. Social Networks and Stable Marriages.

19. Tournaments and King Chickens.

20. Weighted Graphs and Minimum Spanning Trees.

21. Planarity—When Can a Graph Be Untangled.

22. Coloring Graphs and Maps.

23. Shortest Paths and Algorithm Complexity.

24. The Magic of Discrete Mathematics.

Ad

ap

t Tru

th In

You21

5. PENILAIAN

I. NILAI AKHIR

Nilai akhir ditentukan berdasarkan tugas mingguan dan ujian. Ada sebanyak 10 (sepuluh) tugas mingguan (TM), 1 (satu) ujian tengah semester (UTS), dan 1 (satu) ujian akhir semester (UAS).

Nilai akhir (NA) ditentukan oleh 30% TM, 30% UTS, dan 40% UAS.

NA=30%TM+30%UTS+40%U AS

II. NILAI TUGAS

Setiap kuliah, Siswa diwajibkan menyelesaikan tugas mingguan yang akan diberikan nilai berupa poin yang disetarakan dengan tingkatan mutu nilai akhir.

Universitas menganut rezim 9 tingkatan nilai (nilai huruf), yaitu:

NILAI HURUF

BOBOT NILAI NILAI ANGKA

A 4,00 80,00A― 3,70 77,00 – 79,99B+ 3,30 74,00 – 76,99B 3,00 71,00 – 73,99

B― 2,70 68,00 – 70,99C+ 2,30 64,00 – 67,99C 2,00 56,00 – 63,99D 1,00 46,00 – 55,99E 0,00 45,99

Untuk keperluan penilaian tugas mingguan, nilai huruf rentangnya dipecah menjadi dua, yaitu A dan A+ dengan bobot nilai yang sama dengan 4,00 sehingga daftarnya menjadi 10 (sepuluh) tingkatan, yaitu:

NILAI HURUF

BOBOT NILAI NILAI ANGKA

A+ 4,00 90,00 – 100,00A 4,00 80,00 – 89,99

A― 3,70 77,00 – 79,99B+ 3,30 74,00 – 76,99B 3,00 71,00 – 73,99

B― 2,70 68,00 – 70,99C+ 2,30 64,00 – 67,99C 2,00 56,00 – 63,99D 1,00 46,00 – 55,99E 0,00 45,99

Ad

ap

t Tru

th In

You21

Tugas mingguan dinilai berdasarkan 10 poin yang disesuaikan dengan masing-masing kelengkapan isi tugas, sebagai berikut:

Kover 1 poin Kata Penyemangat 1 poin Fakta Obyektif 5 Halaman A4 1 poin Peta Pikiran 1 poin Soal Biasa 1 poin Soal Pembuktian 2 poin Jawaban Singkat 1 poin Jawaban Runtut 2 poin Esai Satu Halaman A4 1 poin Esai Runtut 2 poin

III. DENDA

Tugas dikumpulkan paling lambat Hari Jumat, pukul 21.00 malam pada minggu berikutnya. Tugas disampaikan via e-mail ke alamat [email protected]. Setiap kelambatan pengiriman dikenakan denda 1 poin. Tugas yang terlambat lebih dari 7 (tujuh) hari, tidak akan dinilai.

IV. KEHADIRAN

Siswa diharapkan mengikuti 16 kali pertemuan termasuk UTS dan UAS. Sekalipun tidak datang, diharapkan siswa tetap mengerjakan tugas mingguannya dan menyampaikannya lewat internet.

6. PERMAINAN

Kuliah ini dirancang sebagai suatu kelompok bermain (team game). Pemainnya adalah semua yang ada didalam kelas. Ada dosen dan ada siswa yang saling berinteraksi. Nama permainannya adalah Sekolah Tinggi Matematika in The Second year. Supaya menarik, maka dalam permainan ini ada beberapa aturan yang perlu disepakati.

PANGGILAN. Panggilan harus sama, yaitu Mas atau Mbak. Ini membangkitkan perasaaan sama. Diwajibkan memakai papan nama (nametag) selama kuliah. Papan nama terdiri dari dua suku kata. Misalnya Do-Ni. Jadi panggilan kepada semua peserta selalu terdiri dari tiga suku kata. Mas-Do-Ni.

D O N I

Ad

ap

t Tru

th In

You21

SEMUA SEDERAJAT. Tidak ada yang lebih baik kecuali diukur dari kadar kemampuan-melaksanakan-perannya. Dosen punya peran dan siswa punya peran. Peran Dosen sebagai sutradara yang menyiapkan silabus, memberikan kuliah, memberi tugas, dan melakukan evaluasi. Peran siswa adalah menyiapkan alat bantu belajar mandiri (laptop, koneksi internet, kemampuan browsing), bertanya dan mengajukan gagasan, membuat kelompok belajar, dan melakukan evaluasi.

WAJIB SALING BANTU. Semua saling membantu agar setiap pemain mampu melaksanakan perannya dengan hasil optimal. Bentuk bantuan adalah berbagi pengetahuan, berbagi catatan, berbagi informasi, dan hal baik lain yang dapat dibagi. Dilarang keras membantu pada saat UJIAN. Yang ketahuan membantu kawan pada saat ujian didenda dengan membuat tulisan sepanjang 10.000 kata.

PETUNJUK NAMA. Silahkan memilih nama panggilan dengan menghindari kemiripan dengan pemilik nama sebelumnya. Misalnya jika sudah ada yang menggunakan nama DONI, maka siswa selanjutnya tidak boleh lagi menggunakan nama DONI, tapi bisa menggunakan nama lain. Misalnya ONDI.

NAMA TERDAFTAR. Berikut ini adalah nama panggilan yang sudah digunakan oleh siswa sebelumnya, diurutkan secara abjad.

1. ALFI - Alfiah

2. ANIK - Anik Sustriyani

3. BUDI - Lanang Budi Satria

4. DARTO - Sudarto

5. EKA - Karnila Eka Maryaningtyas

6. FIFI - Rofiatul Hasanah

saling bantu saat ujian

Ad

ap

t Tru

th In

You21

7. HESTI - Suhesti Mayasari

8. INDAH - Sari Indah

9. IPUL - Saifulloh

10. KHAMID - Khamid

11. LIA - Lia Rahmalia (SM2 – THL)

12. LUSI - Lusitania Eka Putri (SM1 – THL)

13. MIDAH - Hamidah

14. NADLAR - Syariful Nadlar

15. NIKEN - Andiken Syahril

16. NOVI - Novia Vadillah

17. OZAN - Achmad Fauzan Arif

18. PIPIN - Pipin Sapinah (SM2 – TPL)

19. PUTRA - Herlambang Adi Saputra

20. PUTRI - Rezky Wibisono Putri

21. RIZKA - Thiara Rizka Hasyuni

22. ROBERT - Yulius Robert Winarto

23. ROBY - Roby Satriya

24. TITIK - Titik Sulistyowati

25. TOTOK - Totok Adianto

26. VERI - Alifiati Veriasi Setianingsih (SM1 – MDT)

27. YUDI - Wahyudi

28. YUSTI - Yustisia Dwi Setia

29. ZEIN - Zein Abdulloh Malik

pedoman kuliah

Documents