TEORI GRAPH

TUGAS TERSTRUKTUR

TEORI GRAPH

“Sejarah Lahirnya Teori Graph dan Pemodelan Dalam Graph”

Dosen Pengampuh:
Rini Warti, S.Si, M.Si

Dibuat Oleh:
kelompok 9

1.      Puryanti                    : TM100662

2.      Rahmat Firdaus        : TM100664

3.      Rita Agustiana Sari  : TM100670

4.      Ulfa Husna               : TM100687

Jurusan

Tadris Matematika

IAIN STS JAMBI

2013

BAB 1
PENDAHULUAN

A.    SEJARAH LAHIRNYA TEORI GRAPH

Teori graph lahir pada Tahun 1736 melalui tulisan Leonhard Euler yang berisi tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa. Permasalahannya adalah " Apakah bisa seseorang  melalui  sekali setiap jembatan yang menghubungkan kota-kota tersebut, dan kembali lagi ke kota dari mana ia berjalan".

Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnya-genap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh, simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakukan perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.

Kurang lebih seratus tahun setelah lahirnya tulisan Euler tersebut tidak ada perkembangan yang berarti berkenaan dengan teori graph.  Tahun 1847, G.R. Kirchoff (1824 – 1887) berhasil mengembangkan teori pohon (Theory of trees) yang digunakan dalam persoalan jaringan listrik. Sepuluh tahun kemudian, A. Coyley (1821 – 1895) juga menggunakan konsep pohon untuk menjelaskan permasalahan kimia yaitu hidrokarbon. Pada masa Kirchoff dan Coyley juga telah lahir dua hal penting dalam teori graph. Salah satunya berkenaan dengan konjektur empat warna, yang menyatakan bahwa untuk mewarnai sebuah atlas cukup dengan menggunakan empat macam warna sedemikian hingga tiap negara yang berbatasan akan memiliki warna yang berbeda.

Para ahli teori graph berkeyakinan bahwa orang yang pertama kali mengemukakan masalah empat warna adalah A.F. Mobius (1790 – 1868) dalam salah satu kuliahnya di Tahun 1840. Sepuluh tahun kemudian, A. De Morgan (1806 – 1871) kembali membahas masalah ini bersama ahli-ahli matematika lainnya di kota London. Dengan demikian tulisan De Morgan dianggap sebagai referensi pertama berkenaan dengan masalah empat warna. Masalah empat warna ini menjadi sangat terkenal setelah Coyley mempublikasikannya pada tahun 1879 dalam “Proceedings of the Royal Geographic Society” volume pertama. Hal lain yang penting untuk dibicarakan sehubungan dengan perkembangan teori graph adalah apa yang dikemukakan oleh Sir W.R. Hamilton (1805 – 1865). Pada Tahun 1859 dia berhasil menemukan suatu permainan yang kemudian dijualnya ke sebuah pabrik mainan di Dublin. Permainan tersebut terbuat dari kayu berbentuk dodecahedron beraturan yakni berupa sebuah polihedron dengan 12 muka dan 20 pojok. Tiap muka berbentuk sebuah pentagon beraturan dan tiap pojoknya dibentuk oleh tiga sisi berbeda. Tiap pojok dari dodecahedron tersebut dipasangkan dengan sebuah kota terkenal seperti London, New York, Paris, dan lain-lain. Masalah dalam permainan ini adalah, kita diminta untuk mencari suatu rute melalui sisi-sisi dari dodecahedron sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali. Walaupun saat ini masalah tersebut dapat dikategorikan mudah, akan tetapi pada saat itu tidak ada seorang pun yang bisa menemukan syarat perlu dan cukup dari eksistensi rute yang dicari.

Kurang lebih setengah abad setelah masa Hamilton, aktivitas dalam bidang teori graph dapat dikatakan relatif kecil. Pada Tahun 1920-an kegiatan tersebut muncul kembali yang dipelopori oleh D. Konig. Konig berupaya mengumpulkan hasil-hasil pemikiran para ahli matematika tentang teori graph termasuk hasil pemikirannya sendiri, kemudian dikemasnya dalam bentuk buku yang diterbitkan pada Tahun 1936. Buku tersebut dianggap sebagai buku pertama tentang teori graph.

Tiga puluh tahun terakhir ini merupakan periode yang sangat intensif dalam aktivitas pengembangan teori graph baik murni maupun terapan. Sejumlah besar penelitian telah dilakukan, ribuan artikel telah diterbitkan dan lusinan buku telah banyak ditulis. Di antara orang terkenal yang banyak berkecimpung dalam bidang ini adalah Claude Berge, Oysten Ore, Paul Erdos, William Tutte, dan Frank Harary.

B.     PEMODELAN DALAM GRAPH

1.      Rangkaian listrik.

Kirchoff (1847) menggunakan graf untuk memodelkan rangkaian listrik. Berdasarkan graf tersebut, Kirchoff menurunkan persamaan arus yang masuk dan keluar pada tiap simpul. Dari sistem persamaan lanjar (linier) simultan yang diperoleh dapat dihitung arus listrik yang mengalir pada setiap komponen.

Gambar 4.1 (a) Rangkaian listrik, (b) graf yang menyatakan rangkaian listrik

2.      Isomer senyawa kimia karbon

Arthur Cayley (1857) menggunakan graf dalam memodelkan molekul senyawa alkana CnH_2n+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 (Gambar 8.7). Isomer adalah senyawa kimia yang mempunyai rumus molekul sama tetapi rumus bangun (bentuk graf) berbeda.

Gambar 4.2 Graf senyawa alkana, masing-masing metana, etana, dan propane

3.      Transaksi konkuren pada basis data terpusat

Ini adalah terapan graf dalam bidang komputer. Basis data (database) terpusat melayani beberapa transaksi (T) yang dilakukan secara konkuren (bersamaan). Transaksi terhadap basis data dapat berupa operasi pembacaan dan operasi penulisan terhadap data yang sama. Persoalan kritis pada proses konkuren adalah deadlock, yaitu keadaan yang timbul karena beberapa transaksi saling menunggu transaksi lainnya sehingga sistem menjadi hang. Misalnya, transaksi T1 akan membaca data B yang sedang ditulis oleh transaksi T2, sedangkan T2 akan membaca data A yang sedang ditulis T1. Kedua transaksi saling menunggu data yang sedang dikuncinya (circular wait). Bila terdapat lebih dari dua transaksi yang saling menunggu sehingga membentuk siklus, maka timbul deadlock. Cara yang digunakan sistem untuk mendeteksi deadlock adalah dengan membangun graf transaksi secara periodik dan memeriksa apakah terdapat siklus pada grafnya. Jika ada siklus, maka kondisi deadlock terjadi . Misalkan:

transaksi T0 menunggu transaksi T1 dan T2 ;

transaksi T2 menunggu transaksi T1 ;

transaksi T1 menunggu transaksi T3 ;

transaksi T3 menunggu transaksi T2 ;

Graf berarah yang menyatakan transaksi menunggu transaksi lainnya ditunjukkan pada Gambar 8.8. Simpul menyatakan transaksi, sedangkan busur (Ti, Tj) menyatakan transaksi Ti menunggu transaksi Tj. Graf ini mengandung siklus, yaitu T1 - T3 - T2 - T1 Untuk mengatasi deadlock, sistem harus memutuskan siklus dengan cara membatalkan satu atau lebih transaksi di dalam siklus. Metode penanganan deadlock tidak dibahas di dalam buku ini, karena merupakan bagian dari kuliah Sistem Operasi dan Sistem Basis Data.

Gambar 4.3 Graf transaksi yang menunjukkan keadaan deadlock

4.      Pengujian program

Dalam bidang rekayasa perangkat lunak, sebuah program harus mengalami tahap pengujian untuk menemukan kesalahan (bug). Salah satu pengujian program adalah pengujian eksekusi. Aliran kendali program harus diperiksa untuk memastikan apakah aliran tersebut sudah benar untuk berbagai kasus data uji. Aliran kendali program dimodelkan dengan graf berarah yang dinamakan graf alir (flow graph). Pada graf berarah tersebut, simpul menyatakan pernyataan atau kondisi yang dievaluasi, sedangkan busur menyatakan aliran kendali program ke pernyataan atau kondisi berikutnya. Sebagai contoh, misalkan terdapat sebagian teks program Pascal di bawah ini:

Gambar 4.4

Gambar 4.5 Graf alir yang menggambarkan aliran kendali program

Data pengujian harus dirancang sedemikian sehingga semua lintasan di dalam graf alir pernah dilalui minimum satu kali. Tujuannya agar kesalahan pada setiap lintasan eksekusi dapat ditemukan dan perbaikan program dilakukan.

5.      Terapan graf di dalam teori otomata [LIU85].

Marilah kita simak masalah pemodelan perilaku sebuah mesin jaja (vending machine) yang menjual coklat seharga 15 sen sebuah. Untuk memudahkan, kita akan memisalkan bahwa mesin tersebut hanya menerima uang logam 5 sen dan 10 sen, dan mesin tidak akan memberi kembalian bila yang dimasukkan lebih dari 15 sen. Graf berbobot (setiap sisi diberi sebuah harga, akan diejlaskan kemudian)

Gambar 4.6 Graf yang memodelkan perilaku mesin jaja

6.      Turnamen Round-Robin

Turnamen yang setiap tim bertanding dengan tim lainnya hanya sekali disebut turnamen round-robin. Turnamen semacam itu dimodelkan dengan graf berarah, yang dalam hal ini simpul menyatakan tiap tim yang bertanding, dan busur menyatakan pertandingan. Busur (a, b) berarti tim a berhasil memukul tim b. Gambar 4.7 memperlihatkan turnamen round-robin untuk 6 buah tim. Tim 1 tidak terkalahkan, sedangkan tim 3 tidak pernah menang.

Gambar 4.7 Turnamen round-robin

Contoh terapan graf yang lain adalah menyatakan aliran informasi dalam pengolahan sinyal dan aliran massa dalam industri kimia. Graf juga berguna memodelkan sesuatu yang abstrak, seperti struktur perusahaan, tingkatan sosial, pohon keluarga, aliran kerja dalam proyek, perencanaan dan manajemen proyek, perpindahan dalam permainan (game), dan langkah-langkah pemecahan masalah. Terapan yang terakhir ini merupakan kemampuan dasar yang harus dikuasai dalam bidang kecerdasan buatan (artificial intelligence).

Model Graf

Contoh 1:

Bagaimana cara merepresentasikan jaringan (dua arah) KA yang menghubungkan sekumpulan kota?

Kita harus memakai graf sederhana dengan garis hubung {a, b} merupakan jalur langsung yang menghubungkan kota a dengan kota b.