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

VERSI CETAK/ASLI

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.