Pembahasan Soal Teori Graf || Latihan 1

Posting Komentar

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.

Catatan : graf disini jika tidak ada keterangan apapun maka graf yang dimaksud adalah graf sederhana.

1. Sepuluh orang duduk mengelilingi meja bundar. Setiap orang berjabat tangan dengan semua orang di meja kecuali orang yang duduk tepat di seberang meja. Gambarkan Graf yang memodelkan situasi ini.

Jawab : Graf yang memodelkan situasi tersebut adalah sebagai berikut.

2. Enam anggota persaudaraan (Adam, Bert, Chuck, Doug, Ernie, dan Filthy Frank) harus berpasangan sebagai teman sekamar untuk tahun ajaran mendatang. Setiap orang telah menyusun daftar orang-orang yang bersedia berbagi kamar dengannya.

Daftar Adam: Doug

Daftar Bert: Adam, Ernie

Daftar Chuck: Doug, Ernie

Daftar Doug: Chuck

Daftar Ernie: Ernie

Daftar Frank: Adam, Bert

Gambarkan sebuah graf berarah yang memodelkan situasi ini.

Jawab : Graf yang memodelkan situasi tersebut adalah sebagai berikut.

3. Ada dua belas tim basket wanita di Atlantic Coast Conference: Boston College (B), Clemson (C), Duke (D), Florida State (F), Georgia Tech (G), Miami (I), NC State (S), University of Maryland (M), University of North Carolina (N), University of Virginia (V), Virginia Tech (T), dan Wake Forest University (W). Pada suatu titik di pertengahan musim,

B sudah bertanding dengan I, T*, W

C sudah bertanding dengan D*, G

D sudah bertanding dengan C*, S, W

F sudah bertanding dengan N*, V

G sudah bertanding dengan C, M

I sudah bertanding dengan B, M, T

S sudah bertanding dengan D, V*

M sudah bertanding dengan G, I, N

N sudah bertanding dengan F*, M, W

V sudah bertanding dengan F, S*

T sudah bertanding dengan B*, I

W sudah bertanding dengan B, D, N

Tanda bintang (*) menunjukkan bahwa kedua tim ini telah bertanding dua kali. Gambarlah multigraf yang memodelkan situasi ini.

Jawab : Graf yang memodelkan situasi tersebut adalah sebagai berikut.

4. Dapatkah Anda menjelaskan mengapa tidak ada penduduk Konigsberg yang mampu berjalan pada rute yang melewati setiap jembatan tepat satu kali?

5. Jika $G$ merupakan graf berorde $n$, berapakah banyak sisi maksimum pada $G$?

Jawab : Agar banyak sisi maksimum maka setiap simpulnya harus bertetangga dengan simpul lainnya yang artinya derajat setiap simpulnya adalah $n-1$. Dengan menggunakan teorema jabat tangan, kita peroleh bahwa $n(n-1)=2|E|$ atau $|E|=\frac{n(n-1)}{2}$. Jadi, berapakah banyak sisi maksimum pada $G$ adalah $\frac{n(n-1)}{2}$.

6. Buktikan bahwa untuk setiap graf $G$ berorde paling sedikitnya $2$, barisan derajat mempunyai paling sedikit satu pasang entri yang berulang.

Jawab : Misalkan graf $G$ berorde $n$ dengan $n\geq 2$. Andaikan bahwa tidak ada sepasang entri pada barisan derajat yang berulang, artinya derajat setiap simpulnya berbeda. Dapat kita lihat bahwa barisan derajat dalam hal ini tidak lain adalah $n-1,n-2,\cdots ,1,0$. Jelas hal ini tidak mungkin karena ada simpul berderajat $n-1$ dan ada simpul berderajat $0$. (Kontradiksi). Jadi, bisa disimpulkan bahwa untuk setiap graf $G$ berorde paling sedikitnya $2$, barisan derajat mempunyai paling sedikit satu pasang entri yang berulang.

7. Perhatikan gambar graf berikut.

a. Berapa banyak lintasan berbeda dimana $c$ sebagai simpul ujungnya?

Jawab : Banyak lintasan berbeda yang dimaksud panjang $5$ adalah $C(4,4)\times 4!=24$, Banyak lintasan berbeda yang dimaksud panjang $4$ adalah $C(4,3)\times 3!=24$, Banyak lintasan berbeda yang dimaksud panjang $3$ adalah $C(4,2)\times 2!=12$. Jadi, banyak lintasan berbeda dimana $c$ sebagai simpul akhirnya adalah $24+24+12=60$.

