BAB II DIMENSI PARTISI

BAB II DIMENSI PARTISI

2.1 Definisi dasar dan keterkaitannya dengan metric dimension Dalam pembahasan dimensi partisi, graf yang dibahas adalah graf terhubung sederhana dan tidak memiliki arah. Sebelum mendefinisikan graf yang digunakan dalam penelitian ini, akan didefinisikan penggabungan dan penjumlahan graf. Misalkan G dan H adalah dua buah graf. Graf G dan H jika himpunan titik V(G

∪

H) = V(G)

} dan himpunan sisi E(G

∪

H) = E(G)

himpunan

+

H)

titik

E(G + H) = E(G)

V(G ∪

E(H)

∪

=

∪

∪

∪

H adalah penggabungan G

V(H), dengan V(G)

∩

V(H) = {

E(H). Graf G + H adalah graf dengan

V(G)

∪

V(H)

dan

himpunan

sisi

{uv | u ∈V(G) dan v ∈V(H)}. Ilustrasi dapat dilihat

pada gambar berikut.

v1

v2

v3

u1

G

u2

u3

H

v1

v2

v3

v1

u1

u2

u3

u1

G∪ H

v2

u2

v3

u3

G+H

Gambar 1 Penggabungan dan Penjumlahan Graf

Dimensi Partisi Graf Kipas dan Graf Kincir

4

Berikut adalah definisi beberapa graf yang digunakan dalam tugas akhir ini. 1. Graf Wheel Dalam teori graf, graf Wheel (Wn) atau graf roda adalah graf hasil tambah K1 + Cn – 1, dimana K1 adalah graf lengkap satu titik dan Cn – 1 adalah graf cycle. Sisi pada graf ini ada dua jenis, yaitu sisi dalam yang merupakan jari-jari dan sisi luar. Titiknya juga ada dua jenis, titik pusat dan titik luar.

W4

W7

W5

W6

W8

W9

Gambar 2 Enam buah graf Wheel pertama

2. Graf Kipas Graf Kipas atau Fan (Fn) adalah graf hasil tambah K1 + Pn – 1. Graf ini memiliki banyak titik n ≥ 4. Graf ini juga dapat dibentuk dari graf Wheel yang dikurangi sebuah sisi luarnya. F4

F6

F5

F7

Gambar 3 Beberapa contoh graf Kipas


5

3. Graf Kincir Graf Kincir adalah graf hasil tambah K1 + nK2. Graf Kincir (Ki) atau sering disebut dengan graf Windmill merupakan graf terhubung n buah batang dengan n ≥ 2. Biasanya n digunakan untuk menyatakan banyaknya titik, tetapi tidak untuk tugas akhir ini. Setiap batang ini memuat 2 titik sehingga graf Ki(n) adalah graf n batang dengan (2n+1) titik. Sebagai contoh, graf kincir dua batang (5 titik), tiga batang (7 titik), dan empat batang (9 titik) dapat dilihat pada gambar berikut.

Gambar 4 Beberapa contoh graf Kincir Di dalam jurnalnya, Gary Chartrand, Ebrahim Salehi, dan Ping Zhang memberikan definisi jarak pada graf. Untuk titik u dan v di graf terhubung G, jarak d(u, v) adalah panjang lintasan terpendek antara u dan v di G. Untuk himpunan terurut W = {w1, w2, …, wk} dari himpunan titik di graf terhubung G dan sebuah titik v di G, k-vektor (k-tuple terurut)

r(v | W) = (d(v, w1 ), d(v, w2 ),...,d(v, wk )) adalah metric representation (koordinat metric) dari v terhadap W. Himpunan W disebut resolving set untuk G jika semua titik di G memiliki koordinat metric yang berbeda. Minimum kardinalitas dari resolving set atau basis dari G disebut metric dimension, yang dinotasikan dengan dim(G). x

u y

v

z Gambar 5


6

Sebagai contoh, graf G pada gambar 7 di atas memiliki basis W = {u, z} sehingga dim(G) = 2. Koordinat untuk semua titik di G terhadap W adalah r(u| W) = (0, 1)

r(u| W) = (2, 1)

r(y| W) = (1, 1)

r(z| W) = (1, 0).

r(x| W) = (1, 2)

Misalkan terdapat sebuah graf terhubung G dengan V(G) adalah himpunan titiktitiknya, S adalah himpunan bagian dari V(G) dan v titik di G, jarak antara v dengan S yang dinotasikan d(v, S) didefinisikan sebagai d (v , S ) = min {d (v , x ) | x ∈ S }.

Misalkan terdapat sebuah graf terhubung G dan k buah partisi Π = {S1, S2,…, Sk} dari V(G) dan v titik di G. Koordinat v terhadap Π didefinisikan sebagai

r(v | Π) = (d(v, S1 ), d(v, S2 ),...,d(v, Sk )) . Partisi Π dikatakan resolving partition jika k-vektor r(v| Π) untuk setiap v

∈V(G),

berbeda. Nilai minimum k agar terdapat resolving k-partition dari V(G) adalah partition dimension dari G atau sering dinotasikan dengan pd(G).Sebagai ilustrasi dari definisi di atas, diberikan contoh berikut. v1

v2

v3

v4

v5 Gambar 6

Misalkan Π1 = {S1, S2}, dengan S1 = {v1, v2, v3} dan S2 = {v4, v5} maka semua koordinat titik di G terhadap Π1 adalah r(v1| Π1) = (0, 1) r(v2| Π1) = (0, 2) r(v3| Π1) = (0, 1) r(v4| Π1) = (1, 0)


7

r(v5| Π1) = (1, 0). Karena r(v1| Π1) = r(v3| Π1) = (0, 1) dan r(v4| Π1) = r(v5| Π1) = (1, 0) maka Π1 bukan resolving partition dari G. Berikutnya, misalkan Π2 = {S1, S2, S3, S4, S5}, dengan S1 = {v1}, S2 = {v2}, S3 = {v3}, S4 = {v4}, dan S5 = {v5} maka semua koordinat titik di G terhadap Π2 adalah r(v1| Π2) = (0, 1, 1, 1, 2) r(v2| Π2) = (1, 0, 2, 2, 3) r(v3| Π2) = (1, 2, 0, 1, 1) r(v4| Π2) = (1, 2, 1, 0, 1) r(v5| Π2) = (2, 3, 1, 1, 0). Karena smua koordinat titik di G terhadap Π2 berbeda maka Π2 merupakan resolving partition dari G. Meskipun demikian, Π2 bukan minimum resolving partition dari G. Untuk menunjukkannya, misalkan Π3 = {S1, S2, S3}, dengan S1={v1, v2}, S2={v3}, dan S3={v4 , v5} maka semua koordinat titik di G terhadap Π3 adalah r(v1| Π3) = (0, 1, 1) r(v2| Π3) = (0, 2, 2) r(v3| Π3) = (1, 0, 1) r(v4| Π3) = (1, 1, 0) r(v5| Π3) = (2, 1, 0). Jadi, Π3 merupakan resolving partition dari G. Lebih lanjut, karena tidak ada 2 partisi dari V(G) yang merupakan resolving partition dari G maka Π3 merupakan minimum resolving partition dari G. Jadi, pd(G) = 3. Partition dimension dan metric dimension saling berhubungan. Hubungan tersebut dapat dilihat pada teorema berikut. Teorema 1. (G. Chartrand, E. Salehi, P. Zhang) Jika G adalah graf terhubung tidak trivial, maka pd (G ) ≤ dim (G ) + 1 .


8

Bukti : Misalkan dim(G) = k dan misal W = {w1, w2, ..., wk} adalah basis dari G. Anggap partisi terurut Π = {S1, S2, ..., Sk+1} dari himpunan titik V(G), dimana Si = {wi} (1 ≤ i ≤ k) dan Sk+1 = V(G) – W. Oleh karena r(v| Π) = (d(v, w1), d(v, w2), ..., d(v, wk), 0) untuk v

∈V(G) – W dan W

adalah resolving set dari G, hal ini mengakibatkan koordinat r(v| Π), untuk v

∈Sk+1, berbeda.

memiliki

elemen

Lebih lanjut, hanya koordinat r(wi| Π), untuk 1 ≤ i ≤ k, ke-i

sama

r(v| Π) ≠ r(wi| Π) untuk semua v Jadi,

Π

adalah

sebuah

dengan

0,

yang

mengakibatkan

∈V(G) – W dan semua i dengan 1 ≤ i ≤ k.

resolving

(k+1)-partition

dari

G

dan

pd (G ) ≤ dim (G ) + 1 . □

Nilai batas atas dari teorema 1 di atas dapat ditemukan pada graf Pn, Cn, Kn, dan K1, k. Penelitian dasar yang mereka lakukan tentang dimensi partisi menghasilkan teorema-teorema untuk graf Pn, Kn, K1,k, dan graf-graf yang berdimensi partisi (n – 1). Untuk lebih jelasnya, dapat dilihat pada subbab berikut.

2.2 Dimensi Partisi Graf Lintasan dan Graf Lengkap Misalkan G adalah graf terhubung orde n ≥ 2 maka 2 ≤ pd(G) ≤ n. Untuk setiap bilangan bulat n ≥ 2, hanya terdapat sebuah graf orde n yang memiliki dimensi partisi 2. Proposisi 1. (G. Chartrand, E. Salehi, P. Zhang) Misal G adalah graf terhubung orde n ≥ 2. Jadi, pd(G) = 2 jika dan hanya jika G = Pn. Bukti : Pertama, misal Pn : v1, v2, ..., vn dan misal Π = {S1, S2} adalah partisi dari V(Pn) dengan S1 = {v1} dan S2 = {v2, v3, ..., vn}. Karena r(v1| Π) = (0, 1,) dan r(vi| Π) = (i - 1, 0) untuk 2 ≤ i ≤ n, berarti Π adalah resolving partition dari Pn sehingga pd(Pn) = 2. Kedua, misal Π = {S1, S2} adalah resolving partition dari sebuah graf G orde n. Karena G terhubung, terdapat ketetanggan titik u v

∈ S2.

Karena koordinat r(w| Π) = (0, d(w, S2)) untuk w


∈ S1 ∈ S1,

dan dan

9

r(w| Π) = (d(w, S1), 0) untuk w

∈S2, berbeda, u adalah titik tunggal di S1

yang bertetangga dengan sebuah titik di S2 dan v adalah titik tunggal di S2 yang bertetangga dengan sebuah titik di S1. Akan ditunjukkan bahwa <S1> dan <S2> adalah lintasan di G. Lebih lanjut, titik u bertetangga dengan paling banyak satu titik di S1. Bila u bertetangga dengan dua titik u1, u2

∈

S1 maka r(u1| Π) = r(u2| Π) = (0, 2), hal ini berkontradiksi dengan Π adalah resolving partition dari V(G). Asumsikan w adalah titik tunggal di S1 yang bertetangga dengan u. w juga bertetangga dengan paling banyak satu titik di S1 yang berbeda dengan u. Dengan melanjutkan proses ini, didapatkan bahwa <S1> adalah lintasan di G. Dengan alasan yang sama, <S2> juga merupakan lintasan di G sehingga G itu sendiri adalah sebuah lintasan. □ Sama halnya dengan hanya terdapat sebuah graf dengan dimensi partisi 2, untuk n ≥ 2 hanya terdapat satu buah graf n titik berdimensi partisi n. Sebelumnya, akan dikonstruksi Lemma berikut. Lemma 1. (G. Chartrand, E. Salehi, P. Zhang) Misal Π resolving partition dari himpunan titik V dan u, v

∈V. Jika d(u, w) = d(v, w) untuk setiap w ∈V – {u, v},

maka u dan v berada pada elemen yang berbeda dalam Π. Bukti : Misal Π = {S1, S2, ..., Sk}, dimana u dan v berada pada elemen yang sama, sebut Si, dalam Π. Maka d(u, Si) = d(v, Si) = 0. Oleh karena d(u, w) = d(v, w) untuk setiap w

∈V – {u, v}, didapat juga bahwa d(u, Sj) = d(v, Sj)

untuk setiap j, dimana 1 ≤ j ≠ i ≤ k. Pada akhirnya, r(u| Π) = r(v| Π) dan Π bukan resolving partition. □ Proposisi 2. (G. Chartrand, E. Salehi, P. Zhang) Misal G adalah graf terhubung orde n ≥ 2. Jadi, pd(G) = n jika dan hanya jika G = Kn. Bukti : Berdasarkan Lemma 1, pd(Kn) = n. Untuk kebalikannya, misal G adalah graf orde n dengan pd(G) = n, dimana V(G) = {v1, v2, ..., vn}. Andaikan G


10

≠ Kn. Dapat diasumsikan bahwa d(v1, vn) = 1 dan d(vn - 1, vn) = 2. Misal Π = {S1, S2, ..., Sn - 1} adalah partisi dari V(G) dengan S1 = {v1, vn} dan Si = {vi} untuk 2 ≤ i ≤ n- 1. Untuk setiap i (1 ≤ i ≤ n – 1), hanya elemen ke- i dari r(vi| Π) yang bernilai 0. Jadi, koordinat r(vi| Π), 1 ≤ i ≤ n – 1, berbeda. Oleh karena elemen pertama r(vn| Π) adalah 0, r(vn| Π) berbeda dari semua r(vi| Π), dimana 2 ≤ i ≤ n – 1. Selain itu, oleh karena elemen ke- (n -1) dari r(vn| Π) adalah 2 dan elemen ke- (n -1) dari r(v1| Π) adalah 1, akibatnya r(vn| Π) ≠ r(v1| Π). Jadi, Π adalah resolving partition dari G dan pd(G) ≤ n – 1, mengakibatkan kontradiksi. □ Berdasarkan Proposisi 1 dan Proposisi 2, semua graf G selain graf Pn dan Kn memiliki 3 ≤ pd(G) ≤ n - 1. Selain kedua graf di atas, Gary Chartrand, Ebrahim Salehi, dan Ping Zhang juga mendapatkan dimensi partisi untuk graf bipartit. Untuk lebih jelas, dapat dilihat pada teorema berikut. Teorema 2. (G. Chartrand, E. Salehi, P. Zhang) Misal G adalah graf bipartit yang terhubung dengan himpunan titik V1 dan V2 berkardinalitas r dan s berturut-turut. Maka (1) pd(G) ≤ r + 1, bila r = s, dan (2) pd(G) ≤ max{r, s}, bila r ≠ s. Lebih lanjut, persamaan (1) atau (2) berlaku, jika dan hanya jika G adalah graf bipartit lengkap. Pada teorema 3 berikut, dimensi partisi (n – 1) hanya dimiliki oleh 3 buah graf. Gary Chartrand, Ebrahim Salehi, dan Ping Zhang memberikan bukti lengkapnya pada jurnal The partition dimension of a graph. Teorema 3. (G. Chartrand, E. Salehi, P. Zhang) Misalkan G adalah graf terhubung dengan orde n ≥ 3. Maka pd(G)= n – 1 jika dan hanya jika G adalah salah satu dari graf K1,n - 1, Kn – e, K1+(K1 ∪ Kn – 1).


11

2.3 Dimensi Partisi Graf Wheel Ioan Tomescu, Imran Javaid dan Slamin memberikan dimensi partisi untuk graf Wheel. Sebelum itu, diperlukan 2 buah Lemma yang mewakili kardinalitas dari partisi yang memuat atau tidak memuat titik pusat sebagai berikut. Lemma 2. (Ioan Tomescu, Imran Javaid, Slamin) Misalkan terdapat graf Wheel (Wn) dengan (n+1) titik dan V(Wn) adalah himpunan dari titik-titiknya. Misal c adalah titik pusat dan Π = {S1, S2, ..., Sk} adalah resolving k-partition dari V(Wn). ⎛ k − 1⎞ ⎛ k − 1⎞ ⎛ k − 1⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ . Jika c ∈S1, maka S1 ≤ 1 + ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠ Bukti : Koordinat titik pusat c adalah r(c| Π) = (0, 1, 1, ..., 1) dan untuk setiap

∈S1 \ {c}, r(v| Π) = (0, ...). Elemen vektor dari koordinat r(v| Π) untuk v ∈S1 \ {c} hanya boleh diisi oleh 1 dan 2 karena diameter graf Kincir

v

adalah 2. Akan tetapi, hanya boleh ada paling banyak 2 elemen yang bernilai 1. Pada akhirnya, hanya terdapat (k – 1) posisi yang hanya boleh diisi oleh paling banyak 2 buah angka 1 dan sisanya dapat diisi oleh angka 2. Jadi, bila ditambahkan dengan koordinat titik pusat, hanya terdapat ⎛ k − 1⎞ ⎛ k − 1⎞ ⎛ k − 1⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ koordinat yg berbeda atau paling banyak ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠ ⎛ k − 1⎞ ⎛ k − 1⎞ ⎛ k − 1⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ . □ S1 ≤ 1 + ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠ Lemma 3. (Ioan Tomescu, Imran Javaid, Slamin) Misalkan terdapat graf Wheel (Wn) dengan (n+1) titik dan V(Wn) adalah himpunan dari titik-titiknya. Misal c adalah titik pusat dan Π = {S1, S2, ..., Sk} adalah resolving k-partition dari V(Wn). ⎛ k − 2⎞ ⎛ k − 2⎞ ⎛ k − 2⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ untuk 2 ≤ i ≤ k. Jika c ∈S1, maka Si ≤ ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠


12

Bukti : Ambil sebuah himpunan selain S1, tanpa mengurangi keumuman, sebut S2 yang tidak memuat titik pusat. Koordinat untuk setiap w

∈ S2

adalah

r(w| Π) = (1, 0, ...). Terdapat (k – 2) posisi di dalam vektor koordinat yang dapat diisi oleh paling banyak 2 buah nilai 1 dan sisanya dapat diisi oleh ⎛ k − 2⎞ ⎛ k − 2⎞ ⎛ k − 2⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ nilai 2. Jadi, hanya terdapat paling banyak ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠ koordinat

yang

berbeda

untuk

setiap

∈

w

S2.

⎛ k − 2⎞ ⎛ k − 2⎞ ⎛ k − 2⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ untuk 2 ≤ i ≤ k. □ Si ≤ ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠ Teorema 4. (Ioan Tomescu, Imran Javaid, Slamin) Untuk setiap titik n ≥ 4 titik,

⎡(2n) ⎤ ≤ pd(W ) ≤ 2⎡n ⎤ + 1 1/ 3

1/ 2

n

Bukti : Batas bawah. Misal terdapat graf Wheel (Wn) dengan (n+1) titik yang memiliki pd[Wn] = k dan Π = {S1, S2, ..., Sk} resolving k-partition dari himpunan titik V(Wn). Misal c adalah titik pusat dan c

∈ S1,

dari

⎛ k − 1⎞ ⎛ k − 1⎞ ⎛ k − 1⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ dan dari Lemma Lemma 2, kita punya S1 ≤ 1 + ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠ 3,

kita

juga

punya

⎛ k − 2⎞ ⎛ k − 2⎞ ⎛ k − 2⎞ ⎟⎟ + ⎜⎜ ⎟⎟ + ⎜⎜ ⎟⎟ Si ≤ ⎜⎜ ⎝ 2 ⎠ ⎝ 1 ⎠ ⎝ 0 ⎠

untuk

2 ≤ i ≤ k. Kita dapat k 2 ⎛ k − 1⎞ 2 ⎛ k − 2⎞ ⎟⎟ + (k − 1)∑i =0 ⎜⎜ ⎟⎟ , akibatnya V (Wn ) = n + 1 = ∑i =1 S i ≤ 1 + ∑i =0 ⎜⎜ ⎝ i ⎠ ⎝ i ⎠

(

)

n ≤ k 3 − 3k 2 + 6k − 2 / 2 < k 3 / 2 untuk setiap k ≥ 2. Jadi, k ≥ ⎡(2n)1/ 3 ⎤. □


13

BAB II DIMENSI PARTISI

Recommend Documents