dimensi partisi pada pengembangan graph...

DIMENSI PARTISI PADA PENGEMBANGAN GRAPH KINCIR

DENGAN POLA K1+mKn

OLEH :MOHAMMAD IQBAL

12 06 100 061

Dosen Pembimbing :Drs. Suhud Wahyudi, M.Si.19600109 198701 1 001

JURUSAN MATEMATIKAFAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

INSTITUT TEKNOLOGI SEPULUH NOPEMBER2010

PENDAHULUAN

KAJIAN PUSTAKA

METODOLOGI PENELITIAN

ANALISIS PEMBAHASAN

KESIMPULAN

DAFTAR PUSTAKA

LATAR BELAKANG

GRAPHPermasalahan dari berbagai disiplin ilmu

Model graph

Teknik teori graph

Digunakan untuk menyelesaikan

berbagai permasalahan

Graph kincir

Graphkincir pola K1 + mKn

Dimensi partisi

Bagaimana menentukan dimensi partisi pada pengembangan graph kincir dengan pola K1 + mKn.

RUMUSAN MASALAH

BATASAN MASALAH

Graph yang digunakan adalah graph yang terbatas (finite), dan sederhana (simple).

Graph kincir yang digunakan adalah graph kincir dengan pola K1 + mKn.

TUJUAN

Mencari dimensi partisi graph G, pd(G) dari graph kincir dengan pola K1 + mKn.

MANFAAT

Diharapkan dapat memberikan kontribusi penelitian dalam bidang teori graph, khususnya dimensi partisi pada graph kincir dengan pola K1 + mKn.

PENDAHULUAN

KAJIAN PUSTAKA

METODOLOGI PENELITIAN

ANALISIS PEMBAHASAN

KESIMPULAN

DAFTAR PUSTAKA

PENGERTIAN GRAPH

Graph tak berarah, selanjutnya disebut sebagai Graph G, didefinisikan sebagaipasangan terurut G(V,E) dimana V adalah himpunan hingga tidak kosong

dan E adalah himpunan bagian dari VxV dimana berlaku(u,v) E mengakibatkan (v,u) E. Anggota dari V disebut vertex digambarkansebagai lingkaran atau titik dan edge digambarkan sebagai ruas garis yangmenghubungkan dua buah vertex. Banyaknya vertex dari G dilambangkandengan |V| = p dan banyaknya edge dari G dilambangkan dengan |E| = q.Secara umum suatu graph G yang mempunyai p-vertex dan q-edge dituliskandengan (p,q)-graph G.

{ }1 2, , , nv v v…∈∈

OPERASI JUMLAHAN PADA GRAPH

Misalkan G1 dan G2 adalah dua buah graph. definisi operasi jumlahan padagraph G1 dan G2 adalah graph G= G1+G2 dengan himpunan vertexV(G) = V(G1) U V(G2) dan himpunan edge-nyaE(G)=E(G1) U E(G2) U {uv|u∈V(G1)danv∈V(G2) }

u1 u2 u3

v1 v2 v3

u1 u2 u3

v1 v2 v3

G1+G2

G1

G2

atau

K4

K1 + 4K2

JENIS – JENIS GRAPH

C

U1

V1 U2

V2

V4

U4 V3

U3

Graph lengkap

Graph kincir

K1 + 5K6

JENIS – JENIS GRAPH

Graph kincir dengan pola

K1 + mKn

y11

y12

y13y14

y15

y16

y21

y22

y23y24

y25

y26

c

y31

y32y33

y34

y35 y36

y41

y42

y43y44

y45

y46

y51

y52

y53y54

y55

y56

JENIS – JENIS GRAPH

...

y21

y22

y23

y11

y12y13c

y32y31

y33y42

y41 y43

y52

y51

y53

ym2

ym3

ym1

y11

c

.....

y12

y22

y21

ym1ym2

y51

y52

y41

y42

y31y32

y33 y24

y23

y14

y13

ym4ym3

y54

y44

y43

y34

y53

DIMENSI PARTISI

