Jurnal Ilmiah Soul Math Vol 4. No. 5,

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

IMPLEMENTASI ALGORITMA MODIFIKASI BROYDEN-FLETCHERGOLDFARB-SHANNO (MBFGS)

Rahmawati Erma Standsyah FKIP, Universitas Dr. Soetomo

Abstract: The concept of minimum resolving set has proved to be useful and or related to a variety of fields such as Chemistry, Robotic Navigation, and Combinatorial Search and Optimization. Two graph are path graph (𝑃𝑛 ) anf circle graph (𝐶𝑚 ). The corona product 𝑃𝑛 ⨀ 𝐶𝑚 is defined as the graph obtained from 𝑃𝑛 and 𝐶𝑚 by taking one copi of 𝑃𝑛 and 𝑚1 copies of 𝐶𝑚 and joining by an edge each vertex from the 𝑛𝑡ℎ copy of 𝑃𝑛 with the 𝑚𝑡ℎ vertex of 𝐶𝑚 . 𝑃𝑛 ⨀ 𝐶𝑚 and 𝐶𝑚 ⨀𝑃𝑛 not commute to 𝑛 ≠ 𝑚, it is showed that order of graph 𝑃𝑛 ⨀ 𝐶𝑚 different with graph 𝐶𝑚 ⨀𝑃𝑛 . Based on research obtained 𝑑𝑖𝑚(𝑃𝑛 ⨀𝐶𝑚 ) = 𝑛. 𝑑𝑖𝑚(𝑊1,𝑚 ) dan 𝑑𝑖𝑚(𝐶𝑚 ⨀𝑃𝑛 ) = 𝑚. 𝑑𝑖𝑚 (𝐾1 + 𝑃𝑛 ) Keyword : Resolving Sets, Metric Dimension, Path Graph, Circle Graph, Corona Graph

Pendahuluan Dimensi Metrik menjadi menarik untuk

Untuk himpunan terurut W = {w1 , w2 , ...,

dibahas karena konsep himpunan pemisah yang

wk } dari vertex-vertex dalam graf terhubung

mempunyai

telah

G dan vertex v ∈ V (G), representasi dari

pembahasan

v terhadap W adalah k-vektor r (v|W ) =

pada bidang lain seperti Kimia (Chartrand,

(d(v, w1 ), d(v, w2 ), ..., d(v, wk )) Jika r(v|W )

dkk, Boundary vertices in Graph and Poisson

untuk setiap vertex v ∈ V (G) berbeda, maka

terbukti

kardinalitas

minimum

sangat berguna untuk

and Zhang, The Metric Dimension of unicyclic graphs),

Navigasi

Robot

dan

Pencarian

(Khuller,

Raghavachari,

and

Rosenfeld,

Landmarks

in

dan

Optimasi

graphs)

W

panjang

disebut

himpunan

pemisah

tersebut dinamakan dimensi

ini merupakan kajian yang sedang marak

Misalkan u dan v adalah

adalah

minimum

kardinalitas

Kajian tentang dimensi metric pada graf

dibicarakan. Terbukti dengan adanya banyak

vertex-vertex dalam graf terhubung G, maka d(u, v)

dengan

metric dari 𝐺 dinotasikan 𝑑𝑖𝑚(𝐺) [1].

adalah kardinalitas

minimum himpunan pemisah (resolving set)

jarak

pemisah

basis metrik

generator of graphs) (Hernando, dkk, 1).

pada graf G.

Himpunan

minimum (basis metrik), dan kardinalitas dari

Kombinasi (Sebo and Tannier, On Metric

Dimensi Metrik

disebut himpunan pemisah dari V (G).

jurnal

lintasan

dan

penelitian-penelitian

yang

membahas tentang kajian ini [1-6], misalnya

terpendek antara u dan v pada G.

Dimensi Metrik Graft Kincir dengan Pola

244

𝐾1 + 𝑚𝐾3 [1], Resolvability in graph and the


metric dimention of a graph [2], On the

{a1 , a2 , ..., an } dan simpul pada graf Cm

Metric Dimension of Corona Product Graph

diberi label V (Cm ) = {𝑏1 , 𝑏2 , . . . , 𝑏𝑚 } dengan

[3], On the Metric Dimension of Some Families

of

Graphs

[4],On

the

jumlah

metric

membahas

dihitung

dimensi

metrik

Berdasarkan

pemisalan-pemisalan

tersebut

maka graf H memiliki 𝑛 + 𝑚𝑛 simpul yaitu 𝑉 (𝐻 ) = {{𝑎1 , 𝑎2 , … , 𝑎𝑛 },

Diberikan dua graf yaitu graf path

{𝑏1,1 , 𝑏1,2 , … , 𝑏1, 𝑚 }, {𝑏1,1 , 𝑏1,2, … , 𝑏1, 𝑚 }

yang disimbolkan dengan 𝑃𝑛 dan graf circle

, … , {𝑏𝑛, 1 , 𝑏𝑛, 2 , . . . , 𝑏𝑛 , 𝑚 }}

yang disimbolkan dengan 𝐶𝑚 . Operasi corona

Graf 𝑃1 ⨀ 𝐶𝑚 bentuknya sama

𝑃𝑛 ⨀ 𝐶𝑚 adalah graf yang diperoleh dari

dengan graf Wheel W1,m . Graf Wheel ini

𝑃𝑛 dan 𝐶𝑚 dengan mengambil 1 graf 𝑃𝑛 yang

memiliki dimensi metrik sebanyak [3]:

masing-

2 𝑢𝑛𝑡𝑢𝑘 𝑚 = 3,4 3 𝑢𝑛𝑡𝑢𝑘 𝑚 = 5,6 dim(𝑊1,𝑚 ) = � 2𝑚 + 2 � 𝑢𝑛𝑡𝑢𝑘 𝑚 ≥ 7 � 5

dihubungkan pada

setiap simpul graf. 𝑃𝑛 ⨀ 𝐶𝑚 dan 𝑃𝑛 ⨀ 𝐶𝑚

tidak bersifat komutatif untuk 𝑛 ≠ 𝑚. Hal ini ditunjukkan bahwa order graf 𝑃𝑛 ⨀ 𝐶𝑚 dengan

Sedangkan graf H

sama. Sehingga pada

bentuknya sama dengan

graf W1,m sebanyak n buah dengan masing-

tulisan ini dihitung besar nilai dimensi metrik

masing pusatnya terhubung.

dari

Untuk menentukan dimensi metrik graf

graf 𝑃𝑛 ⨀ 𝐶𝑚 dan graf 𝐶𝑚 ⨀ 𝑃𝑛 .

H dilakukan pencarian batas bawah dan batas atas.

Dimensi Metrik Graf 𝑃𝑛 ⨀ 𝐶𝑚

Dengan

bentuk

graf

𝑃1 ⨀ 𝐶𝑚

memenuhi persamaan (1) diperoleh paling sedikitnya memenuhi aturan anggota himpunan

Graf 𝑃𝑛 ⨀ 𝐶𝑚 graf yang diperoleh dari Pn

pembeda pada graf wheel. Oleh karena graf H

dan Cm dengan mengambil 1 graf Pn yang

teratur memiliki

masing-masing simpul graf Pn dihubungkan

n buah graf wheel yang

pusatnya saling terhubung maka jelas bahwa

pada setiap simpul graf Cm sehingga graf H

batas

yaitu H =𝑃𝑛 ⨀ 𝐶𝑚 memiliki jumlah simpul sebanyak 𝑛 + 𝑚𝑛.

yang

ke-n memiliki label 𝑏𝑛, 1 , 𝑏𝑛, 2 , . . . , 𝑏𝑛, 𝑚 .

dengan

sebelumnya.

graf 𝐶𝑚 ⨀ 𝑃𝑛 tidak

buah.

yang dikoronakan dengan simpul Pn

mengembangkan graf-graf yang telah dikerjakan

masing simpul graf 𝑃𝑛

nm

𝑏1,1 , 𝑏1,2 , . . . , 𝑏1, 𝑚 sehingga simpul graf Cm

tentang

dimensi metrik pada graf. Oleh karena itu pada tulisan

sebanyak

dengan simpul Pn yang pertama dilabelkan

metric dimension of line graphs [6] dan lain Semuanya

)

Dimisalkan simpul graf Cm yang dikoronakan

dimension of circulant graphs [5] , On the

sebagainya.

