Pembahasan Soal Teori Graf || Latihan 2

 Hallo guys, di sini saya akan membahas soal-soal Teori Graf yang ada dalam buku yang berjudul "Combinatorics and Graph Theory" ditulis oleh John M. Harris dkk edisi kedua. Baiklah berikut adalah soal-soalnya. 

1. Tentukan jari-jari, diameter dan pusat dari graf pada gambar berikut.

2. Tentukan jari-jari dan diameter masing-masing graf berikut: $P_{2k}, P_{2k+1}, C_{2k}, C_{2k+1}, K_n, K_{m,n}$.

3. Untuk setiap graf berikut, tentukan banyaknya simpul di pusat.

4. Jika $x$ berada di keliling $G$ dan $d(x, y) = ecc(x)$, maka buktikan bahwa $y$ berada di keliling $G$.

5. Jika $u$ dan $v$ merupakan simpul-simpul yang bertetangga pada suatu graf, buktikan bahwa perbedaan \textit{eccentricity}nya paling banyak satu.

6. Suatu graf $G$ disebut berpusat pada diri sendiri jika $C(G)= V(G)$. Buktikan bahwa setiap graf bipartit lengkap, setiap siklus, dan setiap graf lengkap berpusat pada diri sendiri.

7. Diberikan sebuah graf terhubung $G$ dan bilangan bulat positif $k$, pangkat ke-$k$ dari $G$, dilambangkan $G^k$, adalah graf dengan $V(G^k)=V(G)$ dan di mana simpul $u$ dan $v$ bertetangga di $G^k$ jika dan hanya jika $d_G(u,v)\leq k$.

a. Gambarkan pangkat ke-2 dan ke-3 dari $P_8$ dan $C_{10}$.

b. Untuk graf $G$ dengan orde $n$, berapakah $G^{diam(G)}$?

8. a. Tentukan graf berorde $7$ yang mempunyai jari-jari $3$ dan diameter $6$.

    b. Tentukan graf berorde $7$ yang mempunyai jari-jari $3$ dan diameter $5$.

    c. Tentukan graf berorde $7$ yang mempunyai jari-jari $3$ dan diameter $4$.

    d. Andaikan $r$ dan $d$ adalah bilangan bulat positif dan $r\leq d\leq 2r$. Deskripsikan suatu graf yang mempunyai jari-jari $r$ dan diameter $d$.

9. Andaikan bahwa $u$ dan $v$ adalah simpul pada suatu graf $G$, $ecc(u)=m, ecc(v)=n$, dan $m<n$. Buktikan bahwa $d(u,v)\geq n-m$. Kemudian gambarkan graf $G_1$ dimana $d(u,v)=n-m$ dan graf $G_2$ dimana $d(u,v)>n-m$. Dalam setiap kasus, beri label $u$ dan $v$, dan berikan nilai $m$ dan $n$.

10. Misalkan $G$ adalah graf terhubung dengan setidaknya satu siklus. Buktikan bahwa $G$ memiliki setidaknya satu siklus yang panjangnya kurang dari atau sama dengan $2 diam(G)+1$.

a. Buktikan bahwa jika $G$ terhubung dan $diam(G)\geq 3$, maka $\overline{G}$ terhubung.

b. Buktikan bahwa jika $diam(G)\geq 3$, maka $diam(\overline{G})\leq 3$.

c. Buktikan bahwa jika $G$ regular dan $diam(G)=3$, maka $diam(\overline{G})=2$.

11. Berikan matriks ketetanggaan untuk setiap graf berikut.

a. $P_{2k}$ dan $P_{2k+1}$, di mana simpulnya diberi label dari satu ujung lintasan ke ujung lainnya.

b.  $C_{2k}$ dan $C_{2k+1}$, di mana simpulnya diberi label secara berurutan di sekitar siklus.

c. $K_{m,n}$, di mana simpulnya pada himpunan partisi pertama diberi label $v_1,\cdots ,v_m$.

d. $K_n$, di mana simpulnya diberi label sesuka kalian.

12. Tanpa menghitung matriks secara langsung, temukan $A^3$ dimana $A$ adalah matriks ketetanggaan $K_4$.

13. Jika $A$ adalah matriks ketetanggaan dari graf $G$, tunjukkan bahwa entri $(j, j)$ dari $A^2$ adalah derajat $v_j$.

14. Misalkan $A$ adalah matriks ketetanggaan dari graf $G$.

a. Tunjukan bahwa banyaknya segitiga yang mengandung $v_j$ adalah $\frac{1}{2}[A^3]_{j,j}$ terhubung.

b. Buktikan bahwa jika $diam(G)\geq 3$, maka $diam(\overline{G})\leq 3$.

c. Buktikan bahwa jika $G$ regular dan $diam(G)=3$, maka $diam(\overline{G})=2$.

d. Trace matriks persegi $M$, dilambangkan $Tr(M)$, adalah jumlah entri pada diagonal utama. Buktikan bahwa jumlah segitiga di $G$ adalah $\frac{1}{6}Tr(A^3)$.

15. Tentukan entri $(1,5)$ dari $A^{2009}$ di mana $A$ adalah matriks ketetanggaan $C_{10}$ dan di mana simpul-simpul $C_{10}$ diberi label secara berurutan di sekitar siklus.

a. Buktikan pernyataan kedua pada Teorema 2.2.3.

b. Buktikan pernyataan ketiga pada Teorema 2.2.3.

16. Gunakan Teorema 2.2.3 untuk merancang algoritma untuk menentukan pusat graf $G$.

17. Graf $G$ mempunyai matriks ketetanggaan $A$ dan matriks jarak $D$. Buktikan bahwa jika $A=D$, maka $G$ graf lengkap.

18. Berikan matriks jarak untuk graf pada soal nomor 12. Anda harus membuat matriks ini secara langsung - tidak perlu menggunakan metode yang dijelaskan dalam bagian ini.