JURNAL ILMIAH SOULMATH (Jurnal Edukasi Matematika)

ISSN 2334-9421

JURNAL ILMIAH “SOULMATH” (Jurnal Edukasi Matematika)

Terbit dua kali setahun pada bulan Januari dan Agustus. Berisi tulisan yang berasal dari hasil penelitian, kajian, atau karya ilmiah di bidang Pendidikan Matematika

Pelindung Dekan Fakultas Keguruan & Ilmu Pendidikan Universitas Dr. Soetomo Surabaya Peninjau Dr. Sukesi, MM

Ketua Penyunting Ahmad Hatip

Penyunting Pelaksana Haerussaleh Sumartono Nuril Huda Ninik Mardiana

Staf Pelaksana Lilik Rusdiana, Warsono, Taufiq

Penerbit Fakultas Keguruan & Ilmu Pendidikan Universitas Dr. Soetomo Surabaya

Alamat Penerbit: Gedung C. 102 Universitas Dr. Soetomo Surabaya Jalan Semolowaru 84 Surabaya 60118 Telp (031) 5944748 ISSN 2334-9421

JURNAL ILMIAH “SOULMATH” (Jurnal Edukasi Matematika)

Volume 4 Nomor 5, Januari 2016 Halaman 217-263

Miftahul Ulum ( SMA Negeri 1 Pasir Belengkong Kalimantan Timur) Pengembangan Perangkat Pembelajaran Matematika Model Learning Cycle 5E Pada Materi Integral Di Kelas XII IPA (hal. 217-231) Viktor Sagala (FKIP, Universitas Dr. Soetomo Surabaya) Profil Lapisan Pemahaman Konsep Turunan Fungsi dan Folding Back Mahasiswa Calon Guru Matematika Berdasarkan Gender (hal. 234-243) Rahmawati Erma Standsyah (FKIP, Universitas Dr. Soetomo Surabaya) Dimensi Metrik Graf Pn O Cm dan Cm O Pn (hal. 244-250) Lusiana Prastiwi, Kristina Yuventa (FKIP, Universitas Dr. Soetomo Surabaya) Penerapan Metode Jalur Kritis Atau Critical Path Method (Cpm) Penentuan Waktu Optimal Dalam Proses Pembuatan Kerajinan Tenun Ikat Tradisional Kupang NTT

(hal 251-256)

Yuni Listiana (FKIP, Universitas Dr. Soetomo Surabaya)

Dimensi Matrik dan Dimensi Partisi pada Graf Hasil Operasi Korona 𝐾𝑛 ⨀𝐾𝑛−1 , 𝑛 ≥ 3

(hal. 257-263)

Jurnal Edukasi Matematika

Vol.4. No.5

Januari 2016

Hal 217-263

ISSN 2334-9421

PETUNJUK BAGI PENULIS 1. Naskah berupa hasil penelitian, kajian atau karya ilmiah yang belum dipublikasikan oleh media cetak lain. Naskah diserahkan dalam bentuk hardcopy dan soft copy. Naskah diketik dengan ukuran kertas A4 dengan program Office Word, spasi 1,5, font Times New Roman 11, dengan jumlah minimal 5 halaman dan maksimal 12 halaman. 2. Sistematika naskah hasil penelitian: a. Judul, nama penulis, lembaga tempat penulis b. Abstrak ditulis dengan bahasa Inggris sebanyak 75-200 kata dan 3-5 kata kunci c. Pendahuluan; latar belakang, masalah, dan tinjauan teori d. Metode dan/atau bahan penelitian e. Hasil dan bahasan f. Simpulan dan saran g. Daftar pustaka 3. Kutipan acuan sumber ditulis dengan nama penulis dan tahun, misalnya: a. Yuwono (2001) telah mengembangkan konsep penelitian sastra lisan...... b. Beberapa penulis (supratno, 2001; Sudikan, 2005) mengatakan bahwa penelitian sastra..... 4. Pustaka Acuan sedapat mungkin ditulis sesuai tata tulis yang baku untuk disiplin ilmu yang mendasari penulisan, misalnya: a. Buku dengan satu penulis: Culler, Jonathan. 2004. Jacques Derrida. Dalam John Sturrock (Ed), Strukturalisme Poststrukturalisme dari Levi-Strauss sampai Derrida (hlm.249-293). Surabaya: JP Press

b. Buku dengan dua penulis atau lebih Wellek, Rene & Austin Warren. 1993. Teori Kesusastraan. Terjemahan oleh Melani Budianta. Jakarta: Gramedia

c. Artikel dalam jurnal profesional Kieran, Carolyn. 1992. The Learning and Teaching of School Algebra. National Council of Teachers of Mathematic. Maxwell Macmillan Canada Inc

