3.1 Beberapa Nilai Dimensi Partisi pada Suatu Graf. Dalam dimensi partisi suatu graf, terdapat kelas graf yang nilai dimensi partisinya

BAB III Dimensi Partisi n-1

BAB III DIMENSI PARTISI n − 1

3.1

Beberapa Nilai Dimensi Partisi pada Suatu Graf

Dalam dimensi partisi suatu graf, terdapat kelas graf yang nilai dimensi partisinya cukup mudah atau sederhana. Kelas graf tersebut diantaranya adalah Pn, Kn, Cn. Dalam tugas akhir ini, penulis tidak akan membahas semua kelas graf tersebut namun hanya beberapa kelas graf saja yang berkaitan dengan dimensi partisi n − 1. Pembahasan ini akan mempermudah mengkajian dimensi partisi n − 1.

Cukup mudah untuk mengetahui bahwa 2 ≤ pd(G) ≤ n adalah kisaran untuk suatu G graf terhubung dengan n ≥ 2 titik. Lebih khusus, ternyata untuk G dengan n ≥ 2 titik, terdapat satu kelas graf khusus dengan n titik yang dimensi partisinya bernilai 2. Proposisi 2 ( Chartrand, Zhang, Salehi 2000 [3] ) : Misalkan G graf terhubung dengan n ≥ 2 titik. Maka pd(G) = 2 jika dan hanya jika G = Pn. Bukti :

⇒ Misalkan Pn = v0v1v2...vn, pilih Π = {S1, S2} adalah partisi V(Pn) dengan S1 = {v1} dan S2 = {v2, v3,…, vn}. Perhatikan r(v1| Π ) = (0, 1) dan r(vi| Π ) = (i − 1, 0) untuk 2 ≤ i ≤ n, sehingga Π adalah resolving partition dari Pn. Jadi pd(Pn) = 2.

Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

16


⇐ Misalkan Π = {S1, S2} adalah resolving partition dari V(G) dengan n titik. G terhubung maka terdapat titik u ∈ S1 dan v ∈ S2 yang bertetangga. Karena koordinat r(w| Π ) = (0, d(w, S2)), untuk w ∈ S1 dan r(w| Π ) = (d(w, S1),0), untuk w ∈ S2 berbeda maka untuk setiap titik di S1 hanya titik u yang bertetangga dengan satu titik di S2 dan untuk setiap titik di S2 hanya titik v yang bertetangga dengan satu titik di S1.

Akan ditunjukkan 〈S1〉 dan 〈S2〉 merupakan lintasan di G. Karena G graf terhubung, jika S1 − {u} ≠ ∅ maka setiap titik di S1 bertetangga dengan minimal satu titik di S1. Lebih lanjut, titik u bertetangga maksimal satu titik di S1 karena jika u bertetangga dengan dua titik u1, u2 ∈ S1 maka r(u1| Π ) = r(u2| Π ) = (0,2) kontradiksi dengan Π adalah resolving partition dari V(G). Misalkan w adalah titik yang bertetangga dengan u di S1. Sama seperti langkah sebelumnya, titik w bertetangga maksimal satu titik di S1 yang berbeda dengan titik u. Lanjutkan langkah diatas maka dapat kita lihat bahwa 〈S1〉 adalah lintasan di G. Dengan cara yang sama, 〈S2〉 adalah lintasan di G. Jadi G adalah lintasan.

Lebih jauh, setelah tadi mengetahui kelas graf dengan dimensi partisinya bernilai 2, terdapat satu kelas graf khusus lain dengan n titik yang dimensi partisinya bernilai n. Sebelum penulis membahas hal tersebut, akan dibahas terlebih dahulu lemma berikut untuk membantu pemahaman. Lemma 3 ( Chartrand, Zhang, Salehi 2000 [4] ) : Misalkan Π adalah resolving partition dari V(G) dan u, v ∈ V(G). Jika d(u, w) = d(v, w), untuk setiap w ∈ V(G) − {u, v} maka u dan v berada pada partisi yang berbeda di Π . Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

17


Bukti : Misalkan Π = {S1, S2,…, Sk} dengan u dan v berada pada partisi yang sama, misal : Si dari Π , maka d(u, Si) = d(v, Si) = 0. Karena d(u, w) = d(v, w), untuk setiap w ∈ V(G) − {u, v} maka d(u, Sj) = d(v, Sj), untuk setiap j dimana 1 ≤ j ≠ i ≤ k. Jadi r(u| Π ) = r(v| Π ) sehingga Π bukan resolving partition.

Lemma diatas cukup mudah untuk dipahami, sekarang pembahasan mengenai dimensi partisi bernilai n. Proposisi 4 ( Chartrand, Zhang, Salehi 2000 [4] ) : Misalkan G graf terhubung dengan n titik. Maka pd(G) = n jika dan hanya jika G = Kn. Bukti :

⇒ Banyaknya partisi maksimal untuk graf terhubung dengan n titik adalah n buah. Jadi pd(Kn) ≤ n. Berdasarkan Lemma 3, pd(Kn) ≥ n. Jadi, pd(Kn) = n.

⇐ Misalkan G graf terhubung dengan n titik yang mempunyai pd(G) = n, dimana V(G) = {v1, v2,..., vn}. Akan dibuktikan dengan kontraposisi. Misalkan G ≠ Kn maka diameter G ≥ 2. Akan ditunjukkan pd(G) ≤ n − 1. Asumsikan d(v1, vn) = 1 dan d(vn − 1,

vn) = 2. Misalkan Π = {S1, S2,…, Sn − 1} merupakan partisi dari V(G), dengan S1 =

{v1, vn} dan Si = {vi} untuk 2 ≤ i ≤ n − 1. Untuk setiap i dimana 1 ≤ i ≤ n − 1, hanya kolom ke-i dari r(vi| Π ) bernilai 0. Jadi koordinat r(vi| Π ), untuk 1 ≤ i ≤ n − 1 berbeda.


18


Untuk vn, kolom ke-1 dari r(vn| Π ) bernilai 0, maka r(vn| Π ) berbeda dengan r(vi| Π ), untuk 2 ≤ i ≤ n − 1. Selain itu, kolom ke-(n − 1) dari r(vn| Π ) bernilai 2 sedangkan kolom ke-(n − 1) dari r(v1| Π ) bernilai 1 sehingga r(vn| Π ) ≠ r(v1| Π ). Jadi Π adalah resolving partition dari G dengan pd(G) ≤ n − 1.

Setelah membahas kelas graf Pn dan Kn, kali ini penulis akan membahas graf bipartit terhubung. Teorema 5 ( Chartrand, Zhang, Salehi 2000 [5] ) : Misalkan G graf bipartit terhubung dengan partisi V1 dan V2 yang kardinalitas masing-masing p dan q. Dengan demikian, 1. Jika p = q maka pd(G) ≤ p + 1, dan 2. Jika p ≠ q maka pd(G) ≤ maks{p, q}

Bukti : Misalkan G bipartit terhubung dengan partisi V1 dan V2 dimana |V1| = p dan |V2| = q. Bagi menjadi 2 kasus : 1. p = q,

Gambar 10 Salah satu cara mencari resolving partition


19


Misalkan V(G) = { u1, u2,..., up ,v1, v2,..., vq}. Misalkan Π = {S1, S2,…, Sp, Sp + 1} partisi dari V(G),dengan Si = {ui, vi}, untuk 1 ≤ i ≤ p − 1, Sp = {up}, dan Sp

+ 1

= {vq}. Karena dua titik dengan partisi yang berbeda pasti

mempunyai koordinat yang berbeda pula, maka cukup memeriksa koordinat r(ui| Π ) dengan r(vi| Π ), untuk 1 ≤ i ≤ p − 1. Perhatikan bahwa, d(ui, up) selalu genap sedangkan d(vi, up) selalu ganjil sehingga koordinat r(ui| Π ) dengan r(vi| Π ), untuk 1 ≤ i ≤ p − 1 berbeda. Jadi, pd(G) ≤ p + 1.

2. p ≠ q, tanpa mengurangi perumuman, misal : p > q

Gambar 11 Salah satu cara mencari resolving partition

Akan dibuktikan pd(G) ≤ p. Misal Π = {S1, S2,…, Sp}, dengan Si = {ui, vi}, untuk 1 ≤ i ≤ q, Si = {ui}, untuk q + 1 ≤ i ≤ p. Serupa dengan sebelumnya cukup memeriksa r(ui| Π ) dengan r(vi| Π ), untuk 1 ≤ i ≤ q. Perhatikan bahwa, d(ui, up) selalu genap sedangkan d(vi, up) selalu ganjil sehingga koordinat r(ui| Π ) dengan r(vi| Π ), untuk 1 ≤ i ≤ q berbeda. Jadi, pd(G) ≤ p.


20


Lebih khusus, jika G graf bipartit lengkap maka 1. pd(G) = p + 1, untuk p = q, dan 2. pd(G) = maks{p, q}, untuk p ≠ q

Bukti : 1. p = q, Cukup dibuktikan pd(G) ≥ p + 1. Berdasarkan lemma 3, u1, u2,..., up berada pada partisi berbeda. Begitu pula dengan v1, v2,..., vq. Sehingga pd(G) ≥ p. Misalkan Π 1 merupakan resolving partition dari Kp,q dengan Π 1 = {S1, S2,…, Sp}. Haruslah setiap partisi beranggotakan satu titik di V1 dan V2. tanpa mengurangi perumuman, misalkan Si = {ui, vi}, untuk 1 ≤ i ≤ p. Perhatikan bahwa koordinat r(ui| Π 1) = r(vi| Π 1), untuk 1 ≤ i ≤ p pada kolom ke-i bernilai 0 sedangkan lainnya bernilai 1. Kontradiksi dengan Π 1 merupakan resolving partition. Jadi, pd(G) ≥ p + 1 sehingga pd(G) = p + 1. 2. p ≠ q, tanpa mengurangi perumuman, misal : p > q Cukup dibuktikan pd(G) ≥ p. Berdasarkan lemma 3, u1, u2,..., up berada pada partisi berbeda. Maka pd(G) ≥ p. Jadi, pd(G) = p.

Kelas graf G dengan n titik dikatakan berkarakteristik jika kelas graf G tersebut mempunyai dimensi partisi tertentu dan dimensi partisi tersebut hanya dipenuhi oleh kelas graf G. Setelah membahas kelas graf diatas kita dapat melihat bahwa Pn dan Kn dikatakan berkarakteristik. Sedangkan Kp,q tidak berkarakteristik.


21


3.2

Graf dengan Dimensi Partisi n − 1

Pada bagian ini, penulis akan membahas mengenai dimensi partisi n − 1. Penulis akan mengkaji bagaimana mencari semua kelas graf dengan n titik yang mempunyai dimensi partisi n − 1. Pertama-tama penulis akan membahas batas bawah dan batas atas dimensi partisi untuk graf dengan n titik yang telah diketahui diameternya. Untuk suatu n bilangan bulat positif dan d dengan n > d ≥ 2, kita definisikan g(n, d) sebagai minimum k yang memenuhi pertidaksamaan (d + 1)k ≥ n.

Teorema 6 ( Chartrand, Zhang, Salehi 2000 [5] ) : Jika G graf terhubung dengan n ≥ 3 titik dan d adalah diameter G maka g(n, d) ≤ pd(G) ≤ n − d + 1. Bukti : Untuk batas atas. Misalkan dua titik u dan v di G dengan d(u, v) = d dan (u, v)-path dengan panjang lintasan d adalah v1v2... vd + 1 dimana u = v1 dan v = vd + 1. Misalkan V(G) = {v1, v2,..., vd, vd + 1,..., vn} dan Π = {S1, S2,…, Sn − d + 1} partisi dari V(G) dengan S1 = {v1, v2,..., vd} dan Si = {vi + d − 1} untuk 2 ≤ i ≤ n − d + 1. Kita cukup membandingkan r(v1| Π ), r(v2| Π ), sampai r(vd| Π ). Perhatikan r(vi| Π ) = {0, (−i + d + 1),…} untuk 1 ≤ i ≤ d. Jadi pd(G) ≤ n − d + 1.

Untuk batas bawah. Misalkan pd(G) = k dan Π merupakan resolving partition dari G. Setiap koordinat titik di G terhadap Π mempunyai k buah vektor yang tiap-tiap vektor memuat bilangan non negatif berkisar 0 − d. Perhatikan bahwa banyaknya semua kemungkinan koordinat titik di G adalah (d + 1)k dan semua koordinat titik


