Soal dan Pembahasan – Ujian Akhir Semester (UAS) Matematika Diskrit (Graf)


Berikut ini adalah 6 soal UAS Matematika Diskrit (TA 2017/2018) yang diujikan pada tanggal 8 Januari 2018 oleh Drs. Ade Mirza, M.Pd. Materi yang diujikan seluruhnya mengenai graf.

Soal Nomor 1
Jika G graf sederhana dengan |V(G)| \geq 2, buktikan bahwa G memiliki paling sedikit 2 titik berbeda dengan derajat yang sama.

Penyelesaian

Misalnya graf sederhana itu memiliki n titik, dengan n \geq 2. Karena ada n titik berbeda, maka derajat maksimum yang mungkin adalah n - 1, tetapi perhatikan bahwa ketika ada 1 buah titik yang memiliki derajat n - 1, maka tidak ada titik yang berderajat 0 dan derajat titik lainnya haruslah n - 2, n - 3, n - 4, ...., 3, 2, 1. Padahal ada n titik berbeda dalam kasus ini, sehingga pastilah setidaknya ada 1 titik yang memiliki derajat yang sama dengan titik lainnya.
Contoh: Misal ada graf sederhana dengan 4 titik. V(G) = \{a, b, c, d\}, dengan d(a) = 3. Ini berakibat tidak ada titik yang berderajat 0. Agar berbeda, ambil d(b) = 2 dan d(c) = 1. Karena d(d) \neq 0, maka derajat titik d yang mungkin adalah 1, 2, atau 3 (derajatnya sama dengan titik lain).

[collapse]

Soal Nomor 2
Buatlah 2 buah graf yang tidak isomorfik, beraturan dengan 8 titik dan 12 sisi.

Penyelesaian


Graf H dan H pada gambar di atas tidak isomorfik, beraturan (berderajat 3) dengan 8 titik dan 12 sisi.

[collapse]

Soal Nomor 3
Tunjukkan bahwa graf pohon dengan n titik memiliki tepat n - 1 sisi.

Penyelesaian

Misalkan H adalah graf pohon, dengan |V(H)| = n. Akan dibuktikan bahwa |E(H)| = n - 1.
Dengan menggunakan induksi matematika pada titik n, maka untuk n=1, maka |E(H)| = 1 - 1 = 0 merupakan pernyataan yang benar karena pohon dengan satu titik jelas tidak memiliki sisi.
Asumsikan benar bahwa untuk n = k, |E(H)| = k - 1. Akan dibuktikan benar untuk n = k + 1 sebagai berikut.
Misalkan e adalah salah satu sisi pada pohon H. Karena H tidak memuat sikel dan terhubung (definisi pohon), maka bila sisi ini dihapus, akan diperoleh graf yang terdiri dari dua komponen, masing-masing komponen memiliki k_1 dan k_2 titik, dengan k_1+k_2=n. Masing-masing komponen pada graf itu merupakan pohon. Berdasarkan asumsi, masing-masing komponen memiliki (k_1-1) dan (k_2-1) sisi. Jika sisi e dimasukkan kembali pada H, maka diperoleh total sisinya, yaitu
\begin{aligned} |E(H)| & = (k_1 - 1)+(k_2-1)+1 \\ & = (k_1 + k_2) - 1 \\ & = n - 1 \end{aligned}
Dengan demikian benar untuk semua n. Jadi, terbukti bahwa pohon dengan n titik mempunyai tepat n - 1 sisi.

[collapse]

Soal Nomor 4
Jika Q_n adalah graf kubus,
a) berapa banyak titik Q_n
b) berapa banyak sisi Q_n
Berikan argumen/alasan!

Penyelesaian

Graf kubus Q_n memiliki 2^n titik dan 2^{n-1}.n sisi.
Penjelasan:
Q_1 (graf berupa segmen garis) memiliki 2 titik dan 1 sisi.
Q_2 (graf berupa bidang persegi panjang) memiliki 4 titik dan 4 sisi.
Q_3 (graf berupa kubus yang direpresentasikan dalam bidang) memiliki 8 titik dan 12 sisi. Selanjutnya, Anda akan memperoleh bahwa graf kubus Q_n memiliki 2^n titik dan 2^{n-1} \times n sisi.

[collapse]

Soal Nomor 5
Buatlah contoh graf yang dual diri.

Penyelesaian


(Sumber: Wolfram MathWorld)

[collapse]

Soal Nomor 6
Perhatikan graf H berikut.

a) Buatlah jalan tertutup dengan panjang 7.
b) Carilah trail yang bukan sirkuit dengan panjang 6.
c) Carilah jalan tertutup yang bukan trail.

Penyelesaian

Contoh jalan tertutup dengan panjang 7 adalah (u~a~v~e~w~f~x~b~u~a~v~e~w~d~u)
Contoh trail yang bukan sirkuit dengan panjang 6 adalah (u~b~x~g~x~f~w~c~u~d~w~e~v)
Contoh jalan tertutup yang bukan trail adalah (u~b~x~b~u)

[collapse]

Ayo Beri Rating Postingan Ini

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *