Mengenal Teori Graf


Jembatan Königsberg
A. Latar Belakang
Matematika merupakan salah satu alat yang dapat membantu mempermudah pemecahan permasalahan kehidupan sehari-hari. Salah satu cabang Matematika yang bermanfaat membantu memecahkan permasalahan adalah Teori Graf. Teori graf merupakan salah satu bidang Matematika, yang diperkenalkan pertama kali oleh ahli Matematika asal Swiss, Leonardo Euler pada tahun 1736. Ide besarnya muncul sebagai upaya menyelesaikan masalah jembatan Königsberg. Dari permasalahan itu, akhirnya Euler mengembangkan beberapa konsep mengenai teori graf.
Sirkit Hamilton
Kemudian seiring dengan perkembangan bidang komputasi serta dalam hal ini berkembangnya perangkat lunak maupun perangkat keras komputer, teori graf banyak dijadikan model dalam memecahkan masalah yang ada dalam kehidupan kita sehari-hari. Salah satu topik menarik dalam teori graf adalah lintasan dan sirkuit Hamilton. Dalam makalah ini akan dibahas bagaimana graf dapat membantu mengatasi permasalahan transportasi dengan menggunakan aplikasi lintasan Hamilton.
Penyedia jasa pengantar dapat menggunakan metode lintasan terpendek dan persoalan pedagang keliling dalam penghematan bahan bakar dan waktu dalam pengantaran. Kedua metode akan sangat membantu dalam merencanakan lintasan yang akan diambil oleh pengantar .
Pertama kita akan mengambil metode persoalan pedagang keliling untuk mengambil beberapa macam lintasan yang dilewati untuk menyederhanakan persoalan. Hal ini agar kemungkinan lintasan yang akan didapat berkurang, sehingga memudahkan mengambil keputusan dalam pemilihan lintasan. Kedua dengan mengambil metode lintasan terpendek,kita mencoba mengurangi waktu tempuh dan bahan bakar yang digunakan. Hal ini mempertimbangkan aspek banyaknya simpul dan jumlah lintasan yang diambil. Dengan demikian kita bisa menentukan lintasan mana yang akan menghasilkan jarak tempuh terpendek.
Dalam hal ini kita akan banyak menggunakan lintasan Hamilton dalam pembahasan kedua metode yang digunakan. Hal ini karena lintasan Hamilton dianggap lebih cocok untuk mengatasi permasalahan ini. Sebab pada sirkuit Hamilton simpul harus dilalui tepat satu kali. Sesuai dengan apa yang diinginkan oleh layanan jasa pengantar. Dengan menggunakan kedua metode tersebut, kita mendapatkan lintasan yang hanya dilewati sekali dan jarak yang terpendek. Sedangkan daerah lintasan penelitian berada dalam batas jalan lingkar, dan pencarian rute perjalanan tidak memperhitungkan, lebar jalan, rambu-rambu dan lampu-lampu lalu lintas,serta kondisi jalan, dan tidak memungkinkan adanya penentuan satu arah atau dua arah, serta penutupan jalan. Jadi, metode di atas sangat berguna untuk mengurangi pengeluaran bahan bakar, jarak dan waktu tempuh di bidang transportasi khususnya untuk para jasa pengantar.
B. TEORI GRAF
Teori Graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan dalam kehidupan sehari-hari sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Banyak persoalan pada dunia nyatayang sebenarnya merupakan representasi visual dari graf. Contoh salah satu representasi visual dari graf adalah peta. Banyak hal yang dapat digali dari representasi tersebut, diantaranya adalah menentukan jalur terpendek dari satu tempat ke tempat lain, menggambarkan 2 kota yang bertetangga dengan warna yang berbeda pada peta, menentukan tata letak jalur transportasi, pengaturan jaringan komunikasi atau jaringan internet dan masih banyak lagi. Selain peta, masih banyak hal lain dalam dunia nyatayang merupakan representasi visual dari graf.

A. Definisi Graf
Secara matematis, graf didefinisikan sebagai berikut:
Graf G didefinisikan sebagai pasangan himpunan (V,E) yang dalam hal ini :
V = himpunan tidak kosong dari simpul - simpul (vertices atau node): {v1,v2,…,vn}
E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul: {e1,e2,…,en}
atau dapat ditulis singkat notasi G = (V, E)
B. Jenis-Jenis Graf
Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka secara umum graf digolongkan menjadi dua jenis:
1. Graf sederhana (simple graph) adalah graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana.
2. Graf tak-sederhana (unsimple-graph) adalah graf yang mengandung sisi ganda atau gelang dinamakan graf tak-sederhana (unsimple graph).
Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:
1. Graf berhingga (limited graph) adalah graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.
2. Graf tak-berhingga (unlimited graph) adalah graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.
Berdasarkan orientasi arah pada sisi, maka secara umum graf dibedakan atas 2 jenis:
1. Graf tak-berarah (undirected graph) adalah graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah.
2. Graf berarah (directed graph atau digraph) adalah graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.
C. Terminologi Dasar
Terdapat beberapa istilah penting yang berkaitan dengan graf. Berikut ini didefinisikan beberapa terminologi yang sering digunakan:
G1 G2 G3
Gambar 2 Graf yang digunakan untuk menjelaskan terminologi pada graf

1. Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau graf G1 : simpul 1 bertetangga dengan simpul 2 dan 3,
simpul 1 tidak bertetangga dengan simpul 4.
2. Bersisian (Incidency)
Untuk sembarang sisi e = (vj, vk) dikatakan e bersisian dengan simpul vj , atau e bersisian dengan simpul vk
Tinjau graf G1: sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,
sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,
tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

3. Simpul Terpencil (Isolated Vertex)
Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Tinjau graf G1: simpul 5 adalah simpul terpencil.
4. Graf Kosong (null graph atau empty graph)
Graf yang himpunan sisinya merupakan himpunan kosong (Nn).
Graf N5 :
5. Derajat (Degree)
Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)
Tinjau graf G1:
d(1) = d(4) = 2
d(2) = d(3) = 3
Tinjau graf G3: d(5) = 0 ? simpul terpencil
d(4) = 1 ? simpul anting-anting (pendant vertex)
Tinjau graf G2: d(1) = 3 ? bersisian dengan sisi ganda
d(2) = 4 ? bersisian dengan sisi gelang (loop)
Pada graf berarah,
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
d(v) = din(v) + dout(v)
G4 G5
Tinjau graf G4:
din(1) = 1; dout(1) = 1
din(2) = 1; dout(2) = 3
din(3) = 1; dout(3) = 1
din(4) = 2; dout(3) = 0
6. Lintasan (Path)
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-sisidari 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.
7. Siklus (Cycle) atau Sirkuit (Circuit)
Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.
Tinjau graf G1: 1, 2, 3, 1 adalah sebuah sirkuit.
Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3.
8. Terhubung (Connected)
Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1 ke v2. G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat lintasandari vi ke vj. Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).
Contoh graf tak-terhubung:
Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya). Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarahdari 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.
graf berarah terhubung lemah graf berarah terhubung kuat
9. Upagraf (Subgraph) dan Komplemen Upagraf
Misalkan G = (V, E) adalah sebuah graf. G1 = (V1, E1) adalah upagraf (subgraph) dari G jika V1 ? V dan E1 ? E.
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.
(a) Graf G1 (b) Sebuah upagraf (c) komplemen dari upagraf (b)
Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.
Graf G di bawah ini mempunyai 4 buah komponen.
Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum upagraf yang terhubung kuat.
Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:
10. Upagraf Rentang (Spanning Subgraph)
Upagraf G1 = (V1, E1) dari G = (V, E) dikatakan upagraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).
(a) graf G, (b) upagraf rentang dari G, (c) bukan upagraf rentang dari G
?
11. Cut-Set
Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.
12. Graf Berbobot (Weighted Graph)
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).
D. Beberapa Graf Khusus
1. Graf Lengkap (Complete Graph)
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.
K1 K2 K3 K4 K5 K6
2. Graf Lingkaran
Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan Cn.
3. Graf Teratur (Regular Graphs)
Graf yang setiap simpulnya mempunyai derajat yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2.

4. Graf Bipartite (Bipartite Graph)
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).

E. Lintasan Terpendek (Shortest Path)
Lintasan terperndek adalah lintasan minimum yang diperlukan untuk mencapai suatu tempat dari tempat tertentu. Lintasan minimum yang dimaksud dapat dicari dengan menggunakan graf. Graf yang digunakan adalah graf yang berbobot, yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Dalam kasus ini, bobot yang dimaksud berupa jarak dan waktu kemacetan terjadi.
Ada beberapa macam persoalan terpendek, antara lain :
a. Lintasan terpendek antara dua buah simpul tertentu.
b. Lintasan terpendek antara semua pasangan simpul.
c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
Aplikasi persoalan penentuan lintasan terpendek ini banyak sekali kita jumpai dalam kehidupan sehari-hari :
a. Menentukan rute atau jalur terbaik yang harus ditempuh dari suatu kota untuk menuju ke kota lain.
b. Menentukan jalur komunikasi dua buah terminal komputer.
c. Menentukan jalur penerbangan dunia yang paling efektif untuk dilakukan.
d. Menentukan jarak terpendek/waktu tempuh tersingkat/ongkos termurah antara dua buah kota
e. Menentukan waktu tersingkat pengiriman pesan (message) antara dua buah terminal pada jaringan komputer.
Algoritma Lintasan Terpendek
Algoritma Dijkstra ditemukan oleh Edger Wybe Dijkstra. Algoritma ini merupakan algoritma yang paling terkenal untuk mencari lintasan terpendek. Algoritma Dijkstra diterapkan pada graf berarah, tetapi selalu benar untuk graf tak-berarah.
Algoritma Dijkstra untuk mencari panjang lintasan terpendek dari vertek a ke vertek z di sebuah graf berbobot G = (V, E, W).
1. Pertama-tama misalkan S = {a} dan B = V - {a}. Untuk setiap verteks t di B tentukan, L(t) = W(a,t), (W(a,t) = ? bila (a,t) ? E).
2. Pilih verteks x di B yeng memiliki label terkecil terhadap S.
3. Jika x adalah verteks yang ingin dicapai, yaitu z, maka stop. Jika tidak, bentuk S’ = S ? {x} dan B’ = B - {x}.
Untuk setiap verteks t di B’ tentukan labelnya terhadap S’ dengan rumus
L’(t) = min [L(t), L(x) + W(x,t)]
4. Ulangi langkah 2) dan 3) dengan memakai S’ sebagai S dan B’ sebagai B.
F. Lintasan dan Sirkuit Hamilton
Dalam teori graf, siklus yang menggunakan semua titik dan kembali ke titik semula dikenal dengan siklus Hamilton (Hamilton Cycle). Sedangkan jika semua titik dilewati tepat satu kali tetapi tidak kembali ke titik semula disebut Lintasan Hamilton (Hamilton Path). Graf yang memiliki lintasan atau siklus Hamilton disebut Graf Hamilton sebagaimana disampaikan oleh Sir William Rowan Hamilton pada tahun 1856. Sedangkan graf yang hanya memiliki lintasan Hamilton disebut graf semi-Hamilton.
(a) (b) (c)
Gambar : (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
Teorema Dasar
Teorema 1
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 2
Setiap graf lengkap adalah graf Hamilton.
Teorema 3
Di dalam graf lengkap G dengan n buah simpul (n ? 3), terdapat (n - 1)!/2 buah sirkuit Hamilton.
Teorema 4
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 :
Untuk graf G = (V,E) dalam Gambar 10.1, carilah sebuah siklus Hamilton.
Penyelesaian :
Sebuah siklus Hamilton untuk graf G adalah siklus (a, b, c, d, e, f, g, a).
Masalah Perjalanan Wiraniaga
Soal perjalanan wiraniaga berkaitan dengan masalah pencarian siklus Hamilton dengan panjang minimum dalam sebuah graf berbobot G. Jika kita menganggap verteks-verteks dalam graf berbobot sebagai kota dan bobot rusuk sebagai jarak, masalah perjalanan wiraniaga adalah mencari sebuah rute terpendek sehingga wiraniaga tersebut dapat mengunjungi setiap kota satu kali, berawal dan berakhir pada kota yang sama.
Persoalan Perjalanan Pedagang (Travelling Salesperson Problem - TSP)
Diberikan sejumlah kota dan jarak antar kota. Tentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan (menentukan sirkuit Hamilton yang memiliki bobot minimum).
Aplikasi TSP:
1. Pak Pos mengambil surat di kotak pos yang tersebar pada n buah lokasi di berbagai sudut kota.
2. Lengan robot mengencangkan n buah mur pada beberapa buah peralatan mesin dalam sebuah jalur perakitan.
3. Produksi n komoditi berbeda dalam sebuah siklus.
Jumlah sirkuit Hamilton di dalam graf lengkap dengan n simpul: (n - 1)!/2.
Graf di atas memiliki (4 – 1)!/2 = 3 sirkuit Hamilton, yaitu:
I1 = (a, b, c, d, a) atau (a, d, c, b, a) ==> panjang = 10 + 12 + 8 + 15 = 45
I2 = (a, c, d, b, a) atau (a, b, d, c, a) ==> panjang = 12 + 5 + 9 + 15 = 41
I3 = (a, c, b, d, a) atau (a, d, b, c, a) ==> panjang = 10 + 5 + 9 + 8 = 32
Jadi, sirkuit Hamilton terpendek adalah I3 = (a, c, b, d, a) atau (a, d, b, c, a) dengan panjang sirkuit = 10 + 5 + 9 + 8 = 32.
Jika jumlah simpul n = 20 akan terdapat (19!)/2 sirkuit Hamilton atau sekitar 6 ? 1016 penyelesaian.
C. APLIKASI TEORI GRAF
a. Metode Pedagang Keliling
Metode ini diambil dari persoalan pedagang keliling yang harus mendatangi setiap kota tepat satu kali. Kota akan kita anggap sebagai tempat tujuan pengantaran, selanjutnya akan kita sebut sebagai simpul. Sedangkan jalan yang bisa dilewati akan kita sebut sebagai sisi. Sisi memiliki jarak tempuh yang kita sebut sebagai bobot. Persoalannya tidak lain adalah menentukan lintasan Hamilton yang memiliki bobot minimum pada graf yang kita dapatkan.
Menurut teori graf, persoalan semacam ini , jika setiap simpul memiliki sisi ke simpul lainnya maka graf ini disebut graf lengkap dengan N buah simpul, maka Sirkuit Hamilton yang kita dapatkan mempunyai rumus:
Rumus ini dihasilkan karena (n-1) untuk simpul pertama, (n-2) untuk simpul kedua, dan seterusnya untuk simpul berikutnya. Dan perlu dibagi dua karena lintasan Hamilton yang terjadi terhitung 2 kali.
A B
D C
Misal pada gambar di atas, jarak A ke B 10, jarak A ke C 12, jarak A ke D 6, Jarak B ke C 5, jarak B ke D 11, jarak C ke D 9. A adalah kantor jasa pengantar, B, C, D adalah tempat tujuan. Lintasan Hamilton ada = 3 sirkuit. Artinya kita mendapatkan 3 lintasan.
Lintasan pertama (A-B-C-D-A) atau (A-D-C-D-A)
A B
D C
Lintasan kedua (A-C-B-D-A) atau (A-D-B-C-A)
A B
D C
Lintasan ketiga (A-C-D-B-A) atau (A-B-D-C-A)
A B
D C
Dari ketiga lintasan yang ada akan menjadi referensi bagi metode selanjutnya.
b. Metode Jarak Terpendek
Pada metode ini yang akan kita gunakan adalah bobot yang ada pada graf tersebut. Kita akan menggunakan algoritma Dijkstra. Algoritma ini juga sudah terkenal diantara teori lintasan terpendek. Dengan pendekatan greedy kita dapat mendapatkan lintasan terpendek dengan membandingkan seluruh lintasan yang kita miliki. Yang perlu diketahui kita menggunakan istilah lintasan untuk mewakili sirkuit Hamilton yang didapat melalui metode sebelumnya.
Dengan melihat gambar lintasan pertama (A-B-C-D-A) atau (A-D-C-D-A)
A 10 B
6 5
D 9 C
Lintasan pertama yaitu (A-B-C-D-A) memiliki jarak tempuh sebesar 10+5+9+6=30
Lintasan kedua (A-C-B-D-A) atau (A-D-B-C-A)
A B
12 11
6 5
D C
Lintasan kedua yaitu (A-C-B-D-A) memiliki jarak tempuh sebesar 12+5+11+6=34
Lintasan ketiga (A-C-D-B-A) atau (A-B-D-C-A)
10
A B
12 11
D C
9
Lintasan ketiga yaitu (A-C-D-B-A) memiliki jarak tempuh sebesar 12+9+11+10=42
Dari ketiga lintasan pilih lintasan (A-B-C-D-A) karena memiliki jarak terpendek dari ketiga lintasasan.
B. Kasus
a. Graf Lengkap

Misalkan ada sebuah perusahaan pengantar bernama PT Antar. Perusahaan tersebut mengantar 4 buah paket ke berbagai tempat. Tempat pertama adalah sebuah rumah di kawasan Pondok Indah yang berjarak 12 dari tempat pengantaran. Tempat kedua adalah sebuah toko di jalan Menteng yang berjarak 15. Tempat ketiga adalah sebuah rumah yang berjarak 24. Tempat keempat adalah rumah yang berjarak 17. Dan setiap tempat memiliki jalan ke tempat lainnya. Jarak antara tempat satu dengan tempat lainnya direpresentasikan dengan kilometer. Dengan representasi gambar didapat graf berbobot sebagai berikut:
A
E B
D C
Anggap kantor PT. Antar sebagai A dan Tempat tujuan sebagai B, C, D, E. Jarak direpresentasikan sebagai sisi.
Dari gambar diketahui jarak dari A ke B adalah 12, dari A ke C adalah 15 dari A ke D adalah 24, dari A ke E adalah 17.
Jarak masing-masing tempat: jarak B ke C adalah 6, jarak B ke D adalah 14, jarak B ke E adalah 13, Jarak C ke D adalah 8, jarak C ke E adalah 11. Jarak D ke E adalah 9.
Dengan metode pertama kita mencari kemungkinan lintasan yang bisa diambil. Dengan rumus (n-1)!/2 = (5-1)!/2 = 12. Jadi ada 12 lintasan. Dengan menggabungkan dengan metode kedua kita bisa mencari jaraknya sekalian.
Dengan menggunakan metode yang sudah ada diatas kita akan mengambil tempat tujuan sebagai sebuah simpul. Masing masing simpul diberi tanda Alfabet. Lalu ambil yang berupa lintasannya saja. Hilangkan sisi yang tidak dilewati. Lalu hitung bobotnya.
Lintasan pertama adalah (A-B-C-D-E-A)
A
E B
D C
Lintasan ini mempunyai panjang 12 + 6 + 8 + 9 + 17 = 52
Lintasan kedua (A-B-C-E-D-A)
A
E B
D C
Lintasan ini mempunyai panjang 12 + 6 + 11 + 9 + 24 = 62
Lintasan ketiga (A-B-E-D-C-A)
A
E B
D C
Lintasan ini mempunyai panjang 12 + 13 + 9 + 8 + 15 = 57
Lintasan keempat (A-B-E-C-D-A)
A
E B
D C
Lintasan ini mempunyai panjang 12 + 13 + 11 + 8 + 24 = 58
Lintasan kelima (A-B-D-C-E-A)
A
E B
D C
Lintasan ini mempunyai panjang 12 + 14 + 8 + 11 + 17 = 62
Lintasan Keenam (A-B-D-E-C-A)
A
E B
D C
Lintasan ini mempunyai panjang 12 + 14 + 9 + 11 + 15 = 61
Lintasan ketujuh (A-C-B-D-E-A)
A
E B
D C
Lintasan ini mempunyai panjang 15+6+14+9+17=61
Lintasan kedelapan (A-C-B-E-D-A)
A
E B
D C
Lintasan ini mempunyai panjang 15 + 6 + 13 + 9 + 24 = 67
Lintasan kesembilan (A-C-D-B-E-A)
A
E B
D C
Lintasan ini mempunyai panjang 15 + 8 + 14 + 13 + 17 = 67
Lintasan kesepuluh (A-C-E-B-D-A)
A
E B
D C
Lintasan ini mempunyai panjang 15 + 11 + 13 + 14 + 24 = 77
Lintasan kesebelas (A-D-B-C-E-A)
A
E B
D C
Lintasan ini mempunyai panjang 24 + 14 + 6 + 11 + 17 = 72
Lintasan keduabelas (A-E-B-C-D-A)
A
E B
D C
Lintasan ini mempunyai panjang 24 + 8 + 6 + 13 + 17 = 68
Dengan mengambil lintasan A-B-C-D-E-A dengan panjang 52 kilometer, kita mendapatkan lintasan yang terpendek

b. Graf Tak Lengkap
Jika graf tak lengkap, maka persoalan tidak bisa diselesaikan dengan rumus (n-1)!/2. Harus dicari sirkuit Hamiltonnya dengan cara manual atau cara biasa. Setelah itu langkahnya tetap sama yaitu dengan membandingkan sirkuit Hamiltonnya. Contoh graf tak lengkap misalnya, PT. Antar harus mengirim paket ke 5 tempat dimana 2 tempat tidak bisa diakses langsung. 2 tempat tersebut hanya bisa diakses melewati 3 tempat lainnya dan antara kedua tempat tadi tidak mempunyai sisi.
Gambar graf dari graf tak lengkap di atas
B C
A D
F E
Jarak A ke B adalah 10, jarak A ke D adalah 20, jarak A ke F adalah 12, jarak B ke C adalah 7, jarak B ke E adalah 15, jarak C ke D adalah 8, jarak C ke F adalah 14, jarak D ke E adalah 9, jarak E ke F adalah 6.
Sekarang kita anggap A sebagai tempat PT. Antar, sedangkan B-F adalah tempat tujuan. Cari sirkuit Hamilton yang ada.
Sirkuit hamiltonnya:
? (A-B-C-D-E-F-A)
? (A-B-C-F-E-D-A)
? (A-B-E-F-C-D-A)
? (A-B-E-D-C-F-A)
? (A-F-E-B-C-D-A)
? (A-F-C-B-E-D-A)
Lalu setelah ada sirkuit Hamiltonnya maka dengan cara yang sama kita buat grafnya menurut sirkuit Hamilton.
Lintasan pertama (A-B-C-D-E-F-A)
B C
A D
F E
Mempunyai panjang lintasan sebesar 10 + 7 + 8 + 9 + 6 + 12 = 52
Lintasan kedua (A-B-C-F-E-D-A)
B C
A D
F E
Mempunyai panjang lintasan sebesar 10 + 7 + 14 + 6 + 9 + 20 = 66
Lintasan ketiga (A-B-E-F-C-D-A)
B C
A D
F E
Mempunyai panjang lintasan sebesar 10 + 15 + 6 + 14 + 8 + 20 = 73
Lintasan keempat (A-B-E-D-C-F-A)
B C
A D
F E
Mempunyai panjang lintasan sebesar 10 + 15 + 9 + 8 + 14 + 12 = 68
Lintasan kelima (A-F-E-B-C-D-A)
B C
A D
F E
Mempunyai panjang lintasan sebesar 12 + 6 + 15 + 7 + 8 + 20 = 68
Lintasan keenam (A-F-C-B-E-D-A)
B C
A D
F E
Mempunyai panjang lintasan sebesar 12 + 14 + 7 + 15 + 9 + 20 = 77
Dengan mengambil lintasan A-B-C-D-E-F-A dengan panjang 52 kilometer, kita mendapatkan lintasan yang terpendek.
Dengan memilih lintasan terpendek maka perusahaan jasa tersebut bisa mengurangi biaya pengeluaran untuk transportasi. Dengan begitu bisa menekan pengeluaran, dari segi bahan bakar. Akan tetapi hal ini masih di luar pertimbangan faktor-faktor yang menghambat perjalanan, seperti lebar jalan, rambu-rambu dan lampu-lampu lalu lintas, serta kondisi jalan, dan tidak memungkinkan adanya penentuan satu arah atau dua arah, serta penutupan jalan
Seperti yang kita ketahui metode pedagang keliling akan mudah dilakukan jika grafnya adalah graf lengkap. Jika tidak lengkap, maka tidak bisa menggunakan rumus (n-1)!/2 untuk menentukan jumlah lintasan. Akan tetapi mencari sirkuit Hamilton masih bisa.
Jika persoalan yang ditemui tidak terdapat sirkuit hamilton maka metode pertama tidak bisa digunakan. Jadi pencarian harus lewat manual.
Aplikasi pada jumlah simpul yang banyak (lebih dari 5) akan membuat manusia sulit dalam menghitungnya. Jadi sebaiknya serahkan penghitungan kepada program komputer.
Persoalan ini juga mengungkap permasalahan transportasi kita. Jika kita mengaplikasikan metode diatas untuk cara kita bepergian, maka kita juga bisa mendapat keuntungan dari penghematan bahan bakar.
DAFTAR PUSTAKA
Anonim, 2008. Algoritma Dijkstra. http://id.wikipedia.org/wiki/. Diakses 5 Desember 2008 pukul 19. 00
Anonim, 2008. Theorygraph http://www.en.wikipedia.org/. Diakses 5 Desember 2008 pukul 19. 00
Munir, Rinaldi. 2006. Matematika Diskrit Edisi Keempat. Bandung. Informatika
Santoso, Judhi S. (1993). Catatan Kuliah Teori Graph dan Aplikasinya. Teknik Informatika, ITB.

Diperkaya oleh Arif Cahyadi, http://arifcahyadiblog.blogspot.com/

0 komentar:

Terungkapnya Dua Misteri Matematika


Dua dari tujuh persoalan matematika milenium ini mungkin sudah terpecahkan. Rahasia Poincare Conjecture dan Hipotesis Riemann itu bakal mengubah masa depan.


Exeter - Para matematikawan dunia telah berada di ambang solusi dua dari tujuh pekerjaan rumah terbesar milenium ini dalam dunia matematika. Satu persoalan menjanjikan pemahaman tentang hubungan antara bentuk dan waktu. Sementara itu, yang lain bisa jadi berpotensi membawa ancaman bagi dunia keuangan karena mampu memecahkan rahasia-rahasia penyandian.
Dua pekerjaan rumah itu adalah tentang Poincare Conjecture - sebuah teorema yang coba menerangkan perilaku bentuk-bentuk multidimensional - dan Hipotesis Riemann, yang mencoba menerangkan pola acak dari bilangan-bilangan prima. Keduanya bersama lima permasalahan lainnya disebut-sebut sebagai "Persoalan Milenium" dan telah ada selama seabad lebih.


Empat tahun lalu, yayasan swasta nirlaba Clay Mathematics Institute di Cambridge, Massachusetts, Amerika, telah menawarkan uang senilai US$ 1 juta kepada siapa pun yang dapat memecahkan salah satu dari tujuh permasalahan matematika itu.
Ternyata, ada saja yang berhasil, setidaknya berupa klaim, yakni Grigori Perelman, ilmuwan asal Steklov Institute of Mathematics, Rusia, dan Louis de Branges dari Purdue University, Amerika Serikat. Sepertinya mereka bakal muncul sebagai kandidat pertama pemenang sayembara tersebut. Perelman mengklaim berhasil mengungkap masalah Poincare Conjecture, sedangkan de Branges untuk Hipotesis Riemann.


Namun, para matematikawan di dunia sepertinya lebih antusias menguji pembuktian yang disodorkan Perelman. Ilmuwan eksentrik Rusia itu mengemukakan dua tahun lalu dan hingga kini masih terus dibuktikan oleh rekan-rekan sejawatnya di seluruh dunia.
Keith Devlin, ilmuwan matematika dari Stanford University, Senin lalu, mengemukakan, penundaan dalam menegaskan atau menolak solusi Perelman mengindikasikan betapa kompleksnya permasalahan Poincare Conjecture. Devlin berbicara dalam Festival Ilmiah British Association di Exeter, Inggris.
"Banyak pakar berpikir bahwa bukti Grigori Perelman tntang nca Cnjecture adalah tepat, tetapi kelihatannya masih dibutuhkan beberapa bulan lagi sebelum mereka pasti apakah itu benar atau salah", kata Devlin.
Devlin sendiri yakin bahwa bukti itu akan terbukti kebenarannya. "Kalaupun tidak, ide-ide baru Perelman yang telah diperkenalkannya masih memiliki banyak percabangan lain yang penting untuk permasalahan yang sama."


Permaslahan Poincare Conjecture dimunculkan oleh Henry Poincare, ahli matematika dan fisika asal Perancis yang sangat dikenal di bidang optik, termodinamika, dan mekanika fluida. Dia juga mengerjakan teori-teori relativitas sebelum Einstein. Pada 1904, dia mengeluarkan pertanyaan yang sangat mendasar: apa bentuk dari ruang yang kita tempati ini ?
"Begitu Anda masuk ke dalam empat dimensi, Anda berbicara tentang ruang yang tidak dapat Anda visualisasikan. Cara termudah untuk memvisualisasikannya adalah dengan mempelajari apa yang terjadi dengan satu dimensi di dalam permukaan-permukaan dua dimensi", ujar Devlin, yang juga Direktur Eksekutif Pusat Studi Bahasa dan Informasi di Stanford.
Teorema yang diciptakan Poincare memang mampu terbukti dalam dunia-dunia imajinasi sehingga obyek-obyek memiliki empat, lima, atau lebih dimensi. Tetapi, tidak dengan tiga dimensi.


"Sebuah kasus yang sangat menarik karena kaitannya dengan fisika adalah sebuah kasus ketika Poincare Conjecture belum terpecahkan", Devlin menambahkan.
Sementara itu, hipotesis Riemann menerangkan pola bilangan prima yang acak. Bilangan prima itu dianalogikan sebagai atom-atom dari aritmetika, merupakan kunci dari kode penyandian (kriptografi) internet. Bilangan prima menjaga bank tetap aman dan kartu kredit terlindungi. Seluruh e-commerce bergantung kepadanya.


Menurut Profesor Marcus Du Sautoy dari University of Oxford, apa yang belum ditemukan para ahli matematika adalah semacam spektrometer bilangan prima matematis. "Ahli kimia memiliki spektrometer, sebuah mesin yang apabila Anda memasukkan sebuah molekul ke dalamnya, mesin akan menginformasikan atom-atom penyusunnya. Ahli matematika belum memiliki mesin seperti itu,. Itulah yang kami cari", Du Sautoy menjelaskan.
Hipotesis Riemann, apabila terbukti benar, memang tidak akan menghasilkan semacam spektrometer kimia. Tetapi, bukti yang diberikannya sudah seharusnya memberi pemahaman yang lebih baik tentang bagaimana bilangan prima bekerja. Berbekal pemahaman itu barulah mungkin dapat diterjemahkan menjadi sesuatu yang mungkin untuk memproduksi spectrometer bilangan prima.


Namun, berbeda dengan Perelman, pembuktian yang coba dikemukakan De Branges (2004) atas Hipotetis Riemann disambut skeptis oleh rekan-rekannya sesama ahli matematika. "Bukti yang diumumkannya kurang komprehensif. Para ahli matematika tidak yakin sayembara itu akan dimenangkannya", ungkap Du Sautoy. Tetapi, Du Sautoy cepat-cepat mengingatkan, para matematikawan juga pernah bersikap yang sama di awal-awal sumbangannya yang terdahulu atas permasalahan matematika yang lain. Tetapi, belakangan, ilmuwan kelahiran Perancis itu terbukti benar.


Tujuh Problem Matematika



Pada 8 Agustus 1900, di depan peserta Kongres Matematika Internasional ke-2 di Paris, Perancis, ahli matematika David Hilbert menggelar kuliah umum yang sangat terkenal. Kuliahnya tentang problem-problem matematika terbuka. Seabad kemudian, terilhami dari kuliah itu, yayasan nirlaba The Clay Mathematics Institute (CMI) yang bermarkas di Cambridge, Massachusetts, Amerika, mencetuskan Sayembara Problem Milenium. Problem-problem matematika yang tak terpecahkan dipilih oleh sebuah Dewan Pertimbangan Ilmiah CMI. Ada tujuh problem matematika pada milenium ini yang menjadi tantangan bagi semua ahli matematika di dunia untuk membuat formulasinya. Barang siapa yang dapat mengungkap rahasia itu, tersedia hadiah US$ 1 juta. Ketujuh problem matematika itu:


  1. Dugaan Birch dan Swinnerton-Dyer: Geometri Euclid untuk abad ke-21, melibatkan apa yang disebut titik Abelian dan fungsi zeta serta jawaban-jawaban terbatas dan tidak terbatas untuk persamaan-persamaan aljabar.
  2. Poincare Conjecture: Permukaan sebuah apel saling tersambung secara sederhana. Tetapi, permukaan sebuah donat tidak. Bagaimana anda memulai dari ide konektivitas sederhana , lalu mengkarakterisasikan ruang dalam tiga dimensi ?
  3. Persamaan Navier-Stokes: Jawaban bagi turbulensi gelombang dan angin terletak di suatu tempat dalam pemecahan persamaan ini.
  4. P versus NP: Beberapa persoalan terlalu besar: Anda dapat dengan cepat membuktikan kebenaran sebuah jawaban yang memang benar, tetapi mungkin akan butuh seumur jagat raya apabila harus memecahkannya dari awal. Dapatkah Anda membuktikan pertanyaan mana yang paling berat dan mana yang tidak ? Hipotesis Riemann: Melibatkan fungsi-fungsi zeta, dan sebuah penekanan bahwa seluruh solusi "menarik" dari sebuah persamaan terdapat pada sebuah (persamaan) garis lurus.
  5. Dugaan Hodge: Di tepian batas antara aljabar dan geometri, melibatkan persoalan teknis dari bentuk-bentuk bangunan dengan merekatkan blok-blok geometric secara bersamaan.
  6. Yang-Mills dan Selisih Massa: Sebuah persoalan yang melibatkan mekanika kuantum dan partikel-partikel dasar. Para ahli fisika menyadari, komputer dapat mensimulasikannya, tetapi belum seorang pun yang telah menemukan teori untuk menerangkannya.
Sumber : Koran Tempo (8 September 2004)

0 komentar:

Mengenal Aljabar

Penemu Aljabar adalah Abu Abdullah Muhammad Ibn Musa al-KhwarizmiAljabar berasal dari Bahasa Arab "al-jabr" yang berarti"pertemuan""hubungan" atau "penyelesaian" adalah cabang matematika yang dapat dicirikan sebagai generalisasi dari bidangaritmatika. Aljabar juga merupakan nama sebuah struktur aljabar abstrak, yaitu aljabar dalam sebuah bidang.

Buku karangan Al-Khwārizmī yang memuat perhitungan aljabar

[sunting]
Aljabar dapat dipilah menjadi kategori berikut:

Jenis-jenis Aljabar

  • Aljabar universal, yang mempelajari sifat-sifat yang dimiliki semua struktur aljabar.
  • Aljabar komputer, yang mengumpulkan manipulasi simbolis benda-benda matematis.

[sunting]Pengertian bentuk aljabar

Bentuk-Bentuk seperti 2a , -5b, x3, 3p + 2q disebut bentuk aljabar.Pada bentuk aljabar 2a, 2 disebut koefisien, sedangkan a disebutvariabel( peubah ).

[sunting]Bentuk-bentuk aljabar

[sunting]Persamaan dan pertidaksamaan linear

  • Persamaan Linear Satu Variabel
Persamaan Linear Satu Variabel berarti persamaan pangkat satu. Pada persamaan linear ini berlaku hukum :
  1. Ruas kiri dan ruas kanan dapat ditambahkan atau dikurangi bilangan yang sama
  2. Ruas kiri dan ruas kanan dapat dikalikan atau dibagi dengan bilangan yang sama.
Contoh :
r:10
1. r + 3 = 10.
r + 3 - 3 = 10 - 3 (sama sama dikurangi dengan bilangan yang sama yaitu 3)
  r = 7
2. 3p = 12
3p / 3 = 12/3 (sama-sama dibagi dengan bilangan yang sama yaitu 3)
  p = 4
  • Pertidaksamaan Linear satu variabel
Pertidaksamaan linear satu variabel berarti kalimat terbuka yang memiliki tanda <,>, Pada persamaan linear berlaku hukum:
  1. Ruas Kiri dan kanan dapat ditambah, dikurangi, dikali, atau dibagi bilangan yang sama
  2. jika variabel bertanda minus, harus diganti menjadi positif dengan mengali bilangan negatif dan membalikan tanda
contoh : 1. 5v - 7 > 23
5v - 7 + 7 > 23 + 7
  5v / 5 > 30 / 5
  v > 6
2. -2a < 10
-2a / -2 > 10 / -2
  a > -5\
3. -2a < 10
-2a / -2 > 10 / -2
  a > -5\
Sumber Wikipedia, http://id.wikipedia.org/wiki/Aljabar

0 komentar:

Mengenal Matematika

Matematika (dari bahasa Yunani: μαθηματικά – mathēmatiká) adalah studi besaran, struktur, ruang, dan perubahan. Para matematikawan mencari berbagai pola,[2][3] merumuskan konjektur baru, dan membangun kebenaran melalui metode deduksi yang kaku dari aksioma-aksioma dan definisi-definisi yang bersesuaian.[4]

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”.[5] 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.”[6]

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.[7]

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. Para matematikawan juga bergulat di dalam matematika murni, atau matematika untuk perkembangan matematika itu sendiri, tanpa adanya penerapan di dalam pikiran, meskipun penerapan praktis yang menjadi latar munculnya matematika murni ternyata seringkali ditemukan terkemudian.[8]
Kata “matematika” berasal dari bahasa Yunani Kuno μάθημα (máthēma), yang berarti pengkajian, pembelajaran, ilmu, yang ruang lingkupnya menyempit, dan arti teknisnya menjadi “pengkajian matematika”, bahkan demikian juga pada zaman kuno. Kata sifatnya adalah μαθηματικός (mathēmatikós), berkaitan dengan pengkajian, atau tekun belajar, yang lebih jauhnya berarti matematis. Secara khusus, μαθηματικὴ τέχνη (mathēmatikḗ tékhnē), di dalam bahasa Latin ars mathematica, berarti seni matematika.

Bentuk jamak sering dipakai di dalam bahasa Inggris, seperti juga di dalam bahasa Perancis les mathématiques (dan jarang digunakan sebagai turunan bentuk tunggal la mathématique), merujuk pada bentuk jamak bahasa Latin yang cenderung netral mathematica (Cicero), berdasarkan bentuk jamak bahasa Yunani τα μαθηματικά (ta mathēmatiká), yang dipakai Aristotle, yang terjemahan kasarnya berarti “segala hal yang matematis”.[9] Tetapi, di dalam bahasa Inggris, kata benda mathematics mengambil bentuk tunggal bila dipakai sebagai kata kerja. Di dalam ragam percakapan, matematika kerap kali disingkat sebagai math di Amerika Utara dan maths di tempat lain.


Sejarah Matematika


Evolusi matematika dapat dipandang sebagai sederetan abstraksi yang selalu bertambah banyak, atau perkataan lainnya perluasan pokok masalah. Abstraksi mula-mula, yang juga berlaku pada banyak binatang[10], adalah tentang bilangan: pernyataan bahwa dua apel dan dua jeruk (sebagai contoh) memiliki jumlah yang sama.
Selain mengetahui cara mencacah objek-objek fisika, manusia prasejarah juga mengenali cara mencacah besaran abstrak, seperti waktu — hari, musim, tahun. Aritmetika dasar (penjumlahan, pengurangan, perkalian, dan pembagian) mengikuti secara alami.
Langkah selanjutnya memerlukan penulisan atau sistem lain untuk mencatatkan bilangan, semisal tali atau dawai bersimpul yang disebut quipu dipakai oleh bangsa Inca untuk menyimpan data numerik. Sistem bilangan ada banyak dan bermacam-macam, bilangan tertulis yang pertama diketahui ada di dalam naskah warisan Mesir Kuno di Kerajaan Tengah Mesir, Lembaran Matematika Rhind.
Sistem bilangan Maya

Penggunaan terkuno matematika adalah di dalam perdagangan, pengukuran tanah, pelukisan, dan pola-pola penenunan dan pencatatan waktu dan tidak pernah berkembang luas hingga tahun 3000 SM ke muka ketika orang Babilonia dan Mesir Kuno mulai menggunakan aritmetika, aljabar, dan geometri untuk penghitungan pajak dan urusan keuangan lainnya, bangunan dan konstruksi, dan astronomi.[11] Pengkajian matematika yang sistematis di dalam kebenarannya sendiri dimulai pada zaman Yunani Kuno antara tahun 600 dan 300 SM.

Matematika sejak saat itu segera berkembang luas, dan terdapat interaksi bermanfaat antara matematika dan sains, menguntungkan kedua belah pihak. Penemuan-penemuan matematika dibuat sepanjang sejarah dan berlanjut hingga kini. Menurut Mikhail B. Sevryuk, pada Januari 2006 terbitan Bulletin of the American Mathematical Society, “Banyaknya makalah dan buku yang dilibatkan di dalam basis data Mathematical Reviews sejak 1940 (tahun pertama beroperasinya MR) kini melebihi 1,9 juta, dan melebihi 75 ribu artikel ditambahkan ke dalam basis data itu tiap tahun. Sebagian besar karya di samudera ini berisi teorema matematika baru beserta bukti-buktinya.”[12]


Ilham, matematika murni dan terapan, dan estetika


Sir Isaac Newton (1643-1727), seorang penemu kalkulus infinitesimal.
!Artikel utama untuk bagian ini adalah: Keindahan matematika
Matematika muncul pada saat dihadapinya masalah-masalah yang rumit yang melibatkan kuantitas, struktur, ruang, atau perubahan. Mulanya masalah-masalah itu dijumpai di dalam perdagangan, pengukuran tanah, dan kemudian astronomi; kini, semua ilmu pengetahuan menganjurkan masalah-masalah yang dikaji oleh para matematikawan, dan banyak masalah yang muncul di dalam matematika itu sendiri. Misalnya, seorang fisikawan Richard Feynman menemukan rumus integral lintasan mekanika kuantum menggunakan paduan nalar matematika dan wawasan fisika, dan teori dawai masa kini, teori ilmiah yang masih berkembang yang berupaya membersatukan empat gaya dasar alami, terus saja mengilhami matematika baru.[13] Beberapa matematika hanya bersesuaian di dalam wilayah yang mengilhaminya, dan diterapkan untuk memecahkan masalah lanjutan di wilayah itu. Tetapi seringkali matematika diilhami oleh bukti-bukti di satu wilayah ternyata bermanfaat juga di banyak wilayah lainnya, dan menggabungkan persediaan umum konsep-konsep matematika. Fakta yang menakjubkan bahwa matematika “paling murni” sering beralih menjadi memiliki terapan praktis adalah apa yang Eugene Wigner memanggilnya sebagai “Ketidakefektifan Matematika tak ternalar di dalam Ilmu Pengetahuan Alam”.[14]

Seperti di sebagian besar wilayah pengkajian, ledakan pengetahuan di zaman ilmiah telah mengarah pada pengkhususan di dalam matematika. Satu perbedaan utama adalah di antara matematika murni dan matematika terapan: sebagian besar matematikawan memusatkan penelitian mereka hanya pada satu wilayah ini, dan kadang-kadang pilihan ini dibuat sedini perkuliahan program sarjana mereka. Beberapa wilayah matematika terapan telah digabungkan dengan tradisi-tradisi yang bersesuaian di luar matematika dan menjadi disiplin yang memiliki hak tersendiri, termasuk statistika, riset operasi, dan ilmu komputer.

Mereka yang berminat kepada matematika seringkali menjumpai suatu aspek estetika tertentu di banyak matematika. Banyak matematikawan berbicara tentang keanggunan matematika, estetika yang tersirat, dan keindahan dari dalamnya. Kesederhanaan dan keumumannya dihargai. Terdapat keindahan di dalam kesederhanaan dan keanggunan bukti yang diberikan, semisal bukti Euclid yakni bahwa terdapat tak-terhingga banyaknya bilangan prima, dan di dalam metode numerik yang anggun bahwa perhitungan laju, yakni transformasi Fourier cepat. G. H. Hardy di dalam A Mathematician’s Apology mengungkapkan keyakinan bahwa penganggapan estetika ini, di dalamnya sendiri, cukup untuk mendukung pengkajian matematika murni.[15] Para matematikawan sering bekerja keras menemukan bukti teorema yang anggun secara khusus, pencarian Paul Erdős sering berkutat pada sejenis pencarian akar dari “Alkitab” di mana Tuhan telah menuliskan bukti-bukti kesukaannya.[16][17] Kepopularan matematika rekreasi adalah isyarat lain bahwa kegembiraan banyak dijumpai ketika seseorang mampu memecahkan soal-soal matematika.

Notasi, bahasa, dan kekakuan


Leonhard Euler. Mungkin seorang matematikawan yang terbanyak menghasilkan temuan sepanjang masa
!Artikel utama untuk bagian ini adalah: Notasi matematika
Sebagian besar notasi matematika yang digunakan saat ini tidaklah ditemukan hingga abad ke-16.[18] Pada abad ke-18, Euler bertanggung jawab atas banyak notasi yang digunakan saat ini. Notasi modern membuat matematika lebih mudah bagi para profesional, tetapi para pemula sering menemukannya sebagai sesuatu yang mengerikan. Terjadi pemadatan yang amat sangat: sedikit lambang berisi informasi yang kaya. Seperti notasi musik, notasi matematika modern memiliki tata kalimat yang kaku dan menyandikan informasi yang barangkali sukar bila dituliskan menurut cara lain.
Bahasa matematika dapat juga terkesan sukar bagi para pemula. Kata-kata seperti atau dan hanya memiliki arti yang lebih presisi daripada di dalam percakapan sehari-hari. Selain itu, kata-kata semisal terbuka dan lapangan memberikan arti khusus matematika. Jargon matematika termasuk istilah-istilah teknis semisal homomorfisme dan terintegralkan. Tetapi ada alasan untuk notasi khusus dan jargon teknis ini: matematika memerlukan presisi yang lebih dari sekadar percakapan sehari-hari. Para matematikawan menyebut presisi bahasa dan logika ini sebagai “kaku” (rigor).

Lambang ketakhinggaan ∞ di dalam beberapa gaya sajian.


Kaku secara mendasar adalah tentang bukti matematika. Para matematikawan ingin teorema mereka mengikuti aksioma-aksioma dengan maksud penalaran yang sistematik. Ini untuk mencegah “teorema” yang salah ambil, didasarkan pada praduga kegagalan, di mana banyak contoh pernah muncul di dalam sejarah subjek ini.[19] Tingkat kekakuan diharapkan di dalam matematika selalu berubah-ubah sepanjang waktu: bangsa Yunani menginginkan dalil yang terperinci, namun pada saat itu metode yang digunakan Isaac Newton kuranglah kaku. Masalah yang melekat pada definisi-definisi yang digunakan Newton akan mengarah kepada munculnya analisis saksama dan bukti formal pada abad ke-19. Kini, para matematikawan masih terus beradu argumentasi tentang bukti berbantuan-komputer. Karena perhitungan besar sangatlah sukar diperiksa, bukti-bukti itu mungkin saja tidak cukup kaku.[20]

Aksioma menurut pemikiran tradisional adalah “kebenaran yang menjadi bukti dengan sendirinya”, tetapi konsep ini memicu persoalan. Pada tingkatan formal, sebuah aksioma hanyalah seutas dawai lambang, yang hanya memiliki makna tersirat di dalam konteks semua rumus yang terturunkan dari suatu sistem aksioma. Inilah tujuan program Hilbert untuk meletakkan semua matematika pada sebuah basis aksioma yang kokoh, tetapi menurut Teorema ketaklengkapan Gödel tiap-tiap sistem aksioma (yang cukup kuat) memiliki rumus-rumus yang tidak dapat ditentukan; dan oleh karena itulah suatu aksiomatisasi terakhir di dalam matematika adalah mustahil. Meski demikian, matematika sering dibayangkan (di dalam konteks formal) tidak lain kecuali teori himpunan di beberapa aksiomatisasi, dengan pengertian bahwa tiap-tiap pernyataan atau bukti matematika dapat dikemas ke dalam rumus-rumus teori himpunan.[21]

Matematika sebagai ilmu pengetahuan

Carl Friedrich Gauss, menganggap dirinya sebagai “pangerannya para matematikawan”, dan mengatakan matematika sebagai “Ratunya Ilmu Pengetahuan”.

Carl Friedrich Gauss mengatakan matematika sebagai “Ratunya Ilmu Pengetahuan”.[22] Di dalam bahasa aslinya, Latin Regina Scientiarum, juga di dalam bahasa Jerman Königin der Wissenschaften, kata yang bersesuaian dengan ilmu pengetahuan berarti (lapangan) pengetahuan. Jelas, inipun arti asli di dalam bahasa Inggris, dan tiada keraguan bahwa matematika di dalam konteks ini adalah sebuah ilmu pengetahuan. Pengkhususan yang mempersempit makna menjadi ilmu pengetahuan alam adalah di masa terkemudian. Bila seseorang memandang ilmu pengetahuan hanya terbatas pada dunia fisika, maka matematika, atau sekurang-kurangnya matematika murni, bukanlah ilmu pengetahuan. Albert Einstein menyatakan bahwa “sejauh hukum-hukum matematika merujuk kepada kenyataan, maka mereka tidaklah pasti; dan sejauh mereka pasti, mereka tidak merujuk kepada kenyataan.”[6]

Banyak filsuf yakin bahwa matematika tidaklah terpalsukan berdasarkan percobaan, dan dengan demikian bukanlah ilmu pengetahuan per definisi Karl Popper.[23] Tetapi, di dalam karya penting tahun 1930-an tentang logika matematika menunjukkan bahwa matematika tidak bisa direduksi menjadi logika, dan Karl Popper menyimpulkan bahwa “sebagian besar teori matematika, seperti halnya fisika dan biologi, adalah hipotetis-deduktif: oleh karena itu matematika menjadi lebih dekat ke ilmu pengetahuan alam yang hipotesis-hipotesisnya adalah konjektur (dugaan), lebih daripada sebagai hal yang baru.”[24] Para bijak bestari lainnya, sebut saja Imre Lakatos, telah menerapkan satu versi pemalsuan kepada matematika itu sendiri.

Sebuah tinjauan alternatif adalah bahwa lapangan-lapangan ilmiah tertentu (misalnya fisika teoretis) adalah matematika dengan aksioma-aksioma yang ditujukan sedemikian sehingga bersesuaian dengan kenyataan. Faktanya, seorang fisikawan teoretis, J. M. Ziman, mengajukan pendapat bahwa ilmu pengetahuan adalah pengetahuan umum dan dengan demikian matematika termasuk di dalamnya.[25] Di beberapa kasus, matematika banyak saling berbagi dengan ilmu pengetahuan fisika, sebut saja penggalian dampak-dampak logis dari beberapa anggapan. Intuisi dan percobaan juga berperan penting di dalam perumusan konjektur-konjektur, baik itu di matematika, maupun di ilmu-ilmu pengetahuan (lainnya). Matematika percobaan terus bertumbuh kembang, mengingat kepentingannya di dalam matematika, kemudian komputasi dan simulasi memainkan peran yang semakin menguat, baik itu di ilmu pengetahuan, maupun di matematika, melemahkan objeksi yang mana matematika tidak menggunakan metode ilmiah. Di dalam bukunya yang diterbitkan pada 2002 A New Kind of Science, Stephen Wolfram berdalil bahwa matematika komputasi pantas untuk digali secara empirik sebagai lapangan ilmiah di dalam haknya/kebenarannya sendiri.

Pendapat-pendapat para matematikawan terhadap hal ini adalah beraneka macam. Banyak matematikawan merasa bahwa untuk menyebut wilayah mereka sebagai ilmu pengetahuan sama saja dengan menurunkan kadar kepentingan sisi estetikanya, dan sejarahnya di dalam tujuh seni liberal tradisional; yang lainnya merasa bahwa pengabaian pranala ini terhadap ilmu pengetahuan sama saja dengan memutar-mutar mata yang buta terhadap fakta bahwa antarmuka antara matematika dan penerapannya di dalam ilmu pengetahuan dan rekayasa telah mengemudikan banyak pengembangan di dalam matematika. Satu jalan yang dimainkan oleh perbedaan sudut pandang ini adalah di dalam perbincangan filsafat apakah matematika diciptakan (seperti di dalam seni) atau ditemukan (seperti di dalam ilmu pengetahuan). Adalah wajar bagi universitas bila dibagi ke dalam bagian-bagian yang menyertakan departemen Ilmu Pengetahuan dan Matematika, ini menunjukkan bahwa lapangan-lapangan itu dipandang bersekutu tetapi mereka tidak seperti dua sisi keping uang logam. Pada tataran praktisnya, para matematikawan biasanya dikelompokkan bersama-sama para ilmuwan pada tingkatan kasar, tetapi dipisahkan pada tingkatan akhir. Ini adalah salah satu dari banyak perkara yang diperhatikan di dalam filsafat matematika.
Penghargaan matematika umumnya dipelihara supaya tetap terpisah dari kesetaraannya dengan ilmu pengetahuan. Penghargaan yang adiluhung di dalam matematika adalah Fields Medal (medali lapangan),dimulakan pada 1936 dan kini diselenggarakan tiap empat tahunan. Penghargaan ini sering dianggap setara dengan Hadiah Nobel ilmu pengetahuan. Wolf Prize in Mathematics, dilembagakan pada 1978, mengakui masa prestasi, dan penghargaan internasional utama lainnya, Hadiah Abel, diperkenalkan pada 2003. Ini dianugerahkan bagi ruas khusus karya, dapat berupa pembaharuan, atau penyelesaian masalah yang terkemuka di dalam lapangan yang mapan. Sebuah daftar terkenal berisikan 23 masalah terbuka, yang disebut “masalah Hilbert”, dihimpun pada 1900 oleh matematikawan Jerman David Hilbert. Daftar ini meraih persulangan yang besar di antara para matematikawan, dan paling sedikit sembilan dari masalah-masalah itu kini terpecahkan. Sebuah daftar baru berisi tujuh masalah penting, berjudul “Masalah Hadiah Milenium”, diterbitkan pada 2000. Pemecahan tiap-tiap masalah ini berhadiah US$ 1 juta, dan hanya satu (hipotesis Riemann) yang mengalami penggandaan di dalam masalah-masalah Hilbert.

Bidang-bidang matematika


Sebuah sempoa, alat hitung sederhana yang dipakai sejak zaman kuno.
Disiplin-disiplin utama di dalam matematika pertama muncul karena kebutuhan akan perhitungan di dalam perdagangan, untuk memahami hubungan antarbilangan, untuk mengukur tanah, dan untuk meramal peristiwa astronomi. Empat kebutuhan ini secara kasar dapat dikaitkan dengan pembagian-pembagian kasar matematika ke dalam pengkajian besaran, struktur, ruang, dan perubahan (yakni aritmetika, aljabar, geometri, dan analisis). Selain pokok bahasan itu, juga terdapat pembagian-pembagian yang dipersembahkan untuk pranala-pranala penggalian dari jantung matematika ke lapangan-lapangan lain: ke logika, ke teori himpunan (dasar), ke matematika empirik dari aneka macam ilmu pengetahuan (matematika terapan), dan yang lebih baru adalah ke pengkajian kaku akan ketakpastian.


Besaran


Pengkajian besaran dimulakan dengan bilangan, pertama bilangan asli dan bilangan bulat (“semua bilangan”) dan operasi aritmetika di ruang bilangan itu, yang dipersifatkan di dalam aritmetika. Sifat-sifat yang lebih dalam dari bilangan bulat dikaji di dalam teori bilangan, dari mana datangnya hasil-hasil popular seperti Teorema Terakhir Fermat. Teori bilangan juga memegang dua masalah tak terpecahkan: konjektur prima kembar dan konjektur Goldbach.
Karena sistem bilangan dikembangkan lebih jauh, bilangan bulat diakui sebagai himpunan bagian dari bilangan rasional (“pecahan”). Sementara bilangan pecahan berada di dalam bilangan real, yang dipakai untuk menyajikan besaran-besaran kontinu. Bilangan real diperumum menjadi bilangan kompleks. Inilah langkah pertama dari jenjang bilangan yang beranjak menyertakan kuarternion dan oktonion. Perhatian terhadap bilangan asli juga mengarah pada bilangan transfinit, yang memformalkan konsep pencacahan ketakhinggaan. Wilayah lain pengkajian ini adalah ukuran, yang mengarah pada bilangan kardinal dan kemudian pada konsepsi ketakhinggaan lainnya: bilangan aleph, yang memungkinkan perbandingan bermakna tentang ukuran himpunan-himpunan besar ketakhinggaan.

Ruang


Pengkajian ruang bermula dengan geometri – khususnya, geometri euclid. Trigonometri memadukan ruang dan bilangan, dan mencakupi Teorema pitagoras yang terkenal. Pengkajian modern tentang ruang memperumum gagasan-gagasan ini untuk menyertakan geometri berdimensi lebih tinggi, geometri tak-euclid (yang berperan penting di dalam relativitas umum) dan topologi. Besaran dan ruang berperan penting di dalam geometri analitik, geometri diferensial, dan geometri aljabar. Di dalam geometri diferensial terdapat konsep-konsep buntelan serat dan kalkulus lipatan. Di dalam geometri aljabar terdapat penjelasan objek-objek geometri sebagai himpunan penyelesaian persamaan polinom, memadukan konsep-konsep besaran dan ruang, dan juga pengkajian grup topologi, yang memadukan struktur dan ruang. Grup lie biasa dipakai untuk mengkaji ruang, struktur, dan perubahan. Topologi di dalam banyak percabangannya mungkin menjadi wilayah pertumbuhan terbesar di dalam matematika abad ke-20, dan menyertakan konjektur poincaré yang telah lama ada dan teorema empat warna, yang hanya “berhasil” dibuktikan dengan komputer, dan belum pernah dibuktikan oleh manusia secara manual.



Geometri Trigonometri Geometri diferensial Topologi Geometri fraktal
Perubahan


Memahami dan menjelaskan perubahan adalah tema biasa di dalam ilmu pengetahuan alam, dan kalkulus telah berkembang sebagai alat yang penuh-daya untuk menyeledikinya. Fungsi-fungsi muncul di sini, sebagai konsep penting untuk menjelaskan besaran yang berubah. Pengkajian kaku tentang bilangan real dan fungsi-fungsi berpeubah real dikenal sebagai analisis real, dengan analisis kompleks lapangan yang setara untuk bilangan kompleks. Hipotesis Riemann, salah satu masalah terbuka yang paling mendasar di dalam matematika, dilukiskan dari analisis kompleks. Analisis fungsional memusatkan perhatian pada ruang fungsi (biasanya berdimensi tak-hingga). Satu dari banyak terapan analisis fungsional adalah mekanika kuantum. Banyak masalah secara alami mengarah pada hubungan antara besaran dan laju perubahannya, dan ini dikaji sebagai persamaan diferensial. Banyak gejala di alam dapat dijelaskan menggunakan sistem dinamika; teori kekacauan mempertepat jalan-jalan di mana banyak sistem ini memamerkan perilaku deterministik yang masih saja belum terdugakan.

Struktur


Banyak objek matematika, semisal himpunan bilangan dan fungsi, memamerkan struktur bagian dalam. Sifat-sifat struktural objek-objek ini diselidiki di dalam pengkajian grup, gelanggang, lapangan dan sistem abstrak lainnya, yang mereka sendiri adalah objek juga. Ini adalah lapangan aljabar abstrak. Sebuah konsep penting di sini yakni vektor, diperumum menjadi ruang vektor, dan dikaji di dalam aljabar linear. Pengkajian vektor memadukan tiga wilayah dasar matematika: besaran, struktur, dan ruang. Kalkulus vektor memperluas lapangan itu ke dalam wilayah dasar keempat, yakni perubahan. Kalkulus tensor mengkaji kesetangkupan dan perilaku vektor yang dirotasi. Sejumlah masalah kuno tentang Kompas dan konstruksi garis lurus akhirnya terpecahkan oleh Teori galois.

Teori bilangan Aljabar abstrak Teori grup Teori orde

Dasar dan filsafat


Untuk memeriksa dasar-dasar matematika, lapangan logika matematika dan teori himpunan dikembangkan, juga teori kategori yang masih dikembangkan. Kata majemuk “krisis dasar” mejelaskan pencarian dasar kaku untuk matematika yang mengambil tempat pada dasawarsa 1900-an sampai 1930-an.[28] Beberapa ketaksetujuan tentang dasar-dasar matematika berlanjut hingga kini. Krisis dasar dipicu oleh sejumlah silang sengketa pada masa itu, termasuk kontroversi teori himpunan Cantor dan kontroversi Brouwer-Hilbert.
Logika matematika diperhatikan dengan meletakkan matematika pada sebuah kerangka kerja aksiomatis yang kaku, dan mengkaji hasil-hasil kerangka kerja itu. Logika matematika adalah rumah bagi Teori ketaklengkapan kedua Gödel, mungkin hasil yang paling dirayakan di dunia logika, yang (secara informal) berakibat bahwa suatu sistem formal yang berisi aritmetika dasar, jika suara (maksudnya semua teorema yang dapat dibuktikan adalah benar), maka tak-lengkap (maksudnya terdapat teorema sejati yang tidak dapat dibuktikan di dalam sistem itu). Gödel menunjukkan cara mengonstruksi, sembarang kumpulan aksioma bilangan teoretis yang diberikan, sebuah pernyataan formal di dalam logika yaitu sebuah bilangan sejati-suatu fakta teoretik, tetapi tidak mengikuti aksioma-aksioma itu. Oleh karena itu, tiada sistem formal yang merupakan aksiomatisasi sejati teori bilangan sepenuhnya. Logika modern dibagi ke dalam teori rekursi, teori model, dan teori pembuktian, dan terpaut dekat dengan ilmu komputer teoretis.


Logika matematika Teori himpunan Teori kategori


Matematika diskret


Matematika diskret adalah nama lazim untuk lapangan matematika yang paling berguna di dalam ilmu komputer teoretis. Ini menyertakan teori komputabilitas, teori kompleksitas komputasional, dan teori informasi. Teori komputabilitas memeriksa batasan-batasan berbagai model teoretis komputer, termasuk model yang dikenal paling berdaya – Mesin turing. Teori kompleksitas adalah pengkajian traktabilitas oleh komputer; beberapa masalah, meski secara teoretis terselesaikan oleh komputer, tetapi cukup mahal menurut konteks waktu dan ruang, tidak dapat dikerjakan secara praktis, bahkan dengan cepatnya kemajuan perangkat keras komputer. Pamungkas, teori informasi memusatkan perhatian pada banyaknya data yang dapat disimpan pada media yang diberikan, dan oleh karenanya berkenaan dengan konsep-konsep semisal pemadatan dan entropi.

Kombinatorika Teori komputasi Kriptografi Teori graf


Matematika terapan


Matematika terapan berkenaan dengan penggunaan alat matematika abstrak guna memecahkan masalah-masalah konkret di dalam ilmu pengetahuan, bisnis, dan wilayah lainnya. Sebuah lapangan penting di dalam matematika terapan adalah statistika, yang menggunakan teori peluang sebagai alat dan membolehkan penjelasan, analisis, dan peramalan gejala di mana peluang berperan penting. Sebagian besar percobaan, survey, dan pengkajian pengamatan memerlukan statistika. (Tetapi banyak statistikawan, tidak menganggap mereka sendiri sebagai matematikawan, melainkan sebagai kelompok sekutu.) Analisis numerik menyelidiki metode komputasional untuk memecahkan masalah-masalah matematika secara efisien yang biasanya terlalu lebar bagi kapasitas numerik manusia; analisis numerik melibatkan pengkajian galat pemotongan atau sumber-sumber galat lain di dalam komputasi.

Sumber: Wikipedia, Ensiklopedia Bebas.
              http://id.wikipedia.org/wiki/Matematika


0 komentar: