Teori Graf dan Otomata

Published by Guebossloh.com // On 22:25:00 // 0 comments
Posted by:BACHTIAR

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
A.Sejarah Lahirnya Teori Graf
Teori graph merupakan sebuah pokok bahasan yang muncul pertama kali pada tahun 1736, yakni ketika Leonhard Euler mencoba untuk mencari solusi dari permasalahan yang sangat terkenal yaitu Jembatan Konigsberg. Di kota Konigsberg (sebelah timur Prussia, Jerman sekarang), sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.
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
Orang pertama yang memperkenalkan masalah untuk menemukan rute terpendek untuk melintasi setiap sisi graf minimal satu kali dalah Meigu Guan. Guan menganalogikan seorang pengantar surat yang ingin mengantarkan surat-suratnya melalui sebuah jaringan jalan dan kembali ke kantor pos secepat mungkin. Jack Edmonds menyebutnya dengan 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 simpul­simpul 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.
Dalam pembuatan lintasan balap atau sirkuit balap tidak sembarangan dalam membuat perlu diperhatikan arah angin dan juga kondisi wilayah. Dengan mempertimbangankan aspek-aspek tersebut maka keamanan balap akan terjaga. Untuk mempermudah mengatasi masalah itu maka dilakukan miniatur lintasan dengan kontur wilayah yang sama, kemudian untuk arah angin akandiletakkan kipas angin kecil untuk menguji coba pada lintasan.
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
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.
Teori graph merupakan sebuah pokok bahasan yang muncul pertama kali pada tahun 1736, yakni ketika Leonhard Euler mencoba untuk mencari solusi dari permasalahan yang sangat terkenal yaitu Jembatan Konigsberg.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
Semoga setelah membaca makalah ini kita semua akan lebih mengetahui tentang sejarah dari teori graf dan pemodelannya. Dan dapat mengetahui betapa pentingnya mempelajari mata kuliah tentang teori graf ini.

File Under: