DIMENSI PARTISI PADA PENGEMBANGAN GRAPH...
Transcript of 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.