Revisi.docx

BAB I PENDAHULUAN A. Latar Belakang Masalah Teori graf merupakan salah satu cabang dalam matematika diskrit yang menarik untuk dibahas karena berkaitan dengan permasalahan yang banyak ditemui dalam kehidupan sehari-hari. Teori graf merupakan pokok bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk mempresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan garis. Adapun contoh graf yang sering di jumpai dalam kehidupan sehari-hari, yaitu: struktur organisasi, bagan alir pengambilan data, peta, rangkaian listrik dan lain-lain. Graf adalah gambaran logika dari suatu kejadian, proses, peristiwa atau hal-hal lain yang berkaitan. Graf adalah himpunan pasangan terurut (V,E) dimana V adalah himpunan vertex atau titik dan E adalah himpunan edge atau rusuk. Teori graf mempunyai banyak sekali cabang dan pembagiannya. Mulai dari bentuk graf, sifat graf dan lain sebagainya. Salah satu topik dalam teori graf yaitu membahas tentang graf lingkaran (cycle graph). Graf lingkaran adalah graf sederhana yang setiap simpul/titiknya berderajat dua. Graf lingkaran dengan n simpul dilambangkan Cn. Salah satu topik dalam teori graf yaitu membahas tentang pelabelan garf. Sebuah pelabelan graf adalah pemetaan yang memasangkan elemen-elemen graf dengan bilangan (biasanya bilangan positif atau non-negatif). Jika domain dari fungsi (pemetaan) adalah himpunan semua titik, maka pelabelan disebut pelabelan titik (vertex labeling), jika domainnya adalah sisi, maka pelabelan disebut pelabelan sisi (edge labeling) dan jika domainnya adalah semua titik dan sisi, maka pelabelan disebut pelabelan total (total labeling). Selain pelabelan total, ada jenis pelabelan lainnya yang disebut pelabelan total tak teratur yaitu pelabelan total tak teratur sisi dan pelabelan total tak

1

teratur titik. Pelabelan-k total didefenisikan sebagai pemetaan yang memasangkan unsur-unsur graf (titik dan garis) dengan bilangan positif yang dinoasikan dengan f:VE1,2,…,k f :V ∪ E →{1,2, … , k } . Pelabelan-k total dikatakan pelabelan-k total tak teratur titik dari graf G, jika untuk setiap titik x dan y yang berbeda maka wt(x) wt(y) wt ( x)≠ wt ( y ) , dimana wt(x)+uxE f(ux) wt ( x ) + ∑ f (ux ) . Nilai total ux∈ E

ketakteraturan titik (total vertex irregularity strength) dari graf G, yang dinotasikan dengan tvs(G) adalah label terbesar minimum yang digunakan untuk melabeli graf G dengan pelabelan total tak teratur titik. Pelabelan-k total dikatakan pelabelan-k total tak teratur sisi dari graf G, jika untuk sembarang dua sisi e=u1v1 dan w=u2v2 yang berbeda dari graf G berlaku

wt(e)wt(w)

wt ( e )=f ( u1 ) + f ( e ) + f (v 1 ) wt ( e )=f ( u1 ) + f ( e ) + f (v 1 )

dengan dan

wt(e)=f(u1)+

f(e)+

wt(w)=f(u1)+

wt ( w )=f ( u1 ) +f ( w ) +f (v 1 ) .

f(v1)

f(w)+

f(v1)

Nilai

total

ketakteraturan sisi (total edge irregularity) dari graf G, yang dinotasikan dengan tes(G) adalah label terbesar minimum yang digunakan untuk melabeli graf G dengan pelabelan total tak teratur sisi. Pelabelan-k total dikatakan Pelabelan-k total tak teratur total dari graf G, jika untuk setiap titik x dan y yang berbeda maka wt(x) wt(y), dan untuk setiap x1x2 dan y1y2 yang berbeda maka wt(x1x2)wt(y1y2)

y1 y2 . wt ( x1 x 2)≠ wt ¿

