PENENTUAN DIMENSI METRIK GRAF HELM

PENENTUAN DIMENSI METRIK GRAF HELM

SKRIPSI

Oleh : DIAN FIRMAYASARI S NIM : H 111 08 011

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS HASANUDDIN MAKASSAR 2012

PENENTUAN DIMENSI METRIK GRAF HELM SKRIPSI

Diajukan sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Hasanuddin Makassar

Oleh : DIAN FIRMAYASARI S NIM : H 111 08 011

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS HASANUDDIN MAKASSAR 2012

PERNYATAAN Saya yang bertanda tangan di bawah ini menyatakan dengan sesungguh-sungguhnya bahwa skripsi yang saya buat dengan judul :


adalah benar-benar kerja saya sendiri, bukan hasil plagiat dan belum pernah dipublikasikan dalam bentuk apapun.

Makassar, 21 Mei 2012

DIAN FIRMAYASARI S H111 08 011


SKRIPSI

Oleh :

DIAN FIRMAYASARI S NIM : H 111 08 011

Telah Diperiksa dan Disetujui untuk Diuji : Tanggal : 21 Mei 2012

Pembimbing Utama

Pembimbing Pertama

Dr. Nurdin, M.Si

Dr. Amir Kamal Amir, M.Sc

NIP. 19700807 200003 1 002

NIP. 19680803 199202 1 001

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS HASANUDDIN

Pada hari ini, Senin, tanggal 21 Mei 2012, panitia ujian sidang sarjana menerima dengan baik skripsi yang berjudul :

PENENTUAN DIMENSI METRIK GRAF HELM yang diajukan untuk memenuhi salah satu syarat guna memperoleh gelar Sarjana Sains pada Program Studi Matematika Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Hasanuddin.


Susunan Panitia Ujian Sidang Sarjana

Tanda Tangan

1. Ketua

(………………)

: Prof. Dr. Syamsuddin Toaha, M.Sc NIP. 19680114 199412 1 001

2. Sekretaris

: Hendra, S.Si, M.Si

(………………)

NIP. 19760102 200312 1 001 3. Anggota

: Drs. Muhammad Zakir, M.Si

(………………)

NIP. 19640217 199103 1 004 4. Anggota

: Dr. Nurdin, M.Si

(………………)

(Ex. Officio) NIP. 19700807 200003 1 002 5. Anggota (Ex. Officio)

: Dr. Amir Kamal Amir, M.Sc NIP. 19680803 199202 1 001

(………………)

KATA PENGANTAR Alhamdulillahirobbil’alamiin, puji dan syukur penulis haturkan kehadirat Allah SWT yang telah melimpahkan rahmat dan hidayah-Nya, sehingga penulisan skripsi dengan judul “Penentuan Dimensi Metrik Graf Helm” dapat terselesaikan dengan baik . Salawat dan salam semoga tetap tercurah kepada Rasulullah SAW yang menjadi suri teladan bagi umat islam dalam menjalani hidup yang sesungguhnya. Penulisan skripsi ini dapat terselesaikan berkat bantuan dan motivasi dari berbagai pihak. Oleh karena itu, penulis sampaikan terima kasih kepada: 1. Ayahanda Siala Rahman dan Ibunda St. Puji tercinta yang senantiasa memberikan kasih sayang, doa dan materi kepada penulis dalam menuntut ilmu. 2. Bapak Dr. Nurdin, M.Si dan Bapak Dr. Amir Kamal Amir, M.Sc yang dengan sabar meluangkan waktunya demi memberikan bimbingan, pengarahan, dan saran sehingga penulisan skripsi ini dapat terselesaikan. 3. Bapak Prof. Dr. Syamsuddin Toaha, M.Sc, Bapak Hendra, S.Si, M.Kom dan Bapak Drs. Muhammad Zakir, M.Si selaku penguji sekaligus penasehat akademik, terima kasih atas saran dan kritiknya demi perbaikan skripsi penulis. 4.

Seluruh dosen di Jurusan Matematika FMIPA Universitas Hasanuddin, yang telah mendidik, mengajarkan, membimbing, dan mencurahkan ilmuilmunya kepada penulis.

5.

Kedua adikku Ardy dan Ria serta seluruh keluarga besarku yang selalu memberikan doa, semangat, dan kasih sayang tanpa batas.

6.

Kedua sahabatku Uchi dan Anti yang selalu menemaniku baik suka maupun duka, memberikan doa dan semangat.

7.

Teman-teman seperjuangan di jurusan matematika khususnya angkatan 2008, terima kasih atas rasa persaudaraan dan kebersamaan yang telah diberikan kepada penulis.

8.

Warga Himatika FMIPA Unhas, terima kasih atas ilmu dan pengalaman yang telah diberikan kepada penulis baik melalui pengkaderan maupun kegiatan kampus lainnya.

9.

Semua pihak yang tidak dapat disebutkan satu-persatu, yang telah membantu penulis dalam menyelesaikan penulisan skripsi ini.

Dengan segala kerendahan hati, penulis menerima kritik dan saran demi tercapainya kesempurnaan skripsi ini. Semoga skripsi ini dapat bermanfaat bagi pembaca khususnya bagi penulis. Amin Ya Rabbal Alamin.


Penulis

ABSTRAK

Misalkan

adalah graf terhubung dan

pada graf terhubung . Himpunan setiap titik pada graf

adalah suatu sub himpunan titik

disebut himpunan penentu pada

jika untuk

memiliki representasi jarak yang berbeda terhadap

.

