[GRAF] Seekor Kelinci, Anjing, Harimau, dan Nelayan yang Hendak Menyeberang

Ini adalah soal Graf pada matakuliah Teori Graf, tugas 01

Seekor kelinci, seekor anjing dan seekor harimau berada di satu tepi sungai dan seorang nelayan dengan perahu yang kecil hendak memindahkan ketiga binatang itu ke sisi sungai yang lain. Karena kecilnya perahu si nelayan, perahu tersebut hanya mampu mengangkut nelayan dan paling banyak 1 ekor binatang yang ada. Jika kelinci dan harimau saja yang ditinggal bersama di satu tepi sungai maka kelinci akan dimakan harimau, begitu pula sebalinya jika anjing dan kelici saja yang ditinggal di sisi sungai maka kelinci akan dimakan oleh anjing. Bagaimana strategi yang dipakai oleh nelayan agar semua binatang yang ditinggal selamat dan banyak nelayan menyeberang sedikit mungkin??



Caranya
pertama Nelayan menyeberang dengan membawa kelinci menuju keseberang sungai yang lain (sisi 2)
Kedua Nelayang menyeberang kembali ke seberang sungai (sisi 1) tanpa membawa binatang
Ketiga Dari (sisi 1) nelayan membawa harimau dan menyeberang ke (sisi 2) lain
Keempat Dari (sisi 2) nelayan membawa kembali kelinci menyeberang ke (sisi 1)
Kelima Nelayan menyeberang ke sisi 2 membawa anjing dan meninggalkan kelinci
Keenam Nelayan kembali ke seberang sungai (sisi 1) tanpa membawa binatang
Ketujuh Nelayang menyeberang kesisi 2 membawa kelinci
Akhirnya ketiga binatang dan Si nelayan berhasil keseberang sungai.
BERHASIL....