DIMENSI METRIK PADA GRAF TURAN


WAHANA || Jurnal Ilmiah Sains dan Ilmu Pendidikan
Volume 67 || Nomer 2 || Desember 2016 || ISSN: 0853-4403
Penerbit : Lembaga Penelitian dan Pengabdian Kepada Masyarakat Universitas PGRI Adi Buana Surabaya

Penulis  : Ninik Mutianingsih

PDF

Abstrak

Himpunan π‘Š adalah resolving set (himpunan pembeda) dari 𝐺 jika setiap simpul di 𝐺 memiliki representasi tunggal pada π‘Š yang ditentukan oleh jarak dari simpul dari 𝐺 terhadap simpul di π‘Š. Dimensi metrik dari 𝐺 adalah kardinalitas minimum dari resolving set pada 𝐺. Pada paper ini akan dijelaskan tentang dimensi metrik pada graf Turan, yaitu graf multipartisi komplit yang dinotasikan dengan π‘‡π‘˜,𝑛 dengan π‘˜ adalah banyaknya seluruh simpul dari graf dan 𝑛 adalah banyaknya partisi. Dimensi metrik dari graf π‘‡π‘˜,𝑛 dengan π‘˜=𝑛2 adalah π‘‘π‘–π‘š(π‘‡π‘˜,𝑛)=π‘˜βˆ’π‘›. Sedangkan untuk graf Turan yang tidak komplit π‘‡π‘˜,𝑛 yang memiliki order π‘˜βˆ’1 dengan menjaga keterhubungan antara setiap simpul pada semua partisi memiliki dimensi metrik yaitu π‘‘π‘–π‘š(|π‘‡π‘˜,𝑛|=π‘˜βˆ’1)=1.

 

Kata Kunci : dimensi metrik, graf Turan, resolving set

 

Pendahuluan

Teori graf aljabar adalah cabang dari matematika yang mempelajari graf dengan menggunakan sifat-sifat aljabar [1]. Graf satu dengan yang lainnya mempunyai karakter masing-masing sehingga berbeda antara satu sama lain. Salah satu karakter tersebut adalah dimensi metrik. Dimensi metrik pertama kali dikenalkan oleh Harary dan Melter [2]. Dimensi metriks adalah resolving set dari 𝐺 dengan kardinalitas minimum. π‘ŠβŠ†πΊ dikatakan sebagai resolving set dari 𝐺 jika 𝐺 memiliki representasi tunggal pada π‘Š yaitu ditentukan oleh jarak dari simpul-simpul di 𝐺 terhadap simpul-simpul di π‘Š. Banyak penelitian yang sudah dilakukan untuk mengetahui dimensi metrik dari suatu graf. Penelitian tersebut antara lain dilakukan oleh Saputro dkk dengan judul The Metric Dimension of a Complete n-Partite Graphs and Its Products [3] yang meneliti graf 𝑛-partisi komplit dengan operasi cartesian dan corona serta meneliti graf lintasan dan sikel. Ada juga Chartrand dkk dengan Resolvability in Graphs and The Metric Dimension of a Graph [4] pada tahun 2000 yang menghasilkan dim(𝑃𝑛), dim⁑(𝐾𝑛), dan graf-graf yang mempunyai dimensi metriks π‘›βˆ’2, juga oleh Jannesari dkk [9]. Selain itu ada juga penelitian dimensi metrik yang dikenakan pada tree dan graf bintang [2,6,7] yang diteliti oleh Khuller dkk, dan juga oleh Harary, graf Cayley [10] yang diteliti oleh Fehr dkk, pada unicyclic graphs [5] oleh Rodriguez dkk, pada graf bipartisi komplit [8], graf yang memiliki pendan [11] oleh Iswadi dkk, dan pada graf lintasan [12] oleh Fajjria. Pada paper ini akan ditentukan dimensi metrik dari graf Turan yang dinotasikan dengan π‘‡π‘˜,𝑛, yaitu graf multipartisi komplit yang mempunyai simpul total π‘˜ simpul dan di setiap partisinya memiliki simpul sebanyak π‘˜π‘›. Namun pada paper ini penulis membatasi graf Turan yang akan dibahas, yaitu graf Turan yang mempunyai simpul total sebanyak π‘˜ dengan partisi sebanyak 𝑛 namun k terbagi habis dengan 𝑛 sehingga π‘˜=𝑛π‘₯. Dengan kata lain graf π‘‡π‘˜,𝑛 adalah graf multipartisi komplit dengan di setiap partisinya mempunyai jumlah simpul yang sama sebanyak π‘₯ simpul.

Resolving Set dan Dimensi Metrik dari Suatu Graf