Nilai ketakteraturan total (totally irregularity strength) dari graf G, yang dinotasikan dengan ts(G) adalah label terbesar minimum yang digunakan untuk melabeli graf G dengan pelabelan total tak teratur total. Oleh karena itu, penulis tertarik untuk membahas nilai total ketakteraturan titik (tvs) dari salah satu bentuk graf, yaitu tentang nilai total ketakteraturan titik dari m-copy graf lingkaran. Karena masih sedikit sekali yang membahas materi ini, sehingga penulis merasa tertarik untuk membahasnya dalam tulisan ini. Dimana m-copy graf lingkaran atau mCn adalah graf yang diperoleh

2

dengan menggandakan Cn sebanyak m, dimana himpunan titik dari setiap graf hasil penggandaannya tidak ada yang beririsan.

B. Ruang Lingkup Pada bab selanjutnya dalam tulisan ini, penulis akan membahas tentang pelabelan total tak teratur titik pada graf mCn. Dengan materi pendukung mengenai dasar-dasar teori graf seperti defenisi graf, macam-macam graf dan pelabelan graf. C. Tujuan Tujuan penulisan dari tulisan ini adalah untuk mengetahui cara pelabelan total tak teratur titik pada graf mCn. D. Sistematika Penulisan Tulisan ini didapat dari berbagai sumber bacaan literatur skripsi, jurnal, beberapa buku dan browsing dari internet. Adapun sistematika tulisan ini mencakup empat bab, yaitu: BAB I Pendahuluan Bab ini menjelaskan tentang latar belakang masalah, ruang lingkup, tujuan dan sistematika penulisan. BAB II Materi Pendukung Bab ini menjelaskan tentang definisi graf, macam-macam graf, jenis-jenis pelabelan graf. BAB III Pembahasan Bab ini menjelaskan tentang pelabelan total tak teratur titik pada graf mCn. BAB IV Penutup Bab ini berisikan kesimpulan dan saran dari materi yang telah dibahas.

3

BAB II MATERI PENDUKUNG A. Definisi Graf Sebuah graf G berisikan dua himpunan yaitu himpunan hingga tak kosong V(G) yang elemen-elemennya disebut titik dan himpunan (mungkin kosong) E(G) yang elemen-elemennya diebut sisi, sedemikian sehingga setip E(G)

elemen e dalam V (G) .

V (G)

adalah sebuah pasangan tidak berurutan dari titik di E(G)

disebut himpunan titik-titik dari G dan

disebut

himpunan sisi dari G. Secara matematis, graf didefenisikan sebagai pasangan himpunan (V,E) ditulis dengan notasi

G=(V , E)

tidak

simpul-simpul

kosong

dari

yang dalam hal ini V adalah himpunan atau

titik

yang

ditulis

dengan

{v 1 , v 2 , … , v n } dan E adalah himpunan sisi yang menghubungkan sepasang simpul / titik yang ditulis dengan {e 1 , e2 , … , en } . Defenisi-defenisi diatas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai sisi satu buah oun, tetapi simpul/titik nya harus ada, minimal satu. Graf yang hanya mempunyai satu simpul tanpa sebuah sisi pun dinamakan graf trivial. Sebuah graf yang tidak memiliki gelung atau tidak memiliki sisi rangkap disebut graf sederhana. Sedangkan graf yang memiliki sisi rangkap tetapi tidak memiliki gelung disebut dengan graf rangkap. Kemudian graf yang tidak memiliki sisi disebut dengan graf kosong. B. Macam-macam Graf Berikut ini adalah beberapa jenis graf yang perlu diketahui: 1. Graf Sederhana Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi ganda.

4

Gambar graf sederhana: P

S

Q

R Gambar 2.1 graf sederhana

2. Graf Lengkap Graf lengkap merupakan graf sederhana yang setiap titik nya terhubung (oleh satu sisi) kesemua titik lainnya. Dengan kata lain, setiap titiknya bertetangga. Graf lengkap denagan n buah titik dilambangkan dengan Kn. Jumlah sisi pada sebuah graf lengkap yang terdiri dari n buah titik adalah n−¿ ¿ sisi. n¿ ¿ Gambar graf lengkap:

v

v

v

v

v

Gambar 2.2 graf lengkap

3. Graf lingkaran Graf lingkaran merupakan graf sederhana yang setiap titik nya berderajat dua. Graf lingkaran dengan n simpul/titik dilambangkan Cn .

5

(b)

(a) Gambar 2.3 (a) graf

C3 (b) graf c 6

4. Graf berbobot Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot). Gambar graf berbobot: c 1 a

1 2

b

Gambar 2.4 graf berbobot

C. Defenisi Pelabelan Graf Pelabelan pada suatu graf adalah pemetaan yang memasangkan unsurunsur graf (titik/sisi) dengan bilangan bulat positif. Jika domainnya adalah sisi maka pelabelannya disebut pelabelan sisi (edge labelling), jika domainnya adalah titik maka pelabelannya disebut pelabelan titik (vertex labelling) dan jika domainnya adalah sisi dan titik maka pelabelannya disebut pelabelan total (total labelling). Bobot (weight) dari elemen graf adalah jumlah dari semua label yang berhubungan dengan elemen graf tersebut. Bobot dari titik v dengan pelabelan f adalah

wt ( v )=f ( v )+ ∑ f ( uv ) . Sedangkan bobot dari uv adalah uvϵE

wt ( uv )=f ( u ) +f (v ) .

6

Salah satu jenis pelabelan adalah pelabelan total tak teratur. Pelabelan total tak teratur pertama kali diperkenalkan oleh M. Baca, dkk pada tahun 2007. Pelabelan tak teratur total terdiri dari pelabelan total tak teratur sisi, pelabelan total tak teratur titik dan pelabelan total tak teratur total. 1.

Pelabelan Total Tak Teratur Sisi Defenisi 2.1 : Pelabelan-k total dikatakan pelabelan-k total tak teratur sisi dari graf G, jika untuk sembarang dua sisi

e=u1 v 1

yang

wt ( e)≠ wt ( w )

berbeda

dari

graf

wt ( e )=f ( u1 ) + f ( e ) + f (v 1 )

G

dan

berlaku

dan

w=u2 v 2

dengan

wt ( w )=f ( u1 ) +f ( w ) +f (v 1 ) . Nilai total

ketakteraturan sisi (total edge irregularity) dari graf G, yang dinotasikan dengan

tes(G)

adalah label terbesar minimum yang digunakan untuk

melabeli graf G dengan pelabelan total tak teratur sisi. Penelitian mengenai

tes(G)

dimulai oleh Baca, dkk pada makalah

“On-Irregular Total Labelling”. Pada makalah tersebut, diberikan batas atas dan batas bawah seperti dituliskan pada Teorema 2.1 G=(V , E)

Teorema 2.1 Misalkan himpunan titik V ⌈

2.

|E|+ 2 3

adalah suatu graf dengan

dan himpunan sisi tak kosong

E , maka:

⌉ ≤tes(G) ≤|E|

Pelabelan total tak teratur titik Defenisi 2.2 : Pelabelan-k total dikatakan pelabelan-k total tak teratur titik dari graf G, jika untuk setiap titik wt ( x)≠ wt ( y ) , dimana

x

dan

y yang berbeda maka

wt ( x ) + ∑ f (ux ) . Nilai total ketakteraturan ux∈ E

titik (total vertex irregularity strength) dari graf G, yang dinotasikan dengan

tvs(G)

adalah label terbesar minimum yang digunakan untuk

melabeli graf G dengan pelabelan total tak teratur titik. Penelitian mengenai

tvs(G)

dimulai oleh Baca, dkk pada makalah

“On-Irregular Total Labelling”. Pada makalah tersebut, diberikan batas atas dan batas bawah seperti dituliskan pada Teorema 2.2

7

Teorema 2.2 Misalkan

– (p , q)

dengan derajat minimum

δ

dan

derajat maksimum ∆ , maka: ⌈

p+δ ⌉ ≤tvs ( G ) ≤ p+ ∆−2 δ +1 ∆+1

