---------------------------------------------------------------------------------------------------------------

UNIVERSITAS YUDHARTA PASURUAN

FAKULTAS TEKNIK

PRODI TEKNIK INFORMATIKA

---------------------------------------------------------------------------------------------------------------

UJIAN AKHIR SEMESTER GENAP

TEORI GRAPH 

---------------------------------------------------------------------------------------------------------------

Soal UAS:

1. Tiga pasang suami istri hendak menyeberangi sungai dan hanya terdapat satu perahu yang hanya untuk mengangkut 2 orang. Dan ternyata semua suami adalah seorang pencemburu yang tidak mau meninggalkan istrinya bersama pria lain. Buatlah algoritma penyeberangan yang mungkin untuk ketiga pasangan suami istri tersebut!

2. Tentukan banyak edge minimal dari sebuah graph dengan 10 vertex, sehingga untuk setiap vertex yang dihilangkan, ada sebuah cycle yang melewati 9 vertex yang tersisa!

3. Di sebuah pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas jalan. Ada 2 kota yang terhubung, ada juga yang tidak. Suatu rute yang dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di pulau tersebut ada rute wisata yang tidak melewati kota tersebut!

Tugas:

Contoh 3:

Misalkan kita ingin menempuh perjalanan dari Jakarta menuju Surabaya. Mungkin kita ingin mengetahui rute terpendek yang dapat dipilih. Dalam permasalahan ini kota direpresentasikan sebagai titik, sedangkan rute atau jalan direpresentasikan sebagai segmen garis atau kurva.

Contoh 4:

Misalnya terdapat satuan tugas dalam kepolisian yang bertugas mengungkap jaringan pengedar obat terlarang. Hal tersebut dapat kita gambarkan ke dalam sebuah graph. Dalam graph tersebut, tiap-tiap anggota komisi dinyatakan dengan sebuah titik, dan hubungan di antara anggota dinyatakan dengan sisi atau kurva. Dalam permasalahan ini kita mungkin ingin tahu seberapa rapuhkah jaringan komunikasi ini, dan seberapa mudahkah kita bisa menghancurkan jaringan tersebut. Dengan menggunakan teori graph desain jaringan komunikasi yang handal dapat diciptakan.

ミ★ѕєlαмαт мєηgєяjαkαη..★彡