1. Perjalanan yang tidak dapat Bimo lakukan dengan menggunakan jam pasir tersebut adalah:
   a. Dari kota A menuju kota D
2. Rute perjalanan yang dapat ditambahkan dalam layanan jam pasir tersebut, supaya Bimo dapat menempuh perjalanan dari kota manapun menuju kota manapun adalah:
   c. Dari kota C ke kota D

Pembahasan

Terdapat 5 kota: A, B, C, D, E.

Rute perpindahan kota yang merupakan fitur dari jam pasir ajaib:

1. A ke B,
2. A ke C,
3. B ke C,
4. C ke E,
5. D ke E,
6. D ke A, dan
7. E ke B.

Soal Nomor 1

Pertanyaan
Jika jam pasir tersebut dapat dipakai tanpa batas, perjalanan manakah yang tidak dapat Bimo lakukan dengan menggunakan jam pasir tersebut?

Penyelesaian

Untuk menjawab pertanyaan ini, kita dapat gambarkan grafnya, dengan asumsi bahwa rute bersifat satu arah, tidak bersifat dua arah (bolak-balik). Contoh graf dapat dilihat pada gambar (tidak mutlak harus seperti itu, karena kota C bisa berada di tengah).

Dari graf tersebut, dapat disimpulkan bahwa yang tidak memiliki arah rute masuk kota adalah kota D. Dari kota D, hanya bisa berpindah ke luar kota.

Dengan demikian, perjalanan yang tidak dapat Bimo lakukan dengan menggunakan jam pasir tersebut adalah:
a. Dari kota A menuju kota D

Untuk opsi lainnya:

• b. Dari kota D menuju kota C
  ⇒ Dapat ditempuh dengan rute D → E → B → C (3 kali membalik jam pasir ajaib).
• c. Dari kota A menuju kota E
  ⇒ Dapat ditempuh dengan rute A → B → C → E (3 kali membalik jam pasir ajaib), atau A → C → E (2 kali membalik jam pasir ajaib).
• d. Dari kota E menuju kota B
  ⇒ Dapat ditempuh dengan sekali membalik jam pasir ajaib (rute 7).
• e. Dari kota C menuju kota B
  ⇒ Dapat ditempuh dengan rute C → E → B (2 kali membalik jam pasir ajaib).

Soal Nomor 2

Pertanyaan
Jika jam pasir tersebut dapat dipakai tanpa batas, rute perjalanan manakah yang dapat ditambahkan dalam layanan jam pasir tersebut, supaya Bimo dapat menempuh perjalanan dari kota manapun menuju kota manapun?

Penyelesaian

Dari soal nomor 1, jelas bahwa rute masuk ke kota D harus ditambahkan. Jadi, opsi a, d, dan e dapat dianulir/diabaikan. Tersisa opsi b dan c.

Opsi b. Dari kota A ke kota D

Dengan penambahan rute ini:

• Dari kota A, dapat dilakukan perjalanan ke semua kota.
• Dari kota B, perjalanan ke kota D dan A tidak dapat dilakukan.

Sampai di sini, kita berhenti memeriksa, karena sudah tidak memenuhi.

Opsi c. Dari kota C ke kota D

• Dari kota A, perjalanan ke kota B, C, dan E jelas dapat dilakukan.
  Dengan penambahan rute ini, perjalanan dari kota A ke kota D menjadi dapat dilakukan, dengan rute A → C → D.
• Dari kota B, perjalanan ke kota C dan E jelas dapat dilakukan.
  Dengan penambahan rute ini, perjalanan dari kota B ke kota A dan D menjadi dapat dilakukan, dengan rute B → C → D → A dan B → C → D.
• Dari kota C, perjalanan ke kota B dan E jelas dapat dilakukan.
  Dengan penambahan rute ini, perjalanan dari kota C ke kota A dan D menjadi dapat dilakukan, dengan rute C → D → A dan C → D.
• Dari kota D, perjalanan ke kota A dan E jelas dapat dilakukan.
  Dengan penambahan rute ini, perjalanan dari kota D ke kota B dan C menjadi dapat dilakukan, dengan rute D → A → B dan D → A → C.
• Dari kota E, perjalanan ke kota B dan C jelas dapat dilakukan.
  Dengan penambahan rute ini, perjalanan dari kota E ke kota A dan D menjadi dapat dilakukan, dengan rute E → B → C → D → A dan E → B → C → D.

Dengan demikian, rute perjalanan yang dapat ditambahkan dalam layanan jam pasir tersebut, supaya Bimo dapat menempuh perjalanan dari kota manapun menuju kota manapun adalah:
c. Dari kota C ke kota D

Tambahan
Alternatif jawaban lain untuk soal nomor 2 ini adalah penambahan rute kota B ke kota D. Jadi, jawabannya tidak mutlak harus opsi c tersebut. Opsi c dipilih karena kita terbatas pada opsi jawaban yang disediakan.