Misalkan terdapat sebuah graph terhubung G dengan V(G) adalah himpunan titik – titiknya, S ⊆ V(G) dan titik v ∈V(G), jarak antara vdengan S yang dinotasikan d(v,S) didefinisikan sebagai

d(v,S) = {min d(v,x) | x ∈ S}Misalkan terdapat sebuah graph terhubung G dan k buah partisi dan untuk himpunan terurut Π = {S1, S2,..., Sk} dari vertex – vertex dalam graph terhubung G dan vertex v pada V(G), representasi dari v terhadap Π adalah k-vektor.

r(v| Π) = (d(v,S1), d(v,S2),..., d(v,Sk))Jika k-vektor r(v| Π), untuk setiap vertex v pada V(G)

berbeda, maka Π disebut himpunan resolving partisi dari V(G). Himpunan resolving partisi dengan kardinalitas minimum disebut dimensi partisi dari G dinotasikan dengan pd(G).

PENDAHULUAN

KAJIAN PUSTAKA

METODOLOGI PENELITIAN

ANALISIS PEMBAHASAN

KESIMPULAN

DAFTAR PUSTAKA

Pemahaman sistem dan studi literatur

Analisis

Evaluasi.

Penyimpulan hasil penelitian

PENDAHULUAN

KAJIAN PUSTAKA

METODOLOGI PENELITIAN

ANALISIS PEMBAHASAN

KESIMPULAN

DAFTAR PUSTAKA

Untuk menentukan dimensi partisi maka dilakukan denganmenentukan kardinalitas minimum dari himpunan resolving partisi.Untuk menentukan kardinalitas minimum dari himpunan resolvingpartisi maka dibutuhkan Lemma berikut:

Lemma 4.1 Misalkan terdapat graph kincir dengan polaK1+mKn dengan n≥3, m≥2 maka berlaku,

d(u,v)= ( )

0 , 1 , ,

jikau vjikau danv pada satu daunkincir yang sama atau

jikau atau v adalah pusat kincir c

=

2 , jikau danvberada pada daunkincir yang berbeda

Bukti : jika u dan v pada satu daun kincir yang sama dan graph yangdigunakan pada daun kincir adalah graph lengkap untuk graph kincirdengan pola K1+mKn, maka jarak dari setiap vertexnya adalah 1, hal inidisebabkan karena setiap vertex terhubung dan u dan v bertetangga,sedangkan jika u dan v pada daun kincir yang berbeda, maka jarakantara u dan v adalah 2, sedangkan jarak setiap vertex terhadap pusatkincir (c) adalah 1.

Dimensi Partisi Graph Kincir G=K1+mKn Dengan n=3,m secara umum

Lemma 4.2 Misalkan terdapat graph kincir denganpola K1+mK3 dengan m≥2. Misal c adalah titik pusatdan merupakan resolving partisi dari

. Jika maka .

3mw

1 2Π { ,  ,  ,  }kS S S= …

3( )mV w 1 c S 2

13 4| |2

k kS − +≤

Bukti : Koordinat titik pusat c adalah dan untuksetiap . Dari Lemma 4.1 elemen vektor darikoordinat untuk hanya boleh diisi oleh angka 1 dan 2.Akan tetapi, boleh diisi paling banyak 2 elemen yang bernilai 1. Halini disebabkan oleh derajat setiap titik adalah 3, yaituterhadap titik pusat c dan titik dan titik . Lebihlanjut, tidak boleh bertetangga dengan titik dan

karena akan mengakibatkan .Sehingga, paling tidak (k-1) posisi yang hanya boleh diisi dengan 2buah angka 1 kemudian sisanya dapat diisi dengan angka 2. Jadi, biladitambahkan dengan titik pusat, maka terdapat paling banyakkoordinat yang berbeda, atau

Jadi,

( )|Π (0,1,1, ,1)r c = …

( ) ( )1 \{ }, |Π 0,1,v S c r v = …( |Π)r v 1 \{ }v S c

1 \{ }v S c \{ , }u V c v \{ , , }t V c v u