V (Cm

bawah

dim(𝐻) = dim(𝑃𝑛 ⨀𝐶𝑚 ) =

𝑛. 𝑑𝑖𝑚 �𝑊1,𝑚 �. Untuk menentukan batas atas

Simpul-simpul yang ada

dimensi metrik graf H dilakukan konstruksi.

pada graf Pn misalkan diberi label V (Pn ) =

245

Kasus 1 m = 3


𝑟(𝑎𝑛 |𝑊 ) = (𝑛, 𝑛, . . . , 2, 2, 1, 1)

Misalkan diambil himpunan pembeda 𝑊 = {𝑏1,1 , 𝑏1,2 , 𝑏2,1 , 𝑏2,2 , . . . , 𝑏𝑛, 1, 𝑏𝑛, 2 }

Dapat dilihat bahwa setiap simpul memiliki

maka diperoleh representasi terhadap W : 𝑟(𝑏1,3 |𝑊 ) = (2, 1, 3, 3, 4, 4, … , 𝑛

dengan

𝑟(𝑏2,3 |𝑊 ) = (3, 3, 2, 1, 3, 3, 4, 4, … , 𝑛, 𝑛),

𝑚=4

representasi yang berbeda-beda terhadap W,

+ 1, +1),

𝑟(𝑏𝑛, 3 |𝑊 ) = (𝑛 + 1, 𝑛

⋮

Kasus 3 𝑚 = 5

Misalkan

+ 1, . . . , 4, 4, 3, 3, 2, 1),

𝑟(𝑎𝑛 |𝑊 ) = (𝑛, 𝑛, . . . , 2, 2, 1, 1)

𝑟(𝑏1,2 |𝑊 ) = (1, 1, 2, 3, 3, 3, 4, 4, 4, . . . , 𝑛 + 1, 𝑛 + 1, 𝑛 + 1)

𝑟(𝑏1,4 |𝑊 ) = (2, 1, 1, 3, 3, 3, 4, 4, 4, . . . , 𝑛 + 1, 𝑛 + 1, 𝑛 + 1)

dengan demikian dim(𝐻) = 𝑛. 2 untuk 𝑚 = 3 diambil

himpunan

𝑟(𝑏2,2 |𝑊 ) = (3, 3, 3, 1, 1, 2, 3, 3, 3, . . . , 𝑛, 𝑛, 𝑛)

𝑟(𝑏2,4 |𝑊 ) = (3, 3, 3, 2, 1, 1, 3, 3, 3, … , 𝑛, 𝑛, 𝑛)

pembeda

𝑊 = {𝑏1,1 , 𝑏1,2 , 𝑏2,1 , 𝑏2,2 , . . . , 𝑏𝑛, 1, 𝑏𝑛, 2 }

𝑟(𝑏𝑛, 2 |𝑊 ) = (𝑛 + 1, 𝑛 + 1, +1, 𝑛, 𝑛, 𝑛, …, 𝑟(𝑏𝑛, 4|𝑊 ) = (𝑛 + 1, 𝑛 + 1, 𝑛 + 1, 𝑛, 𝑛, 𝑛, . . . , 3, 3, 3, 2, 1, 1)

𝑟(𝑏1,3 |𝑊 ) = (2, 1, 3, 3, 4, 4, … , 𝑛 + 1, 𝑛 + 1),

𝑟(𝑎1 |𝑊 ) = (1, 1, 1, 2, 2, 2, 3, 3, 3, . . . , 𝑛, 𝑛, 𝑛),

𝑟(𝑏1,4 |𝑊 ) = (1, 2, 3, 3, 4, 4, … , 𝑛 + 1, 𝑛

𝑟(𝑎2 |𝑊 ) = (2, 2, 2, 1, 1, 1, 2, 2, 2, … , 𝑛 − 1, 𝑛 −

+ 1),

1, 𝑛 − 1),

𝑟(𝑏2,3 |𝑊 ) = (3, 3, 2, 1, 3, 3, 4, 4, … , 𝑛, 𝑛), ⋮

Dapat

𝑟(𝑎𝑛 |𝑊 ) = (𝑛, 𝑛, 𝑛, . . . , 2, 2, 2, 1, 1, 1)

memiliki

𝑟(𝑏𝑛, 3 |𝑊 ) = (𝑛 + 1, 𝑛

dilihat

bahwa setiap simpul

representasi yang berbeda-beda

terhadap W , dengan demikian 𝑑𝑖𝑚 (𝐻 ) =

+ 1, … , 4, 4, 3, 3, 2, 1),

𝑛. 3 untuk 𝑚 = 5

𝑟(𝑏𝑛, 4 |𝑊 ) = (𝑛 + 1, 𝑛

+ 1, … , 4, 4, 3, 3, 1, 2),

Kasus 4 m = 6

𝑟(𝑎1 |𝑊 ) = (1, 1, 2, 2, 3, 3, . . . , 𝑛, 𝑛),

𝑟(𝑎2 |𝑊 ) = (2, 2, 1, 1, 2, 2, . . . , 𝑛 − 1, 𝑛 − 1),

⋮

3, 3, 3, 2, 1, 1)

maka diperoleh representasi terhadap W :

𝑟(𝑏2,4 |𝑊 ) = (3, 3, 1, 2, 3, 3, 4, 4, . . . , 𝑛, 𝑛),

pembeda

terhadap W :

⋮

representasi yang berbeda-beda terhadap W,

Misalkan

himpunan

untuk

𝑏𝑛, 1, 𝑏𝑛, 3 , 𝑏𝑛, 5 } maka diperoleh representasi


Kasus 2 𝑚 = 4

diambil

𝑑𝑖𝑚(𝐻 ) = 𝑛. 2