22


sebanyak n buah harus berbeda maka haruslah (d + 1)k ≥ n. Dengan pendefinisian g(n, d) diatas maka g(n, d) ≤ k = pd(G).

Setelah pembahasan terorema 6 dapat kita lihat akibat langsung dari teorema tersebut. Akibat 7 ( Chartrand, Zhang, Salehi 2000 [6] ) : Jika G graf terhubung dengan n ≥ 2 titik dan pd(G) = n − 1 maka diameter G = 2. Bukti : Misalkan G graf terhubung dengan n ≥ 2 titik dan pd(G) = n − 1 maka G bukan graf lengkap sehingga diameter G ≥ 2. Tinjau untuk diameter G ≥ 3, menurut teorema 6 maka pd(G) ≤ n − 2, kontradiksi dengan pd(G) = n − 1. Jadi diameter G = 2.

Pembahasan lemma, proposisi, dan teorema diatas akan membantu pembuktian teorema tentang dimensi partisi n − 1 : Teorema 8 ( Chartrand, Zhang, Salehi 2000 [6] ) : Misalkan G graf terhubung dengan n ≥ 3 titik. Maka pd(G) = n − 1 jika dan hanya jika G merupakan salah satu dari kelas graf berikut : K1,n− 1, Kn − e, dan K1 + (K1 ∪ Kn − 2). Bukti :

⇐ ♦ Berdasarkan proposisi 4 maka masing-masing kelas graf K1,n− 1, Kn − e, dan K1 + (K1 ∪ Kn − 2) mempunyai pd(G) ≤ n − 1. ♦ Akan dibuktikan masing-masing kelas graf K1,n− 1, Kn − e, dan K1 + (K1 ∪ Kn − 2) mempunyai pd(G) ≥ n − 1. Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

23


Misalkan G = K1,n− 1,

Pembuktiannya sudah dibahas sebelumnya namun akan dibahas kembali agar lebih memahami pembuktian pada graf Kn − e dan K1 + (K1 ∪ Kn

− 2).

Misalkan V(G) = {v1, v2,..., vn} dan Π merupakan resolving partition dari V(G). Berdasarkan lemma 3, v1, v2,..., vn − 1 berada pada partisi berbeda. Maka pd(G) ≥ n − 1.

Misalkan G = Kn − e, tanpa mengurangi perumuman, misal : e = vn − 1vn

Misalkan V(G) = {v1, v2,..., vn} dan Π 1 merupakan resolving partition dari V(G). Berdasarkan lemma 3, v1,..., vn − 2 berada pada partisi berbeda di Π 1. Begitu pula dengan vn − 1 dan vn. Maka pd(G) ≥ n − 2.


24


Misalkan Π 1 = {S1, S2,…, Sn − 2} merupakan n − 2 buah partisi dari V(G). Maka terdapat Sp, Sq ∈ Π 1 dengan Sq = {vq, vn

− 1}

dan Sp = {vp, vn}.

Perhatikan bahwa r(vq| Π 1) = r(vn − 1| Π 1) yaitu hanya bernilai 0 pada kolom ke-q dan lainnya bernilai 1. Begitu juga, r(vp| Π 1) = r(vn| Π 1) yaitu hanya bernilai 0 pada kolom ke-p dan lainnya bernilai 1. Kontradiksi dengan Π 1 merupakan resolving partition dari V(G). Jadi pd(G) ≥ n − 1.

Misalkan G = K1 + (K1 ∪ Kn − 2),

Gambar 15 Beberapa contoh graf K1 + (K1 ∪ Kn − 2) dengan n = 3,4,5,6


25


Misalkan V(G) = {v1, v2,..., vn} dan Π 1 merupakan resolving partition dari V(G). Berdasarkan lemma 3, v1,..., vn − 2 berada pada partisi berbeda di Π 1. Maka pd(G) ≥ n − 2. Misalkan Π 1 = {S1, S2,…, Sn − 2} merupakan n − 2 buah partisi dari V(G). Bagi menjadi 2 kasus : 1. Terdapat Sp, Sq ∈ Π 1, dengan Sq = {vq, vn − 1} dan Sp = {vp, vn}; Perhatikan bahwa r(vq| Π 1) = r(vn

− 1| Π 1)