1 \{ }v S c 1 \{ }u S c1 \{ }t S c ( ) ( ) ( )|Π |Π |Π (0,2,2,2, , 2)r v r u r t= = = …

11

2k −

+

1

11

2k

S−

≤ + ( )( )

1 !1

3 !2!k

k−

= +−

2 3 42

k k− +=

2

13 4| |2

k kS − +≤

Dimensi Partisi Graph Kincir G=K1+mKn Dengan n=3,m secara umum

Lemma 4.3 Misalkan terdapat graph kincir denganpola K1+mK3 dengan m≥2. Misal c adalah titik pusatdan merupakan resolving partisi dari

. Jika maka .

3mw

1 2Π { ,  ,  ,  }kS S S= …

3( )mV w 1 c S 2 3 2 , 22i

k kS i k− +≤ ≤ ≤

Bukti : Ambil sebuah himpunan resolving partisi selain S1, tanpamengurangi keumuman dari c, sebut S2 yang tidak memuat titikpusat. Koordinat untuk setiap adalah . Terdapatposisi (k-2) didalam vektor koordinat yang dapat diisi paling banyakdua buah angka 1 dan sisanya dapat diisi angka 2. Jadi, terdapatpaling banyak koordinat yang berbeda untuk setiap ,atau

Jadi, .

2w S ( ) ( )|Π 1,0,r w = …

2 22 1

k k− − +

2w S

2 2, 2

2 1i

k kS i k

− − ≤ + ≤ ≤

2 3 2 , 22

k k i k− += ≤ ≤

2 3 2 , 22i

k kS i k− +≤ ≤ ≤

Dimensi Partisi Graph Kincir G=K1+mKn Dengan n=3,m secara umum

Lemma 4.4 Untuk graph kincir dengan poladengan m secara umum , bilangan bulat positif,maka berlaku pd( )=k, dengan k adalah integerterkecil yang memenuhi .

3mw 1 3K mK+

2m ≥

3mw

3k

m ≥

Bukti : Untuk membuktikan ditentukan batas atas dan batas bawahdari dimensi partisi .• (batas bawah)Misal graph kincir dengan m buah daun kincir dan merupakan himpunan resolving partisi dari V( ). Misal adalah titik pusat dan , dari Lemma 4.2 dan 4.3, maka

3mw

3mw

3mw

1 2Π { ,  ,  ,  }kS S S= …1 c S

( )3 1 , 2miV w S S i k= + ≤ ≤

2 23 4 3 23 1 , 22 2

k k k km i k− + − ++ ≤ + ≤ ≤

2 23 4 3 23 1 ( 1)2 2

k k k km k− + − ++ ≤ + −

3 26 3 2m k k k≤ − +( )1 ( 2)

3!

k k km

− −≤

3k

m ≤

Dan jika maka pasti ditemukan representasi koordinatvertex yang sama yaitu pasti terdapat makasesuai dengan Lemma 2.1 u dan v harus berada pada partisi yangberbeda sehingga bukan merupakan himpunan resolving partisi,maka pd( ) k.Jadi, pd( )= k dengan k integer terkecil yang memenuhi ...(1)

1 2Π { ,  ,  ,  }kS S S= …( ) ( ), , ,1 1j jd u S d v S j k= ≤ ≤ −

Π

3mw3mw

3k

m ≥

≥

• (batas atas)Misalkan merupakan himpunan resolving partisi dari

V( ).• Perhatikan daun kincir. buah titik yang berlabel

1 merupakan anggota , sedangkan titik lainnya adalahanggota partisi selain .

• Kemudian, perhatikan daun kincir selanjutnya.buah titik yang berlabel 1 adalah anggota , sedangkan

untuk titik yang lainnya adalah anggota partisi selain dan.

• Proses ini diteruskan sampai tersisa 1 daun kincir dimana keduatitiknya belum tergabung dalam partisi manapun. Pada batangterakhir, titik berlabel ganjil adalah anggota dan titik berlabelgenap anggota dari .