𝑊 = {𝑏1,1 , 𝑏1,3 , 𝑏1,5 , 𝑏2,1 , 𝑏2,3 , 𝑏2,5 …,

𝑟(𝑎1 |𝑊 ) = (1, 1, 2, 2, 3, 3, . . . , 𝑛, 𝑛),

𝑟(𝑎2 |𝑊 ) = (2, 2, 1, 1, 2, 2, . . . , 𝑛 − 1, 𝑛 − 1),

demikian

Misalkan ⋮

246

diambil

himpunan pembeda

𝑊 = {𝑏1,1 , 𝑏1,3 , 𝑏1,5 , 𝑏2,1 , 𝑏2,3 , 𝑏2,5 …,

⋮


𝑏𝑛, 1, 𝑏𝑛, 3 , 𝑏𝑛, 5 }

maka

𝑟(𝑏1, 𝑥 + 3 |𝑊 = (2, 1, 1, 2, … , 3, 3, … , 𝑛 + 1, 𝑛

diperoleh

+ 1, . . . )

representasi terhadap W : 𝑟(𝑏1,2 |𝑊 ) = (1, 1, 2, 3, 3, 3, 4, 4, 4, . . . , 𝑛 + 1, 𝑛 + 1, 𝑛 + 1)

r(b1,m |W ) = (2, 2, 2, ..., 3, 3, ..., n + 1, n + 1, ...)

𝑟(𝑏1,4 |𝑊 ) = (2, 1, 1, 3, 3, 3, 4, 4, 4, . . . , 𝑛 + 1, 𝑛

𝑟(𝑏𝑛, 𝑥 + 1 |𝑊 ) = (𝑛 + 1, 𝑛 + 1, … , 3, 3, …,

+ 1, 𝑛 + 1)

𝑟(𝑏𝑛, 𝑥 + 3 |𝑊 ) = (𝑛 + 1, 𝑛 + 1, … , 3, 3, …,

1, 1, 2, . . . )

𝑟(𝑏2,2 |𝑊) = (3, 3, 3, 1, 1, 2, 3, 3, 3, . . . , 𝑛, 𝑛, 𝑛)

2, 1, 1, . . . )

𝑟(𝑏2,4 |𝑊) = (3, 3, 3, 2, 1, 1, 3, 3, 3, . . . , 𝑛, 𝑛, 𝑛)

𝑟(𝑏2,6 |𝑊 ) = (3, 3, 3, 2, 2, 1, 3, 3, 3, . . . , 𝑛, 𝑛, 𝑛) . 𝑟(𝑏𝑛, 2 |𝑊 ) = (𝑛 + 1, 𝑛 + 1, 𝑛

⋮

+ 1, … , 3, 3, … , 2, 2, 2, . . . )

𝑟(𝑎1 |𝑊 ) = (1, 1, . . . , 2, 2, . . . , 3, 3, . . . , . . . , 𝑛, 𝑛, . . . ),

+ 1, 𝑛, 𝑛, 𝑛, . . . , 3, 3, 3, 1, 1, 2)

𝑟(𝑎2 |𝑊 ) = (2, 2, . . . , 1, 1, . . . , 2, 2, . . . , . . . , 𝑛 − 1, 𝑛

+ 1, 𝑛, 𝑛, 𝑛, . . . , 3, 3, 3, 2, 1, 1)

𝑟(𝑎𝑛 |𝑊 ) = (𝑛, 𝑛, . . . , . . . , 2, 2, . . . , 1, 1, . . . )

− 1, . . . ),

𝑟(𝑏𝑛, 6 |𝑊 ) = (𝑛 + 1, 𝑛 + 1, 𝑛


+ 1, 𝑛, 𝑛, 𝑛, . . . , 3, 3, 3, 2, 2, 1)

r

𝑟(𝑎1 |𝑊 ) = (1, 1, 1, 2, 2, 2, 3, 3, 3, . . . , 𝑛, 𝑛, 𝑛), − 1, 𝑛 − 1),

memiliki

Berdasarkan konstruksi dari 5 kasus diatas

⋮

dapat dinyatakan bahwa batas atas untuk dimensi

𝑛. 𝑑𝑖𝑚(𝑊1, 𝑚 ) untuk n ≥ 1 dan 𝑚 > 1.

Lemma: Jika 𝑃𝑛 ⨀ 𝐶𝑚 dengan 𝑛 ≥ 1 dan

Kasus 5 m ≥ 7

himpunan

𝑥=�

2𝑚+2 5

�

dan

adalah

dengan batas bawah maka 𝑑𝑖𝑚 𝑃𝑛 ⨀ 𝐶𝑚 =

representasi yang berbeda-beda

terhadap W , dengan demikian 𝑑𝑖𝑚 (𝐻 ) = Misalkan

𝑃𝑛 ⨀ 𝐶𝑚

metrik

𝑛. 𝑑𝑖𝑚(𝑊1, 𝑚 ). Oleh karena batas atas sama

bahwa setiap simpul