Misal 𝐺 adalah graf, 𝑉𝐺 adalah himpunan simpul pada 𝐺 dan 𝐸𝐺 adalah himpunan sisi pada 𝐺. Jarak antara simpul 𝑒,π‘£βˆˆπΊ dinotasikan dengan 𝑑(𝑒,𝑣) yaitu lintasan terpendek yang menghubungkan simpul 𝑒 dan 𝑣 di 𝐺. Misal π‘ŠβŠ†π‘‰πΊ dengan π‘Š={𝑀1,𝑀2,𝑀3,…,𝑀𝑛}, π‘Ÿ(𝑣|π‘Š)=(𝑑(𝑣,𝑀1),𝑑(𝑣,𝑀2),𝑑(𝑣,𝑀3),…,𝑑(𝑣,𝑀𝑛)) adalah representasi 𝑣 relatif terhadap π‘Š dengan π‘£βˆˆπΊ.π‘Š dikatakan sebagai resolving set (himpunan pembeda) dari 𝐺⁑jika representasi simpul di 𝐺 berbeda antara simpul satu dengan simpul yang lainnya. Sedangkan dimensi metrik dari suatu graf yang dinotasikan dengan dim⁑(𝐺) adalah kardinalitas terkecil dari resolving set (himpunan pembeda) π‘Š[4]. Sebagai contoh, [4] misal 𝐺 adalah graf yang diberikan pada gambar 2. Diberikan π‘Š1={𝑣1⁑,𝑣3} bukan resolving set dari 𝐺 karena representasi π‘Š1 pada 𝐺 menghasilkan representasi yang sama, yaitu π‘Ÿ(𝑣2|π‘Š1)=(1,1)=π‘Ÿ(𝑣4|π‘Š1). Sedangkan untuk π‘Š2={𝑣1,𝑣2,𝑣3} adalah resolving set dari 𝐺 karena representasi dari semua simpulΒ di 𝐺 berbeda, yaitu: π‘Ÿ(𝑣1|π‘Š2)=(0,1,1) π‘Ÿ(𝑣2|π‘Š2)=(1,0,1) π‘Ÿ(𝑣3|π‘Š2)=(1,1,0) π‘Ÿ(𝑣4|π‘Š2)=(1,2,1) π‘Ÿ(𝑣5|π‘Š2)=(2,1,1) Berikut adalah gambar graf 𝐺:

 

Meskipun demikian, π‘Š2 bukan dimensi metrik dari 𝐺 karena π‘Š3={𝑣1,𝑣2} juga resolving set dari 𝐺. π‘Ÿ(𝑣1|π‘Š3)=(0,1) π‘Ÿ(𝑣2|π‘Š3)=(1,0) π‘Ÿ(𝑣3|π‘Š3)=(1,1) π‘Ÿ(𝑣4|π‘Š3)=(1,2) π‘Ÿ(𝑣5|π‘Š3)=(2,1) Dari representasi di atas dapat diketahui bahwa representasi dari semua simpul oleh π‘Š3 berbeda. Maka dapat dikatakan bahwa π‘Š3 adalah resolving set dari 𝐺 dengan kardinalitas minimum yaitu 2. Sehingga dimensi metrik dari 𝐺 adalah dim(𝐺)=|π‘Š3|=2.

 

C. Dimensi Metrik dari Graf Turan

Pada paper ini akan ditunjukkan dimensi metrik dari graf Turan yang dinotasikan π‘‡π‘˜,𝑛, namun penulis membatasi graf Turan pada graf Turan yang mempunyai simpul total sebanyak π‘˜ dengan partisi sebanyak 𝑛 namun π‘˜=𝑛2.

Definisi 1. Graf Turan adalah graf multipartisi komplit yang mempunyai simpul total π‘˜ simpul dan di setiap partisinya memiliki simpul sebanyak π‘˜π‘› dengan 𝑛 adalah jumlah partisinya [13].

Lemma 1. 𝐺 adalah graf 𝑛-partisi komplit dengan 𝑛β‰₯2 dan π‘Š adalah resolving set dari 𝐺. Misalkan π‘Šβ€²=πΊβˆ’π‘Š maka π‘Šβ€² memuat paling banyak satu simpul dari setiap partisi. π‘Šβ€² juga memuat palingΒ banyak satu simpul dari semua partisi singleton [3].

Lemma 2. 𝐺 adalah graf 𝑛-partisi komplit dengan 𝑛β‰₯2 . Misalkan π‘Š adalah resolving set dari 𝐺 maka paling banyak satu simpul di 𝐺 yang tidak dimuat oleh π‘Š [3].