Dengan menggunakan Lemma 4.1 maka akan diperoleh koordinatdari setiap titik.

1 2Π { ,  ,  ,  }kS S S= …3mw

( )1 ( 2)2

k k− − ( )1 ( 2)2

k k− −

( )1 ( 2)2

k k− −1S

1S( )2 ( 3)

2k k− −

( )2 ( 3)2

k k− −

( 1)k −

2S

2S1S( 2)k −

1 kS −

kS

r(y11| )=(0,1,1,2,2,...,2),r(y12| )=(1,0,1,2,2,...,2), r(y13| )=(1,1,0,2,2,...,2),r(y21| )=(0,1,2,1,2,...,2),r(y22| )=(1,0,2,1,2,...,2),r(y23| )=(1,1,2,0,2,...,2),

...r( | )=(0,1,2,2,...,1,2,...,2),r( | )=(1,0,2,2,...,1,2,...,2),r( | )=(1,1,2,2,...,0,2,...,2),

...r(c/ )=(0,1,1,...,1)

Jadi, terdapat (1+3+6+...+ ) daun kincir atau

Jadi, dengan k adalah bilangan terkecil yang memenuhi ..(2)Sehingga, dari persamaan (1) dan (2) maka diperoleh pd( )=k, dengan k adalah integer terkecil yang memenuhi .Jadi, pd( )=k, dengan k adalah integer terkecil yang memenuhi

( )1 ( 2)1

2k k− −

( )1 ( 2)2

2k k− −

( )1 ( 2)3

2k k− −

( )1 ( 2)2

k k− −

ΠΠΠΠΠΠ

ΠΠΠ

Π

3( )mpd w k≤ 3k

m ≥

3k

m ≥

3k

m ≥

3mw

3mw

( )( )1 21 3 6

2k k

m− −

+ + +…+ ≥

( )1 ( 2)3!

k k km

− −≥

3k

m ≥

Dimensi Partisi Graph Kincir G=K1+mKn Dengan n=4,m secara umum

Lemma 4.5 Misalkan terdapat graph kincir denganpola K1+mK4 dengan m≥2. Misal c adalah titik pusatdan merupakan resolving partisi dari

. Jika maka .

4mw

1 2Π { ,  ,  ,  }kS S S= …

4( )mV w 1 c S 3 2

16 11| |

6k k kS − +

≤

Bukti : Koordinat titik pusat c adalah dan untuksetiap . Dari Lemma 4.1 elemen vektor darikoordinat untuk hanya boleh diisi oleh angka 1 dan 2.Akan tetapi, boleh diisi paling banyak 3 elemen yang bernilai 1. Halini disebabkan oleh derajat setiap titik adalah 4, yaituterhadap titik pusat c dan titik dan titik , sertatitik . Lebih lanjut, tidak boleh bertetangga dengantitik , dan karena akan mengakibatkan

. Sehingga, paling tidak (k-1)posisi yang hanya boleh diisi dengan 3 buah angka 1 kemudiansisanya dapat diisi dengan angka 2. Jadi, bila ditambahkan dengantitik pusat, maka terdapat paling banyak koordinat yangberbeda, atau

Jadi,

( )|Π (0,1,1, ,1)r c = …( ) ( )1 \{ }, |Π 0,1,v S c r v = …

( |Π)r v 1 \{ }v S c

1 \{ }v S c \{ , }u V c v \{ , , }t V c v u

1 \{ }v S c1 \{ }u S c

1 \{ }t S c( ) ( ) ( ) ( )|Π |Π |Π |Π (0,2,2,2, , 2)r v r u r t r p= = = = …

11

3k −

+

1

11

3k

S−

≤ + ( )( )

1 !1

4 !3!k

k−

= +−

3 26 116

k k k− +=

3 2

16 11| |

6k k kS − +

≤

\{ , , , }p V c v u t1 \{ }p S c

Dimensi Partisi Graph Kincir G=K1+mKn Dengan n=4,m secara umum

Lemma 4.6 Misalkan terdapat graph kincir denganpola K1+mK4 dengan m≥2. Misal c adalah titik pusatdan merupakan resolving partisi dari

