Review Pembahasan Bab :  Tree

Pohon (tree) merupakan salah satu bentuk khusus dari struktur suatu graf. Misalkan A merupakan sebuah himpunan berhingga simpul (vertex) pada suatu graf G yang terhubung. Untuk setiap pasangan simpul di A dapat ditentukan suatu lintasan yang menghubungkan pasangan simpul tersebut. Suatu graf terhubung yang setiap pasangan simpulnya hanya dapat dihubungkan oleh suatu lintasan tertentu, maka graf tersebut dinamakan pohon (tree). Dengan kata lain, pohon (tree) merupakan graf tak-berarah yang terhubung dan tidak memiliki sirkuit.

A.) Pohon Merentang Minimum (Minimum Spanning Tree)
Spanning Tree dari suatu graf terhubung merupakan subgraf merentang yang berupa pohon. Pohon merentang diperoleh dengan cara menghilangkan sirkuit di dalam graf tersebut.

B.) Pohon Berakar
Pada suatu pohon, yang sisi-sisinya diberi arah sehingga menyerupai graf berarah, maka simpul yang terhubung dengan semua simpul pada pohon tersebut dinamakan akar. Suatu pohon yang satu buah simpulnya diperlakukan sebagai akar maka pohon tersebut dinamakan pohon berakar (rooted tree). Simpul yang berlaku sebagai akar mempunyai derajat masuk sama dengan nol. Sementara itu, simpul yang lain pada pohon itu memiliki derajat masuk sama dengan satu. Pada suatu pohon berakar, Simpul yang memiliki derajat keluar sama dengan nol dinamakan daun.

C.) Penelusuran Pohon Biner 

 

Ada tiga jenis penelusuran pohon biner, antara lain :
1. Preorder : A, S, T
- kunjungi A
- kunjungi S secara preorder
- kunjungi T secara preorder
2. Inorder : S , A, T
- kunjungi S secara inorder
- kunjungi A
- kunjungi T secara inorder
3. Postorder : S, T , A
- kunjungi S secara postorder
- kunjungi T secara postorder
- kunjungi A

You can download chapter Tree here :

Three

Review Pembahasan : Teori graf

Makalah pertama tentang teori graf ditulis pada tahun 1736 oleh seorang matematikawan Swiss yang bernama Leonard Euler. Ia menggunakan teori graf untuk menyelesaikan masalah jembatan Königsberg (sekarang, bernama Kaliningrad).

A.) Definisi Graf

Graf merupakan struktur diskrit yang terdiri himpunan sejumlah berhingga obyek yang disebut simpul (vertices, vertex) dan himpunan sisi (edges) yang menghubungkan simpul-simpul terseut. terdiri dari dari Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut.

B.) Terminologi Graf

Ada beberapa terminologi graf yang perlu diketahui, antara lain : ketetanggaan antara dua simpul, bersisian , derajat suatu simpul, dan lain-lain.

C.) Beberapa Jenis Graf

Beberapa jenis graf tak berarah yang perlu diketahui adalah :
1. Graf sederhana (simple graph) : Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi-ganda.

2. Graf Ganda (multigraph) : Graf ganda merupakan graf tak berarah yang tidak mengandung gelang (loop).

3. Graf semu (Pseudo graph) : Graf semu merupakan graf yang boleh mengandung gelang (loop).

4. Graf berarah (directed graph atau digraph) : Graf berarah merupakan graf yang setiap sisinya mempunyai arah dan tidak mempunyai dua sisi yang berlawanan antara dua buah simpul (tak mempunyai sisi ganda).

5. Graf ganda berarah (directed multigraph) : Graf ganda berarah merupakan graf berarah yang membolehkan adanya sisi ganda pada graf tersebut (boleh mempunyai dua sisi yang berlawanan antara dua buah simpul).

 

D.) Keterhubungan dan Sub Graf

Dua buah simpul v1 dan simpul v2 pada suatu graf dikatakan terhubung jika terdapat lintasan dari v1 ke v2. Jika setiap pasang simpul vi dan vj dalam himpunan V pada suatu graf G terdapat lintasan dari vi ke vj maka graf tersebut dinamakan graf terhubung (connected graph). Jika tidak, maka G dinamakan graf tak-terhubung (disconnected graph).