b. Berapa banyak lintasan berbeda yang menghindari simpul $c$ secara keseluruhan?

Jawab : Banyak lintasan berbeda yang dimaksud panjang $4$ (siklus) adalah $4!=24$. Banyak lintasan berbeda yang dimaksud panjang $3$ adalah $C(4,4)\times 4!=24$, Banyak lintasan berbeda yang dimaksud panjang $3$ adalah $C(4,3)\times 3!=24$, Banyak lintasan berbeda yang dimaksud panjang $2$ adalah $C(4,2)\times 2!=12$, Banyak lintasan berbeda yang dimaksud panjang $1$ adalah $C(4,1)\times 1!=4$, Banyak lintasan berbeda yang dimaksud panjang $0$ adalah $C(4,0)\times 0!=1$. Jadi, banyak lintasan berbeda dimana $c$ sebagai simpul akhirnya adalah $24+24+24+12+4+1=89$.

c. Berapa panjang maksimum suatu sirkuit pada graf tersebut? Berikan contoh sirkuit yang semacam itu.

Jawab : $10$. Contoh nya adalah $dacebdeabcd$.

d. Berapa panjang maksimum suatu sirkuit yang tidak memiliki simpul c? Berikan contoh sirkuit tersebut.

Jawab : $4$. Contoh nya adalah $abdea$.

8. Benarkah bahwa suatu graf berhingga yang memiliki tepat dua simpul berderajat ganjil harus memuat suatu lintasan dari satu simpul ke simpul lainnya? Berikan bukti atau contoh penyangkal.

Jawab : Benar. Misalkan $G$ adalah graf berhingga yang memiliki tepat dua simpul sebutlah $v_1$ dan $v_2$ berderajat ganjil. Jika $G$ graf terhubung maka pastilah ada jalan dari $v_1$ ke $v_2$ sehingga menurut teorema terdapat lintasan yang menghubungkan $v_1$ dan $v_2$. Jadi, kita asumsikan bahwa $G$ graf tak terhubung. Misalkan $H$ adalah komponen terhubung dari $G$ yang mengandung $v_1$. Menurut akibat teorema jabat tangan terdapat sebanyak genap simpul yang berderajat ganjil pada suatu graf. Maka dari itu pada graf $H$, karena $v_1$ berderajat ganjil, haruslah $v_2$ juga berada di $H$. Jadi, terdapat lintasan dari $v_1$ ke $v_2$.

9. Misalkan $G$ suatu graf dimana $\delta(G)\geq k$.

a. Buktikan bahwa $G$ mempunyai suatu lintasan yang panjangnya setidaknya $k$?

b. Jika $k\geq 2$, buktikan bahwa $G$ mempunyai suatu siklus yang panjangnya setidaknya $k+1$.

10. Buktikan bahwa setiap jalan ganjil tertutup dalam suatu graf mengandung siklus ganjil.

Jawab : Kita akan buktikan dengan menggunakan induksi matematika. Misalkan kita punya jalan ganjil tertutup dengan panjang $k$. Untuk $k=1$, sisi tersebut merupakan suatu loop. Jadi, merupakan suatu siklus ganjil. Kita assumsikan bahwa setiap jalan ganjil dengan panjang kurang dari atau sama dengan $k=2r-1$ mengandung siklus ganjil. Sekarang mari kita pertimbangkan jalan tertutup $u=v_0,e_1,v_1,e_2,\cdots ,e_{2r+1},v_{2r+1}=v$ dengan panjang $2r+1$. Jika lintasan tidak memiliki simpul yang berulang, maka lintasan tersebut merupakan siklus ganjil menurut definisinya. Jika tidak, katakanlah $v_i = v_j$ untuk $0 \leq i <j \leq 2r + 1$. Lintasan tersebut dapat dibagi menjadi dua lintasan tertutup:

$v_0,\cdots ,v_i=v_j,\cdots ,v_{k+1}$

$v_i,\cdots ,e_{i+1},\cdots ,v_j$

Salah satu darinya harus memiliki panjang ganjil kurang dari atau sama dengan $2r-1$. Berdasarkan hipotesis induksi, mereka mengandung siklus ganjil.

11. Gambarkan sebuah graf terhubung yang mempunyai paling banyak $10$ simpul, yang mempunyai paling sedikit satu siklus dengan panjang masing-masing dari $5$ sampai $9$, tetapi tidak mempunyai siklus dengan panjang lainnya.

12. Misalkan $P_1$ dan $P_2$ merupakan dua lintasan dengan panjang maksimum pada graf terhubung $G$. Buktikan bahwa $P_1$ dan $P_2$ mempunyai simpul ujung yang sama.