Himpunan penentu dengan banyak anggota minimum disebut himpunan penentu minimum atau basis dari

dan kardinalitas himpunan tersebut menyatakan

dimensi metrik pada graf , dinotasikan dengan Pada skripsi ini dibahas mengenai dimensi metrik graf helm dikontruksi dari graf roda ⌊

yang

. Berdasarkan hasil pembahasan diperoleh bahwa ⌋ untuk

dan

Kata Kunci : Himpunan Penentu, Graf Roda, Graf Helm, Dimensi Metrik.

ABSTRACT

If

is a connected graph and

be a vertices subset on a connected graph .

The set S is called resolving set for

if every vertex on graph

has distinct

representation of . A resolving set containing a minimum number of vertices is called resolving set minimum or basis for

and the cardinality of resolving set is

the metric dimension on graph , denoted by In the thesis discussed about metric dimension of helm graph constructed from graph wheel obtained that

. Based on the discussion of the results ⌊

⌋ for

and

Keyword : Resolving Set, Wheel Graph, Helm Graph, Metric Dimension.

DAFTAR ISI

HALAMAN JUDUL . ......................................................................................

i

HALAMAN PENGAJUAN . ...........................................................................

ii

HALAMAN PERNYATAAN KEASLIAN TULISAN .................................

iii

HALAMAN PERSETUJUAN .........................................................................

iv

HALAMAN PENGESAHAN .........................................................................

v

KATA PENGANTAR .....................................................................................

vi

ABSTRAK . .....................................................................................................

viii

ABSTACT ......................................................................................................

ix

DAFTAR ISI ....................................................................................................

x

DAFTAR GAMBAR .......................................................................................

xii

DAFTAR LAMBANG . ..................................................................................

xiii

BAB I

PENDAHULUAN

1.1 Latar Belakang ................................................................................

1

1.2 Rumusan Masalah ..........................................................................

3

1.3 Batasan Masalah .............................................................................

3

1.4 Tujuan Penulisan ............................................................................

3

1.5 Manfaat Penulisan ................................................................. …….

3

BAB II

TINJAUAN PUSTAKA

2.1 Terminologi Graf ............................................................................

4

2.2 Graf Roda dan Graf Helm .............................................................. .

8

2.3 Dimensi Metrik . ..............................................................................

10

BAB III HASIL DAN PEMBAHASAN 3.1 Graf Helm ......................................................................................

13

3.2 Dimensi Metrik Graf Helm ............................................................

14

BAB IV PENUTUP 4.1 Kesimpulan ......................................................................................

43

4.2 Saran ................................................................................................

43

DAFTAR PUSTAKA .....................................................................................

44

DAFTAR GAMBAR

Gambar 2.1 Graf

dengan 6 titik .................................................................

5

Gambar 2.2 Graf

dengan 4 titik .................................................................

6

Gambar 2.3 Graf

dengan 5 titik .................................................................

7

Gambar 2.4 Graf

dengan 4 titik .................................................................

7

Gambar 2.5 Graf

dengan 5 titik .................................................................

8

Gambar 2.6 Graf

.......................................................................................

9

Gambar 2.7 Graf Roda

............................................................................

9

Gambar 2.8 Graf Helm

.............................................................................

10

......................................................................................

11

Gambar 2.9 Graf


............................................................................

13


.............................................................................

16


............................................................................

19


..............................................................................

20


..............................................................................

21

DAFTAR LAMBANG

Lambang

Keterangan Dimensi metrik graf Jarak antara titik

⌊ ⌋

Pemakaian pertama kali pada halaman 2

dan

pada graf

2

Graf roda dengan

titik

2

Graf helm dengan

titik

2

Bilangan bulat terbesar yang lebih kecil atau sama dengan

2

Himpunan sisi graf

4

Graf

dengan himpunan titik

dan himpunan sisi

4

Himpunan titik graf

4

Banyaknya anggota himpunan titik pada graf

4

Banyaknya anggota himpunan sisi pada graf

4

Derajat titik

6

pada

Derajat titik yang minimum pada graf

6

Derajat titik yang maksimum pada graf

6

Graf lingkaran dengan

9

Representasi dari

titik

terhadap

sub himpunan titik

pada graf

Kardinalitas Himpunan

10 10 12

selisih himpunan

27

BAB I PENDAHULUAN

Pada bab ini dibahas mengenai latar belakang masalah, rumusan masalah, batasan masalah, tujuan penulisan, manfaat penulisan, dan sistematika penulisan dari skripsi ini. 1.1

Latar Belakang Ilmu matematika merupakan alat bantu untuk menyederhanakan penyajian

dan pemahaman masalah. Dalam bahasa matematika, suatu masalah dapat menjadi sederhana untuk disajikan, dipahami, dianalisis, dan dipecahkan. Untuk keperluan tersebut, maka pertama dicari pokok masalahnya kemudian dibuat rumusan atau model matematikanya sehingga masalah lebih mudah dipecahkan. Salah satu konsep dari disiplin ilmu matematika adalah teori graf. Teori graf pertama kali diperkenalkan oleh matematikawan Swiss bernama Leonhard Euler pada tahun 1736 ketika mendiskusikan mengenai persoalan jembatan Konigsberg Rusia. Cikal bakal dari teori graf dinyatakan dalam bentuk permainan atau tekateki. Tetapi sekarang teori graf telah dapat memberikan kerangka dasar bagi banyak persoalan yang berhubungan dengan struktur dan hubungan antara suatu obyek diskrit dalam bentuk apapun. Graf menggambarkan struktur tersebut dalam beberapa objek yang dinyatakan dengan noktah, bulatan atau titik sedangkan hubungan antara objek dinyatakan dengan garis.