E.) Matriks Ketetanggaan (adjacency matrix) dan Matriks Bersisian (incidency matrix) dari Suatu Graf

Matriks ketetanggaan untuk graf sederhana merupakan matriks bukur sangkar yang unsur-unsurnya hanya terdiri dari dua bilangan yaitu 0 (nol) dan 1 (satu). Baris dan kolom pada matriks ini, masing-masing merupakan representasi dari setiap simpul pada graf tersebut. Matriks ketetanggaan untuk graf tak sederhana merupakan matriks bukur sangkar yang unsur-unsurnya hanya terdiri dari bilangan 0 (nol), 1 (satu) dan 2 (dua). Baris dan kolom pada matriks ini, masing-masing merupakan representasi dari setiap simpul pada graf tersebut.

F.) Lintasan dan Sirkuit Euler

Lintasan Euler dalam suatu graf merupakan lintasan yang melalui masing-masing sisi didalam graf tersebut tepat satu kali. Jika lintasan tersebut kembali kesimpul awal, sehingga membentuk lintasan tertutup (sirkuit) maka lintasan ini dinamakan sirkuit Euler. Dengan demikian, sirkuit Euler merupakan sirkuit yang melewati masing-masing sisi tepat satu kali. Graf yang memuat sirkuit Euler dinamakan graf Euler (Eulerian graph), sedangkan graf yang memuat lintasan Euler dinamakan graf semi Euler (semi-Eulerian graph).

G.) Lintasan dan Sirkuit Hamilton

Sir Wiliam Hamilton pada tahun 1859 membuat permainan dodecahedron yang ditawarkan pada pabrik mainan di Dublin. Permainan tersebut terdiri dari 12 buah pentagonal dan ada 20 titik sudut (setiap sudut diberi nama ibu kota setiap negara) . Permainan ini membentuk perjalanan keliling dunia yang mengunjungi setiap ibu kota Negara tepat satu kali dan kembali lagi ke kota asal. Ini tak lain adalah mencari sirkuit Hamilton.

H.) Graf Isomorfik dan Homeomorfik

Suatu graf dapat digambarkan dengan berbagai cara. Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Sebagai contoh dua graf diatas merupakan dua graf yang isomorfik. Dua buah graf dikatakan isomorfik jika memenuhi ketiga syarat berikut (Deo, 1989):
1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama
3. Mempunyai jumlah simpul yang sama berderajat tertentu

I.) Aplikasi Graf

Bebarapa aplikasi dari Graf antara lain ; Lintasan Terpendek (Shortest Path), Algoritma Lintasan Terpendek Dijkstra, Persoalan Perjalanan Pedagang (Travelling Salesperson Problem - TSP), Persoalan Tukang Pos Cina (Chinese Postman Problem).

You can download the slide here :

Graph Teory

Review : Pembahasan Bab Kombinatorik

Kombinatorik merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya. 

A.) Prinsip Dasar Menghitung

Dua prinsip dasar yang digunakan dalam menghitung (counting) yaitu aturan pejumlahan dan aturan perkalian. Secara tidak langsung, pada prinsip penjumlahan, setiap himpunan bagian A1, A2, …, An tidak saling tumpang tindih (saling lepas). Untuk himpunan yang saling tumpang tindih tidak berlaku lagi prinsip penjumlahan, dan ini harus diselesaikan dengan prinsip inklusi-eksklusi. Secara tidak langsung, pada prinsip perkalian, bisa terjadi saling tumpang tindih (tidak saling lepas).

B.) Permutasi dan Kombinasi

Permutasi adalah merupakan susunan yang mungkin dibuat dengan memperhatikan urutan. Dengan kata lain, permutasi merupakan bentuk khusus aplikasi prinsip perkalian. Kombinasi adalah Misalkan r merupakan unsur bilangan bulat tak negatif. Yang dimaksud dengan kombinasi r dari suatu himpunan B yang terdiri dari n anggota (objek) yang berbeda adalah jumlah himpunan bagian dari B yang memiliki anggota r buah objek. Interpretasi yang lain tentang kombinasi adalah menyusun (memilih) objek sejumlah r dari n buah objek yang ada.