3. Pelabelan total tak teratur total Defenisi 2.3 : Pelabelan-k total dikatakan Pelabelan-k total tak teratur total dari graf G, jika untuk setiap titik

x

wt ( x)≠ wt ( y ) , dan untuk setiap

x1 x2

maka

dan dan

y

yang berbeda maka y1 y2

yang berbeda

y1 y2 ). Nilai ketakteraturan total (totally irregularity wt ( x1 x 2)≠ wt ¿

strength) dari graf G, yang dinotasikan dengan

ts(G)

adalah label

terbesar minimum yang digunakan untuk melabeli graf G dengan pelabelan total tak teratur total. D. Langkah-langkah Menentukan Nilai Total Ketakteraturan Titik Adapun langkah-langkah yang digunakan dalam menentukan nilai total ketakteraturan titik dari m -copy graf lingkaran sebagai berikut : 1. Diberikan graf mCn 2. Menentukan batas bawah dari tvs (mCn) untuk m 1 dan n 2(mod 3) dengan menggunakan Teorema 2.2, yaitu: ⌈

p+δ ⌉  tvs (G)  p +  - 2 + 1 ∆+1

3. Menentukan pelabelan-k total tak teratur titik dari graf mCn untuk m=1, 2, 3,...,10 dan n = 5,8,11 dengan menggunakan label terbesar sebesar batas bawah yang diperoleh pada Langkah 2. 4. Menentukan rumus untuk pelabelan titik dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada pola pelabelan yang terdapat pada Langkah 3.

8

5. Menentukan rumus untuk pelabelan sisi dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada pola pelabelan yang terdapat pada Langkah 3. 6. Menentukan rumus bobot titik dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada Langkah 4 dan Langkah 5. 7. Membuktikan bahwa mCn merupakan pelabelan total tak teratur titik pada graf mCn untuk m1 dan n2(mod3) E. Batas Bawah dari Nilai Total Ketakteraturan Titik / Total Vertex Irregularity Strength (TVS) Graf mC n Menentukan batas bawah dari tvs (mCn) untuk m  1 dan n  2(mod3), berdasarkan Teorema 2.2, yaitu ⌈

p+δ ⌉ ≤tvs ( G ) ≤ p+ ∆−2 δ +1 , dimana p=n.m dan ==2 ∆+1

mC (¿¿ n) V¿ , ¿ +δ (mC n ) ¿ ¿ ⌈¿ sehingga diperoleh

= ⌈

=

nm+2 ⌉ ≤tvs ( mC n ) ≤ nm +2−2(2)+1 2+1

⌈

nm +2 ⌉ ≤tvs ( mC n ) ≤ nm−1 3

Sehingga diperoleh batas bawah untuk nilai ketakteraturan total graf mC n , adalah :

tvs (mCn) ≤

⌈

nm+2 ⌉ 3

…………………………..(1)

9

F.

Pelabelan Titik, Sisi, dan Bobot titik pada

mC n

untuk m  1 dan

n2(mod3) 1. Pelabelan titik pada graf mCn, untuk m  1 dan n  2(mod3) adalah sebagai berikut.

(vi)=

untuk i  n (mod 3n) i+2 ⌈ ⌉ 3 untuk i  n +1 (mod 3n) i ⌈ ⌉ 3 untuk i lainnya i+1 ⌈ ⌉ 3