Seiring dengan kemajuan ilmu pengetahuan dan teknologi, akhir-akhir ini banyak sekali penelitian-penelitian terbaru tentang graf. Salah satu topik yang banyak dibicarakan adalah dimensi metrik. Dimensi metrik pada suatu graf pertama kali diperkenalkan oleh F. Harary dan R. A Melter (1976) pada jurnal berjudul on the metric dimension of a graph. Untuk menentukan dimensi metrik graf ada beberapa konsep yang digunakan. Pertama adalah konsep jarak antara dua titik pada suatu graf. Misalkan dan

adalah titik-titik pada graf terhubung

pada graf

, maka jarak antara titik

adalah panjang lintasan terpendek antara

dengan

dan

dan

pada , dinotasikan

. Konsep lainnya adalah himpunan penentu (resolving set). Suatu

himpunan bagian setiap titik di

dari himpunan titik

disebut himpunan penentu pada

mempunyai representasi yang berbeda terhadap

jika

. Himpunan

penentu yang memiliki anggota (kardinalitas) yang minimum disebut himpunan penentu minimum (minimum resolving set) dan anggota pada himpunan penentu minimum disebut basis, sedangkan jumlah anggota dari basis tersebut disebut dimensi metrik dari

dan dinotasikan dengan

.

Berdasarkan hasil penelitian beberapa peneliti terdahulu, dimensi metrik dari beberapa jenis graf sudah diketahui, diantaranya adalah graf roda dan graf lingkaran. Misalnya, Buczkowski dkk (2003) menemukan dimensi metrik graf roda

dengan

adalah ⌊

. Lebih jelasnya, jika

⌋, sedangkan untuk

dan

dan dimensi metrik

dimensi metrik adalah .

Namun demikian, beberapa graf yang dikonstruksi dari graf roda belum ditemukan dimensi metriknya, misalnya graf helm (helm graph). Graf helm

adalah graf yang dikonstruksi dari graf roda dengan menambahkan sisi pendant pada setiap titik dari lingkaran luar graf roda. 1.2

Rumusan Masalah Adapun rumusan masalah yang akan dibahas dalam penulisan skripsi ini

adalah bagaimana menentukan dimensi metrik graf helm. 1.3

Batasan Masalah Batasan masalah dalam penulisan skripsi ini dibatasi pada penentuan

dimensi metrik graf helm hingga 1.4

titik.

Tujuan Penulisan Tujuan penulisan skripsi ini adalah menentukan dimensi metrik graf helm.

1.5

Manfaat Penulisan Adapun manfaat yang diharapkan dalam penulisan skripsi ini adalah

untuk menambah pemahaman tentang konsep teori graf khususnya dimensi metrik suatu graf.

BAB II TINJAUAN PUSTAKA

Pada bab ini dibahas beberapa materi yang dijadikan landasan teori untuk memahami penentuan dimensi metrik suatu graf, khususnya graf helm. Materinya meliputi beberapa definisi, istilah-istilah dalam teori graf

termasuk dimensi

metrik. Adapun definisi, istilah-istilah, dan contoh yang dibahas pada bab ini umumnya dikutip dari referensi [1], [2], [3], [4], [5], [6], [7], dan [8]. 2.1 Terminologi Graf Pada sub bab ini dibahas beberapa definisi dan istilah-istilah dalam teori graf beserta contoh yang digunakan dalam penulisan skripsi ini. Definisi 2.1 Graf

adalah pasangan himpunan

dengan

adalah

himpunan tidak kosong dan berhingga dari obyek-obyek yang disebut sebagai titik dan

adalah himpunan (mungkin kosong) pasangan tidak terurut dari titik-

titik berbeda di

yang disebut sebagai sisi.

Himpunan titik di dinotasikan dengan dan dilambangkan dengan

dinotasikan dengan Sedangkan banyaknya unsur di dan banyaknya unsur di

dan himpunan sisi disebut order dari disebut ukuran dari

dan dilambangkan dengan Berdasarkan Definisi 2.1, didefinisikan graf sederhana adalah graf yang tidak mempunyai sisi ganda (multiple edges) dan loop. Dua buah sisi disebut

ganda pada suatu graf jika kedua sisi tersebut mempunyai titik ujung yang sama. Sedangkan yang disebut dengan loop adalah suatu sisi yang mempunyai titik ujung sama. Pada pembahasan skripsi ini, graf

yang dibahas adalah graf

sederhana. Titik

pada

suatu

graf

dapat

disimbolkan

atau bilangan asli, seperti

dengan

huruf,

seperti

atau gabungan keduanya,

sedangkan sisi dapat disimbolkan dengan

.

Contoh 2.1

v

2

e

2

v

3

e

e

3

1

v

v

1

e

4

e

6

4

v

6

e

5

v

5

Gambar 2.1. Graf G dengan 6 titik Graf pada Gambar 2.1, memiliki himpunan titik dan himpunan sisi sebagai berikut : {

}

{

}

sehingga

dan

.

Definisi 2.2 Misal

adalah graf dengan

pada

disebut bertetangga (adjacent), sedangkan

maka

dan

(incident) dengan

dan

Jika

adalah sisi disebut terkait

disebut terkait dengan

Contoh 2.2

v1

v4

e1

v3

e2

v2

e3

Gambar 2.2. Graf

e4

dengan empat titik

Pada Gambar 2.2 diketahui bahwa pasangan titik yang terhubung langsung (adjacent) yaitu