. Jika maka .

4mw

1 2Π { ,  ,  ,  }kS S S= …

4( )mV w 1 c S 3 26 11 6 , 26i

k k kS i k− + −≤ ≤ ≤

Bukti : Ambil sebuah himpunan resolving partisi selain S1, tanpamengurangi keumuman dari c, sebut S2 yang tidak memuat titikpusat. Koordinat untuk setiap adalah . Terdapatposisi (k-2) didalam vektor koordinat yang dapat diisi paling banyakdua buah angka 1 dan sisanya dapat diisi angka 2. Jadi, terdapatpaling banyak koordinat yang berbeda untuk setiap ,atau

Jadi, .

2w S ( ) ( )|Π 1,0,r w = …

2 23 2

k k− − +

2w S

2 2, 2

3 2i

k kS i k

− − ≤ + ≤ ≤

3 26 11 6 , 26

k k k i k− + −= ≤ ≤

3 26 11 6 , 26i

k k kS i k− + −≤ ≤ ≤

Dimensi Partisi Graph Kincir G=K1+mKn Dengan n=4,m secara umum

Lemma 4.7 Untuk graph kincir dengan poladengan m secara umum , bilangan bulat positif,maka berlaku pd( )=k, dengan k adalah integerterkecil yang memenuhi .

4mw 1 4K mK+

2m ≥

4mw

4k

m ≥

Bukti : Untuk membuktikan ditentukan batas atas dan batas bawahdari dimensi partisi .• (batas bawah)Misal graph kincir dengan m buah daun kincir dan merupakan himpunan resolving partisi dari V( ). Misal adalah titik pusat dan , dari Lemma 4.2 dan 4.3, maka

4mw

4mw

4mw

1 2Π { ,  ,  ,  }kS S S= …1 c S

( )4 1 , 2miV w S S i k= + ≤ ≤

3 2 3 26 11 6 11 64 1 , 26 6

k k k k k km i k− + − + −+ ≤ + ≤ ≤

3 2 3 26 11 6 11 64 1 ( 1) 6 6

k k k k k km k− + − + −+ ≤ + −

4 3 2 24 6 11 6m k k k k≤ − + −( )( )1 2 ( 3)

4!

k k k km

− − −≤

4k

m ≤

Dan jika maka pasti ditemukan representasi koordinatvertex yang sama yaitu pasti terdapat makasesuai dengan Lemma 2.1 u dan v harus berada pada partisi yangberbeda sehingga bukan merupakan himpunan resolving partisi,maka pd( ) k.Jadi, pd( )= k dengan k integer terkecil yang memenuhi ...(3)

1 2Π { ,  ,  ,  }kS S S= …( ) ( ), , ,1 1j jd u S d v S j k= ≤ ≤ −

Π

4mw4mw

4k

m ≥

≥

• (batas atas)Misalkan merupakan himpunan resolving partisi dari

V( ).• Perhatikan daun kincir. buah titik yang

berlabel 1 merupakan anggota , sedangkan titiklainnya adalah anggota partisi selain .

• Kemudian, perhatikan daun kincir selanjutnya.buah titik yang berlabel 1 adalah anggota ,

sedangkan untuk titik yang lainnya adalah anggota partisiselain dan .

• Proses ini diteruskan sampai tersisa 1 daun kincir dimana keduatitiknya belum tergabung dalam partisi manapun. Pada batangterakhir, titik berlabel ganjil adalah anggota dan titik berlabelgenap anggota dari .

Dengan menggunakan Lemma 4.1 maka akan diperoleh koordinatdari setiap titik.

1 2Π { ,  ,  ,  }kS S S= …4mw

( )( )1 2 ( 3)6

k k k− − − ( )( )1 2 ( 3)6

k k k− − −

( )( )1 2 ( 3)6

k k k− − −1S

1S( )( )2 3 ( 4)

6k k k− − −

( )( )2 3 ( 4)6

k k k− − −

( 1)k −

2S

2S1S( 2)k −