Materi pada pembahasan Permutasi dan Kombinasi bisa di download di link dibawah ini.

You can download the slide here :

Kombinatorik

Review : RELASI DAN FUNGSI

Pada pertemuan ini, akan dibahas tentang hubungan antara dua himpunan tak kosong dengan suatu aturan pengkaitan tertentu. Pembahasan tersebut meliputi definisi relasi dan fungsi, operasi beserta sifat-sifatnya.

A.) Definisi Relasi dan Cara Penyajian

Cartesian product, yaitu berupa pasangan terurut yang menyatakan hubungan dari dua himpunan. Semua pasangan terurut yang mungkin merupakan anggota dari himpunan hasil Cartesian product dua buah himpunan. Sebagian dari anggota himpunan tersebut mempunyai hubungan yang khusus (tertentu) antara dua unsur pada pasangan urut tersebut, dengan aturan tertentu. Aturan yang menghubungkan antara dua himpunan dinamakan relasi biner. Relasi antara himpunan A dan himpunan B merupakan himpunan yang berisi pasangan terurut yang mengikuti aturan tertentu. Dengan demikian relasi biner R antara himpunan A dan B merupakan himpunan bagian dari cartesian product A × B atau R ⊆ (A × B).

B.) Sifat Relasi

Relasi yang didefinisikan pada sebuah himpunan mempunyai beberapa sifat. Sifat-sifat tersebut antara lain ; refleksif, transitif, simetris.

C.) Operasi pada Relasi

Relasi merupakan himpunan pasangan terurut maka beberapa operasi aljabar yang berlaku pada himpunan, juga beraku pada relasi. Operasi himpunan seperti irisan, gabungan, selisih, dan beda setangkup juga berlaku atara dua relasi. Jika R1 dan R2 masing-masing merupakan relasi dari himpuna A ke himpunan B, maka R1 ∩ R2, R1 ∪ R2, R1 – R2, dan R1 ⊕ R2 juga adalah relasi merupakan dari A ke B.

D.) Relasi Ekivalen dan Relasi Terurut
Sebuah relasi pada himpunan A dinamakan relasi ekivalen jika relasi tersebut refleksif, simetri dan transitif. Dua unsur yang berelasi ekivalen disebut equivalent.

Materi bisa di download di link dibawah ini.

You can download the slide here :

Relasi dan Fungsi

Review Pembahasan : HIMPUNAN

Pada pertemuan pertama dikelas, pertanyaan awal yang muncul adalah "Apa itu Himpunan?"

Dalam kehidupan nyata, banyak sekali masalah yang terkait dengan data (objek) yang dikumpulkan berdasarkan kriteria tertentu. Kumpulan data (objek) inilah yang selanjutnya didefinisikan sebagai himpunan.

Selanjutnya, pada pembahasan awal ini akan dibahas tentang definisi dan keanggotaan suatu himpunan, operasi himpunan dari beberapa jenis himpunan.

A.) Definisi dan Keanggotaan Suatu Himpunan

Himpunan (set) merupakan sekumpulan objek-objek yang berbeda yang dapat didefinisikan dengan jelas. Objek di dalam himpunan dinamakan unsur atau anggota himpunan. Keanggotaan suatu himpunan dinyatakan oleh notasi ’∈’ (Kalau waktu SMA dulu biasa disebut 'elemen').

B.) Operasi Himpunan

Dalam operasi himpunan yang perlu diketahui ; irisan , gabungan, komplemen, selisih dan beda setangkup.

C.) Prinsip Dualitas

Prinsip dualitas mengemukakan bahwa dua konsep yang berbeda dapat dipertukarkan namun tetap memberikan jawaban yang benar. Dalam membuktikan kebenaran suatu pernyataan atau merepresentasikan suatu pernyataan dengan cara lain dengan menggunakan bantuan himpunan.

E.) Multi Set dan Fuzzy Set

Pada bagian akan diberikan penjelasan tentang Multi Set dan Fuzzi Set. Sehingga diharapkan pembaca dapat mengetahui perbedaan di antara keduanya.

Materi pada pembahasan Himpunan bisa diunduh pada link dibawah.
You can download the slide : Here