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).
