Solusi UTS Teori Graf (2019)

teori graf universitas

Soal 1
a. Jika \( G \) adalah graf reguler-$ k $ dengan $ n $ titik. Berapa banyak sisi yang bisa dimiliki $ G $ ?
b. Gambar graf reguler-$ 3 $ dengan 11 titik atau buktikan bahwa tidak ada graf yang seperti itu !

Penyelesaian
Formula jumlahan derajat titik mengatakan bahwa\[\sum_{v \in V}\deg(v)=2\left|E\right|\]Jadi untuk graf reguler-$k$ yang memiliki titik sebanyak $n$ akan memiliki sisi sebanyak $\boldsymbol{|E| = \frac{kn}{2}}$.

Berdasarkan formula jumlahan titik di atas diperoleh banyak sisi $|E|=\frac{3\cdot 11}{2}$ yang bukan merupakan bilangan bulat. Oleh karena itu tidak ada graf reguler-$3$ dengan 11 titik.

Baca juga : Pembahasan Soal Teori Graf

Soal 2
Misalkan $ n $ bilangan bulat positif. Tunjukkan bahwa subgraf yang teriduksi oleh subset tak kosong dari himpunan titik $ V(K_{n}) $ merupakan graf lengkap !

Penyelesaian
Misalkan $G$ adalah subgraf terinduksi dari graf lengkap $K_{n}$. Ambil sebarang titik $u$ dan $v$ di $G$.

Jika $u$ dan $v$ membentuk garis di $K_{n}$ maka berdasarkan definisi subgraf terinduksi titik $u$ dan $v$ juga harus membentuk garis di $G$.

Karena setiap dua titik membentuk di graf lengkap $K_{n}$ maka ini berlaku untuk sebarang dua titik $u$ dan $v$ di graf $G$.

Oleh karena itu, graf $G$ lengkap.

Soal 3
Jelaskan karakter atau ciri-ciri matriks ketetanggan dari suatu graf bipartit! Jelaskan !

Jangan lewatkan juga : Graf Pohon

Penyelesaian
Misalkan graf $G$ adalah graf bipartit dengan himpunan titik $V$ dipartisi menjadi dua himpunan yaitu $A=\left\{a_{1}, a_{2}, \cdots, a_{m}\right\}$ dan himpunan $A=\left\{b_{1}, b_{2}, \cdots, b_{n}\right\}$.

Berdasarkan definisi graf bipartit maka sebarang titik $a_{i}$ dan $a_{j}$ tidak bertetangga untuk $i \neq j$ begitu pula dengan $b_{i}$ dan $b_{j}$.

Jadi jika setiap titik pada satu partisi diurutkan di entri matriks ketetanggan graf $G$ akan diperoleh bentuk matriks
\[\boldsymbol{\left(\begin{array}{cc}0_{m,m}&H\\H^{T}&0_{n,n}\end{array}\right)}\]dengan $0_{n,n}$  dan $0_{m,m}$ adalah matriks nol dengan ukuran $n \times n$. Sedangkan matriks $H$ adalah matriks berukuran $m \times n$ yang merepresentasikan matriks $G$.

Soal 4
Barisan derajat dari graf adalah barisan derajat setiap titik dari graf ke dalam urutan tak naik.
a. Barisan derajat dari graf $ K_{m,n} $ dengan $ m,n \in \mathbb{N} $ seperti apa? Jelaskan !
b. Berapa banyak sisi yang dimiliki suatu graf jika barisan derajatnya $ 4,3,3,2,2 $? Gambar graf tersebut!

Penyelesaian
(a). Graf bipartit lengkap adalah graf bipartit yang setiap titik di salah satu partisi bertetangga dengan semua titik di partisi yang lain sehingga barisan derajat graf $K_{m,n}$ bisa dibagi dua macam bilangan $m$ dan $n$, yaitu\[\underbrace{m\cdot m \cdot \ldots \cdot m \cdot}_{n \text{ faktor}}\underbrace{n\cdot n \cdot \ldots \cdot n}_{m \text{ faktor}}\]
(b). Berdasarkan formula jumlahan sisi di atas maka banyak sisi adalah\[|E|=\frac{\sum\limits_{v \in V}\deg (v)}{2}=\frac{4+3+3+2+2}{2}=7\]Oleh karena itu banyak sisi yang bisa dimiliki graf adalah 7.

Bagikan

Jangan lewatkan

Solusi UTS Teori Graf (2019)

4/ 5

Oleh Mohammad Mahfuzh Shiddiq

Mohammad Mahfuzh Shiddiq October 16, 2019 Komentar