Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 2
Gambar sebagai berikut adalah peta jalan antar kota di negeri 1001 Malam.
Karena banyak wisatawan yang mengagumi keindahan negeri 1001 Malam, sang raja berencana untuk membangun beberapa jalan tambahan supaya para wisatawan dapat bertamasya mengunjungi setiap kota dengan melewati setiap jalan hanya satu kali saja. Sebuah jalan tambahan yang dibangun hanya dapat menghubungkan tepat dua buah kota, dan dua buah kota dapat dihubungkan oleh lebih dari 1 (satu) jalan. Berapakah minimum banyak jalan tambahan yang perlu dibangun agar seorang wisatawan yang berawal dari sebuah kota dapat menggunakan setiap jalan antar kota tepat sekali (tidak harus kembali ke kota asal)?
5 jawaban
reynaldo wijaya10 tahun lalu
1
2
Salvian Reynaldi10 tahun lalu
semoga menjawab
1
Perjalanan melalui setiap jalan (edge) pada sebuah graf tepat sekali (tanpa perlu kembali ke tempat asal), adalah definisi Eulerian Path.
Syarat yang memungkinkan Perjalanan Eulerian dilakukan pada sebuah graf tak berarah adalah setiap kota (node) i harus terhubung oleh Xi jalan, di mana X adalah bilangan genap, atau tepat 2 node terhubung dengan sejumlah ganjil jalan.
Dengan menamai kota2 tersebut A, B, C, ..., I (dari atas ke bawah - kiri ke kanan), kita bisa menambahkan 2 jalan (B ke F dan E ke H), sehingga tinggal tepat 2 kota saja yang terhubung dengan sejumlah ganjil jalan (C dan D)
Salvian Reynaldi10 tahun lalu
semoga menjawab
ah iya, di soal tidak disebutkan apakah sebuah kota awal perjalanan yang dimaksud adalah salah satu kota saja atau harus semua kota. Jika harus semua kota, maka perlu ada 2 jalan tambahan lagi (dari C dan D ke sembarang kota yang sama [kecuali C atau D tentunya], misal H; sehingga jawabannya empat), sehingga graf memiliki Eulerian Cycle.
Masuk untuk menulis jawaban
Tapi bagaimana jika wisatawan itu tidak berawal di kota C dan D misal di A apakah bisa mengunakan jalan tepat sekali jika menambahkan 2 jalan (B ke F dan E ke H)