sekilas tentang matematika deskrit

   Dalam kehidupan nyata, senantiasa ada hubungan (relasi) antara dua hal atau unsur-unsur dalam suatu kelompok. Misalkan, hubungan antara suatu urusan dengan nomor telepon, antara pegai dengan gajinya, dan lain-lain. Pada bab 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.

   Pada bab sebelumnya, telah dibahas tentang 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).

Notasi dari suatu relasi biner adalah a R b atau (a, b) ∈ R. Ini berarti bahwa a dihubungankan dengan b oleh R. Untuk menyataan bahwa suatu unsur dalam cartesian product bukan merupakan unsur relasi adalah a R b atau (a, b) ∉ R, yang artinya a tidak dihubungkan oleh b oleh relasi R. Himpunan A disebut daerah asal (domain) dari R, dan

himpunan B disebut daerah hasil (range) dari R.

Persoalan kombinatorik bukan merupakan persoalan yang baru dalam kehidupan nyata. Banyak persoalan kombinatorik yang sederhana telah diselesaiakan dalam masyarakat. Misalkan, saat pemilihan pemain untuk tim sepak bola yang terdiri dari 11 pemain. Apabila ada 20 orang ingin membentuk suatu tim sepak bola, ada berapa kemungkinan komposisi pemain yang dapat terbentuk? Contoh lain adalah dalam menentukan sebuah password panjangnya 6 sampai 8 karakter. Karakter boleh berupa huruf atau angka. Berapa banyak kemungkinan password yang dapat dibuat ? Tetapi selain itu para ilmuwan pada berbagai bidang juga kerap menemukan sejumlah persoalan yang harus diselesaikan. Pada Bab ini, kita akan membahas tentang kombinatorik, permutasi dan apa yang terkait dengan itu. Kombinatorik merupakan cabang matematika untuk menghitung jumlah penyusunan objek-objek tanpa harus mengenumerasi semua kemungkinan susunannya.

Dua prinsip dasar yang digunakan dalam menghitung (counting) yaitu aturan

pejumlahan dan aturan perkalian.

Jika suatu himpunan A terbagi kedalam himpunan bagian A1, A2, …, An, maka jumlah unsur pada himpunan A akan sama dengan jumlah semua unsur yang ada pada setiap himpunan bagian A1, A2, …, An.

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.

Misalkan sebuah prosedur dapat dipecah dalam dua penugasan. Penugasan pertama dapat dilakukan dalam n1 cara, dan tugas kedua dapat dilakukan dalam n2 cara setelah tugas pertama dilakukan. Dengan demikian, dalam mengerjakan prosedur tersebut ada (n1 x n2) cara.

Secara tidak langsung, pada prinsip perkalian, bisa terjadi saling tumpang tindih (tidak saling lepas).

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. tidak berarah dan graf berarah. Graf tidak berarah, seperti telah dijelaskan pada contoh graf untuk jembatan Königsberg. Sementara itu, graf berarah (directed graph, digraph) merupakan graf yang mempunyai sisi yang berarah, artinya satu buah simpul yang dihubungkan oleh sisi tersebut merupakan simpul awal (initial vertex) dan simpul yang lain dikatakan sebagai simpul akhir (terminal vertex).