1 kS −

kS

r(y11| )=(0,1,1,1,2,2,...,2),r(y12| )=(1,0,1,1,2,2,...,2),r(y13| )=(1,1,0,1,2,2,...,2),r(y14| )=(1,1,1,0,2,2,...,2),r(y21| )=(0,1,1,2,1,2,...,2),r(y22| )=(1,0,1,2,1,2,...,2),r(y23| )=(1,1,0,2,1,2,...,2),r(y24| )=(1,1,1,2,0,2,...,2),

...r( | )=(0,1,1,2,2,...,1,2,...,2),r( | )=(1,0,1,2,2,...,1,2,...,2),r( | )=(1,1,0,2,2,...,1,2,...,2),r( | )=(1,1,0,2,2,...,1,2,...,2),

...r(c/ )=(0,1,1,1,...,1)

Jadi, terdapat (1+4+10+...+ ) daun kincir atau

ΠΠΠΠΠΠΠΠ

ΠΠΠΠ

Π

( )( )1 2 ( 3)1

6k k k− − −

( )( )1 2 ( 3)2

6k k k− − −

( )( )1 2 ( 3)3

6k k k− − −

( )( )1 2 ( 3)4

6k k k− − −

( )( )1 2 ( 3)6

k k k− − −

( )( )1 2 ( 3)

4!k k k k

m− − −

≥

( )( )1 2 ( 3)1 4 10

6k k k

m− − −

+ + +…+ ≥

4k

m ≥

Jadi, dengan k adalah bilangan terkecil yang memenuhi..(4)

Sehingga, dari persamaan (3) dan (4) maka diperoleh pd( )=k, dengank adalah integer terkecil yang memenuhi .Jadi, pd( )=k, dengan k adalah integer terkecil yang memenuhi

4( )mpd w k≤4k

m ≥

4mw

4mw

4k

m ≥

4k

m ≥

Dimensi Partisi Graph Kincir G=K1+mKn Dengan nsecara umum , m secara umum

Lemma 4.8 Misalkan terdapat graph kincir denganpola K1+mKn dengan m≥2, n≥3. Misal c adalah titikpusat dan merupakan resolvingpartisi dari . Jika maka .

mnw

1 2Π { ,  ,  ,  }kS S S= …( )m

nV w 1 c S 1

1| | 1

1k

Sn−

≤ + −

Bukti : Koordinat titik pusat c adalah dan untuksetiap . Dari Lemma 4.1 elemen vektor darikoordinat untuk hanya boleh diisi oleh angka 1 dan 2.Akan tetapi, boleh diisi paling banyak (n-1) elemen yang bernilai 1.Hal ini disebabkan oleh derajat setiap titik adalah n, yaituterhadap titik pusat c dan titik , titik , ,...,titik

.Lebih lanjut, tidak boleh bertetangga dengantitik , ,..., karena akan mengakibatkan

. Sehingga, paling tidak(k-1) posisi yang hanya boleh diisi dengan (n-1) buah angka 1kemudian sisanya dapat diisi dengan angka 2. Jadi, bila ditambahkandengan titik pusat, maka terdapat paling banyak koordinatyang berbeda, atau

Jadi,

( )|Π (0,1,1, ,1)r c = …( ) ( )1 1 1 \{ }, |Π 0,1,v S c r v = …

1(Π)r v

2 1 \{ , }v V c v 3 1 2 \{ , , }v V c v v

2 1 \{ }v S c1 1 \{ }v S c

3 1 \{ }v S c( ) ( ) ( ) ( )1 2 3 1|Π |Π |Π |Π (0,2,2,2, , 2)nr v r v r v r v −= = =…= = …

11

kn−

+

1

1| | 1

kS

n−

≤ +

1 1 2 1{ , , , , }n nv V c v v v− −…1 1 \{ }nv S c−

1

1| | 1

kS

n−

≤ +

1 1 \{ }v S c

1 1 \{ }v S c

Dimensi Partisi Graph Kincir G=K1+mKn Dengan nsecara umum, m secara umum