d. Artikel dalam harian Panuju, Redi. 19 Desember. Menyoal pemberitaan, Jawa Pos. Hal 5.

-----------------------------------Jurnal Ilmiah Soul Math Vol 4. No. 5, 217-263---------------------------------

DIMENSI MATRIK DAN DIMENSI PARTISI PADA GRAF HASIL OPERASI KORONA

Yuni Listiana FKIP, Universitas Dr. Soetomo Surabaya

Abstract: Let is a connected graph.For an ordered set of vertices, , and a vertex , the representation of with respect to is the ordered ktuple . The set W is called a resolving set of G if every vertex of G has a distinct representation. A resolving set containing a minimum number of vertices is called a basis for . The metric dimension of , denoted by , is the number of vertices in a basis of . Then, for a subset S of V(G), the distance between u and S is . Let be an ordered l-partition of V(G), for dan , the representation of v with respect to is the l-vector . The set is called a resolving partition for G if the vector are distinct. The minimum l for which there is a resolving lpartition of V(G) is the partition dimension of G, denoted by . In this paper, we determine the metric dimension and the partition dimension of corona product graphs , and we get some result that the metric dimension and partition dimension of respectively is and , for . Keyword: Metric dimention, partition dimenstion,corona product graphs

.

Pendahuluan

sebagai

graf bentuk tertentu. Oleh karenanya untuk

,

mendapatkan dimensi metrik bentuk graf

adalah himpunan tidak kosong

tertentu ataupun kelas tertentu dilakukan

Graf pasangan dengan

dapat

didenisikan

himpunan

dan

analisis dari subkelas terlebih dahulu agar lebih

adalah himpunan (boleh kosong) dari

mudah mencari dimensi metrik dari graf secara

elemen yang disebut sisi, selanjutnya untuk

umum [1]. Sedangkan dimensi partisi dari graf

mempermudah pemakaian maka

pertama kali dipelajari oleh Chartrand et. al.

dari

elemen

disingkat

yang

disebut

vertex,

dan

yang kemudian dikuti oleh Chappel et. al [2].

dan . Dalampaper ini, semua

Menemukan hubungan (dalam bentuk

graf yang digunakan adalah berhingga, tidak

dimensi matrik dan dimensi partisi) antara graf

berarah, dan sederhana. kali

asal dan graf yang dihasilkan dari beberapa

dikenalkan oleh Harary dan Melter pada tahun

operasi graf merupakan topik yang menarik

1966, kajian tentang dimensi metrik menjadi

untuk dipertimbangkan. Pada tahun 2010, Yero

sebuah complate problem artinya tidak mudah

et. al. dalam [6] telah meneliti beberapa

untuk mendapatkan dimensi metrik dari suatu

hubungan dari dimensi metrik pada graf hasil

Dimensi

metrik

pertama

korona dengan graf asalnya. Selanjutnya, tahun

257


2011 Iswadi, Baskoro dan Simanjuntak [5] juga

Graf

hasil

korona

melakukan hal serupa untuk kasus yang lebih

merupakan graf hasil korona antara graf

umum. Iswadi menunjukkan bahwa untuk

lengkap

sembarang pasangan

dan

,

,

dan

, maka

,

dengan

jika

,

-1

mengandung vertex dominan. Untuk kasus

dinotasikan

graf dan

dinotasikan

,

partisi dimensi, Baskoro dan Darmaji [2] tahun

lengkap

,

dimana

bilangan bulat positif. Graf hasil korona

2011 juga telah melakukan penelitian pada

adalah

dimensi partisi dari graf-graf hasil operasi

dengan orderdan size

sebagai berikut:

korona. Mereka menunjukkan bahwauntuk semua pasangan graf terhubung

dan

jika

,

diameter

dari H paling besar 2. Dikarenakan penelitian

dari

sebelumnya

beberapa

belum

ada

hasil yang

membahas tentang dimensi metrik dan dimensi Sebagai contoh untuk

partisi pada graf hasil operasi korona antar graf

korona

lengkap, maka dalam paper ini saya akan

pada

graf

hasil

operasi

dapat dilihat pada

Gambar 1.

menganalisis dimensi metrik dan dimensi partisi

, graf hasil

korona

. Graf Hasil Operasi Korona Misalkan dengan

adalah graf terhubung

order

dan

(tidak

terhubung)adalah graf dengan graf

korona

,

harus

. Sebuah

, didefinisikan sebagai

graf yang dibentuk dengan mengambil salinan (copies) graf dan menghubungkan vertex ke

dari

dengan

Seluruh

vertex-vertex

Gambar Graf

dari graf

pada .

Iswadi dkk [5] memperluas ide dari kesamaan

pembahasan pada bab ini, mengacu pada graf sebagai Salinanke pada vertex ke

