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]