Lemma 4.9 Misalkan terdapat graph kincir denganpola K1+mKn dengan m≥2. Misal c adalah titik pusatdan merupakan resolving partisi dari

. Jika maka .

mnw

1 2Π { ,  ,  ,  }kS S S= …( )m

nV w 1 c S 1, 2

1i

kS i k

n−

≤ ≤ ≤ −

Bukti : Ambil sebuah himpunan resolving partisi selain S1, tanpamengurangi keumuman dari c, sebut S2 yang tidak memuat titikpusat. Koordinat untuk setiap adalah . Terdapatposisi (k-2) didalam vektor koordinat yang dapat diisi paling banyakdua buah angka 1 dan sisanya dapat diisi angka 2. Jadi, terdapatpaling banyak koordinat yang berbeda untuk setiap ,atau

Jadi, .

2w S ( ) ( )|Π 1,0,r w = …

2 21 2

k kn n− −

+ − − 2w S

2 2, 2

1 2i

k kS i k

n n− −

≤ + ≤ ≤ − −

( )( ) ( )

1 !, 2

! 1 !k

i kk n n

−= ≤ ≤

− −1

, 21i

kS i k

n−

≤ ≤ ≤ −

1, 2

1k

i kn−

= ≤ ≤ −

Dimensi Partisi Graph Kincir G=K1+mKn Dengan nsecara umum, m secara umum

Teorema 4.10 Untuk graph kincir dengan poladengan ,m,n bilangan bulat positif, makaberlaku pd( )=k, dengan k adalah integer terkecilyang memenuhi .

mnw 1 nK mK+

3, 2n m≥ ≥mnw

km

n

≥

Bukti : Untuk membuktikan ditentukan batas atas dan batas bawahdari dimensi partisi .• (batas bawah)Misal graph kincir dengan m buah daun kincir dan merupakan himpunan resolving partisi dari V( ). Misal adalah titik pusat dan , dari Lemma 4.2 dan 4.3, maka

mnw

mnw

mnw

1 2Π { ,  ,  ,  }kS S S= …1 c S

( ) 1 , 2mn iV w S S i k= + ≤ ≤

1 11 1 , 2

1 1k k

nm i kn n− −

+ ≤ + + ≤ ≤ − − 1 1

( 1)1 1

k knm k

n n− −

≤ + − − − ( )11 1

1k

kn−

= + − − ( )( ) ( )( )( )

1 2 1 !

! !k k k k n k n

mk n n

− − … − + −≤

−

k

mn

≤

Dan jika maka pasti ditemukan representasi koordinatvertex yang sama yaitu pasti terdapat makasesuai dengan Lemma 2.1 u dan v harus berada pada partisi yangberbeda sehingga bukan merupakan himpunan resolving partisi,maka pd( ) k.Jadi, pd( )= k dengan k integer terkecil yang memenuhi ...(3)

1 2Π { ,  ,  ,  }kS S S= …( ) ( ), , ,1 1j jd u S d v S j k= ≤ ≤ −

Π

mnw

mnw

km

n

≥

≥

• (batas atas)Misalkan merupakan himpunan resolving partisi dari

V( ).• Perhatikan daun kincir. buah

titik yang berlabel 1 merupakan anggota , sedangkantitik lainnya adalah anggota partisi

selain .• Kemudian, perhatikan daun kincir

selanjutnya. buah titik yang berlabel 1adalah anggota , sedangkan untuk titik yang lainnya adalahanggota partisi selain dan .

• Proses ini diteruskan sampai tersisa 1 daun kincir dimana keduatitiknya belum tergabung dalam partisi manapun. Pada batangterakhir, titik berlabel ganjil adalah anggota dan titik berlabelgenap anggota dari .

Dengan menggunakan Lemma 4.1 maka akan diperoleh koordinatdari setiap titik.

1 2Π { ,  ,  ,  }kS S S= …mnw

( )( )1 2 ( 1)!

k k k nn

− − … − + ( )( )1 2 ( 1)!

k k k nn

− − … − +

1S

