Soal
Soal No. 1
Tunjukkan bahwa setiap subgraf terinduksi dari suatu graf lengkap adalah graf lengkap!Buktikan bahwa untuk setiap graf sederhana $G$ dengan $\delta(G) \geq 2$ maka $G$ memuat cycle!
Soal No. 2
Misalkan $P_{1}=u_{1}u_{2}\cdots u_{n}$ dan $P_{2}=v_{1}v_{2}\cdots v_{n}$ masing-masing merupakan lintasan terpanjang di graf terhubung $G$.
Soal No. 3
Tunjukkan bahwa terdapat titik $v \in P_{1} \cap P_{2}$ !
Soal No. 4
Buktikan bahwa jika graf $G$ reguler dengan derajat $r$ dan $\kappa=1$ maka $\lambda \leq \left[r/2\right]$!
Pembahasan
Soal No. 1
Misalkan graf $H$ adalah subgraf terinduksi dari graf $K_{n}$. Jika $V(H)=1$ maka $H$ adalah graf lengkap. Pada kasus $V(H) >1$, ambil sebarang titik $u$ dan $v$ di $H$. Berdasarkan definisi graf terinduksi, maka $uv \in E(H)$ karena $uv \in E(K_{n})$. Oleh karena itu, graf $H$ adalah graf lengkap.
Soal No. 2
Misalkan $P=v_{1}v_{2}\cdots v_{n}$ adalah lintasan terpanjang di graf $G$. Karena $\delta(G) \geq 2$ sehingga $\deg(v_{n})\geq 2$ dan terdapat $u \neq v_{n-1}$ yang bertetangga dengan $v_{n}$. Karena $P$ adalah lintasan terpanjang akibatnya $u=v_{i}$ untuk $1 \leq i \leq n-2$. Lintasan $P'=v_{i}v_{i+1}\cdots v_{n}v_{i}$ merupakan cycle di graf $G$.
Soal No. 3
Andaikan $P_{1} \cap P_{2} = \varnothing$. Graf $G$ terhubung sehingga terdapat lintasan $P_{3}=u_{i}w_{1}w_{2}\cdots w_{k}v_{j}$ dengan $P_{1} \cap P_{3}=u_{i}$ dan $P_{2} \cap P_{3}=v_{j}$. Tanpa mengurangi keumuman lintasan $P_{1a}=u_{1}u_{2}\cdots u_{i}$ lebih panjang dari lintasan $P_{1b}=u_{i}u_{i+1}\cdots u_{n}$ dan $P_{2a}=v_{1}v_{2}\cdots v_{j}$ lebih panjang dari pada lintasan $P_{2b}=v_{j}v_{j+1}\cdots v_{n}$. Akibatnya lintasan $P_{1a}\cup P_{3} \cup P_{2a}$ adalah lintasan lebih panjang daripada lintasan $P$ dan $Q$. Kontradiksi dengan yang diketahui. Pengandaian salah. Yang benar $P_{1} \cap P_{2} \neq \varnothing$.
Soal No. 4
Sebagai latihan ya.hehe
NB : Jika ingin membaca secara offline dalam format pdf bisa download di bawah ini
Bagikan
Pembahasan Soal Pengantar Teori Graf
4/
5
Oleh
Mohammad Mahfuzh Shiddiq
Hai sobat...terima kasih telah mampir di blog kami. Silahkan tulis komentar di bawah ini sobat. Kami selalu menyambut baik setiap umpan balik sobat.