dari

setiap

.

dari

Misalkan

grafterhubung. Dua vertex

yang terhubung pada

jarak.

untuk

subgraf

dari

samaterhadap

’ jika

semua

258

adalah dan

dikatakan

dalam ‘berjarak untuk

. Sehingga akibat dari


kondisi tersebut muncul fakta sebagai berikut

konstruksi,

untuk graf

pembeda

.

Fakta: Misalkan korona

antara

diambil

himpunan

adalah graf hasil graf

dimana

misalkan

terhubung dengan ,

. Maka dua vertex

berjarak sama terhadap

, maka diperoleh representasi terhadap W

.

sebagai berikut:

Iswadi [5] juga mengungkap sifat jarak dari dua vertex dari

dan

dalam

atau

. Sebuah vertex

dikatakan

dominan vertex jika vertex lainnya dalam Dimensi Metrik

subgraf

untuk vertexatau

Graf

. Operasi Korona

Untuk menentukan dimensi metrik graf korona

dapat dilakukan pencarian

batas atas dan bawah dari dimensi metrik pada graf

korona

dimensi

.Batas

metrik

bawah

pada

dari dapat

ditemukan melalui lemma sebagai berikut: Dapat dilihat bahwa setiap simpul Lemma: Untuk setiap graf sedikitnya salinan ke

,

,

memiliki representasi yang berbeda terhadap

simpulpada setiap simpul dari

,

dengan demikian batas atas

pasti merupakan

.

himpunan himpunanpembeda W. Teorema: Jika graf Dari Lemma di ats diperoleh batas bawah sedikitnya simpul salinan pembeda. memiliki

Oleh

dengan

simpul pada setiap

,

maka dimensi metrik dari

adalah

.

merupakan himpunan karena

salinan

graf

Bukti. Dengan menggunakan Lemma 3.1, yaitu

,

yang terhubung

masing-masing pada setiap vertex dari

paling sedikit

simpuldari

salinan graf

pada

yang

merupakan

maka

himpunan pembeda. Karena

jelas bahwa batas bawah

vertex sebanyak

. Untuk menemukanbatas atas dimensi metrik graf

adalah

bawah

dapat dilakukan melalui

259

mempunyai

, maka jelas bahwa batas .


Sedangkan pada konstruksi sebelumnya

Sehingga Akibat 3.1 sesuai dengan Teorema di

diperoleh representasi yang berbeda pada setiap

atas yang telah dibuktikan sebelumnya.

himpunan vertex terhadap himpunanpembeda, Dari Teorema dan Akibat didapat Akibat

dengan demikian batas atas

berikutnya

. Oleh karenabatas atas dan batas

yang

dapat

digunakansebagai

bentuk umum dari dimensi metrik pada graf

bawah sama, maka

hasil korona graf komplit

.

, dengan

. Dalam paper ini, sengaja tidak dibahas Akibat: Jika graf

mengenai dimensi metrik dari graf untuk

graf

. Hal ini dikarenakan untuk ,

isomorfis

dari

dengan

sehingga

,

,

, dan

. Makadimensi metrik

adalah:

.

Sedangkan untuk

,

merupakan Dimensi

graf trivial. Jika

adalah

adalah

dibandingkan

dengan

Partisi

Graf

Operasi

Korona

hasil Dalam bab ini, akan dibahas mengenai

penelitian sebelumnya oleh Iswadi dkk. [5], dengan teorema berikut:

dimensi partisi dari graf hasil operasikorona

Teorema: Misalkan

pada dua graf lengkap

adalah graf terhubung,

,

adalah graf dengan orderminimal 2. Maka,

dengan

bilangan

,

bulatpositif.

Dimensi Partisi pada graf

didapat

melalui kardinalitasminimum dari himpunan partisi pembeda dari graf

.

Lemma berikut dapat digunakan dalam Bukti: Karena graf lengkap

menentukan batas bawah dari dimensi partisi

dan

.

pada graf operasi korona

adalah graf yang memuat dominan vertex,maka dari Teorema 3.2 akan didapat corollarry

Lemma: Misalkan

(akibat) sebagai berikut:

adalah graf terhubung

non trivial. Misalkan adalah himpunan partisi Akibat: Jika graf

adalah

dan

pembeda untuk

adalah

dan

. Jika

untuk semua

, maka dimensi metrikdari graf , maka

adalah:

dan

berada pada himpunan yang

berbedadi dalam . Misalkan graf adalah

260

,

adalah

dan graf ,

dengan


adalah himpunan vertex dari .

adalah

partisipembeda dari

partisi

himpunan

. Misalkan

n salinan dari

didapat bahwa sedikitnya terdapat

. Kemudian, untuk menemukan batas

atas dimensi partisi graf