yaitu hanya bernilai 0 pada

kolom ke-q dan lainnya bernilai 1. Kontradiksi dengan Π 1 merupakan resolving partition dari V(G). 2. Terdapat Sp ∈ Π 1, dengan Sp = {vp, vn − 1, vn}; Begitu pula dengan kasus ini. Perhatikan bahwa r(vq| Π 1) = r(vn

− 1| Π 1)

yaitu hanya bernilai 0 pada kolom ke-q dan lainnya bernilai 1. Kontradiksi dengan Π 1 merupakan resolving partition dari V(G).

Dari dua kasus diatas, tidak ada Π 1 dengan n-2 partisi V(G) yang mungkin. Jadi pd(G) ≥ n − 1.


26


⇒ Misalkan G graf terhubung dengan n ≥ 3 titik. Akibat langsung teorema 6 maka diameter graf G adalah 2. Pertama, asumsikan G merupakan graf bipartit. Karena diameternya 2, G merupakan graf bipartit lengkap. Jadi G = Kr,s untuk suatu r dan s dengan n = r + s ≥ 3. Tanpa mengurangi perumuman misalkan |r| ≥ |s|. Haruslah |r| = n − 1 karena jika |r| ≤ n − 2 maka pd(G) ≤ n − 2. Kontadiksi dengan pd(G) = n − 1. Jadi G = K1,n− 1.

Kedua, asumsikan G bukan graf bipartit. Misalkan Y adalah maksimum clique di G. Akan ditunjukkan |Y| ≥ 3. Karena G bukan graf bipartit maka terdapat cycle ganjil di G. Misalkan C2l + 1 adalah cycle ganjil terkecil di G. Karena G mempunyai diameter 2 maka C2l + 1 adalah C3 atau C5.

Misalkan C5 = v1v2v3v4v5v1 merupakan cycle ganjil terkecil di G. Misalkan Π = {S1, S2,…, Sn − 2}, dengan S1 = {v1, v2, v3}, S2 = {v4}, S3 = {v5} dan Si untuk 4 ≤ i ≤ n − 2 beranggotakan satu titik dari V(G) − {v1, v2, v3, v4, v5}. Cukup memeriksa r(v1| Π ), r(v2| Π ), dan r(v3| Π ). Perhatikan bahwa r(v1| Π ) = (0, 2, 1,…), r(v2| Π ) = (0, 2, 2,…), dan r(v3| Π ) = (0, 1, 2,…). Jadi Π merupakan resolving partition dengan n − 2 partisi. Kontradiksi dengan pd(G) = n − 1. Haruslah C2l + 1 = C3 maka G memuat K3 sebagai subgraf dari G. Jadi |Y| ≥ 3.

Misalkan U merupakan subgraf G dengan U = V(G) − Y. Graf G bukan graf lengkap maka |U| ≥ 1. Pertama, asumsikan |U| = 1. Maka G = Ks + (K1 ∪ Kt), untuk suatu s, t Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

27


bilangan bulat. Graf G terhubung maka s ≥ 1 dan G bukan graf lengkap maka t ≥ 1. Misalkan V(Ks) = {u1, u2,..., us}, V(Kt) = {v1, v2,..., vt}, dan V(K1) = {w}. Bagi menjadi 2 kasus : 1. s ≥ t, Misalkan Π = {S1, S2,…, Ss + 1}, dengan Si = {ui, vi} untuk 1 ≤ i ≤ t, Si = {ui} untuk t + 1 ≤ i ≤ s, dan Ss + 1 = {w}. Perhatikan bahwa d(u, w) = 1 untuk u ∈ V(Ks) dan d(v, w) = 2 untuk u ∈ V(Kt) maka Π merupakan resolving partition dengan (s + 1) partisi V(G). Maka pd(G) ≤ s + 1.

