Soal dan Pembahasan – Ujian Akhir Semester Teori Graf

Berikut ini adalah 6 soal UAS Teori Graf (TA 2017/2018) yang diujikan pada tanggal 8 Januari 2018 oleh Drs. Ade Mirza, M.Pd kepada mahasiswa prodi pendidikan matematika FKIP Untan.

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.

Pembahasan

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, \cdots, 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.

Pembahasan Belum Tersedia

[collapse]

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

Pembahasan

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!

Pembahasan

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.

Pembahasan




(Sumber: Wolfram MathWorld)

[collapse]

KategoriMatematika Diskrit, UAS Mata KuliahTag, , , , , , , ,

Tinggalkan Balasan

Silakan beri tanggapan dan saran, tidak perlu sungkan. Mohon juga diinformasikan melalui kolom komentar ini bila ada kesalahan pengetikan sekecil apapun (typo atau bahasa latex yang error) atau kesalahan konsep dan pembahasan soal. Terima kasih. Ganbatte!

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