DIMENSI PARTISI PADA GRAF KINCIR PARTITION DIMENSION OF WINDMILL GRAPH

PROPOSAL TUGAS AKHIR

DIMENSI PARTISI PADA GRAF KINCIR PARTITION DIMENSION OF WINDMILL GRAPH  Oleh: CHANDRA IRAWAN NRP : 1200 109 024

JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI SEPULUH NOPEMBER SURABAYA 2008

ABSTRAK Misalkan G(V,E) adalah graf terhubung sederhana dan S adalah sebuah subset dari V(G),  jarak antara v dan S adalah  d ( v, S ) = min{d ( v, x ) x ∈ S } . Himpunan   berpasangan   Π = ( Π1 , Π 2 ,...., Π k )   dari   V(G)   dan   setiap   titik  v  pada  G, 

representasi dari v pada  Π  adalah k­vektor  r ( v Π) = ( d ( v, Π1 ), d ( v, Π2 ),....., d ( v, Πk ) ) ,  k­partisi  Π  adalah resolving partisi jika k­vektor adalah berbeda. Nilai minimum dari k yang  merupakan resolving k­partisi dari V(G) adalah dimensi partisi  pd(G) dari G. Graf kincir adalah graf lengkap K n  yang terdapat m salinan dari graf lengkap K n  dengan  sebuah titik sebagai titik pusat bersama dari semua salinan graf lengkap tersebut. Dalam tugas akhir ini akan dibahas mengenai dimensi partisi graf kincir. Kata kunci : resolving partisi, resolving k­partisi, dimensi partisi.

2

DIMENSI PARTISI PADA GRAF KINCIR A. LATAR BELAKANG Graph  merupakan salah satu struktur dasar dari ilmu komputer. Banyak permasalahan  dapat   dinyatakan   dalam   bentuk  graph  dan   diselesaikan   menggunakan  graph  pencarian/manipulasi   algoritma.  Graph  adalah   kumpulan  vertek  dan  edge,   didefinisikan  sebagai   G = (V , E ) , dimana  V  adalah kumpulan dari  vertek  dan  E  adalah kumpulan  dari  edge. Setiap  edge  menghubungkan satu  vertek  ke  vertek  yang lain, dan setiap  vertek  dapat  mempunyai banyak edge yang menghubungkannya ke vertek yang lain.  Banyak penelitian telah dilakukan pada  graph, diantaranya  edge labelling,  coloring graph,  teori Ramsey pada graph, vertex labelling, partition dimension of graph, dan lain­lain. Dimensi partisi merupakan permasalahan yang menarik untuk dibahas dan banyak mendapat  perhatian dari kalangan peneliti. Beberapa hasil penelitian tentang dimensi partisi pada graph  sudah banyak dipublikasikan. Dalam  penelitian  sebelumnya  juga telah  dibahas  oleh Tomaseu, I, Javaid, I,  dan  Slamin   tentang   Dimensi   Partisi   pada  Graph   Wheel.   Dimensi   partisi   pada  Graph   Wheel  merupakan   pd ( C n )     dari  graph  G   terhubung   yang   dipengaruhi   oleh   penambahan   vertek  tunggal. Dimensi partisi pada W n  untuk n ≥ 3 maka pd ( C n ) =3 ketika pd (W3 )  = 4 seperti 

pada  pd (Wn )  = 3 ketika 4 ≤ n ≤ 7 dan pd (Wn ) =  4 ketika 8 ≤ n ≤ 19. Secara garis besar, pencarian dimensi partisi dari graph G berisi penentuan nilai k minimum  untuk resolving k­partisi dari V(G).  Graf kincir adalah  Complete graph  / graf lengkap Kn   yang terdapat m salinan dari  complete   graph  dengan   sebuah   vertek   sebagai   pusat   vertek   bersama   dari   semua   salinan  complete graph tersebut. Untuk setiap vertek v dari graph terhubung dan sebuah subset S dari V(G), jarak antara v dan  S   adalah   d   (v,S)   =min   {d(v,x) x   ∈ S }.Untuk   setiap   pasangan   k­partisi  Π = { S1 , S 2 ,....., S k }   dari  V(G)  dan setiap vertek  v  dari  G, merupakan representasi  v  pada  Π  didefinisikan sebagai k­vektor r ( v Π) = ( d ( v, S1 ), d ( v, S 2 ),...., d ( v, S k )

)

), v ∈ V (G ) ,   adalah  Partisi   Π   disebut   sebagai  resolving   partition  jika   k­vektor   r (v Π berbeda. Nilai minimum k untuk resolving k­partisi dari V(G) adalah dimensi partisi  pd ( G )   dari G.[3][4]  Sejauh ini dimensi partisi kincir belum ditentukan. Pada tugas akhir ini akan di bahas tentang Dimensi Partisi pada graf kincir.

B. PERUMUSAN MASALAH Permasalahan­permasalahan   yang   ada   adalah   bagaimana   menentukan   dimensi   partisi  dari graf kincir dengan 2 bilah , 3 bilah dan kemudian menentukan dimensi partisi graf kincir  dengan n­bilah.  C. BATASAN MASALAH Adapun penelitian dalam tugas akhir ini yang dikaji adalah  graph  sederhana dan tak­ berarah  (undirected).

3

Graph sederhana adalah graph yang tidak memuat loop dan multiple edge. Loop adalah sisi  yang menghubungkan suatu titik dengan dirinya sendiri. Jika terdapat lebih dari satu sisi yang  menghubungkan dua titik, maka sisi­sisi tersebut dinamakan multiple edge. TUJUAN DAN MANFAAT PENELITIAN Tujuan dari penelitian ini adalah untuk mencari dimensi partisi pada graph windmill.  Adapun manfaatnya adalah : Memberi kontribusi pada penelitian dalam bidang teori graf, utamanya dalam dimensi partisi  pada graph windmill.  D.

E. TINJAUAN PUSTAKA Graph adalah kumpulan vertek dan edge, didefinisikan sebagai  G = (V , E ) , dimana V  adalah kumpulan dari vertek dan E adalah kumpulan dari edge. Setiap edge menghubungkan  satu  vertek  ke  vertek  yang   lain,   dan   setiap  vertek  dapat   mempunyai   banyak  edge  yang  menghubungkannya  ke  vertek  yang   lain.  Sebuah   segmen  garis  yang   menghubungkan   dua  vertek disebut dengan edge.[2]. e V

V

Gambar 1.  Gambar vertek dan edge graf. V1 dan V2 adalah vertek dan e adalah edge. Graph  adalah   himpunan   dari  vertek  dan  edge  yang   terbatas   dimana   setiap  edge  menghubungkan dua  vertek.  Graph  G mempunyai himpunan  vertek  V (G )   dan himpunan  edge  E (G ) , dimana  jumlahnya  dinyatakan  dengan   V (G )   atau  v  dan   E (G )   atau  e.  Suatu  edge  yang  menghubungkan  dua  vertek  disebut  dengan  adjacent, sedangkan  apabila  sebuah vertek berhubungan dengan dua edge disebut incident.[2] Graph wheel Pada  graph  roda   Wn   untuk n ≥ 3    adalah   C n +   K 1   yang menggabungkan semua  semua vertex pada   C n =   v 0 , v1 ...... v n −1 . Untuk penambahan vertek disebut pusat. Graph  W n  terdiri dari vertek n+1, pusat, dan vertek n lingkaran memiliki diameter 2. Contoh graph  wheel dapat dilihat pada Gambar 2

Gambar 2. Graph Wheel

4

Graph Windmill Windmill  atau kincir adalah  graph  lengkap K n yang terdiri atas m salinan dari  graph  lengkap   K n   dengan   sebuah   titik   sebagai   pusat   titik   bersama   dari   semua   salinan  graph  lengkap tersebut. Contoh graph dapat dilihat pada Gambar 3.

Gambar 3. Graph Windmill dengan tiga bilah( W3( 3 ) )

Untuk titik­titik u dan v dalam graph terhubung G, jarak   d ( u , v )  adalah panjang dari  lintasan   terpendek   antara  u  dan  v  pada  G.   Untuk   himpunan   berpasangan  W = (W1 , W2 ,...., Wk )   dari titik­titik dalam  graph  terhubung  G  dan titik  v  pada  G, adalah  vektor­k (pasangan k­tuple) r (u W ) = ( d ( v, w1 ), d ( v, w2 ),....., d ( v, wk )

)

menunjukkan matrik representasi dari v pada W. Himpunan W dinamakan resolving set G jika  titik­titik G mempunyai representasi berbeda. Himpunan resolving berisi jumlah minimal dari  titik­titik yang dinamakan “minimum resolving set” atau basis G. Jumlah titik­titik pada basis  G adalah (metrik) dimensi = dim (G).[3][4]  Dimensi partisi Graph ( pd(G) )  Untuk setiap titik v dari graph terhubung dan sebuah subset S dari V(G), jarak antara v  dan S adalah  d (v,s) =min {d(v,x) x   ∈ s } Untuk setiap pasangan k­partisi   Π = { S1 , S 2 ,....., S k }   dari  V(G)  dan setiap titik  v  dari  G,  merupakan representasi v pada  Π  didefinisikan sebagai k­vektor r ( v Π) = ( d ( v, S1 ), d ( v, S 2 ),...., d ( v, S k )

)

), v ∈ V (G ) ,   adalah  Partisi   Π   disebut   sebagai  resolving   partition  jika   k­vektor   r (v Π berbeda. Nilai minimum k untuk resolving k­partisi dari V(G) adalah dimensi partisi  pd ( G )   dari G, sebagai contoh : Dimensi partisi pada Path (P n )

Gambar 4. Graph Path (P 4 ) P n = v 1  ,v 2  , ...,v n Misalkan dengan 2 partisi, asumsikan  Π ={ S 1 , S 2 } adalah partisi dari V(P n ) dengan  S 1 ={ v 1 } dan S 2 ={ v 2  ,v 3 , ...,v n }

5

Gambar 5. Graph Path (P 4 )dengan 2 partisi

Maka (v 1 v 1 =0) ; (v 1 v 2 =1) ; (v 1 v 3 =2) ; (v 1 v 4 =3) Berapapun nilai n, maka nilai r(v| Π ) akan berbeda,  sehingga dapat dirumuskan 

r(v 1 | Π )=(0,1) r(v i | Π )=(i­1,0) ; untuk 2  ≤  i  ≤  n karena  Π  adalah resolving partisi dari P n  maka pd (P n )=2 F.   METODOLOGI PENELITIAN Metodologi penelitian dalam mengerjakan tugas akhir ini adalah sebagai     berikut: 1. Studi Literatur Tentang dimensi partisi graph dan graph Windmill Mempelajari teori­teori yang berhubungan dengan graph Windmill dan dimensi  partisi graph. 2. Analisa a.  Menentukan dimensi partisi pada graph Windmill. b.  Menganalisis dimensi partisi graph Windmill. 3. Evaluasi Melakukan evaluasi terhadap analisis, untuk mengetahui apakah analisis  tentang  dimensi partisi pada graph Windmill sesuai dengan yang diharapkan. 4. Penyimpulan Hasil Penelitian Penyimpulan   hasil   penelitian   merupakan   kesimpulan   dan   dokumentasi   dari  analisis tentang dimensi partisi pada graph Windmill.

G. JADWAL PELAKSANAAN  

Kegiatan

Bulan ke 1

1. 2. 3. 4.

2

Studi literatur Analisa Evaluasi Penyusunan Laporan

6

3

4

H. DAFTAR PUSTAKA 1. Harary, F., 1969, Graph Teory, Wesley Publishing Company,Inc. 2. Seshu, Sundaram, Reed, B., Myril, 1961,  Linear Graph and Electrical Network,  Addison­Wesley Publishing Company, Inc. 3. Tomescu,   I.,   Javaid,   I.,   Slamin.,   Maret.   2007.  On   the   partition   dimension   and  connected partition of wheels,  4. Chartrand, G., Salehi, E., Zhang, P., 2000.  “The Partition dimension of a graph”.  Aequation Math 59:45­54.

7