dan

(incident) dengan sisi tetapi titik

dan sisi

. Titik

terkait langsung (incident) dengan titik

tidak terkait langsung (incident) dengan sisi

sebaliknya, yaitu sisi

terkait langsung

, demikian juga

tidak terkait langsung (incident) dengan titik

Definisi 2.3 Derajat (degree) dari suatu titik yang terkait dengan titik

pada graf

adalah banyaknya sisi

dan dinotasikan dengan deg ).

Suatu titik yang berderajat 0 disebut titik terisolasi dan titik yang berderajat 1 disebut titik ujung. Derajat minimum titik di derajat maksimum titik di

dinotasikan dengan

dinotasikan dengan

dan

Contoh 2.3

v

v

e1

1

e2

e6

e5

v

5

e3

v

Gambar 2.3. Graf

2

e4

4

v

3

dengan 5 titik

Derajat titik-titik graf pada Gambar 2.3 adalah sebagai berikut : . Dengan demikian, dipeoleh

dan

.

Definisi 2.4 Misal

adalah graf dengan

Lintasan dari titik

titik

dinotasikan dengan

adalah barisan selang-seling

pada graf

antar titik dan sisi,

ke

, dimulai dengan titik

dan diakhiri dengan titik

di mana

untuk

dan tidak

terdapat pengulangan titik dan sisi. Contoh 2.4

v

1

v

4

Gambar 2.4. Graf

v

2

v

3

dengan 4 titik

Graf pada Gambar 2.4, memiliki lintasan dengan barisan sisi yaitu dan

.

Definisi 2.5 Misal

adalah graf dengan

. Graf

terhubung (connected), jika setiap dua titik yang berbeda di lintasan dari

terdapat suatu

ke

Definisi 2.6 Jarak (distance) antara titik dengan

disebut graf

dan

pada graf

, adalah panjang lintasan terpendek antara

Contoh 2.5

v

dan

, dinotasikan pada .

2

v

v

3

1

v

5

Gambar 2.5. Graf

v

4

dengan 5 titik

Pada Gambar 2.5 diperoleh

2.2 Graf Roda dan Graf Helm Pada sub bab ini dibahas tentang definisi graf roda dan graf helm serta beberapa definisi yang berkaitan dengan kedua graf tersebut. Definisi 2.7 Graf lingkaran (cycle) adalah graf terhubung yang semua titiknya berderajat dua.

Contoh 2.6 v1

v2

v6

v3

v4

v5

Gambar 2.6. Graf Definisi 2.8 Graf roda (wheel) adalah graf terhubung yang dikonstruksi dari graf lingkaran

dinotasikan dengan

dengan menambahkan satu titik

titik pusat dan n sisi sedemikian sehingga lingkaran

sebagai

bertetangga dengan semua titik pada

.

Contoh 2.7

v2

v3

c

v4

v1

v6

v5

Gambar 2.7. Graf Roda Berdasarkan hasil penelitian Buczkowski dkk. pada tahun 2003, diperoleh dimensi metrik dari graf roda Wn. Dimensi metrik dari graf roda dan

adalah ⌊

⌋. Untuk

dan

jika

diperoleh dimensi metriknya .

Definisi 2.9 Sisi pendant adalah sebuah sisi yang terkait (incident) dengan titik ujung (pendant) pada graf . Definisi 2.10 Graf Helm berukuran

adalah graf terhubung berorder

yang dikonstruksi dari graf roda

pendant pada setiap titik pada lingkaran

dan

dengan menambahkan sisi

.

Contoh 2.8 a1

a2 b2

b1

a6

c

b6

b5

b3

a3

b4

a4

a5

Gambar 2.8. Graf Helm 2.3 Dimensi Metrik Pada sub bab ini dibahas tentang istilah-istilah yang berkaitan dengan dimensi metrik dari suatu graf. Misalkan

adalah suatu graf terhubung sederhana, dan .

Definisi 2.11 Representasi dari (

terhadap

adalah pasangan -tuple yaitu )

Definisi 2.12 Himpunan titik pada graf

merupakan himpunan penentu pada graf

jika titik-

mempunyai representasi yang berbeda terhadap .

Definisi 2.13 Himpunan penentu yang memiliki anggota (kardinalitas) yang minimum disebut himpunan penentu (resolving set) minimum pada graf Definisi 2.14 Anggota-anggota pada himpunan penentu minimum disebut basis. Definisi 2.15 Dimensi metrik dari

dinotasikan dengan

yang

menyatakan jumlah anggota dari basis.

Contoh 2.9 v2

v1

c

v3

v4

Gambar 2.9. Graf {

Misal dipilih

} , maka representasi titik-titik di

berikut : (

)

(

)

(

)

(

)

(

)

adalah sebagai

Karena representasi setiap titik di penentu bagi

Selain }

graf

lain, yaitu

{

setiap titik di

berbeda, yaitu :

juga mempunyai himpunan penentu yang

(

)

(

) )

(

)

(

)

Akan tetapi jika

merupakan himpunan

merupakan himpunan penentu karena representasi