Menurut Lemma 3 maka pd(G) > s. Lebih lanjut pd(G) ≠ s karena jika pd(G) = s maka s = n − 1 sehingga G = Kn. Kontradiksi dengan G bukan graf lengkap. Maka pd(G) ≥ s + 1. Jadi pd(G) = s + 1. Karena pd(G) = n − 1 maka s = n − 2 dan t = 1. Jadi G = Kn − 2 + (K1 ∪ K1) = Kn − e. 2. s < t, Misalkan Π = {S1, S2,…, St + 1}, dengan Si = {ui, vi} untuk 1 ≤ i ≤ s, Si = {ui} untuk s + 1 ≤ i ≤ t, dan St + 1 = {w}. Perhatikan bahwa d(u, w) = 1 untuk u ∈ V(Ks) dan d(v, w) = 2 untuk u ∈ V(Kt) maka Π merupakan resolving partition dengan (t + 1) partisi V(G). Maka pd(G) ≤ t + 1.

Menurut Lemma 3 maka pd(G) ≥ t. Lebih lanjut pd(G) ≠ t karena jika pd(G) = t maka t = n − 1 dan s = 0 yang berakibat G tidak terhubung. Maka pd(G) ≥ t + 1. Sehingga pd(G) = t + 1. Karena pd(G) = n − 1 maka t = n − 2 dan s = 1. Jadi G = K1 + (K1 ∪ K n − 2). Kajian Kelas Graf yang Mempunyai Dimensi Partisi n-1 dan Penentuan Dimensi Partisi pada Kn − {e1, e2}

28


Sekarang, asumsikan |U| ≥ 2. Akan ditunjukkan terlebih dahulu bahwa U merupakan independent set dari G. Misalkan U bukan independent set dari G maka terdapat dua titik u, w ∈ V(U) yang bertetangga. Karena definisi dari Y maka terdapat v ∈ Y dengan uv ∉ E(G) dan v′ ∈ Y dengan wv′ ∉ E(G) dimana v dan v′ boleh merupakan titik yang sama. Bagi menjadi 2 kasus : 1. Terdapat satu titik v ∈ Y dengan uv, wv ∉ E(G). Bagi menjadi 2 sub kasus : 1.1. Terdapat satu titik x ∈ Y − {v} yang tepat bertetangga dengan satu titik u atau w, tanpa mengurangi perumuman misal u. Karena |Y| ≥ 3 maka terdapat satu titik y ∈ Y yang berbeda dengan titik v dan x. Untuk lebih jelas, graf G memuat subgraf seperti gambar berikut :

Misalkan Π = {S1, S2,…, Sn − 2}, dengan S1 = {u, w, y}, S2 = {x}, S3 = {y}, dan Si untuk 4 ≤ i ≤ n − 2 masing-masing memuat satu titik dari V(G) − {u, w, y, x, v}. Cukup memeriksa r(u| Π ), r(w| Π ), dan r(y| Π ). Perhatikan bahwa r(u| Π ) = (0, 1, 2,…), r(w| Π ) = (0, 2, 2,…), dan r(y| Π ) = (0, 1, 1,…). Jadi Π merupakan resolving partition dari G dengan n − 2 buah partisi. Kontradiksi dengan pd(G) = n − 1.

1.2. Setiap titik di Y − {v} bertetangga dengan dua titik u dan w atau tidak bertetangga dengan dua titik u dan w. Jika u dan w bertetangga dengan


29


semua titik di Y − {v} maka semua titik di (Y − {v}) ∪ {u, w} saling bertetangga,

kontradiksi

dengan

definisi

Y

yang

merupakan

maksimum clique. Oleh sebab itu, terdapat satu titik y ∈ Y yang berbeda dengan titik v, dimana y tidak bertetangga dengan u dan w. Karena diameter G adalah 2 maka terdapat satu titik x di G yang bertetangga dengan u dan v. Untuk lebih jelas, graf G memuat subgraf seperti gambar berikut :

Misalkan Π = {S1, S2,…, Sn − 2}, dengan S1 = {x, y, w}, S2 = {u}, S3 = {v}, dan Si untuk 4 ≤ i ≤ n − 2 masing-masing memuat satu titik dari V(G) − {u, w, y, x, v}. Cukup memeriksa r(x| Π ), r(y| Π ), dan r(w| Π ). Perhatikan bahwa r(x| Π ) = (0, 1, 1,…), r(y| Π ) = (0, 2, 1,…), dan r(w| Π ) = (0, 1, 2,…). Jadi Π merupakan resolving partition dari G dengan n − 2 buah partisi. Kontradiksi dengan pd(G) = n − 1. Jadi kasus 1 tidak dapat memenuhi pd(G) = n − 1.

