SOAL UAS MATEMATIKA DISKRIT SEMESTER GENAP 2012

1.Berdasarkan graph diatas, tentukanlah :

a. Size, Order, dan Density

b. Apakah graph tersebut termasuk graph planar? jelaskan secara singkat dan gambarkan?

c.Matriks ketetanggan (adjacency matrix)

2.Berdasarkan grapgh tersebut di atas:

a. Gunakan Algoritma Dijkstra, carilah lintasan terpendek dari vertex A ke vertex Y kemudian tulis masing-masing langkahnya dan lintasan yang dihasilkan!\

b.Berapa depth (asumsi akarnya adalah node A ==> asumsi graph yang dihasilkan adalah tree) dan panjang panjang lintasan yang dihasilkan?

c.Jika vertex A diasumsikan sebagai root (asumsi graph yang dihasilkan adalah tree) tentukan hasil penelusuran preorder dan postorder

3.Berdasarkan graph tersebut diatas:

a. Gunakan Algoritma Prim atau kruskal (pilih salah satu), carilah minimum spaning tree kemudian tulis masing-masing langkahnya dan pohon yang dihasilkan?

b.Berapa height (asumsi akarnya adalah node A) dan bobot dari pohon yang dihasilkan?

c. Jika vertex A diasumsikan sebagai root tentukan hasil penelusuran preorder dan postorder

4.Diketahui text berikut:

Text Ganjil: AyuN-AYuNanS

Text Genap: SoSoroDOTan

Berdasarkan string diatas:

a.Tulis pohon Huffman yang dihasilkan dan huffman code yang dihasikan?

b.Tulis text baru berdasarkan huffman code tersebut!

5.Diketahui Algoritma seperti berikut ini:

<br /> FOR A= 1 TO N DO<br /> FOR B= 1 TO N DO<br /> FOR C= 1 TO B DO<br /> IF (C MOD 2 == 0)THEN<br /> Z[A,B]<-- Z[A,B]+X[A,B]*Y[B,C] <br /> END IF <br /> END FOR <br /> END FOR<br /> END FOR

Dari Algo diatas:

a. Hitung Tmin(n) dan Tmax(n) dari algoritma tersebut??

b.Buktikan bahwa algoritma tersebut termasuk O(n^3)?

Referensi Belajar matematika diskrit!

Coba Selesaikan dalam waktu 90 menit -___- !!!