Teorema 1. Misalkan π‘‡π‘˜,𝑛⁑ adalah graf Turan dengan π‘˜=𝑛2 dan 𝑛β‰₯2, maka dim(𝐺)=π‘˜βˆ’π‘›

Bukti. Untuk batas bawah dari π‘‡π‘˜,𝑛, dengan menggunakan lemma 2. Misalkan π‘Š adalah resolving set dari 𝐺. Andaikan terdapat dua simpul 𝑣1,𝑣2βˆˆπ‘‰πΊ yang terletak pada satu partisi dengan 𝑣1,𝑣2βˆ‰π‘Š. karena 𝑣1 dan 𝑣2 terhubung dengan simpul yang sama maka π‘Ÿ(𝑣1|π‘Š)=π‘Ÿ(𝑣2|π‘Š). Hal ini tidak mungkin karena akan mengakibatkan representasi yang tidak berbeda sehingga π‘Š bukan resolving set dari 𝐺. Pernyataan ini kontradiksi dengan pernyataan bahwa π‘Š adalah resolving set dari 𝐺, maka haruslah 𝑣1 dan 𝑣2 berada pada partisi yang berbeda. Sehingga jika graf π‘‡π‘˜,𝑛 terpartisi menjadi 𝑛 partisi maka terdapat 𝑛 simpul dari partisi yang berbeda, sehingga jika |𝑉𝐺|=π‘˜ maka dim(𝐺)β‰₯π‘˜βˆ’π‘›. Untuk batas atas misalkan π‘Šβ€²={𝑣1,𝑣2,𝑣3,…,𝑣𝑛} dengan |π‘Šβ€²|=𝑛 adalah satu simpul yang diambil dari partisi yang berbeda, dan π‘Š dapat dikatakan resolving set dari 𝐺, sehingga π‘Š=πΊβˆ’π‘Šβ€². Misal 𝑣1,𝑣2βˆˆπ‘‰πΊ berlaku π‘Ÿ(𝑣1|π‘Š)=π‘Ÿ(𝑣2|π‘Š). Jika 𝑣1 atau 𝑣2⁑di resolving set maka 𝑣1=𝑣2. Namun jika 𝑣1,𝑣2βˆˆπ‘Šβ€² maka 𝑣1 dan 𝑣2 berada pada partisi yang berbeda sehingga akan memiliki representasi yang berbeda karena 𝑑(𝑣1,π‘Šπ‘£2)=𝑑(𝑣2⁑,π‘Šπ‘£1)=1 dan 𝑑(𝑣1,π‘Šπ‘£1)=𝑑(𝑣2,π‘Šπ‘£2)=2 ⁑dengan π‘Šπ‘£1 adalah partisi yang memuat 𝑣1 dan π‘Šπ‘£2 adalah partisi yang memuat 𝑣2. Misal |𝑉𝐺|=π‘˜ sehingga dim(𝐺)β‰€π‘˜βˆ’π‘›. Karena batas bawah dari dim⁑(𝐺)β‰₯π‘˜βˆ’π‘› dan batas atas dari⁑dim(𝐺)β‰€π‘˜βˆ’π‘›, maka dim(𝐺)=π‘˜βˆ’π‘› dengan 𝐺=π‘‡π‘˜,𝑛.

Remarks 1. Teorema 1 diperkuat oleh hasil sebelumnya, yaitu:

dim(𝐺)={|𝑉𝐺|βˆ’1βˆ’(π‘›βˆ’π‘š),π‘“π‘œπ‘Ÿβ‘π‘š>0|𝑉𝐺|βˆ’π‘›,β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘β‘π‘“π‘œπ‘Ÿβ‘π‘š=0⁑

Teorema 2. Graf Turan yang tidak komplit dan mempunyai order |π‘‡π‘˜,𝑛|=π‘˜βˆ’1 dengan menjaga keterhubungan antara setiap simpul pada semua partisi memiliki dimensi metrik yaitu dim(|π‘‡π‘˜,𝑛|=π‘˜βˆ’1)=1.

Bukti. Misalkan 𝑒 dan 𝑣 adalah simpul-simpul pada π‘‡π‘˜,𝑛 yang mempunyai order π‘˜βˆ’1 dan jarak antara 𝑒 dan 𝑣 adalah 𝑑(𝑒,𝑣)=𝑑 dengan 0β‰€π‘‘β‰€π‘˜βˆ’2. Misal 𝑒𝑖=𝑣𝑖 dengan 0β‰€π‘–β‰€π‘˜βˆ’1, untuk 𝑒0βˆˆπ‘Š dan π‘Š=π‘‰πΊβˆ’(π‘’π‘–βˆ’π‘’0). Karena 𝑑(𝑒0,𝑒𝑖)=𝑖 untuk 1β‰€π‘–β‰€π‘˜βˆ’1, maka π‘Š={𝑒0} adalah resolving set dengan minimum kardinalitas yaitu π‘˜βˆ’1βˆ’π‘‘. Karena untuk menghasilkan jarak yang terkecil, maka digunakan 𝑑 maksimal yaitu π‘˜βˆ’2. Sehingga untuk kardinalitas minimum dari π‘Š adalah π‘˜βˆ’1βˆ’π‘‘=π‘˜βˆ’1βˆ’(π‘˜βˆ’2)=π‘˜βˆ’1βˆ’π‘˜+2=1. Sehingga untuk graf π‘‡π‘˜,𝑛 dengan order π‘˜βˆ’1 mempunyai dimensi metrik yaitu dim(|π‘‡π‘˜,𝑛|=π‘˜βˆ’1)=1. Jika graf Turan yang memiliki order π‘˜βˆ’1 dijabarkan, graf tersebut membentuk graf lintasan dengan simpul sebanyak π‘˜ dan order sebanyak π‘˜βˆ’1. Sehingga dapat dikatakan bahwa dimensi metrik dari graf Turan yang memiliki order π‘˜βˆ’1 sama dengan dimensi metrik dari graf lintasan π‘ƒπ‘˜, yaitu dim(|π‘‡π‘˜,𝑛|=π‘˜βˆ’1)=dim(π‘ƒπ‘˜)=1.

Remark 2. Teorema 2 diperkuat oleh hasil sebelumnya, yaitu: a. Jika 𝐺 adalah sebuah graf terhubung dengan order 𝑛β‰₯2 dan diamater 𝑑, maka 𝑓(𝑛,𝑑)≀dim(𝐺)β‰€π‘›βˆ’π‘‘ b. Sebuah graf terhubung 𝐺 dengan order 𝑛 mempunyai dimensi metrik 1 jika dan hanya jika 𝐺=𝑃𝑛.

Corollary 2. Graf Turan yang tidak komplit dan mempunyai order |π‘‡π‘˜,𝑛|=π‘˜ dan juga 𝛿(π‘‡π‘˜,𝑛)=2 memiliki dimensi metrik yaitu dim(π‘‡π‘˜,𝑛)=2.

 

Daftar Pustaka
[1] F.K.N. Sari, Spektrum Adjacency, Spektrum Laplace, dan Spektrum Signless-Laplace Graf Multipartisi Komplit⁑𝐾𝛼1,𝛼2,𝛼3,…,𝛼𝑛, UIN Malang, 2013.

[2] F. Harary, and R.A. Melter, On The Metric Dimension Of A Graph, Ars combin. 2 1076, 191-195.

[3] S.W. Saputro, E.T. Baskoro, A.N.M. Salman, dan D. Suprijanto, the Metric Dimension Of A Complete n-Partite Graphs And Its Products, ITB.

[4] G. Chatrand, L. Eroh., M. A. Johnson, dan O. R Oellermann, Resolvability in Graphs and The Metric Dimension of a Graph, Discrete Appl. Math., 105 (2000), 99-113.

[5] J.A. Rodriguez, I.G. Yero, dan H. Fernau, On The Partition Dimension Of Unicyclic Graphs, preprint, 2013.

[6] S. Khuller, B. Raghavachari, dan A. Rosenveld, Landmarks in Graphs, Discrete Appl. Math., 70 (1996), 217-229.
[7] J. Caceres, D. Garijo, M.L. Puertas, dan c. Seara, On The Determining Number and The Metric Dimension Of Graphs, Discrete Appl. Math., 17 (2010).

[8] M. Baca, E.T. Baskoro, A.N.M. Salman, S.W Saputro, dan D. Suprijanto, The Metric Dimension Of Regular Bipartite Graphs, Bull. Math. Soc. Math. Roumanie Tome, No. 1 (2011) 15-28.

[9] M. Jannesari, dan B. Omoomi, The Metric Dimension Of The Composition Product Of Graphs, Isfahan University.

[10] M. Fehr, S. Gosselin, dan O.R. Oellermann, The Metric Dimension Of Cayley Digraphs, Discrete Math. 306 (2006) 31-41.

[11] I. Iswadi, E.T. Baskoro, R. Simanjuntak, dan A.N.M. Salman, The Metric Dimension Of Graphs with Pendant Edges, J. Combin. Math. Combin. Comput., 65 (2008) 139-145.

[12] I.M.D. Fajjria, Dimensi Metrik Graf Lintasan Tak Hingga, UIN Malang, 2010.

[13] N. Faizah, Spectrum Adjacency, Spectrum Detour dan Spectrum Laplace pada Graf Turan, UIN Malang, 2012.