2. Terdapat dua titik yang berbeda v dan v′ di Y dengan uv, wv′ ∉ E(G). Terlebih, untuk setiap y0 titik di Y, y0 bertetangga minimal dengan salah satu titik u atau w karena jika sebaliknya (terdapat satu titik y0 ∈ Y dengan uy0, wy0 ∉ E(G)) kita mempunyai kondisi seperti kasus 1. Jadi haruslah, vw,


30


v′u ∈ E(G). Karena |Y| ≥ 3 maka terdapat satu titik y ∈ Y yang berbeda dengan titik v dan v′. Sama dengan yang lainnya, minimal salah satu sisi yu atau yw berada di Y, misalkan yu. Untuk lebih jelas, graf G memuat subgraf seperti gambar berikut :

Misalkan Π = {S1, S2,…, Sn − 2}, dengan S1 = {u, w, y}, S2 = {v}, S3 = {v′}, dan Si untuk 4 ≤ i ≤ n − 2 masing-masing memuat satu titik dari V(G) − {u, w, y, v, v′}. Perhatikan bahwa r(u| Π ) = (0, 2, 1,…), r(w| Π ) = (0, 1, 2,…), dan r(y| Π ) = (0, 1, 1,…). Jadi Π merupakan resolving partition dari G dengan n − 2 buah partisi. Kontradiksi dengan pd(G) = n − 1. Jadi, U merupakan independent set.

Kali ini, klaim bahwa N(u) = N(w) untuk setiap u,w ∈ U. Maksudnya adalah jika uv

∈ E(G) maka wv ∈ E(G). Bukti : Misalkan uv ∈ E(G) untuk suatu titik v di G maka jelas v ∈ Y. Akan dibuktikan dengan kontradiksi. Misalkan wv ∉ E(G). Karena Y merupakan himpunan titik dengan maksimum clique maka terdapat satu titik y ∈ Y dimana uy ∉ E(G). Karena graf G terhubung dan U merupakan independent set maka titik w bertetangga dengan suatu titik di Y. Bagi menjadi 2 kasus :


31


1. Titik w bertetangga hanya dengan titik y. Karena w dan y tidak bertetangga dengan u, terlihat bahwa d(w, u) = 3 yang berakibat kontradiksi dengan diameter G adalah 2. 2. Terdapat suatu titik x di Y yang berbeda dengan y dengan wx ∈ E(G). Untuk lebih jelas, graf G memuat subgraf seperti gambar berikut :

Misalkan Π = {S1, S2,…, Sn − 2}, dengan S1 = {u, w, x}, S2 = {v}, S3 = {y}, dan Si untuk 4 ≤ i ≤ n − 2 masing-masing memuat satu titik dari V(G) − {u, w, y, v, x}. Perhatikan bahwa r(u| Π ) = (0, 1, 2,…), r(w| Π ) = (0, 2,…), dan r(x| Π ) = (0, 1, 1,…). Jadi Π merupakan resolving partition dari G dengan n − 2 buah partisi. Kontradiksi dengan pd(G) = n − 1. Jadi N(u) = N(w) untuk setiap u,w ∈ U.

Sampai pembahasan ini, kita dapatkan V(G) = Y ∪ U, dengan G[Y] merupakan graf lengkap, |Y| ≥ 3, U merupakan independent set, |U| ≥ 2, dan N(u) = N(w) untuk setiap u,w ∈ U.

Sekarang, akan ditunjukkan untuk setiap u ∈ U terdapat maksimum satu titik di Y yang tidak termuat di N(u). Misalkan sebaliknya, yaitu terdapat dua buah titik x, y ∈ Y yang tidak termuat di N(u). Misalkan w titik di U yang berbeda dengan u maka


32


jelas bahwa wx, wy ∉ E(G). Karena graf G terhubung maka terdapat titik z ∈ Y dengan z ∈ N(u) = N(w). Untuk lebih jelas, graf G memuat subgraf seperti berikut :

