graf theory

of 110 /110
DIMENSI PARTISI GRAF MULTIPARTIT DAN GRAF HASIL KORONA DUA GRAF TERHUBUNG DISERTASI Karya tulis sebagai salah satu syarat untuk memperoleh gelar Doktor dari Institut Teknologi Bandung Oleh DARMAJI NIM: 30107003 Program Studi Doktor Matematika INSTITUT TEKNOLOGI BANDUNG 2011

Author: ririn-nirmalasari

Post on 22-Oct-2015

466 views

Category:

Documents


21 download

Embed Size (px)

DESCRIPTION

graf theory

TRANSCRIPT

  • DIMENSI PARTISI GRAF MULTIPARTIT DAN GRAF HASILKORONA DUA GRAF TERHUBUNG

    DISERTASI

    Karya tulis sebagai salah satu syaratuntuk memperoleh gelar Doktor dari

    Institut Teknologi Bandung

    Oleh

    DARMAJI

    NIM: 30107003

    Program Studi Doktor Matematika

    INSTITUT TEKNOLOGI BANDUNG2011

  • Abstrak

    DIMENSI PARTISI GRAF MULTIPARTIT DAN GRAF HASILKORONA DUA GRAF TERHUBUNG

    Oleh

    Darmaji

    NIM: 30107003

    Penentuan basis/partisi pembeda dari suatu graf adalah kajian menarik dalam teorigraf karena mempunyai banyak aplikasi. Klasifikasi senyawa kimia, navigasi robotdan jaringan, dan perancangan sensor adalah tiga contoh aplikasi tersebut. Slater(1975) dan Harary dan Melter (1976) mengenalkan konsep himpunan pembedadalam suatu graf. Misalkan G = (V,E) adalah suatu graf terhubung. UntukW = {w1, w2, , wk} V (G) dan v V (G), representasi v terhadap W adalahr(v|W ) = (d(v, w1), d(v, w2), , d(v, wk)). Himpunan W disebut himpunanpembeda dari V (G) jika r(u|W ) 6= r(v|W ) untuk sebarang dua simpul berbedau, v V (G). Dimensi metrik dari suatu graf G, disimbolkan dim(G), adalahbilangan bulat terkecil k sedemikian hingga G mempunyai sebuah himpunanpembeda dengan k anggota.

    Selanjutnya, Chartrand dkk. (1998) mengenalkan ragam lain dari konsepdimensi metrik yang disebut dimensi partisi graf. Misalkan v V (G) danS V (G), jarak antara v dan S adalah d(v, S) = min {d(v, x)|x S}. Untuksebuah partisi = {S1, S2, , Sk} dari V (G), representasi v terhadap adalahr(v|) = (d(v, S1), d(v, S2), , d(v, Sk)). Partisi disebut partisi pembeda dariG jika semua representasi dari setiap simpul v V (G) berbeda. Dimensi partisipd(G) adalah bilangan bulat terkecil k sedemikian hingga G mempunyai sebuahpartisi pembeda dengan k anggota.

    Penelitian dalam dimensi partisi graf telah mendapatkan banyak perhatian.Sebagai hasil pertama, Chartrand dkk. (1998) menentukan dimensi partisi daribeberapa kelas pohon, yaitu graf bintang ganda dan graf ulat. Selanjutnya, dalam(Chartrand, Salehi dan Zhang, 2000), mereka mengkarakterisasi semua graf ordern dengan dimensi partisi 2, n dan n 1 berturut-turut. Mereka juga menunjukkanbahwa pd(Km,n) = max{m,n}. Kemudian, Tomescu (2008) mengkarakterisasisemua graf order n dengan partisi dimensi n 2. Mereka juga meneliti dimensipartisi beberapa graf tak-hingga. Akan tetapi, penentuan dimensi partisi darisebarang graf secara umum diklasifikasikan sebagai NP-hard problem (Chartrand,Salehi dan Zhang, 2000).

    Dalam disertasi ini, kami menentukan dimensi partisi dari pohon kelas tertentu,yaitu graf ulat (caterpillar), graf kembang api (firecracker), dan graf pohon

    ii

  • pisang (banana tree). Kami juga menentukan dimensi partisi graf multipartit, grafbipartit lengkap minus matching, dan graf tripartit lengkap minus matching. Hasilpenelitian ini memperbaiki hasil dari Chartrand dkk. (1998) dan Chartrand, Salehidan Zhang (2000).

    Untuk graf G dan H , graf hasil korona G H didefinisikan sebagai grafyang yang diperoleh dari G dan H dengan mengambil sebuah kopi graf G dan|V (G)| kopi grafH dan kemudian menghubungkan setiap simpul dari kopi ke-i grafH dengan sebuah titik ke-i dari G. Kami mendapatkan batas atas dimensi partisigraf GH jika diameter H paling banyak 2, yaitu pd(GH) pd(G) + pd(H).Kami menunjukkan bahwa batas atas ini ketat. Untuk kasus tertentu, kamimendapatkan pd(G H), jika G adalah graf lintasan Pm, graf bintang K1,m ataugraf lengkap Km dan H adalah graf lengkap Km, graf bintang K1,m atau beberapakopi saling lepas dari graf lengkap Km.

    Kata kunci: himpunan pembeda, partisi pembeda, dimensi metrik, dimensi partisi,graf multipartisi, matching, graf hasil korona.

    iii

  • Abstract

    THE PARTITION DIMENSION OF MULTIPARTITEGRAPHS AND CORONA PRODUCT OF TWO CONNECTED

    GRAPHS

    by

    Darmaji

    NIM: 30107003

    Finding a set of vertices of a connected graph so that representations of allvertices to such a set are distinct is an interesting research domain in GraphTheory, due to many applications. Compound classification in chemistry, roboticnavigation and network, and censor design are some examples for these appli-cations. Slater (1975) dan Harary dan Melter (1976) introduced the concept ofa resolving partition for a graph. Let G = (V,E) be a connected graph. ForW = {w1, w2, , wk} V (G) and v V (G), the representation of v withrespect to W is r(v|W ) = (d(v, w1), d(v, w2), , d(v, wk)). The set W is called aresolving set for V (G) if r(u|W ) 6= r(v|W ) for any two vertices u, v V (G). Themetric dimension dim(G) is the smallest integer k such that G has a resolving setwith k elements.

    Furthermore, Chartrand dkk. (1998) introduced a variant of metric dimensionconcept called partition dimension of a graph, as follows. Let v V (G) andS V (G), the distance between v and S is d(v, S) = min {d(v, x)|x S}.For an ordered partition = {S1, S2, , Sk} of V (G), the representation of vwith respect to is r(v|) = (d(v, S1), d(v, S2), , d(v, Sk)). The partition is called a resolving partition of G if all representations of vertices are distinct.The partition dimension of a graph G is the smallest integer k such that G has aresolving partition with k elements.

    The investigations on the partition dimension of graphs have been receivingmuch attention. As the first result, Chartrand dkk. (1998) determined the partitiondimension of special classes of trees, namely double stars and certain caterpillars.Furthermore, in Chartrand, Salehi dan Zhang (2000), they characterized all graphson n vertices with partition dimension 2, n and n 1 respectively. They alsoshowed that pd(Km,n) = max{m,n}. Lately, Tomescu (2008) characterized allgraphs on n vertices with partition dimension (n 2). They also investigated thepartition dimension for some infinite graphs. However, determining of the partitiondimension of any graph in general is classified as an NP -hard problem (Chartrand,Salehi dan Zhang, 2000).

    In this dissertation, we determine the partition dimension of specified classes

    iv

  • of trees, namely caterpillars, firecrackers and banana trees. Our result for cater-pillars improved the result of Chartrand dkk. (1998). We also determine thepartition dimension of multipartite graphs, complete bipartite graphs minus amatchings and complete tripartite graphs minus matchings. These works are animprovement of the results in Chartrand dkk. (1998) dan Chartrand, Salehi danZhang (2000).

    For graphs G and H , the corona product G H is defined as the graphobtained from G and H by taking one copy of G and |V (G)| copies of H and thenjoining each vertex of the ith-copy of H with the ith-vertex of G by an edge . Weshall derive an upper bound of the partition dimension of GH if the diameter ofH is at most 2, namely pd(GH) pd(G) + pd(H). We show that this bound istight. For specific cases, we investigate pd(GH), if G is either a path Pm, a starK1,m or a complete graph Km and H is a complete graph Km, a star K1,m or somedisjoin copies of Km.

    Key words: resolving set, resolving partition, metric dimension, partitiondimension, multipartite graph, matching, corona product graph.

    v

  • DIMENSI PARTISI GRAF MULTIPARTIT DAN GRAF HASILKORONA DUA GRAF TERHUBUNG

    Oleh

    Darmaji

    NIM: 30107003

    Program Studi Doktor Matematika

    Institut Teknologi Bandung

    Menyetujui

    Tim Pembimbing

    Tanggal 14 Juni 2011

    Ketua

    Prof. Dr. Edy Tri Baskoro

    Anggota Anggota

    Dr. Saladin Uttunggadewa Dr. Rinovia Simanjuntak

    vi

  • Karena paduka memintaku terus berguru maka aku terus berguru.Peluh dalam berguru adalah kegembiraan tiada berbilang

    karena cinta paduka menebar tak berkesudahan,di dalam setiap ihtiar dan perolehan.

    vii

  • Pedoman Penggunaan Disertasi

    Disertasi Doktor yang tidak dipublikasikan ini terdaftar dan tersedia di Perpus-

    takaan Institut Teknologi Bandung, dan terbuka untuk umum dengan ketentuan

    bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku

    di Institut Teknologi Bandung.

    Referensi kepustakaan diperkenankan dicatat, tetapi pengutipan atau peringkasan

    hanya dapat dilakukan seizin pengarang dan harus disertai dengan kebiasaan ilmiah

    untuk menyebutkan sumbernya.

    Memperbanyak atau menerbitkan sebagian atau seluruh disertasi haruslah seizin

    Dekan Sekolah Pascasarjana, Institut Teknologi Bandung.

    viii

  • Ucapan Terima Kasih

    Yang ada hanya cinta karena yang kita sebut sebagai bukan cinta sesungguhnya

    adalah cinta jua, hanya saja ia tak menemukan wilayah untuk tumbuh dan bersemi.

    Karena cinta pula penulis dapat menyelesaikan pendidikan Program Doktor

    Matematika ITB. Kegembiraan penulis adalah kegembiraan karena cinta yang

    menebar.

    Cinta dari Prof. Dr. Edy Tri Baskoro (promotor), Dr. Saladin Uttunggadewa

    (ko-promotor I) dan Dr. Rinovia Simanjuntak (ko-promotor II) adalah cinta yang

    melimpah mengalir tak berkesudahan dalam diskusi dan pembimbingan. Cinta

    beliau adalah cinta yang menggerakkan untuk menjadi matematikawan yang baik

    karena beliau matematikawan yang sangat baik. Beliau mumpuni dalam keilmuan,

    jernih dalam penyampaian, dan terampil dalam memadukan kepakaran akademik

    dan indahnya silaturahim.

    Cinta dari Prof. Martin Baca adalah cinta yang memberi makna pada indahnya

    keragaman dan hangatnya komunikasi akademik pada tiga bulan masa-masa

    program sandwich-like di Technical University of Kosice, Republik Slovakia.

    Cinta dari segenap kolega di Institut Teknologi Bandung adalah cinta yang

    menguak cakrawala keilmuan, memberi sejumlah petunjuk dan memandu bergerak

    ke depan. Terus bergerak. Belajar tak berkesudahan sambil tetap menjaga

    kerendah-hatian.

    Cinta dari segenap kolega di Institut Teknologi Sepuluh Nopember (ITS) Surabaya

    adalah cinta sawah ladang yang memberi kesuburan bagi tumbuh-kembangnya

    kehidupan akademik penulis. Cinta dari segenap kolega di Jurusan Matematika ITS

    adalah cinta yang memberi kerelaan ketika harus melakoni tugas, yang semestinya

    menjadi tugas penulis, selama masa-masa menempuh jenjang pendidikan S3.

    Cinta dari Kementerian Negara Pendidikan Nasional dan Direktorat Jendral

    Pendidikan Tinggi adalah cinta yang memfasilitasi dengan beragam skema

    pendanaan: BPPS (Beasiswa Pendidikan Pasca Sarjana), Program Sandwich-like,

    Program Penelitian Doktor, dan Program Insentif Penulisan untuk Jurnal Interna-

    ix

  • sional.

    Cinta dari istri, anak, dan keluarga besar adalah cinta yang men-samudra.

    Ke mana hendak berlayar, samudra memberi air dan kapal. Ke mana hendak

    bergerak, samudra memberi layar, angin dan bintang. Ketika letih menjadi kenis-

    cayaan, samudra dan segala anasirnya bersekutu memberi energi. Cinta istri dan

    anak adalah cinta yang juga mewujud dalam bentuk kesanggupan mengambil porsi

    sangat besar peran ayah pada masa-masa si ayah menempuh jenjang pendidikan S3.

    Cinta dari kawan-kawan di Program Doktor Matematika Program Pasca Sarjana

    (PPS) ITB adalah cinta yang memurnikan melaui beragam diskusi dan perbin-

    cangan yang mencerahkan; adalah cinta yang tak memberi ruang bagi segala

    hal yang tak membahagiakan; adalah cinta yang selalu hadir ketika semua yang

    bernama keluarga berada dalam jarak ratusan kilometer dari Bandung.

    Karena cinta dan atas nama cinta, penulis menghaturkan terima kasih tak

    berkesudahan kepada semua yang telah memberikan cinta kepada penulis.

    Karena cinta penulis tumbuh dari ketulusan, tentulah ia bergerak meninggi,

    menjangkau langit, dan sampai jua ke Sang Maha Cinta.

    Bandung, 14 Juni 2011

    Penulis

    x

  • Daftar Isi

    Abstrak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii

    Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv

    Pedoman Penggunaan Disertasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viii

    Ucapan Terima Kasih . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ix

    Daftar Isi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi

    Daftar Gambar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiii

    Daftar Lambang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xv

    Bab I Pendahuluan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1I.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1I.2 Tujuan dan Lingkup Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . 4I.3 Sistematika Penulisan Disertasi . . . . . . . . . . . . . . . . . . . . . . . . . . 4

    Bab II Berbagai Konsep Dimensi dalam Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6II.1 Definisi dan operasi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6II.2 Dimensi metrik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8II.3 Dimensi partisi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12II.4 Kaitan antara dimensi partisi dan parameter lainnya . . . . . . . . 14II.5 Dimensi partisi graf asal dan graf hasil operasi . . . . . . . . . . . . . 18

    Bab III Dimensi Partisi Sejumlah Graf Pohon . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28III.1 Dimensi partisi graf ulat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28III.2 Dimensi partisi graf kembang api . . . . . . . . . . . . . . . . . . . . . . . 36III.3 Dimensi partisi graf pohon pisang . . . . . . . . . . . . . . . . . . . . . . . 43

    Bab IV Dimensi Partisi Graf Multipartit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48IV.1 Dimensi partisi graf multipartit lengkap . . . . . . . . . . . . . . . . . . . 48IV.2 Dimensi partisi graf bipartit minus matching . . . . . . . . . . . . . . . 52IV.3 Dimensi partisi graf tripartit minus matching . . . . . . . . . . . . . . 59

    Bab V Dimensi Partisi Graf Hasil Operasi Korona . . . . . . . . . . . . . . . . . . . . . . . 63V.1 Batas atas dimensi partisi graf hasil operasi korona . . . . . . . . . 63V.2 Dimensi partisi graf lintasan korona graf lengkap . . . . . . . . . . . 64V.3 Dimensi partisi graf lintasan korona graf bintang . . . . . . . . . . . 68V.4 Dimensi partisi graf lengkap korona graf lengkap . . . . . . . . . . 73V.5 Dimensi partisi graf persahabatan . . . . . . . . . . . . . . . . . . . . . . . . 78V.6 Dimensi partisi graf kincir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79V.7 Dimensi partisi graf bintang korona graf lengkap . . . . . . . . . . . 81

    Bab VI Simpulan dan Masalah Terbuka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85VI.1 Simpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85VI.2 Masalah terbuka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

    Daftar Pustaka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

    xi

  • Indeks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

    xii

  • Daftar Gambar

    Gambar II.1 Graf terhubung G dengan diam(G) = 4 . . . . . . . . . . . . . . 6Gambar II.2 a.Union graf lintasan P3 dan P5, dan b.Join graf

    lintasan P3 dan P5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7Gambar II.3 a.Graf lengkap K3 dan graf lintasan P3, b.Graf hasil

    kartesian P3 K3, dan c.Graf hasil korona P3 K3 . . . 8Gambar II.4 Himpunan pembeda dari K2,4: a.W1 = {a1, b1, b2, b3,

    b4}, b.W2 = {a1, b1, b2, b3}, dan c.W3 = {a1, b1, b2} . . . . 9Gambar II.5 Sebuah graf G dengan q (G) dan p / (G) . . . . . . . . 10Gambar II.6 Partisi pembeda dariK2,4: a.1 = {S1, S2, S3, S4, S5},

    b.2 = {S1, S2, S3, S4}, dan c.3 = {S1, S2, S3} . . . . . . 13Gambar II.7 a.pd(Z2, 4) = 3 dan b.pd(Z2, 8) = 4, namun dimensi

    metrik kedua graf tak berhingga . . . . . . . . . . . . . . . . . . . . . 16Gambar II.8 a.Dimensi partisi dari graf G dinyatakan oleh banyak

    simpul anting pada simpul x1 dan b.Dimensi metrikdari graf G dinyatakan oleh banyak simpul putih padagraf tersebut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

    Gambar II.9 Graf bintang ganda T (r, s) dengan deg(u) = r+ 1 dandeg(v) = s+ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

    Gambar II.10 Graf pohon dengan4t(T ) = 3 . . . . . . . . . . . . . . . . . . . . . 20Gambar II.11 Graf gir G8 dan graf helm H4 . . . . . . . . . . . . . . . . . . . . . . . 21Gambar II.12 Graf bunga matahari SF4 . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    Gambar III.1 a.Graf ulat homogen C(3; 4) dan b.Graf ulat tak-homogen C(4; 4, 3, 2, 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

    Gambar III.2 Dua kondisi subgraf graf ulat K1,ni dan K1,nj yangberjarak sama . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

    Gambar III.3 Partisi pembeda minimum graf C(10; 3, 4, 3, 1, 3, 4,2, 2, 4, 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    Gambar III.4 Partisi pembeda minimum graf C(11; 3, 4, 3, 1, 3, 4, 2,2, 4, 4, 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

    Gambar III.5 a.Partisi pembeda minimum graf C(6; 1, 1, 1, 1, 1, 1)dan b.Partisi pembeda minimum graf C(4; 2, 2, 2, 2) . . . . 35

    Gambar III.6 a.Graf kembang api homogen dan b.Graf kembang apitak-homogen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

    Gambar III.7 Dua kondisi subgraf kembang api K1,ni dan K1,njberjarak sama . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

    Gambar III.8 a.Partisi pembeda minimum dari graf F (2; 3) danb.Partisi pembeda minimum dari graf F (2; 4) . . . . . . . . . 41

    Gambar III.9 Partisi pembeda minimum graf F (6; 2, 2, 2, 2, 2, 2) . . . . . 42Gambar III.10 Graf pohon pisang homogen B(3; 5) . . . . . . . . . . . . . . . . . 44Gambar III.11 Partisi pembeda minimum graf pohon pisang B(3; 5) . . . 45Gambar III.12 Partisi pembeda minimum graf pohon pisang B(16; 4) . . 46

    xiii

  • Gambar IV.1 a.Graf tripartit K4,4,4 dan b.Contoh himpunan ber-indeks Ii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

    Gambar IV.2 a.Graf bipartit K4,4 minus perfect matching dan b.Grafbipartit K4,6 minus maximum matching . . . . . . . . . . . . . . 52

    Gambar IV.3 a.Sisi perfect matching graf K4,4,4 dan b.Sisi near-perfect matching graf K5,5,5 . . . . . . . . . . . . . . . . . . . . . . . . 60

    Gambar V.1 Partisi pembeda graf P6 K4 . . . . . . . . . . . . . . . . . . . . . . 65Gambar V.2 a.Partisi pembeda graf Pm K1,2 dengan m = 3 dan

    b.Partisi pembeda graf Pm K1,2 dengan m = 4 . . . . . . 72Gambar V.3 Partisi pembeda graf K11 K3 . . . . . . . . . . . . . . . . . . . . . 74Gambar V.4 a.Graf persahabatan f4 dan b.Graf kincir W 44 . . . . . . . . . . 80Gambar V.5 Graf K1,m korona Kn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

    xiv

  • Daftar Lambang

    PemakaianLambang Keterangan pertama kali

    pada halaman

    B(m;n) Graf pohon pisang homogen . . . . . . . . . . . . . . . . . . . . . . . . 43

    C(m;n) Graf ulat homogen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

    C(m;n1, n2, , nm) Graf ulat tak-homogen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

    cpd(G) Dimensi partisi terhubung graf G . . . . . . . . . . . . . . . . . . . . 14

    deg(v) Derajat simpul v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

    diam(G) Diameter graf G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

    dim(G) Dimensi metrik graf G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

    d(u, v) Jarak dari simpul u ke v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

    d(v, S) Jarak dari simpul u ke subhimpunan S . . . . . . . . . . . . . . . . 7

    4t(T ) = 3 Derajat terminal maksimum simpul mayor eksterior daripohon T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

    F (m;n) Graf kembang api homogen. . . . . . . . . . . . . . . . . . . . . . . . . 36

    F (m;n1, n2, , nm) Graf kembang api tak-homogen . . . . . . . . . . . . . . . . . . . . . 36

    g(n, d) Bilangan bulat positif terkecil k sedemikian hingga (d +1)k n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

    G1 +G2 Graf G1 join G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

    G1 G2 Graf G1 kartesian G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

    G1 G2 Graf G1 korona G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

    G1 G2 Graf G1 union G2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

    G2n Graf gir order 2n+ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

    xv

  • Hn Graf helm order 2n+ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    K1,n Graf bintang order n+ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

    Kn Graf lengkap order n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

    Kn1,n2, ,nr Graf r-partit lengkap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

    Kn,n,n Graf tripartit homogen lengkap . . . . . . . . . . . . . . . . . . . . . . 59

    mKn m buah kopi disjoin dari graf lengkap Kn . . . . . . . . . . . . . 4

    pd(G) Dimensi partisi graf G . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

    ppd(G) Dimensi partisi lintasan graf G . . . . . . . . . . . . . . . . . . . . . . 14

    Pn Graf lintasan order n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

    spd(G) Dimensi partisi bintang graf G . . . . . . . . . . . . . . . . . . . . . . 14

    SFn Graf bunga matahari order 2n+ 1 . . . . . . . . . . . . . . . . . . . 22

    V (G) Himpunan simpul graf G = (V,E) . . . . . . . . . . . . . . . . . . . 1

    w W Simpul w anggota himpunan W . . . . . . . . . . . . . . . . . . . . . . 1

    Wmn Graf kincir order mn+ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

    Wn Graf roda order n+ 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

    W V (G) W himpunan bagian dari atau sama dengan V (G) . . . . . . 1

    (Z2, 4) Graf planar teratur-4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

    (Z2, 8) Graf teratur-8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

    xvi

  • Bab I Pendahuluan

    Pada Bab I ini diberikan latar belakang pemilihan topik penelitian dalam disertasi,

    tujuan dan ruang lingkup, dan sistematika penulisan.

    I.1 Latar Belakang

    Representasi dan klasifikasi senyawa kimia adalah salah satu masalah yang dihadapi

    oleh para kimiawan. Permasalahan ini dapat diuraikan sebagai berikut: Pertama,

    bagaimana merepresentasikan dua atau lebih senyawa kimia yang mempunyai

    rumus kimia sama tetapi mempunyai struktur berbeda. Kedua, bagaimana

    merepresentasikan dua senyawa kimia yang mempunyai rumus kimia berbeda

    tetapi mempunyai struktur sama. Dalam reaksi kimia, struktur sebuah senyawa

    kimia menentukan karakteristik senyawa tersebut. Representasi yang unik akan

    memudahkan klasifikasi sebuah senyawa kimia.

    Johnson (1993), seorang kimiawan pada sebuah perusahaan farmasi, menggunakan

    konsep himpunan pembeda yang dikenalkan secara terpisah oleh Slater (1975) dan

    oleh Harary dan Melter (1976). Dengan konsep ini, senyawa kimia direpresen-

    tasikan secara unik sebagai objek matematika. Klasifikasi senyawa kimia dilakukan

    dengan mempelajari dan mengklasifikasi objek matematika ini (Chartrand dan

    Zhang, 2003). Senyawa kimia direpresentasikan dalam bentuk graf. Simpul

    graf menyatakan atom, dan sisi graf menyatakan ikatan valensi antara dua atom.

    Misalkan V (G) adalah himpunan semua simpul di graf G dan W adalah himpunan

    sejumlah simpul terurut, dengan W V (G). Dengan menghitung jarak setiapsimpul v V (G) terhadap setiap simpul w W , konsep himpunan pembedamemastikan setiap simpul v V (G) mempunyai representasi berbeda. Jika duasenyawa berbeda mempunyai himpunan V (G) dan jarak v ke w yang sama, untuk

    semua v V (G) dan w W , maka kedua senyawa tersebut dalam satu klasifikasi.

    Selanjutnya, Chartrand dkk. (1998) mengenalkan konsep partisi pembeda yang

    merupakan bentuk serupa dari himpunan pembeda suatu graf. Chartrand dkk.

    (1998) melakukan pengelompokan simpul di graf G ke dalam sejumlah kelas

    partisi dan menghitung jarak setiap simpul di G terhadap semua kelas partisi untuk

    1

  • merepresentasikan setiap simpul pada graf G.

    Himpunan pembeda W memastikan representasi berbeda untuk semua simpul di

    grafG, yaitu dengan menunjukkan jarak simpul v V (G) ke semua simpul diW V (G) dan dimensi metrik memastikan kardinalitas W adalah minimal. Sedangkan

    partisi pembeda memastikan representasi berbeda untuk semua simpul di graf G,

    yaitu dengan menunjukkan jarak simpul v V (G) ke semua kelas partisi dalam dan dimensi partisi memastikan kardinalitas adalah minimal.

    Pada paper pertama tentang dimensi partisi, Chartrand dkk. (1998) menunjukkan

    dimensi partisi graf bintang ganda T dan memberikan batas atas dan batas bawah

    dimensi partisi graf ulat (caterpillar). Dua tahun kemudian Chartrand, Salehi dan

    Zhang (2000) membuktikan bahwa sebuah graf G mempunyai pd(G) = 2 jika dan

    hanya jika G adalah graf lintasan Pn dan menunjukkan bahwa graf G mempunyai

    pd(G) = n jika dan hanya jika G = Kn.

    Selain itu, Chartrand, Salehi dan Zhang (2000) mengkarakterisasi semua graf

    terhubung G order n yang mempunyai dimensi partisi (n 1). Jika G adalah grafterhubung order n 2 maka pd(G) = n1 jika dan hanya jika G adalah salah satudari graf berikut: K1,n1, Kn e, atau K1 + (K1Kn2). Karakterisasi berikutnyadilakukan oleh Tomescu (2008), yaitu mengkarakterisasi semua graf terhubung G

    order n yang mempunyai dimensi partisi (n 2). Tomescu (2008) menunjukkanhanya terdapat 23 graf tak-isomorfik yang mempunyai dimensi partisi n2. Dengandemikian, dimensi partisi dari sebarang graf terhubung G order n lainnya terletak

    pada selang [3, (n3)]. Namun, problem penentuan dimensi partisi untuk sebaranggraf terhubung G adalah NP-Complete (Garey dan Johnson, 1979).

    Dimensi partisi untuk beberapa kelas graf tertentu telah dikaji oleh banyak peneliti,

    misalnya dimensi partisi graf pohon (graf bintang ganda, graf ulat (Chartrand dkk.,

    1998), graf bintang, graf bipartit (Chartrand, Salehi dan Zhang, 2000)), graf roda

    (Tomescu dkk., 2007), dan graf mirip roda (graf gir, graf helm, graf bunga matahari

    (Javaid dan Shokat, 2008)). Lebih jauh, Chartrand dkk. (1998) dan Yero dkk. (2010)

    menentukan dimensi partisi graf hasil operasi kartesian antara dua graf terhubung.

    Penelitian dimensi partisi untuk graf tak hingga dimulai oleh Tomescu (2008). Ia

    menunjukkan graf planar teratur-4 (Z2, 4) mempunyai dimensi partisi 3 dan grafteratur-8 (Z2, 8) mempunyai dimensi partisi 4. Graf planar teratur-4 (Z2, 4)adalah graf yang memiliki himpunan simpul V ((Z2, 4)) = Z2 dan himpunan sisi

    2

  • graf (Z2, 4) adalah semua pasangan simpul di (Z2, 4) yang memiliki jarak blokkota 1. Jarak blok kota dari dua simpul (i, j) dan (i, j) pada (Z2, 4) didefi-nisikan dengan d4((i, j), (i, j)) = |i i| + |j j|. Semua daerah pada grafplanar teratur-4 (Z2, 4) berupa bujursangkar. Graf teratur-8 (Z2, 8) adalah grafyang memiliki himpunan simpul V ((Z2, 8)) = Z2 dan himpunan sisi graf (Z2, 8)adalah semua pasangan simpul di (Z2, 8) yang memiliki jarak papan catur 1. Jarakpapan catur dari dua simpul (i, j) dan (i, j) pada (Z2, 8) didefinisikan sebagaid8((i, j), (i

    , j)) = maks(|i i|, |j j|). Graf teratur-8 (Z2, 8) dapat diperolehdengan menggambarkan semua diagonal pada setiap daerah bujursangkar dari graf

    (Z2, 4).

    Dalam hal nilai dimensi partisi dari suatu graf belum dapat ditentukan, peneliti

    memberikan batas atas dan batas bawah dimensi partisi dari graf tersebut. Misalkan

    graf rodaWn, dimensi partisi graf roda pd(Wn) diberikan dalam selang d(2n)1/3e pd(Wn) p + 1, dengan p adalah bilangan prima terkecil sedemikian hinggap(p 1) n (Tomescu dkk., 2007).

    Di antara banyak kelas graf, graf pohon termasuk kelas graf sederhana yang penting

    karena digunakan secara luas tidak hanya di banyak bidang aplikasi tetapi juga

    dalam Teori Graf sendiri. Graf pohon adalah graf terhubung yang tidak memuat

    siklus. Graf pohon digunakan antara lain pada analisis hirarki bisnis, penentuan

    biaya minimum pada jaringan transportasi, dan dasar struktur data pada ilmu

    komputer (Bona, 2002). Ketika berdiskusi tentang suatu konsep atau dugaan dalam

    teroi graf, biasanya orang mengkaji konsep tersebut atau memeriksa dugaan tersebut

    pada kelas pohon terlebih dahulu (Bin dan Zhongyi, 2010).

    Dalam hal dimensi metrik, Chartrand, Eroh, Johnson dan Oellermann (2000) telah

    berhasil memberikan dimensi metrik untuk sebarang graf pohon T secara lengkap.Namun, tidak demikian untuk dimensi partisi graf pohon. Hanya beberapa graf

    dalam kelas pohon yang telah diketahui dimensi partisinya, seperti graf bintang

    ganda dan graf bintang. Lebih jauh, dimensi partisi graf ulat baru didapatkan batas

    atas dan batas bawahnya (Chartrand dkk., 1998). Untuk itu, kami akan membahas

    dimensi partisi beberapa graf dalam kelas pohon, yaitu graf ulat (caterpillar), graf

    kembang api (firecracker), dan graf pohon pisang (banana tree).

    Chartrand, Salehi dan Zhang (2000) mengawali penelitian dimensi partisi untuk

    kelas graf multipartit dengan menentukan dimensi partisi graf bipartit. Oleh karena

    3

  • baru dimensi partisi graf bipartit yang telah diketahui, dalam disertasi ini kami

    membahas pula dimensi partisi graf r-partit, graf bipartit minus sebuah matching,

    dan graf tripartit minus sebuah matching.

    Demikian pula halnya dengan penentuan dimensi partisi graf hasil operasi biner

    antara dua graf. Chartrand dkk. (1998) dan Yero dkk. (2010) memberikan dimensi

    partisi graf hasil operasi kartesian antara dua graf terhubung. Dalam disertasi ini

    kami membahas dimensi partisi graf hasil operasi korona antara dua graf terhubung.

    I.2 Tujuan dan Lingkup Penelitian

    Penelitian dalam disertasi ini mempunyai 3 tujuan berikut:

    Pertama, menentukan dimensi partisi graf kelas pohon, yaitu graf ulat, graf

    kembang api, dan graf pohon pisang .

    Kedua, menentukan dimensi partisi graf r-partit. Tujuan kedua ini dapat dipandang

    sebagai perumuman dari dimensi partisi graf bipartit hasil penelitian (Chartrand,

    Salehi dan Zhang, 2000). Lebih dari itu, kami juga menentukan dimensi partisi graf

    bipartit minus sebuah matching dan graf tripartit minus sebuah matching.

    Ketiga, menentukan dimensi partisi graf hasil operasi korona antara dua graf

    terhubung, yaitu F = GH . Kami menentukan batas atas dimensi partisi GHuntuk sebarang graf G dan graf H berdiameter paling banyak 2. Untuk kasus

    tertentu, kami menentukan dimensi partisi graf dari: PmKn, PmK1,n,KmKn,K1mKn, danK1,mKn, dengan Pm, Km, K1,m danmKn masing-masing adalahgraf lintasan order m, graf lengkap order m, graf bintang order m + 1, dan m kopi

    disjoin graf lengkap Kn. Graf K1 mKn isomorf dengan graf kincir Wmn . Untukn = 2 graf kincir Wmn isomorf dengan graf persahabatan fm.

    I.3 Sistematika Penulisan Disertasi

    Disertasi ini ditulis dengan sistematika sebagai berikut.

    Bab I memberi paparan tentang latar belakang dan perumusan masalah. Peta

    jalan (road map) penelitian dalam bidang dimensi partisi, dari sejak awal sebagai

    topik penelitian sampai penelitian terbaru, juga diberikan dalam bab ini. Dengan

    demikian, pembaca akan menemukan keterkaitan penelitian dalam disertasi ini

    4

  • dengan hasil-hasil yang sudah diperoleh oleh para peneliti sebelumnya dan, pada

    saat yang sama, dapat melihat kecenderungan penelitian dalam bidang ini pada

    masa yang akan datang.

    Dasar-dasar teori graf, definisi dan peristilahan yang diperlukan dalam pembahasan

    dimensi partisi sebuah graf diberikan dalam Bab II. Seperti disampaikan di atas,

    dimensi partisi dapat dipandang sebagai ragam lain dari konsep himpunan pembeda

    dan dimensi metrik sebuah graf. Dengan demikian, agar pembaca lebih mudah

    memahami konsep dimensi partisi, paparan tentang dimensi metrik diberikan

    mendahului paparan tentang konsep dimensi partisi. Pada bagian akhir Bab II

    diberikan teorema-teorema dimensi partisi hasil penelitian peneliti sebelumnya.

    Sejumlah teorema yang terkait langsung dengan penelitian dalam disertasi ini

    disertai dengan pembuktiannya.

    Hasil-hasil penelitian dalam disertasi ini diberikan dalam Bab III dan Bab IV. Bab

    III berisi bahasan dimensi partisi dari sejumlah graf dalam kelas pohon, seperti graf

    ulat, graf kembang api, dan graf pohon pisang. Pada bagian akhir Bab III diberikan

    bahasan dimensi partisi dari graf multipartit, graf bipartit minus sebuah matching,

    dan graf tripartit minus sebuah matching.

    Hasil-hasil dan pembahasan dimensi partisi graf hasil operasi korona antara dua graf

    terhubung G dan H diberikan dalam Bab IV. Pembahasan diawali dengan teorema

    yang memberi batas atas dari dimensi partisi graf F = G H dengan diameterdiam(H) 2. Graf hasil operasi korona yang juga dibahas dimensi partisinyadalam bab ini adalah graf PmKn, PmK1,n,KmKn,K1mKn, danK1,mKn.

    Bab V berisi simpulan dan sejumlah masalah terbuka dalam penelitian dimensi

    partisi. Masalah terbuka pada bab ini diharapkan dapat menjadi bahan diskusi

    dan stimulasi dimulainya penelitian lanjut dalam bidang dimensi partisi sebuah graf

    terhubung G.

    Hasil utama penelitian disertasi ini dinyatakan dalam bentuk lema, teorema, dan

    akibat yang diberi tanda .

    5

  • Bab II Berbagai Konsep Dimensi dalam Graf

    Pada Bab II ini akan dipaparkan beberapa definisi dan istilah dalam teori graf yang

    terkait dengan dimensi partisi sebuah graf terhubung G. Di bagian akhir bab ini

    juga diberikan hasil-hasil penelitian dalam bidang dimensi partisi dari para peneliti

    sebelumnya.

    II.1 Definisi dan operasi

    GrafG = (V,E) didefinisikan sebagai suatu sistem yang terdiri atas dua himpunan,

    yaitu himpunan tak kosong V (G) yang elemennya disebut simpul (vertex) dan

    himpunan (mungkin kosong) E(G) V 2 = {{u, v}|u, v V }. Setiap elemen diE(G) disebut sisi (edge). Jika e = {u, v} E(G) maka u dikatakan bertetanggadengan v dan sisi e dikatakan melekat pada simpul u dan v. Untuk penyederhanaan

    penulisan, sisi e = {u, v} ditulis e = uv dan graf G = (V,E) ditulis G.

    Simpul u dikatakan terhubung dengan simpul v jika terdapat lintasan dari u ke v

    di G. Dalam hal ini, simpul v disebut dapat dicapai (accessible) dari simpul u.

    Jika simpul u dan v terhubung maka panjang lintasan terpendek dari u ke v disebut

    jarak dari u ke v dan dinotasikan dengan d(u, v). Jika G tidak memiliki lintasan

    dari u ke v maka didefinisikan d(u, v) =. GrafG dikatakan terhubung jika setiapdua simpul berbeda u, v V (G) terhubung. Graf G pada Gambar II.1 adalah grafterhubung. Jarak simpul a ke g, d(a, g) = 3.

    Jika simpul u V (G) dan subhimpunan S V (G), maka jarak dari u keS didefinisikan sebagai min{d(u, x)|x S} dan dinotasikan dengan d(u, S).Jelas, untuk u S, d(u, S) = 0. Diameter dari graf G didefinisikan sebagai

    D

    D D

    D

    D

    D D

    D

    a

    D

    b c

    d

    ef

    g

    h

    i

    S

    Gambar II.1: Graf terhubung G dengan diam(G) = 4

    .

    6

  • DDD D

    DD D

    DDD D

    DD D

    D D

    1 2 3 4 5 1 2 3 4 5

    1 2 31 2 3

    Gambar II.2: a.Union graf lintasan P3 dan P5, dan b.Join graf lintasan P3 dan P5.

    max{d(x, y)|x, y V (G)} dan dinotasikan dengan diam(G). Perhatikan graf Gpada Gambar II.1, d(a, S) = 2 dan diam(G) = 4.

    Misalkan G1 = (V1, E1) dan G2 = (V2, E2) dua graf terhubung. Suatu graf baru

    G dapat dibangun dengan mengenakan operasi biner pada graf G1 dan G2. Berikut

    ini diberikan empat contoh operasi biner, yaitu union, join, kartesian, dan korona.

    Union G = G1 G2 adalah graf G(V,E) dengan V (G) = V (G1) V (G2) danE(G) = E(G1) E(G2). Jadi, graf G = G1 G2 terdiri atas sebuah kopi graf G1bersama-sama dengan sebuah kopi graf G2. Gambar II.2.a memberikan gambaran

    graf hasil operasi union P3 dan P4.

    Join dua graf G1 dan G2, dinotasikan dengan G = G1 +G2, mempunyai himpunansimpul V (G) = V (G1) V (G2) dan himpunan sisi E(G) = E(G1) E(G2) {uv|u V (G1) dan v V (G2)}. Dengan kata lain, graf G = G1 + G2 diperolehdengan menambahkan pada G1G2 sisi-sisi yang mempunyai satu simpul ujung diG1 dan simpul ujung lainnya di G2. Jika graf G1 dan G2 masing-masing berorder

    m dan n, maka untuk mendapatkan graf G1 + G2 kita menambahkan mn buah sisi

    pada graf G1 G2. Gambar II.2.b memberikan gambaran graf hasil operasi join P3dan P4.

    Hasil kali kartesian antara graf G1 dan graf G2, dinotasikan dengan G = G1 G2, menghasilkan sebuah graf baru G yang mempunyai himpunan simpul V (G) =

    V (G1) V (G2) dan himpunan sisi E(G) = E(G1) V (G2) V (G1) E(G2).Simpul ujung sisi (d, v) E(G) V (G2) adalah simpul-simpul (x, v) dan (y, v)dengan x dan y adalah simpul ujung dari sisi d E(G1). Simpul ujung sisi (u, e) V (G)E(G2) adalah simpul (u, s) dan (u, t), dengan s dan t adalah simpul ujungdari sisi e E(G2). Gambar II.3.b mengilustrasikan graf hasil kali kartesian P3 K3.

    7

  • Dx

    D

    D

    D

    b1

    (c)

    a1

    D

    y

    D

    D

    D

    D

    zD

    D

    D

    DD

    D

    DD

    D

    DD

    D

    (a,x)

    (a)DD

    D

    DD

    D

    x

    y

    z

    a

    b c (c,x)(b,x)

    (a,y)

    (c,y)(b,y)

    (a,z)

    (c,z)(b,z)

    K3 :

    P3 :

    c1 b2 b3c2 c3

    a2 a3

    (b)

    Gambar II.3: a.Graf lengkap K3 dan graf lintasan P3, b.Graf hasil kartesian P3 K3, dan c.Graf hasil korona P3 K3

    Hasil kali korona G = G1 G2 didefinisikan sebagai graf yang yang diperolehdari G1 dan G2 dengan mengambil sebuah kopi dari G1 dan |V (G1)| kopi dari G2dan kemudian menghubungkan dengan sebuah sisi setiap simpul dari kopi ke-i dari

    G2 dengan sebuah simpul ke-i dari G1, dengan 1 i |V (G1)|, Gambar II.3.bmengilustrasikan graf hasil kali korona P3 K3.

    Misalkan Gi2 adalah kopi ke-i dari graf G2 dalam G1 G2. Karena semua simpulpada Gi2 dihubungkan dengan sebuah simpul di G1, dan bila diam(G2) 3,maka operasi korona menyebabkan diam(Gi2 K1) = 2. Jika diam(G2) 2,maka diam(Gi2)K1 tidak berubah. Seperti ditunjukkan pada Gambar II.3.b, graflengkapK3 mempunyai diam(K3) = 1 = diam(Ki3xi) untuk suatu i pada selang[1, 3].

    II.2 Dimensi metrik

    Slater (1975) mengenalkan konsep himpunan pembeda dengan istilah locating

    set, sedangkan Harary dan Melter (1976) menamakan konsep tersebut dengan

    resolving set. Misalkan G = (V,E) adalah graf dengan himpunan simpul

    V (G) dan himpunan sisi E(G). Jika subhimpunan terurut W V (G), denganW = {w1,w2, , wk}, dan v V (G) maka representasi v terhadap W didefini-sikan sebagai pasangan-k terurut (d(v, w1),d(v, w2), , d(v, wk)) dan dinotasikandengan r(v|W ). Jika untuk setiap dua simpul berbeda u, v V (G) berlakur(u|W ) 6= r(v|W ), maka W disebut himpunan pembeda dari V (G). Himpunanpembeda W dengan kardinalitas minimum disebut himpunan pembeda minimum

    atau basis dari G. Semua simpul anggota basis dari G disebut simpul basis dari G.

    Dimensi metrik dari grafG, dinotasikan dim(G), adalah banyak simpul dalam basis

    8

  • (c)(a) (b)

    D

    a1 a2

    b1 b2 b3 b4

    D

    a1 a2

    b1 b2 b3 b4

    D

    a1 a2

    b1 b2 b3 b4

    Gambar II.4: Himpunan pembeda dari K2,4: a.W1 = {a1, b1, b2, b3, b4}, b.W2 ={a1, b1, b2, b3}, dan c.W3 = {a1, b1, b2}

    G. Jika dim(G) = k maka G dikatakan berdimensi metrik k.

    Representasi dari dua sebarang simpul wi, wj W , dengan i 6= j, masing-masing mempunyai 0 pada koordinat ke-i dan ke-j. Oleh karena itu, representasi

    r(wi|W ) 6= r(wj|W ) berbeda untuk i 6= j .Dengan demikian, untuk menentukanapakah W adalah sebuah himpunan pembeda pada graf G, pemeriksaan cukup

    dilakukan pada semua simpul di V (G)W . Jika d(u, x) 6= d(v, x) maka simpul xdikatakan membedakan simpul u dan v, atau simpul u dan v dapat dibedakan oleh

    simpul x. Hal yang sama, jika r(u|W ) 6= r(v|W ), maka dikatakan himpunan Wmembedakan simpul u dan v, atau simpul u dan v dibedakan oleh himpunan W .

    Gambar II.4 mengilustrasikan suatu himpunan terurut W K2,4 untuk grafbipartit lengkap K2,4. Gambar II.4.a menunjukkan bahwa W1 = {a1, b1, b2, b3, b4}adalah himpunan pembeda karena semua simpul di K2,4 mempunyai representasi

    yang berbeda. Akan tetapi, kardinalitas W1 tidak minimum, karena pada Gambar

    II.4.b dapat ditunjukkan bahwa W2 = {a1, b1, b2, b3} adalah himpunan pembeda.Himpunan W3 = {a1, b1, b2} pada Gambar II.4.c bukanlah himpunan pembeda,karena representasi r(b3|W3) = r(b4|W3) = (1, 2, 2). Selanjutnya, kamimenunjukkan himpunan pembeda dari K2,4 mempunyai kardinalitas sedikitnya 4.

    Misalkan terdapat himpunan pembeda W dari K2,4 dengan |W | = 3 dan V1 danV2 masing-masing adalah partisi dari K2,4. Karena order K2,4 sama dengan 6,

    maka sedikitnya terdapat dua simpul u, v V1 atau u, v V2 sedemikian hinggau, v 6 W . Oleh karena d(u,w) = d(v, w) untuk semua w V (K2,4) {u, v},maka r(u|W ) = r(v|W ), kontradiksi dengan pemisalan W sebagai himpunanpembeda. Jadi, |W | 4. Dengan demikian, W2 adalah salah satu himpunanpembeda minimum dari K2,4 dan karena itu dimensi metrik dari graf K2,4 adalah 4.

    Saputro dkk. (2010) memberikan Teorema II.1 untuk menentukan dimensi metrik

    dari graf r-partit lengkap untuk r 2.

    9

  • DD D D

    DD D D

    D D

    Gambar II.5: Sebuah graf G dengan q (G) dan p / (G).

    Teorema II.1. (Saputro dkk., 2010) Jika G = Kn1,n2, ,nr adalah graf multipartitlengkap untuk r 2 dengan m partisi tunggal, maka

    dim(G) =

    {|V (G)| 1 (r m) , jika m > 0,|V (G)| r , jika m=0.

    Lebih jauh, Chartrand, Eroh, Johnson dan Oellermann (2000) memberikan batas

    bawah dan batas atas untuk dimensi metrik G, dim(G), yang dinyatakan dalam

    diameter dari G pada Teorema II.2 berikut ini.

    Teorema II.2. (Chartrand, Eroh, Johnson dan Oellermann, 2000) Misalkan Gadalah graf terhubung dengan diameter k dan orde n 2, dimana k < n. Maka,berlaku

    f(n, k) dim(G) n k,

    f(n, k) adalah bilangan bulat positif terkecil r sedemikian hingga k + kr n.

    Pandang sebuah graf G = (V,E). Misalkan u, v V (G). Simpul u disebutsimpul batas dari simpul v jika d(w, v) d(u, v) untuk setiap w N(u), denganN(u) adalah himpunan semua simpul di G yang bertetangga dengan u. Selan-

    jutnya, simpul u disebut simpul batas dari G jika u adalah sebuah simpul batas

    untuk suatu simpul di G. Himpunan semua simpul batas dari G disebut batas dari

    G, dinotasikan dengan (G) (Chartrand dkk., 2003). Gambar II.5 menunjukkan

    bahwa simpul q adalah simpul batas dari p tapi tidak untuk sebaliknya. Lebih jauh,

    simpul p / (G).

    Caceres dkk. (2005) menyatakan bahwa batas atas dimensi metrik suatu graf

    G adalah kardinalitas himpunan batas G sebagaimana yang dinyatakan dalam

    10

  • Teorema II.3 berikut ini.

    Teorema II.3. (Caceres dkk., 2005) Misalkan G adalah graf terhubung tak trivialdan (G) adalah himpunan batas dari G. Maka dim(G) (G).

    Dimensi metrik untuk beberapa graf G dapat ditentukan dengan menggunakan

    Teorema II.2. Jika G = Pn maka diameter G adalah n 1 dan fungsi f(n, k)pada II.2 bernilai 1. Dengan menggunakan Teorema II.2, diperoleh dim(Pn) = 1.

    Selanjutnya, andaikan ada graf lain G yang terhubung orde n dengan dim(G) = 1

    dan basis W = {w}. Untuk setiap simpul v G, r(v|W ) = d(v, w) adalahsuatu bilangan bulat tak negatif yang kurang dari n. Karena representasi dari setiap

    simpul v V (G) terhadap W berbeda maka terdapat sebuah simpul u V (G)sedemikian hingga d(u,w) = n 1. Oleh karena itu, diameter G adalah n 1 danmengakibatkan G = Pn.

    Misalkan G = Kn dengan n 2 dan W adalah basis dari G. Jika u / W makasetiap komponen dari representasi r(u|W ) bernilai 1. Sehingga setiap himpunanpembeda pada G harus memuat semua simpul kecuali satu simpul dari G. Jadi,

    dim(Kn) = n1. Dengan menggunakan Teorema II.2, jikaG graf terhubung yangbukan graf lengkap maka dim(G) n2. Dengan demikian, jika dim(G) n2maka haruslah graf G 6= Kn.

    Selain mengkarakterisasi dim(G) = 1 dan n 1 seperti pada dua paragraf di atas,Chartrand, Eroh, Johnson dan Oellermann (2000) juga menunjukkan karakterisasi

    dim(G) = n 2, dan menentukan dimensi metrik dari graf lingkaran Cn dan grafpohon T . Hasil-hasil di atas ditulis dalam Teorema II.4 berikut ini dan merupakan

    hasil fundamental untuk dimensi metrik graf G.

    Teorema II.4. (Chartrand, Eroh, Johnson dan Oellermann, 2000) Misalkan Gadalah sebuah graf terhubung dengan orde n 2.

    (i) dim(G) = 1 jika dan hanya jika G = Pn.

    (ii) dim(G) = n 1 jika dan hanya jika G = Kn.(iii) Untuk n 3, dim(Cn) = 2.(iv) Untuk n 4, dim(G) = n 2 jika dan hanya jika G = Kr,s, (r, s 1),

    G = Kr +Ks, (r 1, s 2), atau G = Kr + (K1 Ks), (r, s 1).

    11

  • (v) Jika T adalah graf pohon yang bukan lintasan maka dim(T ) = (T ) ex(T ),dimana (T ) menyatakan jumlah derajat terminal dari simpul utama T , dan

    ex(T ) menyatakan jumlah simpul utama bagian luar T .

    II.3 Dimensi partisi

    Dimensi partisi dari sebuah graf G dikenalkan oleh Chartrand dkk. pada tahun

    1998. Mereka mengelompokkan semua simpul diG ke dalam sejumlah kelas partisi

    dan menentukan jarak setiap simpul terhadap setiap kelas partisi tersebut. Secara

    tepat, misalkan = {S1, S2, , Sk} merupakan partisi terurut dari V (G) danv V (G). Representasi dari v V (G) terhadap didefinisikan sebagai pasangan-k terurut (d(v, S1), d(v, S2), , d(v, Sk)). Jika untuk setiap dua simpul berbedau, v V (G) berlaku r(u|) 6= r(v|), maka disebut partisi pembeda dari V (G).Partisi pembeda dengan kardinalitas minimum disebut partisi pembeda minimum

    dari G. Dimensi partisi pd(G) dari graf G adalah kardinalitas dari partisi pembeda

    minimum dari G.

    Misalkan = {S1, S2, , Sk} adalah partisi terurut dari V (G). Jika u Si danv Sj , dan i 6= j, maka jelas bahwa r(u|) 6= r(v|) (karena d(u, Si) = 0tetapi d(v, Si) 6= 0). Dengan demikian, ketika diberikan sebuah partisi dariV (G) dan hendak menentukan apakah adalah partisi pembeda untuk V (G) atau

    bukan, pemeriksaan cukup dilakukan pada semua simpul yang termasuk dalam

    suatu kelas partisi yang sama. Jika semua simpul dalam setiap kelas partisi yang

    sama mempunyai representasi berbeda terhadap , maka merupakan partisi

    pembeda. Jika d(u, Si) 6= d(v, Si), maka kelas partisi Si dikatakan memisahkansimpul u dan v di G. Sebuah kelas partisi yang mempunyai satu anggota disebut

    kelas partisi singleton. Dengan sendirinya, simpul dalam kelas partisi singleton

    mempunyai representasi yang unik.

    Sekarang, pandang dua simpul berbeda u, v V (G). Jika d(u,w) = d(v, w) untuksetiap w V (G) {u, v} maka u dan v harus termuat dalam kelas partisi yangberbeda di G. Hal ini jelas, karena jika tidak demikian, r(u|) = r(v|). Dengandemikian diperoleh Lema II.1 berikut ini.

    Lema II.1. (Chartrand, Salehi dan Zhang, 2000) Misalkan G suatu grafterhubung tak-trivial. Misalkan suatu partisi pembeda dari G dan u, v V (G).

    12

  • (c)(a) (b)

    D

    a1 a2

    b1 b2 b3 b4

    D

    a1 a2

    b1 b2 b3 b4

    D

    a1 a2

    b1 b2 b3 b4

    S1

    S2 S3

    S4S1

    S2 S3

    S4 S5 S3

    S2S1

    Gambar II.6: Partisi pembeda dari K2,4: a.1 = {S1, S2, S3, S4, S5}, b.2 ={S1, S2, S3, S4}, dan c.3 = {S1, S2, S3}

    Jika d(u,w) = d(v, w) untuk setiap w V (G) {u, v}, maka u dan v harustermuat dalam kelas partisi yang berbeda di .

    Pada bab-bab selanjutnya Lema II.1 ini banyak digunakan dalam menentukan

    dimensi partisi sebuah graf terhubung G.

    Pada Gambar II.6, diilustrasikan sebuah partisi untuk graf bipartit lengkap K2,4.

    Gambar II.6.a menunjukkan bahwa 1 = {S1, S2, S3, S4, S5}, dengan S1 = {b1},S2 = {a1, b2}, S3 = {a2},S4 = {b3} dan S5 = {b4}, adalah partisi pembedakarena semua simpul di K2,4 mempunyai representasi terhadap 1) yang berbeda.

    Akan tetapi 1 bukan partisi pembeda minimum karena pada Gambar II.4.b dapat

    ditunjukkan bahwa 2 = {S1, S2, S3, S4} dengan S1 = {b1}, S2 = {a1, b2},S3 = {a2, b3} dan S4 = {b4}, adalah partisi pembeda dari G juga. Partisi3 = {S1, S2, S3}, dengan S1 = {a1, b1}, S2 = {a2, b2} dan S3 = {b3, b4}, padaGambar II.6.c bukanlah partisi pembeda karena r(b3|3) = r(b4|3) = (1, 1, 0).

    Untuk menunjukkan pd(K2,4) = 4, andaikan terdapat partisi pembeda dari K2,4dan || = 3. Misalkan V (K2,4) terdiri atas partit V1 dan V2 dengan |V1| = 2 dan|V2| = 4. Maka, sedikitnya terdapat dua simpul u, v V2 sedemikian hingga u, vtermuat dalam kelas partisi yang sama. Oleh karena d(u,w) = d(v, w) untuk semua

    w V (K2,4) {u, v}, maka r(u|W ) = r(v|W ), kontradiksi dengan pemisalan sebagai partisi pembeda. Jadi, || 4 dan karena Gambar II.6.b telah memberikanpartisi pembeda dengan 4 anggota dari K2,4 maka pd(K2,4) = 4.

    Fehr dkk. (2006) mengembangkan konsep dimensi partisi graf berarah dengan

    menerapkan dimensi partisi pada graf berarah D. Misalkan D adalah sebuah graf

    berarah dan u, v V (D). Sisi berarah e E(D) disebut busur. Kemudianjarak dari u ke v, dinotasikan dengan d(u, v), adalah jumlah busur dalam lintasan

    13

  • terpendek dari u ke v. Jika S V (D), jarak v ke S didefinisikan dengand(v, S) = min{d(v, x)|x S}. Sebagaimana pada graf tak berarah, simpulx V (D) (atau subhimpunan S V (D)) membedakan dua simpul u dan v jikad(u, x) 6= d(v, x) (atau d(u, S) 6= d(v, S).

    Saenpholphat dan Zhang (2002) mengenalkan konsep partisi pembeda terhubung.

    Suatu himpunan partisi = {S1, S2, , Sk} disebut partisi pembeda terhubungjika (1) suatu partisi pembeda dari G dan (2) setiap subgraf yang diinduksi oleh

    Si adalah graf terhubung di G, dengan 1 i k. Nilai minimum k sedemikianhingga terdapat suatu k-partisi pembeda terhubung dari V (G) adalah nilai dimensi

    partisi terhubung dari G dan ditulis cpd(G) = k.

    Selanjutnya, Ruxandra (2009) mengkaji partisi pembeda dari suatu graf yang setiap

    subgraf Si berbentuk lintasan. Suatu himpunan partisi = {S1, S2, , Sk}disebut partisi pembeda lintasan jika (1) suatu partisi pembeda dan (2) setiap

    subgraf yang diinduksi oleh Si adalah graf lintasan di G, dengan 1 i k. Jikak adalah kardinalitas minimum dari sebarang partisi pembeda lintasan untuk V (G)

    maka dimensi partisi lintasan dari G adalah k dan ditulis ppd(G) = k.

    Lebih jauh, Marinescu-Ghemeci dan Tomescu (2010) mengenalkan partisi pembeda

    bintang. Suatu himpunan partisi = {S1, S2, , Sk} disebut partisi pembedabintang jika (1) suatu partisi pembeda dan (2) setiap subgraf yang diinduksi oleh

    Si adalah graf bintang di G, dengan 1 i k. Nilai k minimum sedemikianhingga terdapat suatu k-partisi pembeda bintang dari V (G) adalah nilai dimensi

    partisi bintang dari G dan ditulis spd(G) = k.

    II.4 Kaitan antara dimensi partisi dan parameter lainnya

    MisalkanG suatu graf dengan dimensi metrik k danW = {w1, w2, , wk} adalahhimpunan pembeda dari G. Pandang partisi terurut = {S1, S2, , Sk+1} dariV (G), dengan Si = {wi}, bila i [1, k], dan Sk+1 = V (G)W . Maka, diperolehr(v|) = (d(v, {w1}), d(v, {w2}), , d(v, {wk}), 0) berbeda untuk semua simpulv Sk+1 karena W himpunan pembeda dari G. Selain itu, bila v = wi, untuksuatu i [1, k], maka r(wi|) mempunyai nilai 0 pada entri ke-i tetapi tidak untukentri lainnya. Dengan demikian, r(wi|) juga unik. Oleh karena itu, merupakanpartisi pembeda dari G. Sehingga diperoleh Teorema II.5 berikut ini.

    14

  • Teorema II.5. (Chartrand, Salehi dan Zhang, 2000) Jika G adalah grafterhubung tak-trivial, maka pd(G) dim(G) + 1.

    Batas atas Teorema II.5 dipenuhi di antaranya oleh graf lintasan Pn, graf siklus Cn,

    graf lengkap Kn dan graf bintang K1,n.

    Dimensi partisi dari graf G tidak selalu sedikit lebih kecil dari dimensi metriknya.

    Hal ini ditunjukkan oleh graf planar teratur-4 (Z2, 4) dan graf teratur-8 (Z2, 8)yang memiliki dimensi metrik tidak berhingga (Melter dan Tomescu, 1984), namun

    dimensi partisinya berturut-turut 3 dan 4 (Tomescu, 2008). Graf (Z2, 4) adalah grafplanar teratur-4 yang daerahnya berbentuk bujursangkar, sedangkan graf teratur-

    8 (Z2, 8) dapat diperoleh dengan menggambarkan semua diagonal pada daerahbujursangkar pada graf (Z2, 4). Indeks 4 dan 8 masing-masing menunjukkanbanyak simpul berjarak 1 dari sebarang simpul pada graf tersebut. Simpul u pada

    Gambar II.7.a mempunyai empat buah simpul tetangga dan simpul v pada Gambar

    II.7.b mempunyai delapan buah simpul tetangga.

    Teorema II.6. (Tomescu, 2008) Dimensi partisi graf planar teratur 4pd(Z2, 4) = 3 dan dimensi partisi graf teratur 8 pd(Z2, 8) = 4.

    Bukti. Misalkan 1 = {S1, S2, S3} adalah partisi pembeda dari graf (Z2, 4)dengan S1 = {(x, y) Z2|x 0, y 0}, S2 = {(x, y) Z2|x 1, y 0}dan S3 = {(x, y) Z2|y 1} (lihat Gambar II.7.a). Maka, dapat ditun-jukkan bahwa setiap simpul v V ((Z2, 4)) mempunyai representasi r(v|1)unik. Dengan demikian, pd(Z2, 4) 3. Selanjutnya, Chartrand, Salehi dan Zhang(2000) menunjukkan bahwa pd(G) = 2 jika dan hanya jika G adalah graf lintasan.

    Oleh karena itu, pd(Z2, 4) 3. Jadi, pd(Z2, 4) = 3.

    Selanjutnya, misalkan 2 = {S1, S2, S3, S4} adalah partisi pembeda dari graf(Z2, 8) dengan S1 = {(x, y) Z2|x 0, y 0}, S2 = {(x, y) Z2|x 1, y 0}, S3 = {(x, y) Z2|x 0, y 1} dan S4 = {(x, y) Z2|x 1, y 1} (lihat Gambar II.7.b). Maka, dapat ditunjukkan bahwa setiap duasimpul berbeda u, v V ((Z2, 8)) mempunyai r(u|2) 6= r(v|2). Dengandemikian, pd(Z2, 8) 4. Lebih jauh, dapat ditunjukkan bahwa jika terdapatsuatu partisi pembeda 2 dari graf (Z2, 8) maka terdapat sedikitnya sebarangdua simpul berbeda u, v V ((Z2, 8)) sedemikian hingga r(u|2) = r(v|2),kontradiksi.

    15

  • 2 1

    3 4

    12

    3

    Gambar II.7: a.pd(Z2, 4) = 3 dan b.pd(Z2, 8) = 4, namun dimensi metrik keduagraf tak berhingga

    Lebih jauh, dalam Teorema II.7 berikut, Chartrand, Salehi dan Zhang (2000)

    menunjukkan bahwa untuk setiap pasang bilangan bulat positif a, b, dengan d b2e +

    1 a b + 1, terdapat suatu graf terhubung G yang mempunyai pd(G) = a dandim(G) = b. Misalkan Ks,t adalah graf bipartit dengan s = a, t = b a + 2,dan memenuhi d b

    2e + 1 a b + 1. Teorema II.4 menunjukkan bahwa

    dim(Ks,t) = s + t 2 = a + (b a + 2) 2 = b. Selanjutnya, jelas darinilai s, t, dan syarat yang diberikan, bahwa s > t. Menurut Teorema II.17,

    pd(Ks,t) = max{s, t} = s = a.

    Teorema II.7. (Chartrand, Salehi dan Zhang, 2000) Untuk setiap pasangbilangan bulat positif a, b dengan d b

    2e+1 a b+1, terdapat suatu graf terhubung

    G yang mempunyai dimensi partisi pd(G) = a dan dimensi metrik dim(G) = b.

    Dari Teorema II.7, muncul pertanyaan baru, yakni apakah ada grafG yang memiliki

    dimensi partisi kurang dari separuh dimensi metriknya. Pertanyaan ini selanjutnya

    dijawab oleh Chappell dkk. (2008) dengan menunjukkan bahwa graf seperti pada

    Gambar II.8 mempunyai dim(G) = b, pd(G) = a dan 3 a b + 1 denganhimpunan pembeda dan partisi pembedanya ditunjukkan pada Gambar II.8.a dan

    Gambar II.8.b , berturut-turut.

    Karena terdapat a buah simpul anting yang terkait dengan simpul x1, dan a adalah

    banyak simpul anting maksimum di graf G, maka berdasarkan Lema II.1 pd(G) a. Misalkan = {S1, S2, , Sa} adalah suatu partisi untuk V (G), dengan S1 =

    16

  • D D D

    D

    D...

    D D

    D

    D D

    D

    D D

    D ...

    D D

    D

    x1 x2 x3 x4

    D

    D

    ...

    D

    D

    D

    D

    D

    D ...

    D

    D

    (a) (b)a

    b-a+1

    a

    b-a+2

    xb-a+2 x1 x2 x3 x4 xb-a+2

    1 2 a-1 a

    1 1 1 1 1

    1 1

    1 1 22

    2 2

    Gambar II.8: a.Dimensi partisi dari graf G dinyatakan oleh banyak simpul antingpada simpul x1 dan b.Dimensi metrik dari graf G dinyatakan olehbanyak simpul putih pada graf tersebut

    {xi, ui1|1 i ba+2}, S2 = {ui2|1 i ba+2} dan Si = {u1i|3 i a}.Karena semua r(u|) berbeda untuk semua simpul u G, maka adalah partisipembeda untuk V (G) dan pd(G) a. Jadi, pd(G) = a.

    Misalkan grafGmempunyai simpul pemutus (cut-vertex) v dan U adalah himpunan

    k simpul terisolasi pada grafG{v}. Maka himpunan pembeda minimum dari grafG terdiri atas paling sedikit k 1 simpul di U . Pandang graf ulat G pada GambarII.8.b. Dengan demikian dim(G) = (a 1) + (b a+ 1) = b.

    Teorema II.8. (Chappell dkk., 2008) Untuk setiap pasang bilangan bulat positifa, b dengan 3 a b + 1, terdapat sebuah graf terhubung G sedemikian hinggamempunyai dimensi partisi pd(G) = a dan dimensi metrik dim(G) = b.

    Untuk beberapa graf, dimensi partisinya relatif konstan (tidak bergantung pada

    order dari graf tersebut), misalnya lintasan dan siklus. Namun, secara umum,

    Chartrand, Salehi dan Zhang (2000) menunjukkan hubungan antara dimensi partisi,

    order dan diameter sebagai berikut.

    Teorema II.9. (Chartrand, Salehi dan Zhang, 2000) Jika G adalah graf order(n 3) dan diameter d, maka g(n, d) pd(G) n d + 1, dengan g(n, d)merupakan bilangan bulat positif terkecil k sedemikian hingga (d+ 1)k n.

    Bukti. Pandang sebuah graf G order n, diameter d dan V (G) ={v1, v2, ,vd, vd+1, , vn}. Ambil u, v V (G) yang memenuhi d(u, v) = d.Misalkan u = v1, v2, , vd+1 = v adalah lintasan dari u ke v dengan panjang d.Dapat ditunjukkan bahwa = {S1, S2, , Snd+1} adalah partisi pembeda untuk

    17

  • V (G), dengan S1 = {v1, v2, , vd} dan Si = {vi+d1} untuk 2 i n d + 1.Oleh karena itu, pd(G) n d+ 1.

    Selanjutnya, definisikan g(n, d) sebagai bilangan bulat positif terkecil k sedemikian

    hingga (d + 1)k n. Misalkan terdapat suatu partisi pembeda untuk V (G)dan || = k. Karena representasi setiap simpul di G adalah vektor-k, makasetiap koordinat dari vektor-k tersebut adalah bilangan bulat tak-negatif yang tidak

    melebihi d. Karena adalah partisi pembeda, maka n buah simpul diGmempunyai

    representasi berbeda terhadapnya. Oleh karena itu, (d + 1)k n. Jadi, dang(n, d) = k pd(G).

    Selanjutnya, Chappell dkk. (2008) menunjukkan hubungan antara dimensi partisi,

    order dan diameter dari sebuah graf G pada Teorema II.10 berikut ini.

    Teorema II.10. (Chappell dkk., 2008) Jika G adalah graf order n ( 3), dimensipartisi k dan diameter d, maka n kdk1.

    Bukti. Pandang sebuah graf G order n dengan diameter d. Misalkan ={S1, S2, , Sk} adalah suatu partisi pembeda minimum dari graf G. Karena adalah partisi pembeda, maka representasi r(v|) unik untuk setiap simpulv V (G). Dengan kata lain, graf G mempunyai sedikitnya n buah representasiberbeda. Karena simpul v berada tepat di satu Si , dengan 1 i k, makarepresentasi r(v|) memuat tepat satu 0 dan koordinat lainnya adalah bilangan bulattak negatif dari 1 sampai k. Posisi 0 dalam r(v|) mempunyai k pilihan posisi.Setiap koordinat pada k 1 sisa representasi k-vektor adalah satu dari d nilai yangberbeda. Oleh karena itu, n kdk1.

    II.5 Dimensi partisi graf asal dan graf hasil operasi

    Dalam subbab ini diberikan beberapa hasil yang telah diketahui dari beberapa graf

    dalam kelas pohon, yaitu graf bintang ganda, dan graf ulat. Pada bagian lain,

    diberikan juga pengetahuan tentang dimensi partisi dari graf mirip roda (seperti

    graf gir, graf helm, dan graf bunga matahari) dan dimensi partisi graf hasil operasi

    kartesian.

    Sebuah graf pohon disebut graf bintang ganda jika graf pohon tersebut mempunyai

    tepat dua simpul u dan v berderajat lebih dari satu. Jika u dan v berderajat r+1 dan

    18

  • DD

    D

    D

    3

    D

    D

    D

    D

    D

    1

    2

    3

    r

    1

    2

    s

    Gambar II.9: Graf bintang ganda T (r, s) dengan deg(u) = r+1 dan deg(v) = s+1

    s+1 berturut-turut maka graf bintang ganda ini dinotasikan dengan T (r, s). Gambar

    II.9 adalah graf bintang ganda T (r, s) dengan deg(u) = r+ 1 dan deg(v) = s+ 1.

    Graf bintang ganda order 4 adalah sebuah lintasan P4 yang mempunyai dimensi

    partisi 2. Graf bintang ganda order 5 mempunyai dimensi partisi 3. Secara umum,

    dimensi partisi graf bintang ganda diberikan oleh Teorema II.11.

    Teorema II.11. (Chartrand dkk., 1998) Misalkan T (r, s) adalah graf bintangganda order n 6, dengan u dan v adalah simpul yang berderajat r + 1 dans+ 1, berturut-turut. Maka, pd(T (r, s)) = max{r, s}.

    Bukti. Misalkan r s, simpul u1, u2, , ur adalah simpul ujung dari T (r, s)yang terkait ke simpul u dan simpul v1, v2, , vs adalah simpul ujung T (r, s) yangterkait ke simpul v. Dua simpul sebarang ui, uj , dengan 1 i 6= j r, mempunyaijarak sama ke semua simpul di T {ui, uj}. Menurut Lema II.1 simpul ui dan ujharus termuat dalam kelas partisi yang berbeda. Karena r s, maka pd(T (r, s)) r.

    Sekarang akan ditunjukkan bahwa pd(T (r, s)) r. Pandang dua kasus berikut:Kasus 1. r = s.

    Misalkan = {S1, S2, , Sr} adalah partisi pembeda dengan S1 = {u, u1, v1},S2 = {v, u2, v2} dan Si = {ui, vi} untuk 3 i r. Periksa representasi simpuldi S1: r(u1|) = (0, 2, 2, 2, , 2), r(v1|) = (0, 1, 2, 2, , 2) dan r(u|) =(0, 1, 1, 1, , 1). Demikian pula simpul di S2: r(u2|) = (1, 0, 2, 2, , 2),r(v2|) = (2, 0, 2, 2, , 2) dan r(v|) = (1, 0, 1, 1, , 1). Untuk 3 i r,r(ui|) = (1, 2, , 0, ) dan r(vi|) = (2, 1, , 0, ) dengan koordinat ke-i pada setiap representasi adalah 0. Dapat dilihat bahwa setiap simpul di T (r, s)

    mempunyai representasi yang berbeda. Oleh karena itu, adalah partisi pembeda

    dan pd(T (r, s)) r.

    19

  • DD

    D

    D

    D

    D

    D

    1

    D

    DD

    D

    D

    2

    3

    4

    5

    6

    7

    1

    234

    5

    Gambar II.10: Graf pohon dengan4t(T ) = 3

    Kasus 2. r > s. Pandang dua subkasus dalam Kasus 2 ini.

    Subkasus 2.1. s = 1.

    Karena n 6, dengan sendirinya r 3. Misalkan = {S1, S2, , Sr}adalah partisi pembeda dengan S1 = {u, u1}, S2 = {v, u2}, S3 = {u3, v1},dan Si = {ui} untuk 4 i r. Karena r(u1|) = (0, 2, 2, , , , ),r(u2|) = (1, 0, 2, , , , ), r(u3|) = (1, 2, 0, , , , ),r(u|) = (0, 1, 1, , , , ), r(v|) = (1, 0, 1, , , , ) danr(v1|) = (2, 1, 0, , , , ) dengan adalah koordinat yang tidak berpen-garuh. Dengan demikian, adalah partisi pembeda dan pd(T (r, s)) r.

    Subkasus 2.2. s 2.Misalkan = {S1, S2, , Sr} adalah partisi pembeda dengan S1 = {u, u1, v1},S2 = {v, u2, v2}, Si = {ui, vi} untuk 3 i s dan Si = {ui} untuk s+1 i r.Dengan pembuktian yang serupa dengan Subkasus 2.1., dapat ditunjukkan bahwa

    adalah partisi pembeda dan pd(T (r, s)) r.

    Graf ulat adalah sebuah graf pohon T yang mempunyai sifat apabila semua daunnya

    dihilangkan, graf pohon tersebut menjadi sebuah lintasan. Sebuah simpul di graf

    pohon T dengan derajat paling sedikit 3 disebut simpul mayor dari T . Simpul ujung

    u V (T ) disebut simpul terminal dari simpul mayor v V (T ) jika d(u, v) dG1G2((c, d),Wj {u1}).

    Kasus 2. a, c Wi.Misalkan dG2(b, u1) = dG2(d, u1). Karena terdapat j 6= i sedemikian hinggadG(a,Wj) 6= dG(c,Wj), maka dG1G2((a, b),Wj {u1}) = dG1(a,Wj) +dG2(b, u1) 6= dG1(c,Wj)+dG2(d, u1) = dG1G2((c, d),Wj{u1}). Jika dG2(b, u1) 6=dG2(d, u1), maka terdapat dG1G2((a, b),Wi {u1}) = dG2(b, u1) 6= dG2(d, u1) =dG1G2((c, d),Wi{u1}). Oleh karena itu, untuk setiap simpul berbeda (a, b), (c, d)terdapat r((a, b)|) 6= r((c, d)|).

    Dari Teorema II.5 dan Teorema II.20 diperoleh Akibat II.2 berikut ini.

    Akibat II.2. Untuk sebarang dua graf terhubung G dan H , pd(G H) dim(G) + dim(H) + 1.

    27

  • Bab III Dimensi Partisi Sejumlah Graf Pohon

    Graf pohon termasuk kelas graf yang digunakan secara luas tidak hanya di banyak

    bidang aplikasi tetapi juga dalam Teori Graf sendiri. Graf pohon digunakan antara

    lain pada analisis hirarki bisnis, penentuan biaya minimum pada jaringan trans-

    portasi, dan dasar struktur data pada ilmu komputer (Bona, 2002). Dalam Teori

    Graf, Chartrand, Eroh, Johnson dan Oellermann (2000) telah berhasil memberikan

    dimensi metrik dari sebarang graf pohon secara lengkap. Namun, tidak demikian

    halnya untuk dimensi partisi graf pohon, baru beberapa graf saja yang telah

    diperoleh dimensi partisinya. Chartrand dkk. (1998) mengawali penelitian dalam

    bidang dimensi partisi dari graf dalam kelas graf pohon, yaitu dengan menentukan

    batas atas dan bawah dapatkan dimensi partisi graf ulat, dan dimensi partisi graf

    bintang ganda. Selanjutnya, Chartrand, Salehi dan Zhang (2000) mengkarakterisasi

    semua graf G order n dengan dimesi partisi 2, yaitu pd(G) = 2 jika dan hanya jika

    G adalah graf lintasan Pn. Graf lintasan Pn adalah graf dalam kelas graf pohon

    juga.

    Pada Subbab III.1 dibahas dimensi partisi dari graf ulat (caterpillar) secara tepat.

    Hasil ini merupakan penyempurnaan hasil dari Chartrand dkk. (1998). Selanjutnya,

    pada Subbab III.2 dan Subbab III.3 dibahas dimensi partisi dari graf kembang

    api (firecracker) dan graf pohon pisang (banana tree), berturut-turut. Kedua graf

    tersebut termasuk dalam kelas pohon mempunyai struktur yang mirip dengan graf

    ulat.

    III.1 Dimensi partisi graf ulat

    Misalkan terdapat graf lintasan Pm dengan himpunan simpul V (Pm) =

    {x1, x2, , xm} dan himpunan sisi E(Pm) = {x1x2, x2x3, , xm1xm}. Grafulat diperoleh dengan menambahkan ni buah sisi anting pada setiap simpul xidari sebuah graf lintasan Pm, dengan 1 i m, dan dinotasikan denganC(m;n1, n2, , nm). Graf ulat C(m;n1, n2, , nm) terdiri atas himpunansimpul V (C(m;n1, n2, , nm)) = {aij|1 i m, 1 j ni} {xi|1 i m} dan himpunan sisi E(C(m;n1, n2, , nm)) = {xiaij|1 i m, 1 j ni} {xixi+1|1 i m 1}. Untuk n1 = n2 = = nm = n, grafulat disebut homogen dan dinotasikan dengan C(m;n). Gambar III.1.a mengilus-

    28

  • DDDD

    D

    2

    24232221

    D D D D

    D

    1

    31 32 33 34

    D D D D

    D

    11 12 13 14

    DDD

    D

    2

    232221

    D D D D

    D

    1

    41 42 43 44

    D D D D

    D

    11 12 13 14

    DD

    D

    3

    32

    4

    31

    3

    Gambar III.1: a.Graf ulat homogen C(3; 4) dan b.Graf ulat tak-homogen C(4; 4,3, 2, 4)

    trasikan graf ulat homogen C(3; 4) dan Gambar III.1.b mengilustrasikan graf ulat

    tak-homogen C(4; 4, 3, 2, 4).

    Jelas, bahwa setiap graf C(m;n1, n2, , nm) memuat tepat m buah subgrafK1,ni . Notasikan himpunan simpul dan sisi dari K1,ni sebagai berikut: V (K1,ni) =

    {aij|1 j ni} {xi} dan E(K1,ni) = {xiaij|1 j ni}. Definisikannmaks = max{n1, n2, . . . , nm}. Subgraf K1,nmaks disebut sebagai subgraf ulatmaksimum pada C(m;n1, n2, , nm). Dalam hal terdapat p 1 buah K1,nmaks ,masing-masing subgraf, dari kiri ke kanan, dinotasikan dengan Ki1,nmaks dengan

    1 i p.

    Pada Teorema II.12, Chartrand dkk. (1998) menunjukkan batas atas dan batas

    bawah dimensi partisi graf ulat dan menyatakannya dalam 4t(T ), yaitu derajatterminal maksimum simpul mayor eksterior dari T . Secara khusus untuk m = 2,

    graf ulat C(2;n1, n2) disebut graf bintang ganda. Pada Teorema II.11, Chartrand

    dkk. (1998) memberikan dimensi partisi graf bintang ganda secara tepat. Pemba-

    hasan berikut akan memberikan dimensi partisi dari sebarang graf ulat secara tepat.

    Definisi III.1. Misalkan K1,ni , K1,nj C(m;n1, n2, . . . , nm), dengan 1 i 6=j m. Jika ni = nj = nmaks 1, sedemikian hingga

    1. d(xi, xm) = d(xj, xm), dengan xm anggota dari suatu K1,nmaks (Lihat Gambar

    III.2.a), atau

    2. d(xi, xo) = d(xj, xp), dengan xo dan xp masing-masing anggota dari suatu

    K1,nmaks yang berbeda (Lihat Gambar III.2.b),

    maka subgraf K1,ni dan K1,nj disebut subgraf ulat berjarak sama.

    29

  • DDD

    D

    DDD

    D

    DDD D

    DDD

    D

    DD

    D

    D D

    D

    xp

    d(xi,xm)

    xmxi xj xkd(xj,xm) d(xk,xp)

    DDD

    D

    DDD

    D

    DD

    D

    D D

    d(xi,xm)

    xmxi xjd(xj,xm)

    DDD

    D

    DDD D

    D

    xpxj

    d(xj,xp)

    DDD D

    D

    xo

    DDD

    D

    xid(xi,xo)

    (a) (b)

    Gambar III.2: Dua kondisi subgraf graf ulat K1,ni dan K1,nj yang berjarak sama

    Lema II.1 secara langsung memberikan Akibat III.3 berikut ini:

    Akibat III.1. Misalkan adalah partisi pembeda untuk V (C(m;n1,n2, , nm)) dan K1,ni C(m;n1, n2, , nm). Jika u dan v adalah sebarangdua simpul anting berbeda di K1,ni , dengan ni 2, maka u dan v harus beradadalam kelas partisi yang berbeda di .

    Bukti. Misalkan u dan v dua simpul anting berbeda di K1,ni . Karena jarakd(u,w) = d(v, w) untuk semua simpul w V (C(m;n1, n2, , nm)) {u, v},maka menurut Lema II.1 simpul anting u dan v harus termuat dalam kelas partisi

    yang berbeda di .

    Lema III.1. Misalkan adalah partisi pembeda untuk V (C(m;n1,n2, , nm)). Jika Ki1,nmaks dan Kj1,nmaks dua subgraf ulat maksimum, dengani 6= j, maka xi V (Ki1,nmaks) dan xj V (Kj1,nmaks) harus termuat dalam kelaspartisi yang berbeda di .

    Bukti. Misalkan = {S1, S2, , Snmaks} suatu partisi pembeda dari grafC(m;n1, n2, , nm). Akibat III.1 memastikan setiap simpul anting pada Ki1,nmaks(atau Kj1,nmaks) harus termuat dalam kelas partisi yang berbeda. Oleh karena itu,

    setiap simpul anting pada K1,nmaks dapat diasosiasikan dengan nmaks kelas partisi

    di . Misalkan simpul xi V (Ki1,nmaks) dan xj V (Kj1,nmaks) berada dalam kelaspartisi yang sama. Maka, d(xi, Z) = d(xj, Z) = 0, dengan Z adalah kelas partisi

    yang memuat simpul xi dan xj , dan d(xi, Y ) = d(xj, Y ) = 1, dengan Y adalah

    kelas partisi selain Z. Dengan demikian, r(xi|) = r(xj|), kontradiksi.

    Lema III.2. Misalkan adalah partisi pembeda untuk V (C(m;n1,n2, , nm)) untuk m 2. Jika sebarang dua subgraf berbeda K1,ni , K1,nj

    30

  • C(m;n1, n2, , nm) berjarak sama dan sebarang dua simpul anting aik K1,nidan ajk K1,nj , dengan 1 k ni, termuat dalam kelas partisi yang sama, makaxi dan xj harus termuat dalam kelas partisi yang berbeda di .

    Bukti. Misalkan = {S1, S2, , Snmaks} suatu partisi pembeda dari grafC(m;n1, n2, , nm). Misalkan xi, xj X untuk suatu kelas partisi X .Karena subgraf K1,ni dan K1,nj berjarak sama dan sebarang dua simpul anting

    aik K1,ni dan ajk K1,nj , dengan 1 k ni, termuat dalam kelas partisiyang sama, maka d(aik, X) = d(aik, X) = 1 untuk suatu kelas partisi X yang memuat xi dan xj , dan d(aik, Y ) = d(ajk, Y ) = 2 untuk suatu kelas partisi

    Y yang memuat simpul anting pada subgraf K1,ni (atau K1,nj ). Lebih jauh,d(aik, Z) = d(ajk, Z) untuk suatu kelas partisi Z yang tidak memuat simpulanting pada subgraf K1,ni (atau K1,nj ). Dengan demikian, r(ajk|) = r(aik|),untuk suatu k pada selang tertutup [1, ni], kontradiksi.

    Teorema III.3 berikut ini menunjukkan dimensi partisi dari graf ulat C(m;n1,

    n2, , nm).

    Teorema III.1. Misalkan K1,nmaks adalah subgraf ulat maksimum dariC(m;n1, n2, , nm) dan p menyatakan banyak subgraf K1,nmaks . Maka, untuknmaks 3, dimensi partisi graf ulat C(m;n1, n2, , nm) adalah

    pd(C(m;n1, n2, , nm)) ={nmaks , jika p nmaks,nmaks + 1 , jika p > nmaks.

    Bukti. Pandang dua kasus berikut:Kasus 1: p nmaksMisalkan terdapat suatu partisi pembeda = {S1, S2, , Sp} untuk grafC(m;n1,n2, , nm). Akibat III.1 memastikan setiap simpul anting pada K1,ni termuatdalam kelas partisi yang berbeda. Karena K1,nmaks memiliki nmaks simpul anting,

    maka sedikitnya terdapat nmaks kelas partisi di untuk C(m;n1, n2, , nm).Dengan demikian p nmaks.

    Sekarang, pandang graf C(m;n1, n2, , nm). Misalkan terdapat suatu partisipembeda = {S1, S2, , Snmaks} untuk graf V (C(m;n1, n2, , nm)).Letakkan setiap simpul v V (C(m;n1, n2, , nm)) ke dalam kelas partisiSj , untuk suatu 1 j nmaks, menurut algoritma berikut ini:

    31

  • a. Hitung banyak subgraf K1,nmaks dan nyatakan dengan p. Notasikan masing-

    masing subgraf tersebut, secara berurut dari kiri ke kanan, dengan Kk1,nmaks ,

    dengan 1 k p,b. Setiap simpul xk V (Kk1,nmaks) secara berurut diletakkan pada kelas partisi Sj ,

    untuk suatu 1 j p,c. Setiap simpul anting pada Kk1,nmaks , secara berurut diletakkan pada kelas partisi

    S1, S2, S3, , Snmaks ,d. Definisikan A1 sebagai selang terbuka sebelum graf bintang K11,nmaks , Ak+1

    sebagai selang terbuka antara Kk1,nmaks dan Kk+11,nmaks

    , dengan 1 k p 1,dan Ap+1 sebagai selang terbuka setelah K

    p1,nmaks

    ,

    e. Definisikan himpunan T = {semua kombinasi-(nmaks1) dari nmaks buah kelaspartisi di }, sedemikian hingga T = {T1, T2, , Tnmaks} dengan Ti Tadalah kombinasi yang tidak memuat kelas partisi Si,

    f. Identifikasi letak subgrafK1,ni pada selang sebagaimana yang didefinisikan pada

    item d,

    g. Jika K1,ni terletak pada selang A1 atau A2 maka setiap simpul anting pada K1,nisecara berurut diletakkan pada kelas partisi yang berasosiasi dengan T1,

    h. Jika K1,ni terletak pada selang Ak, dengan 3 k p + 1 maka setiap simpulanting pada K1,ni secara berurut diletakkan pada kelas partisi yang berasosiasi

    dengan Tk1

    i. Jika K1,ni dan K1,nj berjarak sama terhadap suatu K1,nmaks , maka berdasarkan

    Lema III.2 xi V (K1,ni) dan xj V (K1,nj) harus termuat dalam kelas partisiyang berbeda di .

    j. Setiap simpul pusat xk V (Kk1,ni), dengan Kk1,ni bukan subgraf ulat maksimumdan subgraf ulat berjarak sama, xk diletakkan pada kelas partisi yang memuat

    salah satu antingnya.

    Untuk memastikan bahwa adalah partisi pembeda dari graf C(m;n1,

    n2, , nm), pandang sebarang dua simpul berbeda u, v V (C(m;n1,n2, , nm)) sedemikian hingga u dan v dalam kelas partisi yang sama. Jika simpulanting u V (K1,ni) dan v V (K1,nj), dengan ni = nj = nmaks, maka u dan vdibedakan oleh sebuah kelas partisi yang memuat xi atau xj . Jika simpul anting

    u V (K1,ni) dan v V (K1,nj), dengan K1,ni dan K1,nj berada dalam selang yangberbeda, katakan Ao dan Ap, maka u dan v dibedakan oleh kelas partisi So atau Sp.

    Jika simpul anting u V (K1,ni) dan v V (K1,nj), dengan K1,ni dan K1,nj beradadalam selang sama, katakan Ao, dan subgraf K1,ni dan K1,nj tidak berjarak sama,

    32

  • D D D

    D

    D

    1

    1

    2 3 4

    D D D

    D

    D

    1

    2

    2 3 4

    D D D

    D

    D

    1

    3

    2 3 4

    D D D

    D

    D

    1

    4

    2 3 4

    D D

    DD D D

    DD D D

    DDD

    D

    D

    DD D

    DD

    2 3 2 4 1 3

    2 3 4 2 3 4 2 3 42 1 3 1 3

    Gambar III.3: Partisi pembeda minimum graf C(10; 3, 4, 3, 1, 3, 4, 2, 2, 4, 4)

    maka u dan v dibedakan oleh kelas partisi So. Jika K1,ni dan K1,nj berjarak sama

    maka u dan v dibedakan kelas partisi yang memuat xi atau xj .

    Selanjutnya, jika simpul anting u V (K1,ni) dan v V (K1,nj), dengan salah satudari ni atau nj adalah nmaks, tanpa mengurangi keumunan katakan ni = nmaks dan

    nj < nmaks, maka u dan v dibedakan kelas partisi X , dengan X adalah kelas partisi

    yang memuat simpul antingK1,ni tetapi tidak memuat simpul antingK1,nj . Dengan

    demikian, untuk setiap u, v V (C(m;n1, n2, , nm)), r(u|) 6= r(v|). (LihatGambar III.3).

    Kasus 2: p > nmaksMisalkan terdapat suatu partisi pembeda = {S1, S2, , Sp} untuk V (C(m;n1,n2, , nm)). Jika p > nmaks maka, menurut Lema III.1 terdapat paling sedikit duabuah simpul xi V (Ki1,nmaks) dan xj V (Kj1,nmaks), sedemikian hingga simpulxi dan xj termuat dalam kelas partisi yang sama, kontradiksi. Dengan demikian,

    p nmaks + 1.

    Selanjutnya, definisikan partisi pembeda = {S1, S2, , Snmaks+1} untuk grafC(m;n1, n2, , nm) menurut algoritma berikut ini:a. Setiap simpul anting pada V (K1,ni), dengan 1 i m, secara berurut

    diletakkan pada kelas partisi S1, S2, S3, , Sni ,b. Letakkan simpul x1 pada kelas partisi Snmaks+1,

    c. Letakkan simpul xi lainnya sedemikian hingga x2 S1, x3 S2, x4 S3,x5 S1 dan seterusnya dengan pola pengulangan yang sama.

    Pandang sebarang dua simpul berbeda u, v V (C(m;n1, n2, , nm)) sedemikianhingga simpul u dan v termuat dalam kelas partisi yang sama. Jika u V (K1,ni)dan v V (K1,nj), untuk i 6= j, maka jarak d(u, Snmaks+1) 6= d(v, Snmaks+1)dan oleh karena itu r(u|) 6= r(v|). Jika simpul u V (K1,ni) {xi} dan

    33

  • D D D

    D

    D

    1

    1

    2 3 4

    D D D

    D

    D

    1

    2

    2 3 4

    D D D

    D

    D

    1

    2

    2 3 4

    D D D

    D

    D

    1

    1

    2 3 4

    D D

    DD D D

    DD D D

    DDD

    D

    D

    DD D

    DD

    5 2 3 1 3 1

    1 2 3 1 2 3 1 2 31 1 2 1 2

    DDD

    D

    D

    1 2 3 4

    3

    Gambar III.4: Partisi pembeda minimum graf C(11; 3, 4, 3, 1, 3, 4, 2, 2, 4, 4, 4)

    v = xi+1, untuk suatu i pada selang tertutup 1 i m 1, maka u danv dibedakan oleh sedikitnya satu kelas partisi X , dengan X adalah kelaspartisi yang memuat simpul anting K1,ni+1 , sedemikian hingga d(v,X) = 1

    dan d(u,X) 6= 1. Oleh karena itu, r(u|) 6= r(v|). Dengan demikian,setiap simpul v V (C(m;n1, n2, , nm)) mempunyai representasi unik danpd(C(m;n1, n2, , nm)) nmaks + 1. (Lihat Gambar III.4).

    Dalam hal ni = n untuk setiap i, Teorema III.1 memberikan akibat berikut ini:

    Akibat III.2. Jika C(m;n) adalah graf ulat homogen yang dibangun denganmenambahkan n buah sisi anting pada setiap simpul pada lintasan Pm, dengan

    n 3, makapd(C(m;n) =

    {n , jika m n,n+ 1 , jika m > n.

    Selanjutnya, pandang kasus khusus graf ulat homogen C(m;n), dengan n = 1

    dan m 2, yaitu C(1; 1) dan C(2; 1). Keduanya adalah graf ulat yang isomorfikmasing-masing dengan graf lintasan P2 dan P4. Dengan demikian, pd(C(1; 1)) =

    pd(C(2; 1)) = 2. Dimensi partisi graf ulat homogen C(m;n) untuk n = 1, 2 dan

    m 3 mengikuti teorema berikut:

    Teorema III.2. Jika m 3 maka pd(C(m; 1)) = pd(C(m; 2)) = 3.

    Bukti. (Chartrand, Salehi dan Zhang, 2000) menunjukkan bahwa dimensi partisigraf terhubung pd(G) = 2 jika dan hanya jika G adalah graf lintasan. Karena graf

    C(m; 1) dan C(m; 2) bukan graf lintasan, maka pd(C(m; 1)) = pd(C(m; 2)) 3.

    Sekarang, definisikan partisi pembeda = {S1, S2, S3} untuk V (C(m; 1))

    34

  • DD

    1

    DD

    DD

    DD

    DD

    DD

    1 11 11

    3 2 22 22

    D

    D D

    1 2

    3

    D

    D D

    1 2

    2

    D

    D D

    1 2

    2

    D

    D D

    1 2

    2

    (b)(a)

    Gambar III.5: a.Partisi pembeda minimum graf C(6; 1, 1, 1, 1, 1, 1) dan b.Partisipembeda minimum graf C(4; 2, 2, 2, 2)

    sedemikian hingga

    Sq =

    {ai1|3 i m} , jika q = 1,{xi|2 i m} , jika q = 2,{x1} , jika q = 3.

    Pandang sebarang dua simpul berbeda u, v V (C(m; 1)) sedemikian hingga u danv dalam kelas partisi yang sama. Jarak simpul anting d(ai1, S3) = d(a(i+1), S3) 1dan d(xi, S3) = d(x(i+1), S3) 1, untuk 2 i m 1. Dengan demikian, setiapsimpul u V (C(m; 1)) mempunyai representasi berbeda. Demikian pula halnyasimpul dalam kelas partisi S2, setiap simpul xi V (C(m; 1)) mempunyai repre-sentasi yang berbeda. Karena kelas partisi S3 adalah singleton, dengan sendirinya

    xm S3 mempunyai representasi yang unik. Jadi, pd(C(m; 1)) 3. (LihatGambar III.5.a.

    Batas atas dimensi partisi dari graf C(m; 2) dapat dapat ditunjukkan dengan

    mendefinisikan partisi pembeda = {S1, S2, S3} untuk V (C(m; 2)) sedemikianhingga

    Sq =

    {ai1|3 i m} , jika q = 1,{ai2, xi|2 i m} , jika q = 2,{x1} , jika q = 3.

    Setiap simpul anggota S1 dibedakan oleh kelas partisi S3 dan setiap simpul di S2dibedakan oleh oleh kelas partisi S1 dan S3. Oleh karena S3 merupakan kelas partisi

    singleton, maka x1 S3 dengan sendirinya unik. Dengan demikian untuk sebarangdua simpul berbeda u, v C(m; 2), r(u|) 6= r(v|). Jadi, pd(C(m; 2)) 3.(Lihat Gambar III.5.b.

    35

  • DDDD

    D

    2

    24232221

    D D D D

    D

    1

    31 32 33 34

    D D D D

    D

    11 12 13 14

    DDD

    D

    2

    232221

    D D D D

    D

    1

    41 42 43 44

    D D D D

    D

    11 12 13 14

    DD

    D

    3

    32

    4

    31

    3

    D D D

    1

    2

    3

    D DD D

    1

    2 3

    4

    Gambar III.6: a.Graf kembang api homogen dan b.Graf kembang api tak-homogen

    III.2 Dimensi partisi graf kembang api

    Graf kembang api (firecracker) adalah sebuah graf yang diperoleh dengan

    menghubungkan m buah graf bintang K1,ni dengan cara menghubungkan satu

    simpul anting dari setiap graf bintang K1,ni dengan 1 i m (Chen dkk., 1997)dan dinotasikan dengan F (m;n1, n2, , nm). Graf kembang api F (m;n1,n2, , nm) terdiri atas himpunan simpul V (F (m;n1, n2, , nm)) = {ci|1 i m} {aij|1 i m, 1 j ni 1} {xi|1 i m} dan himpunan sisiE(F (m;n1, n2, , nm)) = {cixi, ciaij|1 i m, 1 j ni1}{xixi+1|1 i m1}. Jika n1 = n2 = = nm = n, graf kembang api disebut graf kembangapi homogen dan dinotasikan dengan F (m;n). Gambar III.6.a adalah graf kembang

    api homogen F (3; 5) dan Gambar III.6.b adalah graf kembang api tak-homogen

    F (4; 5, 4, 3, 5).

    Untuk suatu i dalam selang tertutup [1,m], subgraf K1,ni F (m;n1, n2, . . . , nm)adalah subgraf kembang api yang terdiri atas himpunan simpul V (K1,ni) =

    {xi, ci, aij|1 i m, 1 j ni 1} dan himpunan sisi E(K1,ni) ={xici, ciaij|1 i m, 1 j ni1}. Dalam hal nmaks = max{n1, n2, . . . , nm},maka K1,nmaks disebut subgraf kembang api maksimum. Jika terdapat p buah

    K1,nmaks , masing-masing subgraf ulat maksimum, secara berurut dari kiri ke kanan,

    dinotasikan dengan Ki1,nmaks dengan 1 i p.

    Definisi III.2. Misalkan K1,ni , K1,nj F (m;n1, n2, . . . , nm), dengan 1 i 6=j m. Jika ni = nj = nmaks 2, sedemikian hingga

    1. d(xi, xm) = d(xj, xm), dengan xm anggota dari suatu K1,nmaks (Lihat Gambar

    III.7.a), atau

    2. d(xi, xo) = d(xj, xp), dengan xo dan xp masing-masing anggota dari suatu

    36

  • DDD

    D

    DDD

    D

    DD

    D

    D D

    d(xi,xm)

    cmci cj

    d(xj,xm)

    DDD

    D

    DDD D

    D

    xpxj

    d(xj,xp)

    DDD D

    D co

    DDD

    D

    xi

    d(xi,xo)(a) (b)

    D D D D D D D

    xoci cj cp

    xi xm xj

    Gambar III.7: Dua kondisi subgraf kembang api K1,ni dan K1,nj berjarak sama

    K1,nmaks yang berbeda (Lihat Gambar III.7.b),

    maka subgraf K1,ni dan K1,nj disebut subgraf kembang api berjarak sama.

    Akibat III.3 berikut ini adalah konsekuensi dari Lema II.1.

    Akibat III.3. Misalkan adalah partisi pembeda untuk V (F (m;n1,n2, , nm)). Jika u dan v adalah sebarang dua simpul anting pada (K1,ni),dengan ni 2, maka u dan v harus termuat dalam kelas partisi yang berbedadi .

    Bukti. Misalkan sebarang dua simpul anting berbeda u, v V (K1,ni). Karenad(u,w) = d(v, w) untuk setiap simpul w V (F (m;n1, n2, , nm)) {u, v},maka menurut Lema II.1 simpul anting u dan v harus termuat dalam kelas partisi

    yang berbeda di .

    Lema III.3. Misalkan = {S1, S2, , Snmaks1} adalah partisi pembedauntuk V (F (m;n1, n2, , nm)). Jika subgrafKi1,nmaks danKj1,nmaks , dengan i 6= j,maka simpul pusat ci V (Ki1,nmaks) dan cj V (Kj1,nmaks) harus termuat dalamkelas partisi yang berbeda di .

    Bukti. Misalkan terdapat suatu partisi pembeda = {S1, S2, , Snmaks1} untukgraf F (m;n1, n2, , nm). Akibat III.3 memastikan setiap dua simpul anting diK1,ni termuat dalam kelas partisi yang berbeda di . Oleh karena subgraf K1,nidan K1,nj masing-masing memiliki nmaks 1 simpul anting, maka semua simpulanting padaK1,ni danK1,nj dapat diasosiasikan dengan nmaks1 kelas partisi yangterdapat di . Jika simpul pusat ci dan cj berada dalam kelas partisi yang sama,

    37

  • katakan ci, cj X , maka d(ci, X) = d(cj, X) = 0, dan d(ci, Y ) = d(cj, Y ) = 1,untuk setiap kelas partisi Y yang tidak memuat simpul ci dan cj . Oleh karena itu,

    r(ci|) = r(cj|), kontradiksi.

    Lema III.4. Misalkan adalah partisi pembeda untuk V (C(m;n1,n2, , nm)) untuk m 2. Jika sebarang dua subgraf berbeda dari graf kembangapiK1,ni danK1,nj berjarak sama dan sebarang dua simpul anting aik K1,ni danajk K1,nj , dengan 1 k ni 1, termuat dalam kelas partisi yang sama, makamaka ci, xi X dan cj, xj Y , dengan X dan Y merupakan dua kelas partisiberbeda di .

    Bukti. Misalkan terdapat suatu partisi pembeda = {S1, S2, , Snmaks1} untukV (F (m;n1, n2, , nm)). Asumsikan X, Y dan X = Y sedemikianhingga ci, xi, cj, xj X (atau ci, xi, cj, xj Y ). Tanpa kehilangan keumuman,ambil kemungkinan yang pertama, yaitu ci, xi, cj, xj X . Karena simpul antingdari K1,ni dan K1,nj didistribusikan ke sejumlah kelas partisi yang sama, maka

    d(ci, X) = d(cj, X) = 0 dan d(ci, Z) = d(cj, Z) = 1 untuk setiap kelas partisi

    Z di selain X serta d(ci,W ) = d(cj,W ) untuk sebuah kelas partisi W yangmemuat simpul dariK1,nk tetapi tidak memuat simpul dariK1,ni danK1,nj . Dengan

    demikian, r(ci|) = r(cj|), kontradiksi.

    Teorema III.3 berikut ini memberikan dimensi partisi graf kembang api F (m;n1,

    n2, , nm) dengan m 2 dan nmaks 5.

    Teorema III.3. Misalkan p menyatakan banyak subgraf K1,nmaks pada grafF (m;n1, n2, , nm). Maka, untuk nmaks 5 dan m 2,

    pd(F (m;n1, n2, , nm)) ={nmaks 1 , jika p nmaks 1,nmaks , jika p > nmaks 1.

    Bukti. Pandang dua kasus berikut:Kasus 1: p nmaks 1Misalkan terdapat suatu partisi pembeda = {S1, S2, , Sp} dari graf F (m;n1,n2, , nm). Akibat III.3 memastikan setiap simpul anting di K1,ni termuat dalamkelas partisi yang berbeda di . Karena K1,nmaks memiliki nmaks 1 buah simpulanting, maka sedikitnya terdapat nmaks1 buah kelas partisi berbeda di . Dengan

    38

  • demikian, p nmaks 1.

    Sekarang, definisikan suatu partisi pembeda = {S1, S2, , Snmaks1} untukV (F (m;n1, n2, , nm)) sedemikian hingga mengikuti algoritma berikut:a. Hitung jumlah subgraf K1,nmaks dan nyatakan dengan p. Notasikan masing-

    masing subgraf tersebut, berurut dari kiri ke kanan, dengan Kk1,nmaks , dengan

    1 k p,b. Setiap simpul pusat ck V (Kk1,nmaks) secara berurut diletakkan pada kelas

    partisi Sk, dengan 1 k p,c. Setiap simpul xk V (Kk1,nmaks) secara berurut diletakkan pada kelas partisiSnmaks1, Snmaks2, , Snmaksp,

    d. Setiap simpul anting pada Kk1,nmaks , secara berurut diletakkan pada kelas partisi

    S1, S2, S3, , Snmaks1,e. Definisikan A1 sebagai selang terbuka sebelum subgraf K11,nmaks , Ak+1 sebagai

    selang antar