1S ( )( )2 3 ( 2)!

k k k nn

− − … − +

( 1)k −

2S2S1S( 2)k −

1 kS −

kS

( )( )1 2 ( 1)!

k k k nn

− − … − +

( )( )2 3 ( 2)!

k k k nn

− − … − +

r(y11| )=(0,1,1,1,...,1,2,2,...,2),r(y12| )=(1,0,1,1,...,1,2,2,...,2),r(y13| )=(1,1,0,1,...,1,2,2,...,2),

...r(y1n| )=(1,1,1,1,...,0,2,2,...,2),r(y21| )=(0,1,1,1,...,2,1,2,...,2),r(y22| )=(1,0,1,1,...,2,1,2,...,2),r(y23| )=(1,1,0,1,...,2,1,2,...,2),

...r(y2n| )=(1,1,1,1,...,2,0,2,...,2),

...r( | )=(0,1,1,1,...,2,2,...,1,2,...,2),r( | )=(1,0,1,1,...,2,2,...,1,2,...,2),r( | )=(1,1,0,1,...,2,2,...,1,2,...,2),

...r( | )=(1,1,1,1,...,2,2,...,0,2,...,2),

...r(c/ )=(0,1,1,1,....,1)

Jadi, terdapat (1+2+3(n+1) +...+ ) daun kincir atau

ΠΠΠ

ΠΠΠΠ

Π

Π

ΠΠ

Π

Π

( )( )1 2 ( 1)1

!k k k n

n− − … − +

( )( )1 2 ( 1)2

!k k k n

n− − … − +

( )( )1 2 ( 1)3

!k k k n

n− − … − +

( )( )1 2 ( 1)!

k k k nn

n− − … − +

( )( )1 2 ( 1)!

k k k nn

− − … − +

Jadi, dengan k adalah bilangan terkecil yang memenuhi..(6)

Sehingga, dari persamaan (5) dan (6) maka diperoleh pd( )=k,dengan k adalah integer terkecil yang memenuhi .Jadi, pd( )=k, dengan k adalah integer terkecil yang memenuhi

( )mnpd w k≤k

mn

≥

mnw

mnw

km

n

≥

km

n

≥

( )( )1 2 ( 1)1 2 3(n 1)

!k k k n

mn

− − … − ++ + + +… ≥

( )( )1 2 ( 1)

!k k k k n

mn

− − … − +≥

k

mn

≥

PENDAHULUAN

KAJIAN PUSTAKA

METODOLOGI PENELITIAN

ANALISIS PEMBAHASAN

KESIMPULAN

DAFTAR PUSTAKA

Sesuai dengan Teorema 4.1, dapat disimpulkan bahwa dimensi partisi pada pengembangan graph kincir dengan pola K1+mKn , diperoleh pd( wn

m) adalah k dimana k adalah integer terkecil yang memenuhi

KESIMPULAN

PENDAHULUAN

KAJIAN PUSTAKA

METODOLOGI PENELITIAN

ANALISIS PEMBAHASAN

KESIMPULAN

DAFTAR PUSTAKA

[1] Chartrand, G., Salehi, E., Zhang, P. “The Partition Dimension of a Graph”. Aequationes Math. Vol 59 No. 45-54, 2000.

[2] Connery, Setiawan S. 2007. Kajian Kelas Graf Yang Mempunyai Dimensi Partisi n-1 Dan Penentuan Dimensi Partsisi Pada Kn – {e1, e2}. Tugas Akhir, Jurusan Matematika FMIPA ITB.

[3] Purwono, Johanes A. 2009. Dimensi Metrik Pada Pengembangan Graph Kincir Dengan Pola K1+mKn. Tugas Akhir, Jurusan Matematika FMIPA ITS.

[4] Syah, N. 2008. Dimensi Partisi Graf Kipas dan Graf Kincir. Tugas Akhir, Jurusan Matematika FMIPA ITB.

[5] Wilson, Robin J., Watkins, John J. 1990. Graphs An Introductory Approach, John Wiley & Sons, Inc.