{

2. Pelabelan sisi pada graf mCn, untuk m  1 dan n  2(mod3) adalah sebagai berikut. (ei)= ⌈

i+1 ⌉ untuk 1  i  3 nm

3. Berdasarkan pelabelan di atas, dapat dihitung bobot titik pada graf mCn, untuk n2(mod3) sebagai berikut: a. Untuk i  n +1 (mod 3n) wt(vi) = (vi)+(ei)+(ei+1) =

i i+1 i+1+1 ⌈ ⌉+⌈ ⌉+ ⌈ ⌉ 3 3 3

i i+1 i+ 2 ⌉+ ⌈ ⌉ = ⌈ ⌉+⌈ 3 3 3 b. Untuk i  1 (mod 3n) dan i  2n +1 (mod 3n) wt(vi) = (vi)+(ei)+(ei+1) =

⌈

i +1 i+1 i+1+1 ⌉+⌈ ⌉+⌈ ⌉ 3 3 3

= 2⌈

i+1 i+ 2 ⌉+ ⌈ ⌉ 3 3

10

c. Untuk i  n (mod 3n) wt(vi) = (vi)+(ei)+(ei+1) =

⌈

= ⌈

i +2 i−1+1 i+1 ⌉+⌈ ⌉+⌈ ⌉ 3 3 3

i+2 i i+ 1 ⌉ + ⌈ ⌉+ ⌈ ⌉ 3 3 3

d. Untuk i  2n (mod 3n) dan i  0 (mod 3n) wt(vi) = (vi)+(ei)+(ei+1) =

⌈

i +1 i−1+1 i+1 ⌉+⌈ ⌉+⌈ ⌉ 3 3 3

= 2⌈

i+1 i ⌉+ ⌈ ⌉ 3 3

e. Untuk i lainnya wt(vi) = (vi)+(ei)+(ei+1) =

⌈

= ⌈

i +1 i−1+1 i+1+1 ⌉+⌈ ⌉+⌈ ⌉ 3 3 3

i+1 i i+ 2 ⌉ + ⌈ ⌉+ ⌈ ⌉ 3 3 3

Adapun rumus untuk bobot titik dari graf mCn, untuk m1 dan n2(mod3) adalah sebagai berikut.

wt (vi) =

untuk i  1 (mod 3n) dan i  2n +1 (mod 3n) i+ 1 i+ 2 2⌈ ⌉+⌈ ⌉ 3 3 untuk i  2n (mod 3n) dan i  0 (mod 3n) i+1 i 2⌈ ⌉+⌈ ⌉ 3 3 untuk i lainnya i+1 i i+2 ⌈ ⌉+ ⌈ ⌉ + ⌈ ⌉ 3 3 3

{

11

Bobot titik dari graf mCn dimana m  1 dan n2(mod3) adalah bilangan bulat positif berurutan yaitu i+2, dengan i = 1, 2, 3, …nm, atau dengan kata lain bobot titik dari graf mCn adalah bilangan bulat positif berurutan mulai dari 3 sampai dengan nm+2, sehingga bobot setiap titiknya berbeda semua. Jadi, ⌈

nm +2 ⌉ 3

……………………...(2)

Oleh karena itu, tvs (mCn)  ⌈

nm+2 ⌉ 3

dari persamaan (1) dan tvs

tvs (mCn) 

(mCn) ⌈

nm +2 ⌉ 3

dari persamaan (2) terbukti bahwa: nm+2 ⌉ tvs (mCn) = ⌈ 3 BAB III

BAB III PEMBAHASAN A. Pemberian Nama Titik dan Sisi pada Graf mCn Defenisi 3.1: Graf mCn merupakan sebuah graf yang diperoleh dengan menggandakan graf Cn sebanyak m, dimana untuk setiap himpunan titik dari graf penggandaan tidak ada yang beririsan. Adapun pemberian nama titik dan sisi pada graf mCn sebagai berikut: 1. Pemberian nama titik dan sisi pada graf mCn untuk n ganjil. Graf n C hasil penggandaan ke-i adalah

v(i-1)n+1 e(i-1)n+2 v(i-1)n+3 e(i-1)n+4…ein-1 vin ein vin-1 ein-2 vin-3 ein-4 …e(i-1)n+3 v(i-1)n+2 e(i-1)n+1 v(i-1)n+1 dengan 1  i  m

12

contoh: graf 2C5, yang mana 1  i  2, maka i=1,2 penggandaan ke-1: v1 e2 v3 e4…e4 v5 e5 v4 e3 v2 e1 penggandaan ke 2: v6 e7 v8 e9…e9 v10 e10 v9 e8 v7 e6

e10

e5 e4 v5

e9

v2

v8

v3

v7

e1

e2

v9 e 8

v10

v4 e3

e6

e7

v6

v1 (a)

(b)

Gambar 3.1 (a) pengandaan ke-1 dan (b) penggandaan ke-2 graf 2C5

2. Pemberian nama graf mCn untuk n genap.

Graf n C hasil penggandaan ke-i adalah

v(i-1)n+1 e(i-1)n+2 v(i-1)n+3 e(i-1)n+4…ein vin ein-1 vin-2 ein-3 vin-4…e(i-1)n+3 v(i-1)n+2 e(i-1)n+1 v(i-1)n+1 dengan 1  i  m contoh: graf 2C8, yang mana 1  i  2, maka i=1,2 penggandaan ke-1: v1 e2 v3 e4 v5 e6 v7 e8…e8 v8 e7 v6 e5 v4 e3 v2 e1 penggandaan ke 2: v9 e10 v11 e12 v13 e14 v15 e16…e16 v16 e15 v14 e13 v12 e11 v10 e9

e8 v7

v8

V V

v15

Vv6 V

e6 v5

e16

e7

e5

e3

e4 v3

V vV2

V

e2

v1

e1

e15

V V

vV14 V

e14

v4 v13

V

v16

e13 v12

V

e11

e12

V Vv10

V

v11

e10

v9

e9 13

(a)

(b)

Gambar 3.1 (a) pengandaan ke-1 dan (b) penggandaan ke-2 graf 2C8

B. Penentuan Batas Bawah dari Nilai Total Ketakteraturan Titik/Total Vertex Irregularity Strength (TVS) Graf mC n Menentukan batas bawah dari tvs (mCn) untuk m  1 dan n  2(mod3), dapat menggunakan rumus yang telah dibuktikan sebelumnya, yaitu: tvs (mCn) =

⌈

nm +2 ⌉ 3

Contoh: Diberikan graf 1C5, maka tvs (1C5) =

⌈

7 5(1)+2 ⌉ = ⌈ ⌉ =3 3 3

Sehingga didapat bahwa nilai batas bawah dari nilai ketakteraturan titik untuk graf

1C 5

adalah 3, yang digunakan sebagai label

terbesarnya. C. Pelabelan Total Tak Teratur Titik pada Graf 1C5 (untuk n ganjil) Berikut akan dilakukan pelabelan total pada graf 1C 5 . Langkah 1: Menentukan batas bawah dari tvs (mCn). Pada contoh sebelumnya telah didapat bahwa tvs (1C5) adalah 3. Langkah 2: Menentukan pelabelan-k total tak teratur titik dari graf mCn untuk m=1, 2, 3,...,10 dan n = 5,8,11 dengan menggunakan label terbesar sebesar batas bawah pada tvs. Berdasarkan langkah 1, maka akan ditentukan pelabelan-3 total tak teratur titik dari graf 1C5.

14

Langkah 3: Menentukan rumus untuk pelabelan titik dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada pola pelabelan yang terdapat pada Langkah 2. (v1) ¿ ⌈

i+1 1+1 ⌉=⌈ ⌉=1 3 3

(v2) ¿ ⌈

i+1 2+1 ⌉=⌈ ⌉=1 3 3

(v3) ¿ ⌈

i+1 3+1 ⌉=⌈ ⌉=2 3 3

(v4) ¿ ⌈

i+1 4+ 1 ⌉=⌈ ⌉=2 3 3

(v5) ¿ ⌈

i+2 5+2 ⌉=⌈ ⌉=3 3 3

Langkah 4: Menentukan rumus untuk pelabelan sisi dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada pola pelabelan yang terdapat pada Langkah 2. (e1) ¿ ⌈

i+1 1+1 ⌉=⌈ ⌉=1 3 3

(e2) ¿ ⌈

i+1 2+1 ⌉=⌈ ⌉=1 3 3

(e3) ¿ ⌈

i+1 3+1 ⌉=⌈ ⌉=2 3 3

(e4) ¿ ⌈

i+1 4+ 1 ⌉=⌈ ⌉=2 3 3

(e5) ¿ ⌈

i+1 5+ 1 ⌉=⌈ ⌉=2 3 3

Langkah 5: Menentukan rumus bobot titik dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada Langkah 3 dan Langkah 4.

2 e5

3 v5 2 e4

2 v4

e3 2 v

15

2

v2

v3 e2 1

v1

e1

1

1

1

Gambar 3.3 penggandaan ke-1 graf 1C5

wt(v1) = (v1) + (e1) + (e2) = 1+1+1 = 3 wt(v2) = (v2) + (e1) + (e3) = 1+1+2 = 4 wt(v3) = (v3) + (e2) + (e4) = 2+1+2 = 5 wt(v4) = (v4) + (e3) + (e5) = 2+2+2 = 6 wt(v5) = (v5) + (e4) + (e5) = 3+2+2 = 7 Atau dengan menggunakan rumus, yaitu wt ( v i )=⌈

i+1 i i+2 ⌉ +⌈ ⌉ +⌈ ⌉ 3 3 3

wt ( v 1) =⌈

1+1 1 1+2 ⌉+⌈ ⌉+⌈ ⌉ =3 3 3 3

wt ( v 2 )=⌈

2+1 2 2+2 ⌉+⌈ ⌉+⌈ ⌉ =4 3 3 3

wt ( v 3 )=⌈

3+1 3 3+2 ⌉ +⌈ ⌉ + ⌈ ⌉=5 3 3 3

wt ( v 4 ) =⌈

4 +1 4 4 +2 ⌉+⌈ ⌉+⌈ ⌉=6 3 3 3

wt ( v 5 )=⌈

5+1 5 5+ 2 ⌉+ ⌈ ⌉ + ⌈ ⌉ 3 3 3

=7

Langkah 6: Membuktikan bahwa mCn merupakan pelabelan total tak teratur titik pada graf mCn untuk m1 dan n2(mod3). Berdasarkan pada Langkah 5, karena terbukti bahwa bobot setiap titiknya berbeda maka pelabelan tersebut merupakan pelabelan-3 total tak teratur titik pada 1C 5 .

16

Sehingga dapat disimpulkan bahwa berdasarkan defenisi 2.2, maka pelabelan ini adalah pelabelan-3 total tak teratur titik yang optimal pada 1C 5 . D. Pelabelan Total Tak Teratur Titik pada Graf 1C8 (untuk n genap) Berikut akan dilakukan pelabelan total pada graf 1C 8 . Langkah 1: Menentukan batas bawah dari tvs (mCn). tvs (1C8) =

⌈

10 8( 1)+2 ⌉ = ⌈ ⌉ =4 3 3

Langkah 2: Menentukan pelabelan-k total tak teratur titik dari graf mCn untuk m=1, 2, 3,...,10 dan n = 5,8,11 dengan menggunakan label terbesar sebesar batas bawah pada tvs. Berdasarkan langkah 1, maka akan ditentukan pelabelan-4 total tak teratur titik dari graf 1C8. Langkah 3: Menentukan rumus untuk pelabelan titik dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada pola pelabelan yang terdapat pada Langkah 2. (v1) ¿ ⌈

i+1 1+1 ⌉=⌈ ⌉=1 3 3

(v5) ¿ ⌈

i+1 5+ 1 ⌉=⌈ ⌉=2 3 3

(v2) ¿ ⌈

i+1 2+1 ⌉=⌈ ⌉=1 3 3

(v6) ¿ ⌈

i+1 6+1 ⌉=⌈ ⌉=3 3 3

(v3) ¿ ⌈

i+1 3+1 ⌉=⌈ ⌉=2 3 3

(v7) ¿ ⌈

i+1 7 +1 ⌉=⌈ ⌉=3 3 3

(v4) ¿ ⌈

i+1 4+ 1 ⌉=⌈ ⌉=2 3 3

(v8) ¿ ⌈

i+1 8+2 ⌉=⌈ ⌉=4 3 3

Langkah 4: Menentukan rumus untuk pelabelan sisi dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada pola pelabelan yang terdapat pada Langkah 2.

17

(e1) ¿ ⌈

i+1 1+1 ⌉=⌈ ⌉=1 3 3

(e5) ¿ ⌈

i+1 5+ 1 ⌉=⌈ ⌉=2 3 3

(e2) ¿ ⌈

i+1 2+1 ⌉=⌈ ⌉=1 3 3

(e6) ¿ ⌈

i+1 6+1 ⌉=⌈ ⌉=3 3 3

(e3) ¿ ⌈

i+1 3+1 ⌉=⌈ ⌉=2 3 3

(e7) ¿ ⌈

i+1 7 +1 ⌉=⌈ ⌉=3 3 3

(e4) ¿ ⌈

i+1 4+ 1 ⌉=⌈ ⌉=2 3 3

¿⌈

(e8)

i+1 8+1 ⌉=⌈ ⌉=3 3 3

Langkah 5: Menentukan rumus bobot titik dari graf mCn untuk m1 dan n2(mod3) dengan mengacu pada Langkah 3 dan Langkah 4.

Gambar 3.4 penggandaan ke-1 graf 1C8

wt(v1) = (v1) + (e1) + (e2) = 1+1+1 = 3 wt(v2) = (v2) + (e1) + (e3) = 1+1+2 = 4 wt(v3) = (v3) + (e2) + (e4) = 2+1+2 = 5 wt(v4) = (v4) + (e3) + (e5) = 2+2+2 = 6 wt(v5) = (v5) + (e4) + (e6) = 2+2+3 = 7 wt(v6) = (v6) + (e5) + (e7) = 3+2+3 = 8 wt(v7) = (v7) + (e6) + (e8) = 3+3+3 = 9

18

wt(v8) = (v8) + (e7) + (e8) = 4+3+3 = 7 Langkah 6: Membuktikan bahwa mCn merupakan pelabelan total tak teratur titik pada graf mCn untuk m1 dan n2(mod3). Berdasarkan pada Langkah 8, karena terbukti bahwa bobot setiap titiknya berbeda maka pelabelan tersebut merupakan pelabelan-4 total tak teratur titik pada 1C 8 . Sehingga dapat disimpulkan bahwa berdasarkan defenisi 2.2, maka pelabelan ini adalah pelabelan-4 total tak teratur titik yang optimal pada 1C 8 .

19

BAB IV PENUTUP A. Kesimpulan Berdasarkan hasil dan pembahasan tentang nilai total ketakteraturan titik dari m-copy graf lingkaran, dapat disimpulakan bahwa nilai total ketakteraturan titik dari m-copy graf lingkaran adalah tvs (mCn) =

⌈

nm +2 ⌉ 3

untuk m1

dan n2(mod3) sehingga n = 5, 8, 11, 14,… Adapun untuk menentukan nilai total ketakteraturan titik perlu untuk menentukan tvs, pelabelan-k total tak teratur titik, pelabelan titik, pelabelan sisi, dan bobot titik dari graf mCn. Untuk graf

1C 5 karena terbukti bahwa bobot setiap titiknya berbeda

maka pelabelan tersebut merupakan pelabelan-3 total tak teratur titik yang oprimal pada 1C 5 . Sedangkan untuk graf

1C 8 karena terbukti bahwa bobot setiap titiknya

berbeda maka pelabelan tersebut merupakan pelabelan-4 total tak teratur titik yang oprimal pada 1C 8 B. Saran Dalam pembahasan ini, penulis mencari nilai ketakteraturan titik dari mcopy graf lingkaran untuk m1 dan n2(mod3). Selanjutnya, penulis menyarankan kepada pembaca untuk dapat menentukan nilai ketakteraturan sisi pada m-copy graf lingkaran untuk m1 dan n2(mod3).

20

DAFTAR REFERENSI Ahmad, A., Bača, M., dan Bashir, Y. “Total Vertex Irregularity Strength of Certain Classes of Unicyclic Graphs”. Bull. Math. Soc. Sci. Math. Roumanie. Vol.57 (105) No. 2 (2014) 147-152. Bača, M., Jendrol J., Miller, M., dan Ryan, J. “On Irregular Total Labellings,” Discrete Math. Vol. 307 (2007) 1378-1388.

21