SEJARAH DARI MATEMATIKA DESKRIT
MATEMATIKA MENURUT SEJARAH
Matematika (dari bahasa Yunani: μαθηματικά - mathēmatiká) adalah studi besaran, struktur, ruang, dan perubahan. Para matematikawan mencari berbagai pola, merumuskan konjektur baru, dan membangun kebenaran melalui metode deduksi yang kaku dari aksioma-aksioma dan definisi-definisi yang bersesuaian.
Terdapat perselisihan tentang apakah objek-objek matematika seperti bilangan dan titik hadir secara alami, atau hanyalah buatan manusia. Seorang matematikawan Benjamin Peirce menyebut matematika sebagai "ilmu yang menggambarkan simpulan-simpulan yang penting". Di pihak lain, Albert Einstein menyatakan bahwa "sejauh hukum-hukum matematika merujuk kepada kenyataan, mereka tidaklah pasti; dan sejauh mereka pasti, mereka tidak merujuk kepada kenyataan."
Melalui penggunaan penalaran logika dan abstraksi, matematika berkembang dari pencacahan, perhitungan, pengukuran, dan pengkajian sistematis terhadap bangun dan pergerakan benda-benda fisika. Matematika praktis telah menjadi kegiatan manusia sejak adanya rekaman tertulis. Argumentasi kaku pertama muncul di dalam Matematika Yunani, terutama di dalam karya Euklides, Elemen.
Matematika selalu berkembang, misalnya di Cina pada tahun 300 SM, di India pada tahun 100 M, dan di Arab pada tahun 800 M, hingga zaman Renaisans, ketika temuan baru matematika berinteraksi dengan penemuan ilmiah baru yang mengarah pada peningkatan yang cepat di dalam laju penemuan matematika yang berlanjut hingga kini.
Kini, matematika digunakan di seluruh dunia sebagai alat penting di berbagai bidang, termasuk ilmu alam, teknik, kedokteran/medis, dan ilmu sosial seperti ekonomi, dan psikologi. Matematika terapan, cabang matematika yang melingkupi penerapan pengetahuan matematika ke bidang-bidang lain, mengilhami dan membuat penggunaan temuan-temuan matematika baru, dan kadang-kadang mengarah pada pengembangan disiplin-disiplin ilmu yang sepenuhnya baru, seperti statistika dan teori permainan.
Sejarah penemuan dari Matematika Diskrit
Sejarah matematika diskrit muncul dari beragam permasalahan rumit yang mengundang perhatian ke bidang tersebut. Di grafis, banyak penelitian dilakukan untuk membuktikan teorema 4 warna, yang pertama kali muncul pada tahun 1852, berhasil dibuktikan pada tahun 1976 oleh Kenneth Appel serta Wolfgang Haken menggunakan bantuan computer.
Kebutuhan untuk memecahkan kode dikembangkan oleh Jerman pada Perang Dunia II menyebabkan perkembangan kriptografi serta ilmu computer, dengan berkembangnya komputer dijital elektronik dapat di program pertama di Inggris. Pada waktu bersamaan, kebutuhan militer mengundang perkembangan pada penelitian operasi.
Perang Dingin menunjukan bahwa kriptografi tetaplah penting, dengan perkembangan penting seperti kriptografi public-key dikembangkan bertahun-tahun kemudian. Penelitian operasi tetap menjadi alat penting di dalam bisnis manajemen proyek, dengan metode jalur penting dikembangkan pada tahun 1950an. Industri telekomunikasi juga memacu perkembangan perhitungan, terutama pada teori grafis dan teori informasi. Verifikasi sebuah pernyataan logika menjadi wajib di pengembangan perangkat lunak dan sistem keamanan.
Geometri komputasional juga menjadi bagian penting di grafis komputer menjadi bagian permainan video modern dan peralatan desain komputer. Beberapa bagian matematika diskrit seperti teori ilmu komputer, teori grafis dan kombinatoris menjadi penting dalam menghadapi permasalah bioinformatika dalam memahami pohon kehidupan.
Sejarah Graf
Penemu graf adalah L. Euler ( Leonhard Euler ). Graf ditemukan disebuah jembatan Königsberg (tahun1736). Di kota Königsberg (sebelah timur negara bagian Prussia, Jerman), yang sekarang bernama kota Kaliningrad, terdapat sungai Pregal yg mengalir mengintari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai. Ada 7 buah jembatan yg menghubungkan daratan yg dibelah oleh sungai tersebut. Sejarah Graf : masalah jembatan Königsberg (tahun 1736)Graf yang merepresentasikan jembatan Königsberg:
Simpul (vertex) à menyatakan daratan
Sisi (edge) à menyatakan jembatan
Definisi Graf
Graf merupakan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini:
– V = himpunan tidak - kosong dari simpul-simpul (vertices) = { v1 , v2 , ... , vn }, dan
– E = himpunan sisi (edges) yang mnghubungkan sepasang simpul = {e1 , e2 , ... , en }
Definisi diatas mengatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong.
Jadi sebuah graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada.
Unsur - Unsur dari Graf
Simpul (Vertex) adalah daratan ( titik - titik yg dihubungkan oleh jembatan ), yang dinyatakan sebagai titik (noktah).
Sisi (Edge) adalah jembatan yang dinyatakan sebagai garis.
Garis Paralel adalah pada G2, sisi E3 = (1,3) dan sisi E4 = (1,3) dinamakan sisi ganda.
Komponen Graf
Alur adalah setiap lintasan yang semua titik simpul berbeda satu sama lain kecuali titik awal dan titik akhirnya.
Panjang adalah banyak sisi / lintasan yang ditempuh.
Derajat adalah jumlah rusuk atau sisi yang menuju satu titik simpul.
Titik terasing adalah titik yang tidak memiliki garis penghubung / jalan.
Jalan tapak adalah suatu lintasan yang tidak memiliki dua rusuk yang sama.
Ketetanggan adalah dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Graf Kosong adalah graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Siklus atau sirkuit adalah lintasan yang berawal dan berakhir pada simpul yang sama.
Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut.
Terhubung adalah dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1. Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari Gdiperoleh dengan menghilangkan arahnya).
Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u. Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).
Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.
Upagraf dan Komplomen Upagraf Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
UpagrafRentang Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).
Cut - Set adalah adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.
Contoh :
Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set, tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).
Sisi (Edge) adalah jembatan yang dinyatakan sebagai garis.
Garis Paralel adalah pada G2, sisi E3 = (1,3) dan sisi E4 = (1,3) dinamakan sisi ganda.
Komponen Graf
Alur adalah setiap lintasan yang semua titik simpul berbeda satu sama lain kecuali titik awal dan titik akhirnya.
Panjang adalah banyak sisi / lintasan yang ditempuh.
Derajat adalah jumlah rusuk atau sisi yang menuju satu titik simpul.
Titik terasing adalah titik yang tidak memiliki garis penghubung / jalan.
Jalan tapak adalah suatu lintasan yang tidak memiliki dua rusuk yang sama.
Ketetanggan adalah dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Graf Kosong adalah graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Siklus atau sirkuit adalah lintasan yang berawal dan berakhir pada simpul yang sama.
Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut.
Terhubung adalah dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1. Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari Gdiperoleh dengan menghilangkan arahnya).
Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u. Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).
Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.
Upagraf dan Komplomen Upagraf Komplemen dari upagraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E - E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
UpagrafRentang Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).
Cut - Set adalah adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.
Contoh :
Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung. Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set, tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).
Jenis - Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. G1 pada contoh graf sederhana.
2. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph). G2 dan G3 pada contoh adalah graf tak-sederhana.
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf takberhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas dua jenis:
1. Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada contoh a,b,dan c adalah graf tak-berarah.
2. Graf berarah (directed graph atau digraph)
Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
Pada graf berarah notasi : d(v)
din(v) = derajat-masuk (in-degree)
= jumlah busur yang masuk ke simpul v
dout(v) = derajat-keluar (out-degree)
= jumlah busur yang keluar dari simpul v
Lemma Jabat Tangan. Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graf tersebut. Dengan kata lain, jika G = (V, E), maka :
Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10
= 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10
= 2 ´ jumlah sisi = 2 ´ 5
Tinjau graf G3: d(1) + d(2) + d(3) + d(4) + d(5) = 2 + 2 + 3 + 1 + 0 = 8
= 2 ´ jumlah sisi = 2 ´ 4
Contoh :
Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, karena jumlah derajat semua simpulnya ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, karena jumlah derajat semua simpulnya genap
(2 + 3 + 3 + 4 + 4 = 16).
Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,... , vn –1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ... , en = (vn-1, vn) adalah sisi-sisi dari graf G.
Tinjau graf G1: lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).
Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1 memiliki panjang 3.
Beberapa Graf Sederhana Khusus
a. Graf Lengkap
Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.
b. Graf Lingkaran
Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.
c. Graf Teratur
Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sbagai graf teratur derajat r.
d. Graf Bipartite
Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G(V1, V2).
Macam - Macam Graf
A. Graf Euler
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 : 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.
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 : 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.
B. Graf 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.
C. Graf Isomorfik
· Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik.
· Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.
· Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.
· Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Ini benar karena sebuah graf dapat digambarkan dalam banyak cara.
0 komentar :
Post a Comment
Silahkan Berkomentar Sesuai Dengan Topik, Jangan Menggunakan Kata-Kata Kasar, Komentar Dengan Link Aktif Tidak Akan Dipublikasikan
ttd
Admin Blog