Misalkan Π = {S1, S2,…, Sn − 2}, dengan S1 = {y, z, w}, S2 = {u}, S3 = {x}, dan Si untuk 4 ≤ i ≤ n − 2 masing-masing memuat satu titik dari V(G) − {u, w, y, x, z}. Perhatikan r(y| Π ) = (0, 2, 1,…), r(z| Π ) = (0, 1, 1,…), dan r(w| Π ) = (0, 2, 2,…). Jadi

Π merupakan resolving partition dari G dengan n − 2 buah partisi. Kontradiksi dengan pd(G) = n − 1.

Jadi, N(u) = Y atau N(u) = Y − {v} untuk suatu v ∈ Y. Ternyata kedua bentuk ini dapat dimasukkan kedalam satu kelas G. Jika N(u) = Y maka G = Ks + K t untuk s = |Y| ≥ 3 dan t = |U| ≥ 2. Jika N(u) = Y − {v} maka G = Ks + (K1 ∪ K t) = Ks + K t + 1. Dengan kata lain G = Ks + K t dengan t ≥ 3 dan berakibat s ≤ n − 3. Misalkan V(Ks) = {u1, u2,..., us} dan V(K t) = {v1, v2,..., vt}. Bagi menjadi 3 kasus : 1. s = t, Misalkan Π = {S1, S2,…, Ss + 1}, dengan Si = {ui, vi} untuk 1 ≤ i ≤ s − 1, Ss = {us}, dan Ss

+ 1

= {vs}. Cukup memeriksa koordinat r(ui| Π ) dengan

r(vi| Π ), untuk 1 ≤ i ≤ s − 1. Perhatikan bahwa d(u, vs) = 1 untuk u ∈ V(Ks) dan d(v, vs) = 2 untuk v ∈ V(K t) sehingga r(ui| Π ) ≠ r(vi| Π ). Jadi Π


33


merupakan resolving partition dari G dengan s + 1 buah partisi. Jadi pd(G) ≤ s + 1 ≤ n − 3 + 1 = n − 2. Kontradiksi dengan pd(G) = n − 1. 2. s > t, Misalkan Π = {S1, S2,…, Ss + 1}, dengan Si = {ui, vi} untuk 1 ≤ i ≤ t − 1, Si = {ui} untuk t + 1 ≤ i ≤ s, dan Ss

+ 1

= {vt}. Cukup memeriksa koordinat

r(ui| Π ) dengan r(vi| Π ), untuk 1 ≤ i ≤ t − 1. Perhatikan bahwa d(u, vt) = 1 untuk u ∈ V(Ks) dan d(v, vt) = 2 untuk v ∈ V(K t) sehingga r(ui| Π ) ≠ r(vi| Π ). Jadi Π resolving partition dari G dengan s + 1 buah partisi. Jadi pd(G) ≤ s + 1 ≤ n − 3 + 1 = n − 2. Kontradiksi dengan pd(G) = n − 1. 3. s < t, Misalkan Π = {S1, S2,…, St}, dengan Si = {ui, vi} untuk 1 ≤ i ≤ s, Si = {vi} untuk s + 1 ≤ i ≤ t. Cukup memeriksa koordinat r(ui| Π ) dengan r(vi| Π ), untuk 1 ≤ i ≤ t − 1. Perhatikan bahwa d(u, vt) = 1 untuk u ∈ V(Ks) dan d(v, vt) = 2 untuk v ∈ V(K t) sehingga r(ui| Π ) ≠ r(vi| Π ). Jadi Π merupakan resolving partition dari G dengan t buah partisi. Jadi pd(G) ≤ t ≤ n − 2. Kontradiksi dengan pd(G) = n − 1.

Setelah pembahasan teorema 8 dapat disimpulkan bahwa tidak ada kelas graf selain K1,n− 1, Kn − e, dan K1 + (K1 ∪ Kn − 1) yang mempunyai pd(G) = n − 1. Jadi selain graf Pn dan Kn, kelas graf yang mempunyai pd(G) = n − 1 juga dikatakan berkarakteristik.


34

3.1 Beberapa Nilai Dimensi Partisi pada Suatu Graf. Dalam dimensi partisi suatu graf, terdapat kelas graf yang nilai dimensi partisinya

Recommend Documents