𝑛. 3 untuk 𝑚 = 6

5

𝑚 ≥ 7

𝑟(𝑎𝑛 |𝑊 ) = (𝑛, 𝑛, 𝑛, . . . , 2, 2, 2, 1, 1, 1)

dilihat

representasi yang berbeda-beda terhadap W , dengan demikian 𝑑𝑖𝑚 (𝐻 ) = 𝑛. �2𝑚+2� untuk

𝑟(𝑎2 |𝑊 ) = (2, 2, 2, 1, 1, 1, 2, 2, 2, . . . , 𝑛 − 1, 𝑛

Dapat

⋮

𝑟(𝑏𝑛, 𝑚 |𝑊 ) = (𝑛 + 1, 𝑛

𝑟(𝑏𝑛, 4 |𝑊 ) = (𝑛 + 1, 𝑛 + 1, 𝑛 5

⋮

+ 1, 𝑛 + 1)

𝑟(𝑏1,6 |𝑊 ) = (2, 2, 1, 3, 3, 3, 4, 4, 4, . . . , 𝑛 + 1, 𝑛

⋮

𝑚 > 1

diambil

merupakan

graf

teratur

maka

𝑑𝑖𝑚 (𝑃𝑛 ⨀ 𝐶𝑚 ) = 𝑛. 𝑑𝑖𝑚(𝑊1, 𝑚 ).

pembeda

𝑊 = {𝑏1,1 , 𝑏1,3 , … , 𝑏1, 𝑥 , 𝑏2,1 ,

Bukti: Dengan bentuk

graf

𝑃𝑛 ⨀ 𝐶𝑚

𝑏2,3 , … , 𝑏2, 𝑥 … , 𝑏𝑛, 1, 𝑏𝑛, 3 , . . . , 𝑏𝑛, 𝑥

memenuhi persamaan (1) diperoleh paling

maka diperoleh representasiterhadap W :

himpunan pembeda pada graf wheel. Oleh

𝑟(𝑏1, 𝑥 + 1 |𝑊) = (1, 1, 2, … , 3, 3, 3, … , 𝑛

karena graf H teratur memiliki n buah graf

+ 1, 𝑛

+ 1, . . . )

sedikitnya

memenuhi

aturan

anggota

wheel yang pusatnya saling terhubung maka

247


jelas

bahwa

batas

𝑑𝑖𝑚 𝑃𝑛 ⨀ 𝐶𝑚 = 𝑛. (𝑊1,𝑚 )

bawah 𝑑𝑖𝑚 (𝐻 ) =

dim(𝐾1 + 𝑃𝑛 )

2 𝑢𝑛𝑡𝑢𝑘 𝑚 = 3,4 3 𝑢𝑛𝑡𝑢𝑘 𝑚 = 5,6 = � 2𝑚 + 2 (2) � � 𝑢𝑛𝑡𝑢𝑘 𝑚 ≥ 7 5

Sedangkan pada konstruksi sebelumnya diperoleh representasi yang berbeda pada setiap himpunan

sedangkan

simpul terhadap himpunan pembeda, dengan

yang mana simpul masin- masing simpul K1

(W1,m ). Oleh karena batas atas sama dengan bawah,

maka

𝑛. 𝑑𝑖𝑚�𝑊1,𝑚 �.

bentuk yang

sama dengan graf 𝐾1 + 𝑃𝑛 sebanyak m buah

demikian batas atas dim ( 𝑃𝑛 ⨀ 𝐶𝑚 ) = n.dim batas

graf G memiliki

𝑑𝑖𝑚(𝑃𝑛 ⨀ 𝐶𝑚 ) =

dihubungkan menentukan

secara dimensi

melingkar. metrik

graf

𝐶𝑚 ⨀ 𝑃𝑛

Dimensi Metrik Graf 𝐶𝑚 ⨀ 𝑃𝑛

Untuk 𝐺 =

dilakukan pencarian batas bawah dan batas atas. Dengan bentuk graf 𝐶1 ⨀ 𝑃𝑛 memenuhi

Graf 𝐶𝑚 ⨀ 𝑃𝑛 graf yang diperoleh dari Cm dan yang

persamaan (2) diperoleh paling sedikitnya

masing-masing simpul graf Cm dihubungkan

memenuhi aturan anggota himpunan pembeda

sehingga graf G

pada graf 𝐾1 + 𝑃𝑛 . Oleh Karena graf G

Pn dengan mengambil 1 graf Cm

pada setiap simpul graf Pn

teratur memiliki m buah graf 𝐾1 + 𝑃𝑛 yang

yaitu 𝐺 = 𝐶𝑚 ⨀ 𝑃𝑛 memiliki jumlah simpul

masing- masing

sebanyak m+nm. Simpul-simpul yang ada pada

bawah dim(𝐺) = dim(𝐶𝑚 ⨀ 𝑃𝑛 ) = 𝑚.

{𝑢1 , 𝑢2 , . . . , 𝑢𝑚 } dan simpul pada graf Pn label

𝑑𝑖𝑚 (𝐾1 + 𝑃𝑛 ). Untuk memenuhi batas atas

𝑉 (𝑃𝑛 ) = {𝑣1 , 𝑣2 , . . . , 𝑣𝑛 }

dimensi metrik graf G dilakukan konstruksi.

dengan jumlah 𝑉 (𝑃𝑛 ) sebanyak 𝑚𝑛 buah.

Kasus 1 n = 3

Dimisalkan simpul graf Pn yang dikoronakan dengan simpul Cm

Misalkan

yang pertama dilabelkan

pembeda


yang dikoronakan dengan simpul Cm

𝑟(𝑣1,2 |𝑊 ) = (1, 1, 3, 3, . . . , 4, 4, 3, 3), 𝑟(𝑣2,2 |𝑊 ) = (3, 3, 1, 1, 3, 3, . . . , 4, 4),

yang kem memiliki label {𝑣𝑚, 1 , 𝑣𝑚, 2 , . . . , 𝑣𝑚 , 𝑛 }. Berdasarkan pemisalan-pemisalan tersebut maka

⋮ 𝑟(𝑣𝑛, 2 |𝑊 ) = (3, 3, 4, 4, . . . , 1, 1),

graf G memiliki m +nm simpul yaitu 𝑉 (𝐺) = {{𝑢1 , 𝑢2 , … , 𝑢𝑚 }, {𝑣1,1 , 𝑣1,2 , … , 𝑣1, 𝑛 },

𝑟(𝑢1 |𝑊 ) = (1, 1, 2, 2, 3, 3, . . . , 2, 2),

{𝑣2,1 , 𝑣2,2 , … , 𝑣2, 𝑛 }, . . . , {𝑣𝑚, 1 , 𝑣𝑚, 2 , . . . , 𝑣𝑚, 𝑛 }} Graf 𝐶1 ⨀ 𝑃𝑛

diambil himpunan

𝑊 = {𝑣1,1 , 𝑣1,3 , 𝑣2,1 , 𝑣2,3 , . . . , 𝑣𝑛, 1, 𝑣𝑛, 3 }

{𝑣1,1 , 𝑣1,2 , . . . , 𝑣1, 𝑛 } sehingga simpul graf Pn

dihubungkan

secara melingkar maka jelas bahwa batas

graf Cm misalkan diberi label 𝑉 (𝐶𝑚 ) = diberi

simpul K1

𝑟(𝑢2 |𝑊 ) = (2, 2, 1, 1, 2, 2, . . . , 3, 3),

sama dengan graf K1 + Pn . Graf

⋮ 𝑟(𝑢𝑛 |𝑊 ) = (2, 2, . . . , 2, 2, 1, 1)

K1 + Pn memiliki dimensi metrik sebanyak [4]:

248


𝑟(𝑢1 |𝑊 ) = (1, 1, 1, 2, 2, 2, 3, 3, 3, . . . , 2, 2, 2),


𝑟(𝑢2 |𝑊 ) = (2, 2, 2, 1, 1, 1, 2, 2, 2, . . . , 3, 3, 3),

representasi yang berbeda-beda terhadap W ,

⋮

dengan demikian 𝑑𝑖𝑚 (𝐺) = 𝑚. 2 untuk

𝑟(𝑢𝑛 |𝑊 ) = (2, 2, 2, . . . , 2, 2, 2, 1, 1, 1)

𝑛 = 3


Kasus 2 n = 4

Misalkan

diambil

himpunan


pembeda

dengan demikian 𝑑𝑖𝑚 (𝐻 ) = 𝑚. 3 untuk

𝑊=

𝑛 = 5

{𝑣1,1 , 𝑣1,3 , 𝑣2,1 , 𝑣2,3 , . . . , 𝑣𝑛, 1 , 𝑣𝑛, 3 }

Kasus 4 n = 6


Misalkan

𝑟(𝑣1,2 |𝑊 ) = (1, 1, 3, 3, . . . , 4, 4, 3, 3),

𝑣𝑛, 1, 𝑣𝑛, 3 , 𝑣𝑛, 5 }

𝑟(𝑣2,2 |𝑊 ) = (3, 3, 1, 1, 3, 3, . . . , 4, 4),

⋮

𝑟(𝑣1,6 |𝑊 ) = (2, 2, 1, 3, 3, 3, … , 4, 4, 4, 3, 3, 3) 𝑟(𝑣2,2 |𝑊 ) = (3, 3, 3, 1, 1, 2, 3, 3, 3, … , 4, 4, 4)

𝑟(𝑢2 |𝑊 ) = (2, 2, 1, 1, 2, 2, . . . , 3, 3),

𝑟(𝑣2,4 |𝑊 ) = (3, 3, 3, 2, 1, 1, 3, 3, 3, … , 4, 4, 4)

⋮

𝑟(𝑣2,6 |𝑊 ) = (3, 3, 3, 2, 2, 1, 3, 3, 3, . . . , 4, 4, 4)

𝑟(𝑢𝑛 |𝑊 ) = (2, 2, . . . , 2, 2, 1, 1)

⋮


𝑟(𝑣𝑛, 2 |𝑊 ) = (3, 3, 3, 4, 4, 4, . . . , 1, 1, 2)


𝑟(𝑣𝑛, 4 |𝑊 ) = (3, 3, 3, 4, 4, 4, . . . , 2, 1, 1)

dengan demikian 𝑑𝑖𝑚 (𝐻 ) = 𝑚. 2 untuk n =

𝑟(𝑣𝑛, 6 |𝑊 ) = (3, 3, 3, 4, 4, 4, . . . , 2, 2, 1)

𝑟(𝑢1 |𝑊 ) = (1, 1, 1, 2, 2, 2, 3, 3, 3, . . . , 2, 2, 2),

4

𝑟 (𝑢2 |𝑊 ) = (2, 2, 2, 1, 1, 1, 2, 2, 2, … ,3,3, 3)

Kasus 3 n = 5 pembeda

𝑊 = {𝑣1,1 , 𝑣1,3 , 𝑣1,5 , 𝑣2,1 , 𝑣2,1 , 𝑣2,5 …,

Misalka 𝑥 = �2𝑚+2� dan diambil himpunan 5

terhadap W :

pembeda 𝑊 = {𝑣1,1 , 𝑣1,3 , … , 𝑣1, 𝑥 , 𝑣2,1 , 𝑣2,3 , … , 𝑣2, 𝑥 … , 𝑣𝑛, 1 , 𝑣𝑛, 3 , . . . , 𝑣𝑛, 𝑥

𝑟(𝑣1,2 |𝑊 ) = (1, 1, 2, 3, 3, 3, . . . , 4, 4, 4, 3, 3, 3) 𝑟(𝑣1,4 |𝑊 ) = (1, 1, 2, 3, 3, 3, . . . , 4, 4, 4, 3, 3, 3)


𝑟(𝑣2,2 |𝑊 ) = (3, 3, 3, 1, 1, 2, 3, 3, 3, . . . , 4, 4, 4)

𝑟(𝑣1,2 |𝑊 ) = (1, 1, 2, . . . , 3, 3, 3, . . . , . . . , 3, 3, 3, . . . )

𝑟(𝑣2,4 |𝑊 ) = (3, 3, 3, 2, 1, 1, 3, 3, 3, . . . , 4, 4, 4) 𝑟(𝑣𝑛, 4 |𝑊 ) = (3, 3, 3, 4, 4, 4, . . . , 2, 1, 1)

⋮

Kasus 5 m ≥ 7

𝑣𝑛, 1, 𝑣𝑛,53 , 𝑣𝑛, 5 } maka diperoleh representasi

𝑟(𝑣𝑛, 2 |𝑊 ) = (3, 3, 3, 4, 4, 4, . . . , 1, 1, 2)

diperoleh

𝑟(𝑣1,4 |𝑊 ) = (2, 1, 1, 3, 3, 3, … , 4, 4, 4, 3, 3, 3)

𝑟(𝑢1 |𝑊 ) = (1, 1, 2, 2, 3, 3, . . . , 2, 2),

himpunan

maka

𝑟(𝑣1,2 |𝑊 ) = (1, 1, 2, 3, 3, 3, … , 4, 4, 4, 3, 3, 3)

𝑟(𝑣𝑛, 4 |𝑊 ) = (3, 3, 4, 4, . . . , 2, 1),

diambil

pembeda

representasi terhadap W :

𝑟(𝑣𝑛, 2 |𝑊 ) = (3, 3, 4, 4, . . . , 1, 1),

Misalkan

himpunan

𝑊 = {𝑣1,1 , 𝑣1,3 , 𝑣1,5 , 𝑣2,1 , 𝑣2,3 , 𝑣2,5 …,

𝑟(𝑣1,4 |𝑊 ) = (2, 1, 3, 3, . . . , 4, 4, 3, 3),

𝑟(𝑣2,4 |𝑊 ) = (3, 3, 2, 1, 3, 3, . . . , 4, 4),

diambil

𝑟(𝑣1,4 |𝑊 )

⋮

= (2, 1, 1, 2, . . . , 3, 3, 3, . . . , . . . , 3, 3, 3, . . . )

249

⋮

𝑟(𝑣1, 𝑚 |𝑊 ) = (2, 2, 2, . . . , 3, 3, 3, . . . , . . . , 3, 3, 3, . . . )


himpunan

⋮ 𝑟(𝑣𝑛, 2 |𝑊 ) = (3, 3, . . . , 4, 4, . . . , . . . , 1, 1, 2, . . . )

sama

atas

•

representasi yang berbeda-beda terhadap W ,

untuk n ≥ 7

•

�

𝐶𝑚 ⨀ 𝑃𝑛

dengan

batas

bawah

adalah

Lemma: Jika 𝐶𝑚 ⨀ 𝑃𝑛 dengan m ≥ 1 dan n > teratur

maka

dim(𝐶𝑚 ⨀ 𝑃𝑛 ) = 𝑚. 𝑑𝑖𝑚 (𝐾1 + 𝑃𝑛 ).

graf

Bukti:

graf

Dengan

bentuk

𝐶𝑚 ⨀ 𝑃𝑛 dengan 𝑚 > 1 dan 𝑛 > 1 graf

teratur

maka

Yero.L.G,Kuziak.D,Rodr´iguezVela´zquez.J.A, On The Metric Dimension Of Corona Product Graphs, Computer and Mathematics with Applications.61(2011) 2793-2798.

𝐶𝑚 ⨀ 𝑃𝑛 memenuhi persamaan (2) diperoleh

Hernando, Carmen. dkk, On The Metric Dimension of Some Families of Graphs,Electronic Note in Dis- crete Mathematics 22 (2005) 129-133.

paling sedikitnya memenuhi aturan anggota

himpunan pembeda pada graf K1 + Pn . Oleh karena graf G teratur memiliki m buah graf

Imrana.M,Baig.A Q, Ahtsham.Syed ,Javaid.Imran , On the metric dimension of circulant graphs,Applied Mathematics Letters 25 (2012) 320-325.

K1 + Pn yang simpul K1 saling terhubung secara melingkar maka jelas bahwa batas bawah dim(𝐺) = dim (𝐶𝑚 ⨀ 𝑃𝑛 ) = 𝑚. 𝑑𝑖𝑚 (𝐾1 + 𝑃𝑛 ).

maka

G. Chartrand, L. Eroh, M. A. Johnson, O. R. Oeller- mann, Resolvabil- ity in graphs and the metric dimension of a graph, Discrete Applied Mathematics 105 (2000) 99-113.

maka

≥ 1 dan n > 1.

merupakan

teratur

Wahyudi, Suhud dan Sumarno. 2010. Dimensi Metrik pada Graf Kincir dengan Pola K1 + mK3 . FMIPA ITS, 731-744.

dim(𝐶𝑚 ⨀ 𝑃𝑛 ) = 𝑚. 𝑑𝑖𝑚 (𝐾1 + 𝑃𝑛 ). untuk m

1

graf

Daftar Pustaka

𝑚. 𝑑𝑖𝑚(𝐾1 + 𝑃𝑛 ). Oleh karena batas atas sama

maka


dapat dinyatakan bahwa batas atas untuk metrik

bawah,

dim( 𝑃𝑛 ⨀𝐶𝑚 ) = 𝑛. dim(𝑊1,𝑚 ). merupakan

Berdasarkan konstruksi dari 5 kasus diatas

dimensi

batas

𝑃𝑛 ⨀ 𝐶𝑚 dengan 𝑛 ≥ 1 dan 𝑚 > 1

merupakan


5

dengan

Simpulan

𝑟(𝑢𝑛 |𝑊 ) = (2, 2, . . . , . . . , 2, 2, . . . , 1, 1, . . . )

𝑑𝑖𝑚 (𝐺 ) = 𝑚. �

Oleh


⋮

demikian

himpunan

karena batas

𝑟(𝑢2 |𝑊 ) = (2, 2, . . . , 1, 1, . . . , 2, 2, . . . , . . . , 3, 3, . . . ),

dengan

hadap


⋮

𝑟(𝑢1 |𝑊 ) = (1, 1, . . . , 2, 2, . . . , 3, 3, . . . , . . . , 2, 2, . . . ),

2𝑚+2

ter-

pembeda, dengan demikian batas atas

𝑟(𝑣𝑛, 4 |𝑊 ) = (3, 3, . . . , 4, 4, . . . , . . . , 2, 1, 2, . . . )

𝑟(𝑣𝑛, 𝑚 |𝑊 ) = (3, 3, . . . , 4, 4, . . . , . . . , 2, 2, 2, . . . )

simpul

Feng.Min ,Xu.Min ,Wang.Kaishun ,On the metric dimension of line graphs,Discrete Applied Mathe- matics 161 (2013) 802-805

Sedangkan pada konstruksi sebelumnya

diperoleh representasi yang berbeda pada setiap

250

Jurnal Ilmiah Soul Math Vol 4. No. 5,

Recommend Documents