13. Misalkan $G$ adalah graf berorde $n$ yang tidak terhubung. Berapa ukuran maksimum dari $G$?

Jawab : Andaikan $G$ terhubung berorde $n$, ukuran maksimum dari $G$ diperoleh ketika $G$ graf lengkap. Ukuran maksimum $G$ yaitu $C(n,2)=\frac{n(n-1)}{2}$. Untuk $G$ tidak terhubung ukuran maksimum dari $G$ adalah $\frac{(n-1)(n-2)}{2}$

14. Misalkan $G$ adalah suatu graf berorde $n$ dan berukuran lebih kecil dari $n-1$. Buktikan bahwa $G$ tidak terhubung.

15. Buktikan bahwa sisi $e$ merupakan jembatan dari $G$ jika dan hanya jika $e$ tidak terletak pada siklus $G$.

16. Buktikan atau sangkal pernyataan berikut.

a. Jika $G$ tidak memiliki jembatan, maka $G$ memiliki tepat satu siklus.

b. Jika $G$ tidak mempunyai simpul pemotong, maka $G$ tidak memiliki jembatan.

c. Jika $G$ tidak mempunyai jembatan, maka $G$ tidak memiliki simpul pemotong.

17. Buktikan atau sangkal : Jika setiap simpul dari suatu graf terhubung $G$ terletak pada paling sedikit satu siklus, maka $G$ adalah graf $2-$terhubung.

18. Buktikan bahwa setiap graf $2-$terhubung mengandung setidaknya satu siklus.

19. Buktikan bahwa untuk setiap graf $G$,

a. $\kappa (G)\leq \delta (G)$;

b. Jika $\delta (G)\geq n-2$, maka $\kappa (G)=\delta (G)$.

20. Misalkan $G$ graf berorde $n$.

a. Jika $\delta (G)\geq \frac{n-1}{2}$, maka buktikan bahwa $G$ terhubung.

b. Jika $\delta (G)\geq \frac{n-2}{2}$, maka tunjukkan bahwa $G$ tidak perlu dihubungkan.

21. Untuk $n\geq 1$, buktikan bahwa $K_n$ mempunyai $n(n-1)/2$ sisi.

22. Jika $K_{r_1,r_2}$ adalah graf regular, buktikan bahwa $r_1=r_2$.

23. Tentukan apakah $K_4$ merupakan subgraf dari $K_{4,4}$. Jika ya, tunjukkan. Jika tidak, jelaskan alasannya.

24. Tentukan apakah $P_4$ merupakan subgraf terinduksi dari $K_{4,4}$. Jika ya, tunjukkan. Jika tidak, jelaskan alasannya.

25. Daftarkan semua subgraf terhubung yang tidak berlabel dari $C_{34}$.

26. Konsep graf bipartit lengkap dapat digeneralisasi untuk mendefinisikan graf multipartit lengkap $K_{r_1,r_2,\cdots,r_k}$. Graf ini terdiri dari $k$ himpunan simpul $A_1, A_2, \cdots, A_k$, dengan $|A_i| = r_i$ untuk setiap $i$, di mana semua kemungkinan "sisi interset" ada dan tidak ada "sisi intraset". Temukan ekspresi untuk orde dan ukuran $K_{r_1,r_2,\cdots,r_k}$.

27. Graf garis $L(G)$ pada graf $G$ didefinisikan sebagai berikut: simpul pada $L(G)$ merupakan sisi $G$, $V(L(G))=E(G)$, dan dua simpul pada $L(G)$ bertetangga jika dan hanya jika sisi-sisi yang bersesuaian pada $G$ bersisian dengan simpul yang sama.

a. Misalkan $G$ adalah graf yang ditunjukan pada gambar berikut. Tentukan $L(G)$.

b. Tentukan komplemen dari $L(K_5)$.

c. Misalkan $G$ memiliki $n$ simpul, dengan label $v_1,\cdots, v_n$, dan derajat simpul $v_i$ adalah $r_i$. Misalkan $m$ menyatakan ukuran $G$, jadi $r_1 + r_2 + \cdots+ r_n = 2m$. Temukan rumus untuk orde dan ukuran $L(G)$ (dalam $n$, $m$, dan $r_i$).

28. Buktikan bahwa jika graf $G$ dan $H$ isomorfik, maka komplemennya $\overline{G}$ dan $\overline{H}$ juga isomorfik.

29. Buktikan bahwa dua graf gambar berikut tidak isomorfik.