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)
2.
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.
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.
Total bobot dari spanning tree berikut adalah … (gambar 3)
a. 24
b. 20
c. 15
d. 30
Jawaban : A
Penjelasan :
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).