(

bagi

berbeda, maka

dengan

. Karena setiap titik di

maka

bukan himpunan penentu

mempunyai derajat lebih besar 3, maka

setidaknya untuk setiap titik memiliki 3 titik tetangga. Dengan demikian,

merupakan himpunan penentu minimum bagi

Jadi,

BAB III HASIL DAN PEMBAHASAN

Pada bab ini dibahas tentang hasil penelitian penulis dan buktinya serta beberapa hasil peneliti lain yang terkait dengan kajian penulis. Beberapa peneliti terdahulu menemukan dimensi metrik dari beberapa jenis graf, antara lain graf roda dan graf lingkaran. Berdasarkan hasil penelitian Buczkowski dkk, pada tahun 2003, dimensi metrik dari graf roda adalah ⌊

dan

⌋, sedangkan untuk

dan

untuk

adalah .

3.1 Graf Helm Pada sub bab ini dibahas definisi himpunan titik dan himpunan sisi serta jarak setiap titik pada graf helm

.

Contoh 3.1 a1

a2 b2

b1

a6

c

b6

b5

b3

b4

a5


a4

.

a3

Berdasarkan Gambar 3.1, diketahui himpunan titik dan himpunan sisi pada graf helm

yaitu : {

}

{

}

{

}

Berdasarkan definisi himpunan titik dan himpunan sisi graf helm tersebut, diperoleh beberapa sifat yang terkait dengan jarak titik - titik pada graf helm

sebagai berikut :

1. 2.

3.

(

)

{

4.

(

)

{

5.

(

)

{

3.2 Dimensi Metrik Graf Helm Pada sub bab ini dibahas tentang penentuan dimensi metrik graf helm beserta pembuktian dimensi metrik graf helm.

Lemma 1 Misalkan

merupakan graf helm dengan n

3, maka dim(

) > 1.

Bukti: Diketahui bahwa banyaknya titik pada berderajat ,

titik berderajat 1 dan

Misal, dipilih

{ } dengan

adalah

, di mana terdapat 1 titik

titik berderajat 4. maka terdapat 3 kemungkinan, yaitu

dan i.

jika

, maka

bertetangga dengan

titik lainnya,

sehingga

Akibatnya,

(terdapat nilai representasi yang sama). ii.

jika

, maka

untuk suatu ,

sehingga Akibatnya,

(terdapat nilai representasi

yang sama). iii.

jika

, maka

untuk suatu ,

sehingga

,

Akibatnya, (terdapat nilai representasi yang sama).

Dengan demikian, jika himpunan penentu. Akibatnya,

{ } dengan

maka

bukan

Teorema 1 Dimensi metrik graf helm

adalah 3.

Bukti: Graf helm

digambarkan sebagai berikut :

a

1

b

1

c

b

b

3

2

a

a

3

2

Gambar 3.2. Graf helm Berdasarkan Lemma 1

Selanjutnya akan ditunjukkan bahwa

dengan jalan akan dibuktikan bahwa jika

maka

bukan

himpunan penentu. Untuk itu, dibuktikan 6 kasus berikut . Kasus 1. Untuk

{

} diperoleh representasi titik

dan

terhadap

adalah (

)

(

)

Karena penentu bagi {

}, maka {

Kasus 2. Untuk

{

maka Karena posisi } dan { {

{

} bukan himpunan

} serupa dengan posisi {

} dan

} juga bukan himpunan penentu bagi } diperoleh representasi titik

adalah (

)

dan

terhadap

( Karena

maka Karena posisi {

bagi {

)

} dan {

Kasus 3. Untuk

{

} bukan himpunan penentu


} dan {

} maka

} juga bukan himpunan penentu bagi {


dan

terhadap

adalah (

)

(

)

Karena Karena posisi {

bagi {

maka

} dan {

Kasus 4. Untuk

{



} dan {

} maka



dan

terhadap

adalah (

)

(

)


bagi {

maka

} dan {

Kasus 5. Untuk

{



} dan {

}, maka



adalah ( (

) )

dan

terhadap


penentu bagi {

{

maka

}, maka {

} dan {

Kasus 6. Untuk

{

} bukan himpunan


} dan


dan

terhadap

adalah (

)

( Karena

)

penentu bagi

Karena posisi { } dan {

} {

} maka {

{

} juga bukan himpunan penentu bagi

Dengan demikian, untuk setiap himpunan penentu bagi {

. Akibatnya,

} bukan himpunan


{

Misal

{

maka

}, {

}, {

dengan

},

} {

} dan

maka

bukan

.

} representasi semua titik pada graf

berikut ; (

}, {

)

(

)

(

)

(

)

(

)

(

)

(

)

adalah sebagai

Karena semua titik memiliki representasi yang berbeda maka {

} merupakan himpunan penentu bagi

Dengan demikian, Karena

dan

maka

Teorema 2. Dimensi metrik graf helm

adalah 2.

Bukti : Graf helm

digambarkan sebagai berikut:

a

a

1

2

b

b

1

2

c b

b

4

a

3

a

4

3


atau

Selanjutnya akan

ditunjukkan bahwa Misal dipilih

{


sebagai berikut : (

)

(

)

(

)

(

)

(

)

adalah

(

)

(

)

(

)

(

)

Karena semua titik pada graf {

relatif terhadap bagi

mempunyai representasi yang berbeda

}, maka

{

Dengan demikian,

} merupakan himpunan penentu

Jadi,


adalah 2.

Bukti : Graf helm

digambarkan sebagai berikut :

a

1

a

5

b

b

a

b

1

5

2

2

c

a

b

4

4

a

b

3

3


atau

. Selanjutnya akan

ditunjukkan bahwa Misal dipilih

{


sebagai berikut : ( (

) )

adalah

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

Karena semua titik pada graf relatif terhadap bagi

{

}, maka

Dengan demikian,

mempunyai representasi yang berbeda {

} merupakan himpunan penentu

Jadi,


adalah 3.

Bukti: a1

a2 b2

b1

a6

c

b6

b5

a5

b3

b4

a4

Gambar 3.5.Graf helm

a3

Berdasarkan Lemma 1


dengan jalan akan dibuktikan bahwa jika

maka

bukan

himpunan penentu. Untuk itu, dibuktikan 12 kasus berikut. {

Kasus 1. Untuk


dan

terhadap

adalah (

)

(

)

Karena

{

}{

}{

}{

{

} {

} dan { {

}

Karena posisi {

bukan himpunan penentu bagi

Kasus 2. Untuk

{

maka

}

dan

{

}

} serupa dengan

maka

{

}{

}


dan

terhadap

adalah (

)

(

)


} {

Kasus 3. Untuk

{

maka Karena posisi { } dan { {

} bukan himpunan


} {


adalah (

)

(

)

dan

terhadap

}


penentu bagi {

{

maka

} maka {

} dan { {

Kasus 4. Untuk

} bukan himpunan


} dan



dan

terhadap

adalah (

)

( Karena

} { {

{


penentu bagi {

)

} dan {

} bukan himpunan


} maka {

} {

} {

} {

}{


dan

} }


Kasus 5. Untuk

terhadap

adalah (

)

(

)

Karena


penentu bagi {

} {

{

} maka {

{

} {

Kasus 6. Untuk

} {

} { } {

} {

} dan { {

} bukan himpunan

} serupa dengan posisi { } {

} {

{

} { } {

} { } {

} { }

{

} } dan

} {



adalah (

} {

)

dan

terhadap

}

(

)

Karena

{


penentu bagi {

} {

}

{

} maka

{

} {

{

} {

{ } {

Kasus 7. Untuk

{

} {

} {

} dan {

bukan


} {

}

} {

} {

} {

} {

} {

himpunan } {

}

}

dan

} {

}



dan

terhadap

adalah (

)

(

)

Karena

{

maka

penentu bagi



{

} {

{


Kasus 8. Untuk

{

} bukan himpunan

} maka {

} {

} {


} { } {

dan

} } dan

terhadap

adalah (

)

( Karena bagi {

) maka


} maka {


{



} {

} {

} { } dan {

} { }

} juga

{

Kasus 9. Untuk


dan

terhadap

adalah (

)

(

)

Karena

{


penentu bagi }

{

} {

{


Kasus 10. Untuk

{

bukan

himpunan


{

dan

}

} maka

{

} {

} {

}

} {

} {

}


dan

terhadap

dan

adalah (

)

(

)

Karena

{


penentu bagi

} dan {


{

} {

{


Kasus 11. Untuk

{

} bukan himpunan

} maka {

} {

} {


} { } {

dan

} } dan

terhadap

adalah (

)

( Karena penentu bagi

) maka

Karena posisi {

{

} bukan himpunan


} {

}

{

} {

} dan {

} maka {

{


Kasus 12. Untuk

} {

} {

} {

} dan


dan

terhadap

adalah (

)

(

)


} maka {


himpunan penentu bagi {

} bukan himpunan


} dan


Dengan demikian, untuk setiap

Misal

{

maka

dengan

maka

bukan

Akibatnya,


berikut: (

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

(

)

adalah sebagai

(

)

(

)

(

)

(

)

Karena semua titik memiliki representasi yang berbeda terhadap {

maka

} merupakan himpunan penentu bagi Karena

dan

dengan demikian,

⌋ untuk

Untuk tujuan tersebut, pertama akan ditunjukkan bahwa ⌊

⌋ maka

},

maka ⌊


{

dengan


Untuk tujuan tersebut, beberapa lemma digunakan sebagai berikut : Lemma 2. Misalkan

⌊

dengan

⌋ dan

{

} maka

himpunan penentu bagi Bukti : Ada dua kemungkinan : I.

II.

Ada dua titik

dan

Ada titik

dan dan

Jika kemungkinan I yang benar, maka Dengan demikian,

{ } dan

bukan

Jika kemungkinan II yang benar, maka { }

{ }

dan

Dengan demikian, Hal ini menunjukkan bahwa


Lemma 3. Misalkan

⌊

dengan

⌋ dan

{

} maka

bukan

himpunan penentu bagi Bukti: Ada dua kemungkinan : I.

Ada dua titik

II.

dan

Ada titik

dan { }

dan Jika kemungkinan I yang benar, maka

dan

Dengan demikian, Jika kemungkinan II yang benar, maka { }

dan Dengan demikian, Hal ini menunjukkan bahwa


Lemma 4. Misalkan ⌊

dengan ⌋ maka

dengan


dan

Bukti: Ada empat kemungkinan: I.

Ada dua titik

yang mempunyai jarak lebih besar

atau sama dengan dua ke titik-titik yang ada pada II.

Ada dua titik a. Titik pada b. Titik

dan

yang memenuhi dua syarat berikut. mempunyai jarak 1 ke salah satu titik yang ada

. dan

mempunyai jarak lebih besar atau sama dengan dua ke

semua titik yang ada pada III.

Ada dua titik

kecuali titik yang disebut pada bagian a. yang mempunyai jarak lebih besar

atau sama dengan tiga ke titik-titik yang ada pada IV.

Ada dua titik a.

b.

.

Titik

dan

pada

.

Titik

dan

.

yang memenuhi dua syarat berikut. mempunyai jarak 2 ke salah satu titik yang ada

mempunyai jarak lebih besar atau sama dengan tiga ke

semua titik yang ada pada

kecuali titik yang disebut pada bagian a.

Jika kemungkinan I yang benar, maka diperoleh dan sebelumnya, diperoleh juga

Dengan demikian,

Dengan argumentasi dan

yang sama dengan

Jika kemungkinan II yang benar, tanpa mengurangi pembuktian pada bagian ini, dapat dimisalkan bahwa salah satu titik pada adalah -

atau

yang mempunyai jarak 1 ke

.

.Jika titik yang dimaksud adalah

maka diperoleh

{ } dan

,

Lebih lanjut, diperoleh juga

, { }

,

,

{ } dan

,

dan

{ }.

,

Dengan demikian, -

Jika titik yang dimaksud adalah { } dan

,

Lebih lanjut, diperoleh juga dan

maka diperoleh

, { }

,

,

{ }

,

{ } Dengan demikian,

,

Dengan demikian, Jika kemungkinan III yang benar, maka diperoleh dan

Dengan argumentasi yang sama dengan

sebelumnya, diperoleh juga

dan

Dengan demikian, Jika kemungkinan IV yang benar, tanpa mengurangi pembuktian pada bagian ini, dapat dimisalkan bahwa salah satu titik pada dan

adalah -

atau

.Jika titik yang dimaksud adalah

yang mempunyai jarak 2 ke

. maka diperoleh

,

{ } dan

,

Lebih lanjut, diperoleh juga

-

{ }

,

,

,

{ } dan ,

{ }. Dengan demikian,

Jika titik yang dimaksud adalah { } dan

,

Lebih lanjut, diperoleh juga dan

maka diperoleh

, { }

,

,

,

{ }

{ }

,

Dengan demikian, Hal ini menunjukkan bahwa


Berdasarkan lemma 2, 3, dan 4, diperoleh teorema berikut.

Teorema 5. Misal penentu bagi

Teorema 6. Dim

⌊

dengan

⌋ maka

untuk

=⌊

⌋ untuk

Bukti: Berdasarkan teorema 5 diperoleh Selanjutnya akan dibuktikan bahwa

⌊

⌋ untuk ⌊

⌋ untuk

bukan himpunan

Untuk tujuan tersebut, pemilihan titik-titik penentu bagi

dengan

⌊

di

yang merupakan himpunan

⌋ akan dibagi menjadi dua bagian sebagai

berikut: {

1. Misal pilih 4 kasus yakni

} ,

⌊

,

⌋ berlaku untuk , dan

maka diperoleh representasi titik-titik di

terhadap

sebagai berikut :

di mana angka

di mana angka

di mana angka

di mana angka

dan

,

dan

,

dan

,

dan

,

dan

,

masing-masing berada pada posisi ke.


masing-masing berada pada posisi ke-


,

,

di mana angka ke-


dan

.

di mana angka

di mana angka

di mana angka

di mana angka

dan

,

dan

,

dan

,

dan

,

dan

,




,


,

di mana angka 2 masing-masing berada pada posisi ke-

dan ke-

. Untuk lebih jelasnya, representasi titik-titik di

terhadap

menjadi 4 kasus berikut : Kasus 1. Untuk Misal pilih

{

} dengan

dan

akan dibagi

⌊

⌋ representasi titik-titik di

Karena setiap titik pada graf

⌋, maka ⌊

Jadi,

dengan

memiliki representasi

{

yang berbeda terhadap ⌊

sebagai berikut:

} dengan

dan

merupakan himpunan penentu bagi ⌋

Kasus 2. Untuk {

Misal pilih ⌊

} dengan


Karena setiap titik pada graf yang berbeda terhadap dan

⌊

⌋, maka

dengan {

dan

sebagai berikut:

memiliki representasi } dengan

merupakan himpunan penentu bagi

⌊

Jadi,

⌋

Kasus 3. Untuk {

Misal pilih ⌊

} dengan



⌊

⌋, maka ⌊

Jadi,

sebagai berikut:

dengan


{

yang berbeda terhadap

dan

} dengan

merupakan himpunan penentu bagi ⌋

Kasus 4. Untuk Misal pilih ⌊

{ ⌋ representasi titik-titik di

} dengan sebagai berikut:

dan

dan

Karena setiap titik pada graf {

yang berbeda terhadap ⌊

⌋, maka

2. Misal pilih

{

} dan

terhadap

di mana angka

di mana angka

} dengan

dan

⌋

untuk 1 kasus yakni di


merupakan himpunan penentu bagi

⌊

Jadi,

dengan

⌊

⌋ berlaku

, maka diperoleh representasi titik-titik sebagai berikut :



dan

,

dan

,

dan

,

.

.

di mana angka


. dan

di mana angka


. dan

di mana angka

di mana angka

di mana angka

di mana angka

di mana angka

di mana angka

,


,

dan ke-

dan

,

dan

,

dan

,

dan

,

dan

,


masing-masing berada pada posisi

-




.

.

dan

keSelanjutnya, untuk

maka representasinya adalah



{

yang berbeda terhadap maka

dengan

} dan

⌊

⌋

merupakan himpunan penentu bagi ⌊

Jadi,

⌋

Selain dengan cara mendaftarkan representasi semua titik seperti bukti diatas, representasi titik dapat juga ditinjau dari pembagian kasus-kasus sebagai berikut : Kasus 1. Untuk

Misal dipilih

{

} maka {

Akan ditunjukkan bahwa

⌊

⌊

⌋

} dan

⌋ adalah himpunan penentu dari

Ambil representasi dari

dengan dan

terhadap

beberapa kasus dan sub kasus.

selanjutnya akan ditunjukkan bahwa berbeda. Pembuktian ini akan dibagi dalam

A.

atau maka (

Jika

)

dan (

)

untuk suatu

Jadi, jika

)

dan (

)

untuk suatu

Jadi, jika

maka maka (

Jika

maka B.

dan B.1.

atau maka (

Jika

)

untuk setiap

Hal ini menunjukkan

bahwa Begitu pula jika

maka (

)

untuk setiap

Hal ini menunjukkan bahwa B.2.

dan B.2.1.

atau Jika

maka

Jadi titik yang mungkin

mempunyai representasi yang sama dengan karena begitu pula

tetapi

. Oleh karena itu, representasi

Jika

dan

terhadap

dan

begitu pula

berbeda.

maka

Jadi titik yang mungkin

mempunyai representasi yang sama dengan karena tetapi

atau

Namun demikian,

tetapi

representasi

adalah

adalah

Namun demikian, begitu pula

tetapi

atau

. Oleh karena itu, representasi representasi B.2.2.

dan

terhadap

dan

begitu pula

berbeda.

dan

B.2.2.1.

atau Jika

maka

sehingga titik yang

mungkin mempunyai representasi yang sama dengan terhadap

adalah

dan

untuk setiap ,

, karena

dan

Akan tetapi

dan Oleh karena itu, (

)

atau

. Pada sisi lain, , sedangkan (

untuk setiap

untuk suatu

Oleh karena itu,

)

dengan tidak mempunyai representasi yang

sama dengan salah satu

untuk

dan

Dengan demikian, Begitu pula, jika

B.2.2.2.

maka akan menunjukkan bahwa

dan B.2.2.2.1.

dan

untuk

dan genap.

Tanpa mengurangi berlaku umumnya pembuktian, bisa dimisalkan ganjil sehingga

Karena

genap, maka

Dapat dilihat bahwa

sedangkan

B.2.2.2.2.

dan Jika

Jadi,

.

ganjil maka

tetapi

, sehingga Jika

genap, maka

dan

ganjil, sehingga sedangkan atau Jadi, B.2.2.2.3.

dan Jika

.

genap, maka

ganjil dan

sehingga

,

tetapi Oleh karena itu,

B.2.2.2.4.

dan

untuk

dan ganjil.

Tanpa mengurangi berlaku umumnya pembuktian, bisa dimisalkan

Karena

genap sehingga

ganjil, maka

Dapat dilihat bahwa sedangkan

Jadi, B.2.2.2.5.

dan Jika tetapi

.

genap maka

, sehingga Jika

genap, sehingga

ganjil, maka

dan

sedangkan atau Jadi, B.2.2.2.6.

dan Jika

.

ganjil, maka

genap dan

sehingga

,

tetapi Oleh karena itu,

Dari keseluruhan kasus dan sub kasus terlihat bahwa untuk setiap dengan

diperoleh

Akibatnya,

adalah himpunan penentu

bagi Dengan cara yang serupa, hal ini dapat dilakukan untuk empat kasus lainnya, yaitu

dan ⌊

dengan

⌋

Karena

⌊

⌋ dan

Teorema 7.

⌊

⌊

⌋ maka

⌋ untuk

⌊

⌋

dan

Bukti: ⌊

Berdasarkan teorema 6 diperoleh

⌋ serta hasil penelitian ⌊

Buczkowski dkk, pada tahun 2003, diperoleh

Dengan demikian,

⌊

⌋ untuk

⌋ untuk

dan

dan

BAB IV PENUTUP

4.1

Kesimpulan Berdasarkan hasil yang diperoleh maka dapat disimpulkan bahwa dimensi

metrik graf helm

adalah i.

ii. iii. 4.2

⌊

⌋ ⌊

⌋

Saran Bagi yang ingin mengkaji tentang dimensi metrik suatu graf, penulis

menyarankan untuk menggunakan program agar memudahkan pencarian dimensi metrik suatu graf tanpa harus mencoba satu persatu titik-titik pada graf tersebut. Selain itu, penulis berharap akan ada yang tertarik untuk mengembangkan graf helm.

DAFTAR PUSTAKA

[1] Buczkowski, P., Chartrand, G., Poisson, C., dan Zhang, P. (2003), ‘On kDimensional Graphs and Their Bases’, Period. Math. Hungar. 46(1), 9-15. [2] Chartrand, G. dan Lesniak, L. (1986). Graph and Digraph second Edition. California: Wadsworth. Inc. [3]

Chartrand, G., Eroh, L., Johnson, M. dan Oellermann, O. (2000a), ‘Resolvability in Graphs and the Metric Dimension of a Graph’, Discrete Appl. Math. 105, 99-113.

[4] Chartrand, G. dan Zhang, P. (2005). Introduction to Graph Theory. McGrawHill Companies, Inc. [5] Harary, F. (1969). Graph Teory. Wesley Publishing Company,Inc. [6] Harary, F. dan Melter, R. (1976), ‘On the Metric Dimension of a Graph’, Ars Combin. 2, 191 – 195. [7] Ghofur, Abdul. (2008). Pewarnaan Titik Pada Graf Yang Berkaitan dengan Sikel. Malang : UIN.Skripsi ,tidak diterbitkan. [8] Robert F. Bailey and Peter J. Cameron. (2000). “Base size, metric dimension and

other

invariants

of

groups

and

http://www.math.uregina.ca/~bailey/papers/basesize_metdim.pdf. tanggal 7 Februari 2012.

graphs”. Diakses

PENENTUAN DIMENSI METRIK GRAF HELM

Recommend Documents