BAB I
PENDAHULUAN
A. Latar Belakang
Pada bagian ini Anda akan mempelajari sejarah singkat perkembangan
teori graph serta beberapa pengertian dasar teori graph Setelah Anda
mengenal beberapa pengertian teori graph, selanjutnya akan disajikan
materi graph sebagai model matematika dan aplikasinya yang mencakup
graph sebagai model matematika, graph berarah sebagai model matematika,
jaringan kerja, silsilah keluarga, sistem komunikasi, jaringan
transportasi, desain arsitektur, dan ikatan kimia.Mengingat materi yang akan Anda pelajari ini merupakan landasan utama dalam mempelajari Teori graf, maka pemahaman yang baik tentang materi yang disajikan merupakan langkah yang tepat dalam upaya memahami materi setiap pembahasan secara keseluruhan.
Setelah mengenal sejarah tentang teori graf ini, anda diharapkan mengenal sejarah singkat munculnya teori graph.
B. Rumusam Masalah Adapun rumusan masalah dari ugas ini adalah :
- menjelaskan sejarah perkembangan teori graph
- menjelaskan Bentuk Permodelan teori graph
BAB II
PEMBAHASAN
Konigsberg, sebuah kota di bagian utara Jerman, memiliki sebuah kisah terkenal yang memberikan pengaruh besar pada kehidupan seorang bernama Euler dan sejarah perkembangan teori Graph. Sungai Pregel yang melalui Konigsberg membagi wilayah daratan pada kota tersebut menjadi empat bagian. Tujuh buah jembatan dibangun di atas sungai tersebut pada bagian yang memungkinkan untuk bepergian antar keempat wilayah tersebut. Pada abad ke-17, warga Konigsberg gemar berjalan di tepi sungai, hingga akhirnya beberapa dari mereka memikirkan apakah mungkin untuk berjalan di Konigsberg dan melalui setiap jembatan hanya sekali. Hal inilah yang kemudian disebut Teka-Teki Jembatan Konigsberg yang tidak dapat terselesaikan untuk waktu yang cukup lama dan menjadi terkenal di seluruh negeri.
Teka-teki tersebut menarik perhatian Euler, yang diyakini ketika itu berada di St. Petersburg. Ia kemudian meneliti bahwa kasus tersebut dapat direpsersentasikan dalam diagram. Setelah sekian banyak kegagalan warga Konigsberg untuk menemukan cara melalui seluruh jembatan hanya sekali, hingga akhirnya pada tahun 1736 masalah tersebut dijadikan sebuah kasus matematika dan kemustahilan, untuk menyelesaikan teka-teki tersebut terbukti. Pada tahun tersebut, seorang pakar matematika ternama, Leonard Euler, menulis sebuah artikel yang membahas tidak hanya solusi atas teka-teki Konigsberg semata, akan tetapi juga dilengkapi dengan metode umum untuk persoalan serupa lainnya .
Gambar di atas merupakan representasi graf dari jembatan Konisberg, konon kabarnya, Penduduk kota Konisberg (sekarang bernama Kalilingrad, di Uni Soviet) sering berjalan – jalan pada saat libur ke kota tersebut. kemudian muncul suatu keinginan untuk dapat menikmati daerah tersebut dengan melalui ketujuh jembatan tepat satu kali yakni bermula dari satu tempat ( A, B, C atau D) dan kembali ketempat semula. Mereka berusaha untuk memperoleh rute yang sesuai dengan keinginan tersebut dan selalu mencoba menjalaninya. setelah mencoba berkali-kali ternyata mereka tidak berhasil kemudian mereka mengirim surat kepada Euler. Namun sesuai dengan tulisannya bahwa tidak mungkin seseorang dapat melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ketempat semula. karena pada graph model jembatan Konigsberg itu tidak semua simpul berderajat genap (derajat sebuah simpul adalah jumlah sisi yang bersisian dengan simpul yang bersangkutan).
Dalam kasus jembatan Konigsberg huruf C akan muncul sebanyak tiga kali (BAC, DAC, BDC) karena terdapat lima jembatan yang menyusun jalan menuju C. Kemudian, karena tiga jembatan menyusun jalan menuju A, maka A akan muncul sebanyak dua kali (CDA, BDA). Dengan cara serupa kita dapatkan bahwa kemunculan B dan D juga dua kali. Maka dalam kombinasi delapan huruf sebagai solusi dengan kemunculan huruf ,C dan D sebanyak masing-masing dua kali, ternyata kombinasi seperti itu tidak mungkin ada, sehingga kesimpulannya adalah bahwa teka-teki Konigsberg adalah mustahil.
- B. Bentuk Permodelan Graf
- 1. Aplikasi pada Teka-Teki Tukang Pos Cina
Definisi masalah:
Seorang tukang pos berjala melalui sebuah lintasan tertutup dengan menggunakan setiap sisi jalan minimal satu kali. Rute terpendek adalah sebuah rute dengan total bobot sisi minimum. Kumpulan M yang beranggotakan sisi-sisi E(G) yang merupakan bagian dari graf G, di mana tidak ada dua sisi yang berakhir pada simpul yang sama disebut matching pada graf G. Matching yang setiap simpul di dalamnya bukan merupakan simpul akhir dari sisi manapun disebut matching sempurna.
Tujuan akhir dari Teka-Teki Tukang Pos Cina ini adalah mencari sebuah rute optimal dari sebuah graf berbobot, di mana setiap bobot sisi merepresentasikan suatu kuantitas terukur tertentu, tergantung pada masing-masing kasus (contohnya jarak, waktu, biaya, dll). Sesungguhnya jika semua simpul pada graf memiliki derajat bernilai genap, maka setiap rute Euler adalah suatu rute optimal. Akan tetapi jika tidak, maka sejumlah sisi harus ditinjau ulang. Oleh karena itu, tujuan akhir solusi teka-teki ini adalah mencari setiap sisi buntu dengan jumlah bobot minimum.
Edmonds dan Johnson dengan menggunakan algoritma polinomial waktu berhasil menyelesaikan Teka-Teki Tukang Pos Cina tersebut. Ide utama dari algoritma Edmonds dan Johnson adalah mencari sisi dengan jalur terpendek antara simpul-simpul berderajat ganjil, di mana bobot sisi dipandang sebagai jarak. Jika sisi-sisi antara dua simpul berderajat ganjil diduplikasi, maka simpulsimpul tersebut akan tetap sama.
- 2. Pemodelan graph dan otomata atau yang disebut PGO atau lebih familiar dengan Teori graf dan otomata atau TGO bertujuan untuk menyelesaikan permasalahan yang dalam konteks besar atau dengan masalah tingkat kompleks dengan membuat suatu rancangan atau simulasi model.Membuat model ditujukan untuk dapat mempermudah menyelesaikan masalah dengan biaya dan resiko yang minimal. Model yang dibuat adalah berupa matematis dengan persamaan dan fungsi ataupun secara visual.
Selain itu dalam membuat peta juga menggunakan skala, hal ini juga menggunakan pemodelan.Dalam melihat wilayah tertentu hanya dibuat simbol-simbol tertentu untuk mempermudah mengerjakan suatu masalah. Pembuatan suatu jaringan komputer juga dapat dilakukan pemodelan.Kemudian dalam membuat tiang listrik juga dapat dilakukan pemodelan.Alat deteksi wajah juga menggunakan pemodelan dengan menggunakan model pohon diagram.Rencana tata ruang dan tata wilayah juga menggunakan pemodelan juga. Penyebaran wabah penyakit juga dapat dilakukan pemodelan untuk mempermudah penanganan dan antisipasi. Penyebaran penduduk sebagaiprediksi penyebaran penduduk juga dapat dilakukan. Kemudian penyebaran kebakaran hutan juga dapat dilakukan untuk mencegah kebakaran hutan yang lebih luas, dengan cara menghitung kelembapan udara dan arah angin.
- 3. Isomer senyawa kimia karbon
Gambar Graf senyawa alkana, masing-masing metana, etana, dan propane
BAB III
PENUTUP
- A. Kesimpulan
Adapun banyak sekali bentuk-bentuk pemodelan dari garaf misalnya; teka-teki tukang pos di cina
Pemodelan graph dan otomata atau yang disebut PGO atau lebih familiar dengan Teori graf dan otomata atau TGO bertujuan untuk menyelesaikan permasalahan yang dalam konteks besar atau dengan masalah tingkat kompleks dengan membuat suatu rancangan atau simulasi model.Membuat model ditujukan untuk dapat mempermudah menyelesaikan masalah dengan biaya dan resiko yang minimal. Model yang dibuat adalah berupa matematis dengan persamaan dan fungsi ataupun secara visua
Isomer senyawa kimia karbon Arthur Cayley (1857) menggunakan graf dalam memodelkan molekul senyawa alkana CnH2n+2 untuk menghitung jumlah isomernya. Atom karbon (C) dan atom hidrogen (H) dinyatakan sebagai simpul, sedangkan ikatan antara atom C dan H dinyatakan sebagai sisi . Isomer adalah senyawa kimia yang mempunyai rumus molekul sama tetapi rumus bangun (bentuk graf) berbeda.
- B. Saran