sehingga

Selanjutnya,karena

himpunan

.

setiap

,

partisi

pembeda

,

,

rumusan sebagai berikut:

juga memiliki jarak yang

sama, maka berdasarkan Lemma 4.1, juga harus berada pada kelaspartisi yang berbeda di dalam himpunan partisi pembeda dari

, sehingga

Karena vertexnya,

,dihubungkan

,

,

singelton dapat

.

, adalah graf

pada

berada

yang setiap dengan

graf

maka setiap

dan dalam

pada kelas

vertex ,

partisi

, yang

samadalam himpunan partisi pembeda sedemikian hingga singelton

,

Maka diperoleh representasi

memuat beberapa vertex

,

terhadap

. Sehingga

dapat dikatakan bahwa, yang merupakan batas bawah dari dimensi partisigraf menentukan

. Sehingga untuk

partisi

dimensi

dari

graf

, dapat digunakan teorema sebagai berikut: Teorema: Untuk dari graf

dapat

dilakukan melalui konstruksi, misalkan diambil

berbeda dalamhimpunan partisi pembeda dari

dalam graf

pembeda

memiliki

harus berada pada kelas partisi yang

,

partisi

bawah

.Karena

jarak yang sama, maka dengan Lemma 4.1, dan

himpunan

. Sehingga jelas bahwa batas

adalah

,

setiap dua vertex

dalam

kelas

, maka dimensi partisi diberikan sebagai berikut:

Bukti: Dengan menggunakan argumentasi yang dijabarkan sebagai akibat Lemma 4.1,

261

adalah:

dengan


.Sedangkan untuk ,

merupakan graf trivial.

Sebelumnya, disebutkan bahwa Darmaji dkk (2009) telah melakukan penelitian terkait dimensi partisi dari graf hasil operasi korona . Mereka menunjukkan bahwa untuk semua pasangan graf terhubung G an H, jika dari

diameter

paling besar 2. Sedangkan Chartrand

dkk [3] mengungkapkan hanya

jika

jika dan

.

Sehingga

dapat

disimpulkan bahwa:

Sehingga dapat dilihat bahwa setiap vertex dalam

memiliki representasi

yang berbeda terhadap kardinalitas dari

, dengan demikian

adalah

Dari Teorema-teorema di atas maka didapat

. Jadi batas atas dimensi partisi dari

Akibat yang dapat digunakansebagai bentuk

adalah

umum dari dimensi partisi pada graf hasil korona graf komplit

Oleh karena batas atasdan batas bawah

Akibat: Jika graf

sama, maka kardinalitas minimum dari adalah

graf

.Sehingga dimensi partisi dari adalah

adalah

dari

, dengan adalah

,

,

. , dan

. Makadimensi partisi

adalah:

. Sama halnya dengan dimensi metrik, Simpulan

dalam paper ini juga tidak menjelaskan lebih banyak mengenai dimensi partisi pada graf untuk dikarenakan

.

Hal

isomorfis

sehingga dimensi partisi dari

ini

Dari hasil analisis dimensi metrik dan

juga

dengan

dimensi

,

partisi

pada

graf

hasil

korona

didapat kesimpulan sebagai berikut:

adalah

262


1. Dimensi metrik dari graf hasil korona ,

dengan

Darmaji, and E.T. Baskoro, Further results on partition dimension of coronaproducts, AIP Conf. Proc. 1450, 2012, 77-81.

adalah .

G. Chartrand, E. Salehi, dan P. Zhang, The Partition dimension of a graph,Aequantiones Math 59, 2000, 4554.

2. Dimensi metrik dari graf hasil korona ,

dengan

adalah .

G. Chartrand, L. Eroh, M.A. Johnson, and O.R. Oellermann, Resolvabilityin graphs and the metric dimension of a graph, Discrete Appl. Math. 105,2000, pp. 99113.

3. Dimensi partisi dari graf hasil korona ,

dengan

adalah .

4. Dimensi partisi dari graf hasil korona ,

dengan

H.Iswadi, E.T. Baskoro, and R. Simanjuntak, On the metric dimension ofcorona product of graphs, Far East Journal of Mathematical Sciences 52 (2),2011, 155170.

adalah .

Daftar Pustaka I.G. Yero, D. Kuziak, and J.A.Rodr_iguezVel_azquez, On the metric dimension of corona product graphs, Computers & Mathematics with ApplicationsVolume 61, Issue 9, May 2011, Pages 2793-2798.

A.B. Permana, and Darmaji, Dimensi Metrik Graf Pohon Bentuk Tertentu, JURNAL TEKNIK POMITS Vol.1, No.1, 2012, 14.

263

JURNAL ILMIAH SOULMATH (Jurnal Edukasi Matematika)

Recommend Documents