1.Jawablah pertanyaan-pertanyaan berikut ini:
a.)Jika diberikan sembarang Simple graf, sebagai berikut: G = (V, E); V = {1, 2, 3, 4, 5, 6}; E = {13, 14, 15, 16, 23, 24, 26, 35, 36, 46, 56}Apakah graf G tersebut merupakan graf planar? Jika iya, gambarkanlah grafnya (tanpa adanya egde yang saling bersilangan).
b.)Sebutkan 3 bentuk graf yang bukan merupakan graf planar (setiap graf hanya boleh disebutkan dengan istilah yang Anda kenal, bukan dalam bentuk representasi graf: himpunan graf, matriks adjacent, ilustrasi graf)
<a href="https://adilalaras.files.wordpress.com/2015/04/matif-jawaban-no1.png"><img src="https://adilalaras.files.wordpress.com/2015/04/matif-jawaban-no1.png?w=300" alt="matif jawaban no1" width="300" height="170" class="alignnone size-medium wp-image-142" /></a>
2. <a href="https://adilalaras.files.wordpress.com/2015/04/matif-soal-no2.png"><img src="https://adilalaras.files.wordpress.com/2015/04/matif-soal-no2.png?w=300" alt="matif soal no2" width="300" height="140" class="alignnone size-medium wp-image-146" /></a>
Dari gambar 1 berikut yang merupakan tree adalah ...
a. G1 dan G3
b. G3 dan G4
c. G2 dan G4
d. G1 dan G2
Jawaban : D
Penjelasan : Disebut tree karena setiap komponen dalam graph terhubung dengan lintasan tunggal dan tidak mengandung sirkuit yaitu G1 dan G2, sedangkan G3 mengandung sirkuit yaitu pada titik adf dan G4 merupakan forest karena mengandung dua tree.
3. <a href="https://adilalaras.files.wordpress.com/2015/04/matif-soal-no3.png"><img src="https://adilalaras.files.wordpress.com/2015/04/matif-soal-no3.png?w=300" alt="matif soal no3" width="300" height="100" class="alignnone size-medium wp-image-147" /></a>
Dari gambar 2 berikut yang merupakan spanning tree dari graf G adalah …
a. T1,T2
b. T3,T4
c. T1,T3,T4
d. Benar semua
Jawaban : D
Penjelasan : Spanning tree memiliki lintasan tunggal dan tidak mengandung sirkuit dan dari gambar tersebut semuanya merupakan spanning tree.
4. <a href="https://adilalaras.files.wordpress.com/2015/04/matif-soal-no4.png"><img src="https://adilalaras.files.wordpress.com/2015/04/matif-soal-no4.png?w=300" alt="matif soal no4" width="300" height="213" class="alignnone size-medium wp-image-148" /></a>
Total bobot dari spanning tree berikut adalah … (gambar 3)
a. 24
b. 20
c. 15
d. 30
Jawaban : A
Penjelasan :
<a href="https://adilalaras.files.wordpress.com/2015/04/matif-jawaban-no4.png"><img src="https://adilalaras.files.wordpress.com/2015/04/matif-jawaban-no4.png?w=300" alt="matif jawaban no4" width="300" height="217" class="alignnone size-medium wp-image-149" /></a>
Terlihat bahwa spanning tree tersebut mempunyai total bobot 2 + 3 + 4 + 4 + 4 + 4 + 3 = 24
5.Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 16 buah sisi dan tiap simpul berderajat sama dan tiap simpul berderajat ≥ 4 ?
* Jawaban: Tiap simpul berderajat sama -> graf teratur.
* Jumlah sisi pada graf teratur berderajat r adalah e = nr/2. Jadi, n = 2e/r = (2)(16)/r = 32/r.
* Untuk r = 4, jumlah simpul yang dapat dibuat adalah maksimum, yaitu n = 32/4 = 8.
* Untuk r yang lain (r > 4 dan r merupakan pembagi bilangan bulat dari 32):
r = 8 -> n = 32/8 = 4 -> tidak mungkin membuat graf sederhana.
r = 16 -> n = 32/16 = 2 -> tidak mungkin membuat graf sederhana.
* Jadi, jumlah simpul yang dapat dibuat adalah 8 buah (maksimum dan minimum).
