Bab II Graf dan Operasi graf
Dalam subbab ini akan diberikan konsep dasar, definisi dan notasi pada teori graf yang dipergunakan dalam penulisan disertasi ini. Konsep dasar tersebut ditulis sesuai dengan (Chartrand dan Lesniak, 1996).
II.1
Graf dan subgraf
Graf G(V, E) adalah suatu sistem yang terdiri dari himpunan berhingga tak kosong V = V (G) dan himpunan E = E(G) yang merupakan himpunan pasangan tak terurut {u, v} dengan u, v ∈ V dan u 6= v. Selanjutnya, himpunan V disebut himpunan titik dan himpunan E disebut himpunan sisi dari G. Setiap v ∈ V disebut titik, sedangkan setiap e = {u, v} ∈ E disebut sisi. Sisi e = {u, v} sering ditulis uv. Jika e = uv, maka titik u disebut tetangga dari titik v, dan sebaliknya. Banyaknya titik di G disebut order, sedangkan banyaknya sisi di G disebut ukuran dari G. Graf dengan order satu disebut graf trivial.
Notasi N (u) menyatakan himpunan semua tetangga dari titik u, yakni N (u) = {v|uv ∈ E(G)}. Derajat, dG (v), dari titik v pada graf G adalah banyaknya tetangga dari titik v. Jadi dG (v) = |N (v)|. Suatu titik yang berderajat satu pada suatu graf disebut titik pendan, sedangkan sisi yang menempel pada titik pendan disebut sisi pendan. Titik terisolasi dari suatu graf adalah titik berderajat nol. Derajat minimum, δ(G), dari graf G adalah derajat terkecil dari titik-titik di G. Derajat maksimum, ∆(G), dari graf G adalah derajat terbesar dari titik-titik di G. Pada Gambar II.1 (a), u6 adalah titik pendan dan u7 titik terisolasi. Titik u1 , u3 , u4 dan u5 bertetangga dengan u2 . Jadi N (u2 ) = {u1 , u3 , u4 , u5 } dan |N (u2 )| = 4. Jika semua titik pada graf G berderajat r, maka G disebut graf r-reguler. Graf 3-reguler disebut juga graf kubik, salah satu contohnya dapat dilihat dalam Gambar II.1(b). Dua graf G dan H disebut isomorfik, ditulis dengan G ∼ = H, jika terdapat fungsi bijektif ψ : V (G) → V (H) sedemikian sehingga berlaku uv ∈ E(G) jika dan hanya jika ψ(u)ψ(v) ∈ E(H). Fungsi ψ yang demikian disebut isomorfisma. Pada Gambar
II.2 diberikan graf G1 yang isomorfik dengan G2 . Sebagai contoh, fungsi 6
Gambar II.1. Ketetanggaan pada graf dan graf 3-reguler
ψ : V (G1 ) → V (G2 ) yang didefinisikan dengan ψ(u1 ) = u1 , ψ(u2 ) = u3 , ψ(u3 ) = u5 , ψ(u4 ) = u2 , ψ(u5 ) = u4 , ψ(u6 ) = u6 adalah sebuah isomorfisma. Di pihak lain, G1 tidak isomorfik dengan G3 , karena G3 memuat C3 sedangkan G1 tidak.
Gambar II.2. Graf yang isomorfik dan tidak isomorfik
Graf H disebut subgraf dari graf G, dinotasikan H ⊆ G, jika V (G) ⊆ V (H) dan E(G) ⊆ E(H). Suatu subgraf dari graf G dapat diperoleh dengan menghapus suatu titik atau sisi di G. Misalkan u ∈ V (G) dan |V (G)| ≥ 2, maka G − u adalah subgraf dari graf G dengan V (G − u) = V (G) \ {u} dan E(G − u) = E(G) \ {uv|uv ∈ E(G)}. Misalkan e ∈ E(G), maka G − e adalah suatu subgraf dari graf G dengan V (G − e) = V (G) dan E(G − e) = E(G) \ {e}. Gambar II.3 menunjukkan graf G dan subgrafnya yang diperoleh dengan menghapus suatu sisi atau titik.
Gambar II.3. Graf dan subgrafnya
Jika u dan v tidak bertetangga di G, maka G + uv adalah suatu graf dengan
7
V (G + uv) = V (G) dan E(G + uv) = E(G) ∪ {uv}. Gambar II.4 menunjukkan graf G dan G + uv.
Gambar II.4. Graf G dan G + uv
Jalan W dari titik u ke titik v pada graf G adalah barisan u = u0 , e1 , u1 , e2 , u2 , e3 , . . . , uk−1 , ek , uk = v dari titik-titik dan sisi-sisi pada G sedemikian sehingga ei = ui−1 ui untuk i = 1, 2, . . . , k. Bilangan k (banyaknya sisi) disebut panjang dari W . Pada suatu jalan mungkin terjadi pengulangan titik dan sisi. Jalan W biasanya dituliskan sebagai u0 , u1 , . . . , uk . Selanjutnya, titik u dan titik v disebut titik ujung dari jalan W . Jika semua titik di W berbeda, maka W disebut lintasan. Lintasan dengan n titik dinotasikan sebagai Pn .
Titik u dikatakan terhubung dengan titik v pada graf G jika terdapat suatu lintasan dengan titik u dan v sebagai titik ujungnya. Suatu graf G dikatakan terhubung jika setiap dua titiknya terhubung, sedangkan graf yang tidak demikian disebut tak terhubung. Jarak, d(u, v), antara titik u dan titik v pada suatu graf terhubung G didefinisikan sebagai panjang lintasan terpendek antara u dan v di G.
Subgraf F dari graf G dikatakan terhubung maksimal jika untuk setiap subgraf terhubung H dari G dengan F ⊆ H ⊆ G, maka F = H. Setiap subgraf terhubung maksimal dari suatu graf G disebut komponen dari G. Banyaknya komponen pada suatu graf G dinotasikan dengan k(G). Suatu titik v di graf G didefinisikan sebagai titik potong dari G jika k(G) < k(G−v). Jembatan e dari suatu graf G adalah suatu sisi di E(G) sehingga k(G − e) = k(G) + 1. Graf dengan 4 komponen ditunjukkan dalam Gambar II.5.
Gambar II.5. Graf dengan 4 komponen
Graf tak trivial terhubung yang tidak mempunyai titik potong disebut graf tak ter8
pisahkan (nonseparable). Graf tak trivial yang mempunyai titik potong mempunyai subgraf khusus yang disebut blok. Blok dari suatu graf G adalah subgraf tak terpisahkan maksimal dari G. Sebagai contoh, Gambar II.6 menunjukkan suatu graf dengan 5 blok, titik v3 , v5 dan v8 adalah titik potong, v3 v5 dan v4 v5 adalah jembatan.
Gambar II.6. Graf dengan 5 blok
II.2
Klasifikasi graf
Suatu graf disebut graf lengkap jika setiap dua titiknya bertetangga. Graf lengkap dengan n titik dinotasikan dengan Kn . Graf G(V, E) disebut bipartit jika V (G) dapat dipartisi menjadi dua himpunan V1 dan V2 sedemikian sehingga jika uv ∈ E(G), maka {u, v} * Vi untuk setiap i = 1, 2. Suatu graf bipartit disebut bipartit lengkap, dinotasikan Km,n dengan m = |V1 | dan n = |V2 |, jika setiap titik di V1 bertetangga dengan setiap titik di V2 dan sebaliknya. Graf bipartit lengkap K1,n disebut graf bintang. Gambar II.7 menunjukkan graf lengkap K6 dan graf bipartit lengkap K3,4 .
Gambar II.7. Graf lengkap K6 dan graf bipartit lengkap K3,4
Misalkan m dan n adalah bilangan bulat positif, n ≥ 3 dan 1 ≤ m ≤ b n2 c. Graf Petersen diperumum P (n, m) adalah suatu graf kubik dengan himpunan titik dan himpunan sisi, berturut-turut, V (P (n, m)) = {xi , yi |1 ≤ i ≤ n} 9
dan E(P (n, m)) = {xi xi+1 |1 ≤ i ≤ n} ∪ {xi yi |1 ≤ i ≤ n} ∪ {yi yi+m |1 ≤ i ≤ n} dengan penjumlahan indeks dalam modulo n. Jika m = 1, graf Petersen diperumum P (n, 1) disebut juga graf prisma. Biasanya graf prisma dengan 2n titik dinotasikan dengan Dn . Graf Petersen adalah graf P (5, 2). Graf P (5, 2) dan graf prisma D5 ditunjukkan pada Gambar II.8.
Gambar II.8. Graf Petersen diperumum
Graf siklus Cn adalah graf 2-reguler terhubung dengan n titik. Suatu graf disebut tanpa siklus (acyclic) jika tidak memuat subgraf yang isomorfik dengan graf siklus. Graf tanpa siklus yang terhubung disebut pohon. Graf tanpa siklus G dengan k(G) ≥ 1 disebut hutan. Suatu graf G disebut siklus-tunggal (unicyclic) jika G terhubung dan hanya memuat sebuah graf siklus. Sebagai ilustrasi, perhatikan Gambar II.9.
Gambar II.9. Graf pohon, graf hutan, dan graf siklus-tunggal
Selanjutnya didefinisikan beberapa kelas graf pohon dan graf yang komponennya berupa graf pohon. Lintasan Pn , dapat juga didefinisikan sebagai graf yang diperoleh dari graf siklus Cn dengan menghapus sebuah sisi. Caterpillar adalah suatu graf pohon sedemikian hingga jika semua titik pendannya dihapus diperoleh graf lintasan. 10
Sedangkan, graf lobster adalah suatu graf pohon yang bila semua titik pendannya dihapus akan diperoleh caterpillar. Graf yang setiap komponennya merupakan graf lintasan disebut hutan linier, sedangkan graf yang setiap komponennya adalah graf bintang disebut graf galaksi. Sebagai contoh, perhatikan Gambar II.10.
Gambar II.10. Beberapa graf tanpa siklus
II.3
Operasi pada graf
Misalkan G1 dan G2 adalah dua buah graf sedemikian sehingga V (G1 ) ∩ V (G2 ) = ∅. Gabungan G = G1 ∪ G2 adalah graf dengan V (G) = V (G1 ) ∪ V (G2 ) dan E(G) = E(G1 ) ∪ E(G2 ). Secara umum, jika G1 , G2 , . . . , Gn adalah n buah graf sedemikian sehingga V (Gi ) ∩ V (Gj ) = ∅ untuk i 6= j, maka gabungan G1 ∪ G2 ∪ . . . ∪ Gn = ∪ni=1 Gi ∼ = G adalah graf dengan V (G) = ∪ni=1 V (Gi ) dan E(G) = ∪ni=1 E(Gi ). Jika G1 = G2 = . . . = Gn = H, maka G = ∪ni=1 Gi ditulis G = nH.
Join dari graf G1 dan G2 , dinotasikan dengan G = G1 + G2 , adalah graf G dimana V (G) = V (G1 ) ∪ V (G2 ) dan E(G) = E(G1 ) ∪ E(G2 ) ∪ {uv|u ∈ V (G1 ), v ∈ V (G2 )}. Graf roda Wn adalah join dari Cn dan K1 . Graf pertemanan (friendship graph) C3t 11
adalah join dari K1 dengan tP2 . Graf kipas Fn adalah join dari Pn dan K1 . Graf kipas ganda Fn,2 adalah join dari Pn dan 2K1 (lihat Gambar II.11).
Gambar II.11. Graf yang dihasilkan dari operasi join
Hasil kali graf G1 dan G2 adalah graf G = G1 × G2 yang didefinisikan sebagai berikut: V (G) = V (G1 ) × V (G2 ) dan (x1 , x2 )(y1 , y2 ) ∈ E(G) ⇔ x1 = y1 dan x2 y2 ∈ E(G2 ) atau x2 = y2 dan x1 y1 ∈ E(G1 ). Graf buku Bn didefinisikan sebagai K1,n × P2 . Graf prisma diperumum didefinisikan sebagai Cn × Pm . Graf tangga Ln didefinisikan sebagai Pn × P2 . Graf tangga L4 dan graf buku B4 dapat dilihat pada Gambar II.12.
Gambar II.12. Graf yang dihasilkan dari operasi perkalian
Corona G H dari dua graf G and H didefinisikan sebagai graf yang diperoleh dengan mengambil sebuah duplikat dari graf G dan |V (G)| duplikat H1 , H2 , . . . , H|V (G)| dari H, kemudian menghubungkan titik ke-i dari G ke setiap titik di Hi , i = 1, 2, 3, . . . , |V (G)|. Sebagai contoh, C5 2K1 dan P3 P2 , berturut-turut ditunjukkan Gambar II.13.
12
Gambar II.13. Graf yang dihasilkan dari operasi corona
13
