graf theory

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


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 G�H jika diameter H paling banyak 2, yaitu pd(G�H) ≤ 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 G�H if the diameter ofH is at most 2, namely pd(G�H) ≤ pd(G) + pd(H). We show that this bound istight. For specific cases, we investigate pd(G�H), 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


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,nidan 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,nidan K1,nj

berjarak sama . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37Gambar III.8 a.Partisi pembeda minimum dari graf F (2; 3) dan

b.Partisi pembeda minimum dari graf F (2; 4) . . . . . . . . . 41Gambar 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 4

4 . . . . . . . . . . 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 setiap

simpul v ∈ V (G) terhadap setiap simpul w ∈ W , konsep himpunan pembeda

memastikan setiap simpul v ∈ V (G) mempunyai representasi berbeda. Jika dua

senyawa 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 graf

terhubung order n ≥ 2 maka pd(G) = n−1 jika dan hanya jika G adalah salah satu

dari graf berikut: K1,n−1, Kn− e, atau K1 + (K1∪Kn−2). Karakterisasi berikutnya

dilakukan oleh Tomescu (2008), yaitu mengkarakterisasi semua graf terhubung G

order n yang mempunyai dimensi partisi (n − 2). Tomescu (2008) menunjukkan

hanya terdapat 23 graf tak-isomorfik yang mempunyai dimensi partisi n−2. Dengan

demikian, dimensi partisi dari sebarang graf terhubung G order n lainnya terletak

pada selang [3, (n−3)]. Namun, problem penentuan dimensi partisi untuk sebarang

graf 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 graf

teratur-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 blok

kota 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 graf

planar teratur-4 (Z2, ε4) berupa bujursangkar. Graf teratur-8 (Z2, ε8) adalah graf

yang 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. Jarak

papan catur dari dua simpul (i, j) dan (i′, j′) pada (Z2, ε8) didefinisikan sebagai

d8((i, j), (i′, j′)) = maks(|i − i′|, |j − j′|). Graf teratur-8 (Z2, ε8) dapat diperoleh

dengan 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 hingga

p(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 ∼= G�H . Kami menentukan batas atas dimensi partisi G�Huntuk sebarang graf G dan graf H berdiameter paling banyak 2. Untuk kasus

tertentu, kami menentukan dimensi partisi graf dari: Pm�Kn, Pm�K1,n,Km�Kn,

K1�mKn, danK1,m�Kn, dengan Pm, Km, K1,m danmKn masing-masing adalah

graf 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 . Untuk

n = 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 diameter

diam(H) ≤ 2. Graf hasil operasi korona yang juga dibahas dimensi partisinya

dalam bab ini adalah graf Pm�Kn, Pm�K1,n,Km�Kn,K1�mKn, danK1,m�Kn.

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 di

E(G) disebut sisi (edge). Jika e = {u, v} ∈ E(G) maka u dikatakan bertetangga

dengan 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 setiap

dua simpul berbeda u, v ∈ V (G) terhubung. Graf G pada Gambar II.1 adalah graf

terhubung. Jarak simpul a ke g, d(a, g) = 3.

Jika simpul u ∈ V (G) dan subhimpunan S ⊂ V (G), maka jarak dari u ke

S 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 G

pada 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) dan

E(G) = E(G1) ∪ E(G2). Jadi, graf G ∼= G1 ∪G2 terdiri atas sebuah kopi graf G1

bersama-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 himpunan

simpul 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 diperoleh

dengan menambahkan pada G1∪G2 sisi-sisi yang mempunyai satu simpul ujung di

G1 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 P3

dan 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 ujung

dari sisi e ∈ E(G2). Gambar II.3.b mengilustrasikan graf hasil kali kartesian P3 ×K3.

7

D

x

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 diperoleh

dari G1 dan G2 dengan mengambil sebuah kopi dari G1 dan |V (G1)| kopi dari G2

dan 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.b

mengilustrasikan graf hasil kali korona P3 �K3.

Misalkan Gi2 adalah kopi ke-i dari graf G2 dalam G1 � G2. Karena semua simpul

pada 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, graf

lengkapK3 mempunyai diam(K3) = 1 = diam(Ki3�xi) 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), dengan

W = {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 dinotasikan

dengan r(v|W ). Jika untuk setiap dua simpul berbeda u, v ∈ V (G) berlaku

r(u|W ) 6= r(v|W ), maka W disebut himpunan pembeda dari V (G). Himpunan

pembeda 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 menentukan

apakah 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 x

dikatakan 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 W

membedakan simpul u dan v, atau simpul u dan v dibedakan oleh himpunan W .

Gambar II.4 mengilustrasikan suatu himpunan terurut W ⊆ K2,4 untuk graf

bipartit 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, kami

menunjukkan himpunan pembeda dari K2,4 mempunyai kardinalitas sedikitnya 4.

Misalkan terdapat himpunan pembeda W dari K2,4 dengan |W | = 3 dan V1 dan

V2 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 hingga

u, 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 himpunan

pembeda. Jadi, |W | ≥ 4. Dengan demikian, W2 adalah salah satu himpunan

pembeda 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 multipartit

lengkap 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 G

adalah 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 disebut

simpul batas dari simpul v jika d(w, v) ≤ d(u, v) untuk setiap w ∈ N(u), dengan

N(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 trivial

dan ∂(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) adalah

suatu 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 dan

mengakibatkan G ∼= Pn.

Misalkan G = Kn dengan n ≥ 2 dan W adalah basis dari G. Jika u /∈ W maka

setiap komponen dari representasi r(u|W ) bernilai 1. Sehingga setiap himpunan

pembeda pada G harus memuat semua simpul kecuali satu simpul dari G. Jadi,

dim(Kn) = n−1. Dengan menggunakan Teorema II.2, jikaG graf terhubung yang

bukan graf lengkap maka dim(G) ≤ n−2. Dengan demikian, jika dim(G) ≤ n−2

maka 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 graf

pohon 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 G

adalah 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) dan

v ∈ 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 berbeda

u, 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 dan

v ∈ Sj , dan i 6= j, maka jelas bahwa r(u|Π) 6= r(v|Π) (karena d(u, Si) = 0

tetapi d(v, Si) 6= 0). Dengan demikian, ketika diberikan sebuah partisi Π dari

V (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 memisahkan

simpul 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) untuk

setiap w ∈ V (G) − {u, v} maka u dan v harus termuat dalam kelas partisi yang

berbeda di G. Hal ini jelas, karena jika tidak demikian, r(u|Π) = r(v|Π). Dengan

demikian diperoleh Lema II.1 berikut ini.

Lema II.1. (Chartrand, Salehi dan Zhang, 2000) Misalkan G suatu graf

terhubung 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 harus

termuat 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 pembeda

karena 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. Partisi

Π3 = {S1, S2, S3}, dengan S1 = {a1, b1}, S2 = {a2, b2} dan S3 = {b3, b4}, pada

Gambar 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,4

dan |Π| = 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, v

termuat 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 memberikan

partisi 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. Kemudian

jarak 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 dengan

d(v, S) = min{d(v, x)|x ∈ S}. Sebagaimana pada graf tak berarah, simpul

x ∈ V (D) (atau subhimpunan S ⊂ V (D)) membedakan dua simpul u dan v jika

d(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 terhubung

jika (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 sedemikian

hingga 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. Jika

k 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 pembeda

bintang 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 sedemikian

hingga 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} adalah

himpunan pembeda dari G. Pandang partisi terurut Π = {S1, S2, · · · , Sk+1} dari

V (G), dengan Si = {wi}, bila i ∈ [1, k], dan Sk+1 = V (G)−W . Maka, diperoleh

r(v|Π) = (d(v, {w1}), d(v, {w2}), · · · , d(v, {wk}), 0) berbeda untuk semua simpul

v ∈ Sk+1 karena W himpunan pembeda dari G. Selain itu, bila v = wi, untuk

suatu i ∈ [1, k], maka r(wi|Π) mempunyai nilai 0 pada entri ke-i tetapi tidak untuk

entri lainnya. Dengan demikian, r(wi|Π) juga unik. Oleh karena itu, Π merupakan

partisi pembeda dari G. Sehingga diperoleh Teorema II.5 berikut ini.

14

Teorema II.5. (Chartrand, Salehi dan Zhang, 2000) Jika G adalah graf

terhubung 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 graf

planar teratur-4 yang daerahnya berbentuk bujursangkar, sedangkan graf teratur-

8 (Z2, ε8) dapat diperoleh dengan menggambarkan semua diagonal pada daerah

bujursangkar pada graf (Z2, ε4). Indeks 4 dan 8 masing-masing menunjukkan

banyak 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 4

pd(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 dua

simpul berbeda u, v ∈ V ((Z2, ε8)) mempunyai r(u|Π2) 6= r(v|Π2). Dengan

demikian, pd(Z2, ε8) ≤ 4. Lebih jauh, dapat ditunjukkan bahwa jika terdapat

suatu partisi pembeda Π2 dari graf (Z2, ε8) maka terdapat sedikitnya sebarang

dua 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 dan

dim(G) = b. Misalkan Ks,t adalah graf bipartit dengan s = a, t = b − a + 2,

dan memenuhi d b2e + 1 ≤ a ≤ b + 1. Teorema II.4 menunjukkan bahwa

dim(Ks,t) = s + t − 2 = a + (b − a + 2) − 2 = b. Selanjutnya, jelas dari

nilai 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 pasang

bilangan bulat positif a, b dengan d b2e+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 dengan

himpunan 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 ≤ b−a+2}, S2 = {ui2|1 ≤ i ≤ b−a+2} dan Si = {u1i|3 ≤ i ≤ a}.Karena semua r(u|Π) berbeda untuk semua simpul u ∈ G, maka Π adalah partisi

pembeda 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 graf

G terdiri atas paling sedikit k − 1 simpul di U . Pandang graf ulat G pada Gambar

II.8.b. Dengan demikian dim(G) = (a− 1) + (b− a+ 1) = b.

Teorema II.8. (Chappell dkk., 2008) Untuk setiap pasang bilangan bulat positif

a, b dengan 3 ≤ a ≤ b + 1, terdapat sebuah graf terhubung G sedemikian hingga

mempunyai 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, · · · , Sn−d+1} adalah partisi pembeda untuk

17

V (G), dengan S1 = {v1, v2, · · · , vd} dan Si = {vi+d−1} 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, maka

setiap 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, dan

g(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), dimensi

partisi k dan diameter d, maka n ≤ kdk−1.

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 simpul

v ∈ V (G). Dengan kata lain, graf G mempunyai sedikitnya n buah representasi

berbeda. Karena simpul v berada tepat di satu Si ∈ Π, dengan 1 ≤ i ≤ k, maka

representasi r(v|Π) memuat tepat satu 0 dan koordinat lainnya adalah bilangan bulat

tak 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 yang

berbeda. Oleh karena itu, n ≤ kdk−1. �

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

D

D

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 bintang

ganda order n ≥ 6, dengan u dan v adalah simpul yang berderajat r + 1 dan

s+ 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) yang

terkait ke simpul v. Dua simpul sebarang ui, uj , dengan 1 ≤ i 6= j ≤ r, mempunyai

jarak sama ke semua simpul di T − {ui, uj}. Menurut Lema II.1 simpul ui dan uj

harus 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 simpul

di 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

D

D

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, ∗, ∗, · · · , ∗) dan

r(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) <

d(u,w) untuk setiap simpul mayor w ∈ V (T )− {v}. Derajat terminal dari simpul

mayor v adalah banyak simpul terminal dari v. Sebuah simpul mayor v ∈ V (T )

disebut simpul mayor eksterior dari T jika v mempunyai derajat terminal positif.

Sebagai contoh, graf pohon pada Gambar II.10 mempunyai empat simpul mayor

v1, v2, v3, v4. Simpul terminal dari v1 adalah u1 dan u2, simpul terminal dari v3

adalah u3, u4 dan u5, dan simpul terminal dari v4 adalah u6 dan u7. Simpul mayor v2

20

8

0

1

2

3

4

5

6

7

4

0

1

2

3

0

1

2

3

Gambar II.11: Graf gir G8 dan graf helm H4

tidak mempunyai simpul terminal dan, karenanya, v2 bukan simpul mayor eksterior

dari T . Misalkan4t(T ) menyatakan derajat terminal maksimum dari semua simpul

mayor eksterior dari pohon T . Gambar II.10 menunjukkan sebuah graf pohon

T dengan 4t(T ) = 3. Maka, (Chartrand dkk., 1998) menunjukkan batas atas

dan batas bawah dari dimensi partisi graf T yang dinyatakan dalam 4t(T ) pada

Teorema II.12 berikut ini.

Teorema II.12. (Chartrand dkk., 1998) Misalkan T adalah graf ulat dengan

4t(T ) ≥ 3. Maka,4t(T )− 2 ≤ pd(T ) ≤ 4t(T ) + 1.

Selain graf pohon, graf mirip roda juga menjadi kajian menarik dalam penelitian

dimensi partisi. Graf mirip roda adalah graf yang diperoleh dengan memberi

perubahan kecil, misalkan dengan penambahan simpul atau sisi, pada sebuah graf

roda. Graf gir, graf helm, dan graf bunga matahari adalah tiga contoh graf mirip

roda.

Graf girG2n didefinisikan sebagai graf yang diperoleh dari sebuah graf siklus genap

C2n dengan himpunan simpul V (C2n) = {v0, v1, · · · , v2n−1}, dengan n ≥ 2 dan

sebuah simpul baru c yang terkait dengan n buah simpul C2n, yaitu v0, v2, · · · v2n−2.

Graf gir G2n mempunyai order 2n + 1 dan 3n sisi. Dengan cara lain, graf gir

G2n diperoleh dari sebuah graf roda Wn dengan menambah sebuah simpul di antara

sepasang simpul (bukan pusat) yang bertetangga di graf roda Wn. Gambar II.11.a

memberi ilustrasi graf gir G8.

Teorema II.13. (Javaid dan Shokat, 2008) Misalkan n ≥ 2 dan k menyatakan

partisi dimensi dari graf gir G2n. Maka berlaku 2n+ 1 < 3k4(k + 2)2k−7.

21

0

1

2

3

0

12

3

Gambar II.12: Graf bunga matahari SF4

Graf Helm Hn adalah sebuah graf yang diperoleh dari sebuah roda Wn dengan

siklus Cn dengan menambah sebuah simpul anting (pendant) yang terkait dengan

setiap simpul (bukan pusat) dari siklus tersebut. Graf helmHn terdiri atas himpunan

simpul V (Hn) = {vi|0 ≤ i ≤ n− 1} ∪ {ai|0 ≤ i ≤ n− 1} ∪ c dan himpunan sisi

E(Hn) = {vivi+1|0 ≤ i ≤ n− 1} ∪ {viai|0 ≤ i ≤ n− 1} ∪ {vic|0 ≤ i ≤ n− 1}dengan i+ 1 diambil modulo n. Gambar II.11.b memberi ilustrasi graf gir H4.


partisi dimensi dari graf helm Hn. Maka, berlaku 2n + 1 < 2k−1+∑3

i=0 2k−i−1(k−1

i

)(k − i)+

∑1j=0

∑2i=0 2k−i−j−2

(k−1i,j

)(k − i− j + 1).

Graf bunga matahari didefinisikan sebagai graf yang diperoleh dari sebuah graf

rodaWn, yang terdiri simpul pusat c dan n-siklus v0, v1, · · · , vn−1, dan penambahan

n buah simpul tambahan w0, w2, · · ·wn−1, dengan wi dihubungkan oleh sebuah sisi

ke vi, vi+1 untuk setiap i = 1, 2, · · · , n1 dan i + 1 diambil modulo n. Graf bunga

matahari SFn mempunyai order 2n+1 dan 4n sisi. Gambar II.12 memberi ilustrasi

graf bunga matahari SF4. SFn


partisi dimensi dari graf bunga matahari SFn. Maka, 2n+1 < 2k−1+∑4

i=0 2k−i−2(k−1

i

)(k − i+ 1)+

∑2j=0

∑4i=0 2k−i−j−1

(k−1i,j

)(k − i− j).

Selanjutnya, Chartrand, Salehi dan Zhang (2000) menunjukkan dimensi partisi graf

bipartitG((V1, V2), E) dalam Teorema II.16 berikut ini. Graf bipartit adalah sebuah

graf yang himpunan simpulnya dapat dipartisi dalam dua subhimpunan, katakan V1

dan V2, sedemikian hingga setiap sisi e ∈ E(G) mempunyai sebuah simpul ujung

di V1 dan simpul ujung lainnya di V2.

22

Teorema II.16. (Chartrand, Salehi dan Zhang, 2000) Jika graf G((V1, V2), E)

adalah graf bipartit dengan partisi V1 dan V2, dimana |V1| = m dan |V2| = n,

maka

pd(G((V1, V2), E)) ≤

{m+ 1 , jika m = n,

max{m,n} , jika m 6= n.

Bukti. MisalkanG((V1, V2), E) adalah graf bipartit, dengan V1 = {a1, a2, · · · , am}dan V2 = {b1, b2, · · · , bn}. Pandang dua kasus berikut:

Kasus 1. m = n.

Misalkan Π = {S1, S2, · · · , Sm+1} adalah partisi pembeda untuk graf

G((V1, V2), E), dengan Si = {ai, bi} dengan 1 ≤ i ≤ m − 1, Sm = {am} dan

Sm+1 = {bn}. Jarak d(ai, Sm) selalu genap dan jarak d(bi, Sm) selalu gasal. Jadi,

r(ai|Π) 6= r(bi|Π) untuk 1 ≤ i ≤ m − 1. Selanjutnya, Sm dan Sm+1 adalah kelas

partisi singleton, maka am dan bm mempunyai representasi yang unik. Oleh karena

itu, pd(Km,n) ≤ m+ 1.

Kasus 2. m 6= n.

Misalkan Π = {S1, S2, · · · , Sm} adalah partisi pembeda untuk graf G((V1, V2), E),

dengan Si = {ai, bi} untuk 1 ≤ i ≤ n dan Si = {ai} untuk n + 1 ≤ i ≤ m. Jarak

d(ai, Sm) selalu genap dan jarak d(bi, Sm) selalu gasal. Jadi, r(ai|Π) 6= r(bi|Π)

untuk 1 ≤ i ≤ n. Selanjutnya, karena Si untuk n + 1 ≤ i ≤ m adalah kelas partisi

singleton, maka ai ∈ Si mempunyai representasi yang unik. Dengan demikian

pd(Km,n) ≤ m. �

Pandang graf bipartit graf G((V1, V2), E). Jika setiap simpul u ∈ V1 bertetangga

dengan semua simpul v ∈ V2 dan setiap simpul v ∈ V2 bertetangga dengan semua

simpul u ∈ V1 maka graf bipartit G((V1, V2), E) disebut graf bipartit lengkap dan

dinotasikan dengan Km,n, dengan m dan n masing-masing adalah kardinalitas V1

dan V2. Teorema II.17 berikut ini menunjukkan bahwa batas atas Teorema II.16

dipenuhi oleh graf bipartit lengkap.

Teorema II.17. (Chartrand, Salehi dan Zhang, 2000) Jika Km,n adalah graf

23

bipartit lengkap dengan kardinalitas partisi masing-masing m dan n, maka

pd(Km,n) =

{m+ 1 , jika m = n,

max{m,n} , jika m 6= n.

Bukti. MisalkanKm,n adalah graf bipartit lengkap , dengan |V1| = m dan |V2| = n.

Pandang dua kasus berikut:

Kasus 1. m = n.

Menurut Teorema II.16, kita cukup menunjukkan batas bawah dari pd(Km,n). Jika

simpul ai, aj ∈ V (Km,n) dan ai, aj ∈ V1, dengan 1 ≤ i 6= j ≤ mmaka berdasarkan

Lema II.1, ai dan aj harus berada pada partisi yang berbeda. Lebih jauh, jika ai ∈V1, bi ∈ V2 dan keduanya termuat dalam kelas partisi yang sama, katakan Si ∈ Π,

maka ai dan bi harus dibedakan oleh sedikitnya sebuah kelas partisi yang beranggota

simpul-simpul di V1 saja (atau V2 saja). Jika tidak, r(ai|Π) = r(bi|Π). Oleh karena

itu, pd(Km,n) ≥ m+ 1.

Kasus 2. m 6= n.

Menurut Lema II.1 pd(Km,n) ≥ max{m,n} dan Teorema II.16 memberi batasnya,

yaitu pd(Km,n) ≤ max{m,n}. Dengan demikian, pd(Km,n) = max{m,n}. �

Menentukan dimensi partisi dari suatu graf baru yang dibangun dengan operasi

biner pada dua graf asal merupakan ranah riset yang menarik. Operasi biner adalah

operasi yang dikenakan pada dua buah graf operan, misalkan G dan H , untuk

mendapatkan sebuah graf baru F . Operasi kartesian dan operasi korona merupakan

dua contoh dari operasi biner. Caceres dkk. (2005) dan Caceres dkk. (2007) menun-

jukkan hubungan antara dimensi metrik graf hasil operasi kartesian dengan dimensi

metrik graf faktornya. Sedangkan Chartrand dkk. (1998) dan Yero dkk. (2010)

menunjukkan hubungan antara dimensi partisi graf hasil operasi kartesian dengan

dimensi partisi graf faktornya.

Teorema II.18. (Chartrand dkk., 1998) Untuk setiap graf terhubung tak-trivial

G, pd(G×K2) ≤ pd(G) + 1.

Bukti. Misalkan G ∼= H × K2, dengan H adalah graf terhubung non-trivial.

Misalkan pd(H) = k dan Π = {S1, S2, · · · , Sk} merupakan suatu partisi pembeda

dari V (H). Untuk dua kopi graf H dalam konstruksi G, misalkan H1 dan H2.

Selanjutnya, misalkan Π1 = {W1,W2, · · · ,Wk} dan Π2 = {U1, U2, · · · , Uk}

24

merupakan partisi pembeda masing-masing dari V (H1) dan V (H2). Kami klaim

bahwa

Π∗ = {W1 ∪ U1,W2 ∪ U2, · · · ,Wk−1 ∪ Uk−1,Wk, Uk}

merupakan partisi pembeda dari V (G). Misalkan x, y ∈ V (G) sedemikian hingga

r(x|Π∗) = r(y|Π∗). Akan ditunjukkan bahwa x = y. Pandang dua kasus berikut:

Kasus 1. x, y ∈ H1 (atau x, y ∈ H2).

Tanpa mengurangi keumuman, katakan x, y ∈ H1. Maka, untuk 1 ≤ i ≤ k − 1,

dG(x,Wi ∪ Ui) = dH1(x,Wi), dG(y,Wi ∪ Ui) = dH1(y,Wi) dG(x,Wk) =

dH1(x,Wk), dG(y,Wk) = dH1(y,Wk), dG(x, Uk) = dH1(x,Wk) + 1, dan

dG(y, Uk) = dH1(y,Wk) + 1. Andaikan x 6= y. Karena Π1 merupakan partisi

pembeda dari V (H1), maka dH1(x,Wi) 6= dH1(y,Wi) untuk sebuah i dengan

1 ≤ i ≤ k. Oleh karena itu, dG(x,Wi) 6= dG(y,Wi), kontradiksi dengan kenyataan

r(x|Π∗) = r(y|Π∗). Dengan demikian, x = y.

Kasus 2. x ∈ H1 dan y ∈ H2 (atau x ∈ H2 dan y ∈ H1).

Tanpa mengurangi keumuman, katakan x ∈ H1 dan y ∈ H2. Dalam kasus ini,

dG(x,Wk) = dG(x, Uk) − 1 dan dG(y,Wk) = dG(y, Uk) + 1. Jadi, dG(x,Wk) 6=dG(y,Wk) dan dG(x, Uk) 6= dG(y, Uk), kontradiksi dengan r(x|Π∗) = r(y|Π∗).

Dengan demikian, x = y. �

Secara umum, pada Teorema II.19, Yero dkk. (2010) menunjukkan batas atas dari

dimensi partisi graf hasil operasi kartesian antara dua graf terhubung G1 dan G2

sebarang, dan menyatakannya dalam pd(G1) dan pd(G2).

Teorema II.19. (Yero dkk., 2010) Untuk sebarang graf terhubung G1 dan G2,

pd(G1 ×G2) ≤ pd(G1) + pd(G2).

Bukti. Misalkan Π1 = {W1,W2, · · · ,Wk} dan Π2 = {U1, U2, · · · , Ul} masing-

masing merupakan partisi pembeda dari G1 = (V1, E1) dan G2 = (V2, E2). Kami

akan menunjukkan bahwa Π1 = {W1×U1,W1×U2, · · · ,W1×Ul,W2×U1,W3×U1, · · · ,Wk×U1, C}, dengan C = (V1×V2)−((V1×U1)∪(W1×V2)), merupakan

partisi pembeda dari G1 ×G2.

Pandang dua simpul berbeda (a, b), (c, d) ∈ V (V1 × V2). Jika a = c maka terdapat

Ui ∈ Π2 sedemikian hingga dG2(b, Ui) 6= dG2(d, Ui). Oleh karena itu, terdapat

dG1×G2((a, b),W1 × Ui) = dG1(a,W1) + dG2(b, Ui) 6= dG1(c,W1) + dG2(d, Ui) =

25

dG1×G2((c, d),W1 × Ui).

Sekarang, jika a 6= c, periksa dua kasus berikut:

Kasus 1. a ∈ Wi dan c ∈ Wj , dengan i 6= j.

Jika dG1×G2((a, b),Wi × U1) = dG1×G2((c, d),Wi × U1), dan dG1×G2((a, b),Wj ×U1) = dG1×G2((c, d),Wj × U1), maka dG2(b, U1) = dG1×G2((a, b),Wi ×U1) = dG1×G2((c, d),Wi × U1) = dG1(c,Wi) + dG2(d, U1) = dG1(c,Wi) +

dG1×G2((c, d),Wj × U1) = dG1(c,Wi) + dG1×G2((a, b),Wj × U1) = dG1(c,Wi) +

dG1(c,Wj) + dG2(b, U1), sebuah kontradiksi.

Kasus 2. a, c ∈ Wi.

Kasus 2.1. b, d ∈ Ul. Misalkan Wj ∈ Π1 sedemikian hingga dG1(a,Wj) 6=dG1(c,Wj). Dalam kasus ini, jika dG2(b, U1) = dG2(d, U1) maka terdapat

dG1×G2((a, b),Wj × U1) = dG1(a,Wj) + dG2(b, U1) 6= dG1(c,Wj) + dG2(d, U1) =

dG1×G2((c, d),Wj × U1). Sebaliknya, jika dG2(b, U1) 6= dG2(d, U1) maka terdapat

dG1×G2((a, b),Wi × U1) = dG2(b, U1) 6= dG2(d, U1) = dG1×G2((c, d),Wi × U1)

Kasus 2.2. b ∈ Uj dan d ∈ Ul, j 6= l.

Kasus ini serupa dengan Kasus 1. Oleh karena itu, setiap simpul berbeda

(a, b), (c, d) ∈ V (V1 × V2), terdapat r((a, b)|Π) 6= r((c, d)|Π). �

Dari Teorema II.5 dan Teorema II.19 diperoleh akibat berikut ini.

Akibat II.1. Untuk sebarang dua graf terhubung G1 dan G2, pd(G1 × G2) ≤pd(G1) + dim(G2) + 1.

Lebih jauh, Yero dkk. (2010) memperbaiki batas yang diberikan oleh Akibat II.1

dan menyatakannya dalam Teorema II.20.

Teorema II.20. (Yero dkk., 2010) Untuk sebarang graf terhubung G dan H ,

pd(G×H) ≤ pd(G) + dim(H).

Bukti. Misalkan Π1 = {W1,W2, · · · ,Wk} merupakan suatu partisi pembeda dari

G1 = (V1, E1) dan S = {u1, u2, · · · , ut} merupakan suatu himpunan pembeda

dari G2 = (V2, E2). Misalkan C = (V1 × V2) − ((V1 × {u1}) ∪ (W1 × {u2}) ∪· · · ∪ (W1×{ut})). Sekarang, kami menunjukkan bahwa Π1 = {W1×{u1},W2×{u1}, · · · ,Wk×{u1},W1×{u2},W1×{u3}, · · · ,W1×{ut}, C}merupakan suatu

26

partisi pembeda dari G1 ×G2.

Pandang dua simpul berbeda (a, b), (c, d) ∈ V (V1 × V2). Jika a = c maka b 6=d. Oleh karena itu, terdapat uj ∈ S sedemikian hingga dG2(b, uj) 6= dG2(d, uj).

Selanjutnya, dG1×G2((a, b),W1 × {uj}) = dG1(a,W1) + dG2(b, uj) 6= dG1(c,W1) +

dG2(d, uj) = dG1×G2((c, d),W1 × {uj}).

Sekarang, jika a 6= c, maka periksa dua kasus berikut:

Kasus 1. a ∈ Wi dan c ∈ Wj , i 6= j.

Misalkan, dG2(b, u1) ≤ dG2(d, u1). Dalam kasus ini terdapat dG1×G2((a, b),Wi ×{u1}) = dG2(b, u1) ≤ dG2(d, u1) < dG1(c,Wi) + dG2(d, u1) = dG1×G2((c, d),Wi ×{u1}). Dengan cara yang serupa, jika dG2(b, u1) ≥ dG2(d, u1), maka terdapat

dG1×G2((a, b),Wj × {u1}) > dG1×G2((c, d),Wj × {u1}).

Kasus 2. a, c ∈ Wi.

Misalkan dG2(b, u1) = dG2(d, u1). Karena terdapat j 6= i sedemikian hingga

dG(a,Wj) 6= dG(c,Wj), maka dG1×G2((a, b),Wj × {u1}) = dG1(a,Wj) +

dG2(b, u1) 6= dG1(c,Wj)+dG2(d, u1) = dG1×G2((c, d),Wj×{u1}). Jika dG2(b, u1) 6=dG2(d, u1), maka terdapat dG1×G2((a, b),Wi × {u1}) = dG2(b, u1) 6= dG2(d, u1) =

dG1×G2((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, · · · , xm−1xm}. Graf

ulat diperoleh dengan menambahkan ni buah sisi anting pada setiap simpul xi

dari sebuah graf lintasan Pm, dengan 1 ≤ i ≤ m, dan dinotasikan dengan

C(m;n1, n2, · · · , nm). Graf ulat C(m;n1, n2, · · · , nm) terdiri atas himpunan

simpul 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, graf

ulat 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 subgraf

K1,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}. Definisikan

nmaks = max{n1, n2, . . . , nm}. Subgraf K1,nmaksdisebut sebagai subgraf ulat

maksimum 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 derajat

terminal 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,nmaksyang berbeda (Lihat Gambar III.2.b),

maka subgraf K1,nidan 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 xk

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

DDD

D

DDD

D

DD

D

D D

d(xi,xm)

xmxi xj

d(xj,xm)

DDD

D

DDD D

D

xpxj

d(xj,xp)

DDD D

D

xo

DDD

D

xi

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

Gambar III.2: Dua kondisi subgraf graf ulat K1,nidan 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 sebarang

dua simpul anting berbeda di K1,ni, dengan ni ≥ 2, maka u dan v harus berada

dalam kelas partisi yang berbeda di Π.

Bukti. Misalkan u dan v dua simpul anting berbeda di K1,ni. Karena jarak

d(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, dengan

i 6= j, maka xi ∈ V (Ki1,nmaks

) dan xj ∈ V (Kj1,nmaks

) harus termuat dalam kelas

partisi yang berbeda di Π.

Bukti. Misalkan Π = {S1, S2, · · · , Snmaks} suatu partisi pembeda dari graf

C(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,nmaksdapat diasosiasikan dengan nmaks kelas partisi

di Π. Misalkan simpul xi ∈ V (Ki1,nmaks


) berada dalam kelas

partisi 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. �


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,ni

dan ajk ∈ K1,nj, dengan 1 ≤ k ≤ ni, termuat dalam kelas partisi yang sama, maka

xi dan xj harus termuat dalam kelas partisi yang berbeda di Π.

Bukti. Misalkan Π = {S1, S2, · · · , Snmaks} suatu partisi pembeda dari graf

C(m;n1, n2, · · · , nm). Misalkan xi, xj ∈ X untuk suatu kelas partisi X ∈ Π.

Karena subgraf K1,nidan K1,nj

berjarak sama dan sebarang dua simpul anting

aik ∈ K1,nidan ajk ∈ K1,nj

, dengan 1 ≤ k ≤ ni, termuat dalam kelas partisi

yang 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 simpul

anting 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,nmaksadalah subgraf ulat maksimum dari

C(m;n1, n2, · · · , nm) dan p menyatakan banyak subgraf K1,nmaks. Maka, untuk

nmaks ≥ 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 ≤ nmaks

Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Sp} untuk grafC(m;n1,

n2, · · · , nm). Akibat III.1 memastikan setiap simpul anting pada K1,nitermuat

dalam kelas partisi yang berbeda. Karena K1,nmaksmemiliki 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 partisi

pembeda Π = {S1, S2, · · · , Snmaks} untuk graf V (C(m;n1, n2, · · · , nm)).

Letakkan setiap simpul v ∈ V (C(m;n1, n2, · · · , nm)) ke dalam kelas partisi

Sj ∈ Π, untuk suatu 1 ≤ j ≤ nmaks, menurut algoritma berikut ini:

31

a. Hitung banyak subgraf K1,nmaksdan 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 Kp1,nmaks

,

e. Definisikan himpunan T = {semua kombinasi-(nmaks−1) dari nmaks buah kelas

partisi di Π}, sedemikian hingga T = {T1, T2, · · · , Tnmaks} dengan Ti ∈ T

adalah kombinasi yang tidak memuat kelas partisi Si,

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

item d,

g. Jika K1,niterletak pada selang A1 atau A2 maka setiap simpul anting pada K1,ni

secara berurut diletakkan pada kelas partisi yang berasosiasi dengan T1,

h. Jika K1,niterletak pada selang Ak, dengan 3 ≤ k ≤ p + 1 maka setiap simpul

anting pada K1,nisecara berurut diletakkan pada kelas partisi yang berasosiasi

dengan Tk−1

i. Jika K1,nidan 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 partisi

yang berbeda di Π.

j. Setiap simpul pusat xk ∈ V (Kk1,ni

), dengan Kk1,ni

bukan subgraf ulat maksimum

dan 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 simpul

anting u ∈ V (K1,ni) dan v ∈ V (K1,nj

), dengan ni = nj = nmaks, maka u dan v

dibedakan oleh sebuah kelas partisi yang memuat xi atau xj . Jika simpul anting

u ∈ V (K1,ni) dan v ∈ V (K1,nj

), dengan K1,nidan K1,nj

berada dalam selang yang

berbeda, 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,nidan K1,nj

berada

dalam selang sama, katakan Ao, dan subgraf K1,nidan 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,nidan 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 satu

dari 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,nitetapi tidak memuat simpul antingK1,nj

. Dengan

demikian, untuk setiap u, v ∈ V (C(m;n1, n2, · · · , nm)), r(u|Π) 6= r(v|Π). (Lihat

Gambar III.3).

Kasus 2: p > nmaks

Misalkan 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 dua

buah simpul xi ∈ V (Ki1,nmaks


), sedemikian hingga simpul

xi dan xj termuat dalam kelas partisi yang sama, kontradiksi. Dengan demikian,

p ≥ nmaks + 1.

Selanjutnya, definisikan partisi pembeda Π = {S1, S2, · · · , Snmaks+1} untuk graf

C(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)) sedemikian

hingga 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 dan

v dibedakan oleh sedikitnya satu kelas partisi X ∈ Π, dengan X adalah kelas

partisi 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 dan

pd(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 dengan

menambahkan n buah sisi anting pada setiap simpul pada lintasan Pm, dengan

n ≥ 3, maka

pd(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 isomorfik

masing-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 partisi

graf 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 dan

v dalam kelas partisi yang sama. Jarak simpul anting d(ai1, S3) = d(a(i+1), S3)− 1

dan d(xi, S3) = d(x(i+1), S3) − 1, untuk 2 ≤ i ≤ m − 1. Dengan demikian, setiap

simpul u ∈ V (C(m; 1)) mempunyai representasi berbeda. Demikian pula halnya

simpul 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. (Lihat

Gambar 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)) sedemikian

hingga

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 S2

dibedakan oleh oleh kelas partisi S1 dan S3. Oleh karena S3 merupakan kelas partisi

singleton, maka x1 ∈ S3 dengan sendirinya unik. Dengan demikian untuk sebarang

dua 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 D

D 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,nidengan cara menghubungkan satu

simpul anting dari setiap graf bintang K1,nidengan 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 sisi

E(F (m;n1, n2, · · · , nm)) = {cixi, ciaij|1 ≤ i ≤ m, 1 ≤ j ≤ ni−1}∪{xixi+1|1 ≤i ≤ m−1}. Jika n1 = n2 = · · · = nm = n, graf kembang api disebut graf kembang

api 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 ≤ ni−1}. 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

xo

ci cj cp

xi xm xj

Gambar III.7: Dua kondisi subgraf kembang api K1,nidan K1,nj

berjarak sama

K1,nmaksyang berbeda (Lihat Gambar III.7.b),

maka subgraf K1,nidan 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 berbeda

di Π.

Bukti. Misalkan sebarang dua simpul anting berbeda u, v ∈ V (K1,ni). Karena

d(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, · · · , Snmaks−1} adalah partisi pembeda

untuk 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 dalam

kelas partisi yang berbeda di Π.

Bukti. Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Snmaks−1} untuk

graf F (m;n1, n2, · · · , nm). Akibat III.3 memastikan setiap dua simpul anting di

K1,nitermuat dalam kelas partisi yang berbeda di Π. Oleh karena subgraf K1,ni

dan K1,njmasing-masing memiliki nmaks − 1 simpul anting, maka semua simpul

anting padaK1,nidanK1,nj

dapat diasosiasikan dengan nmaks−1 kelas partisi yang

terdapat 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. �


n2, · · · , nm)) untuk m ≥ 2. Jika sebarang dua subgraf berbeda dari graf kembang

apiK1,nidanK1,nj

berjarak sama dan sebarang dua simpul anting aik ∈ K1,nidan

ajk ∈ K1,nj, dengan 1 ≤ k ≤ ni− 1, termuat dalam kelas partisi yang sama, maka

maka ci, xi ∈ X dan cj, xj ∈ Y , dengan X dan Y merupakan dua kelas partisi

berbeda di Π.

Bukti. Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Snmaks−1} untuk

V (F (m;n1, n2, · · · , nm)). Asumsikan X, Y ∈ Π dan X = Y sedemikian

hingga 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 anting

dari K1,nidan 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 ∈ Π yang

memuat simpul dariK1,nktetapi 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,nmakspada graf

F (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 − 1

Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Sp} dari graf F (m;n1,

n2, · · · , nm). Akibat III.3 memastikan setiap simpul anting di K1,nitermuat dalam

kelas partisi yang berbeda di Π. Karena K1,nmaksmemiliki nmaks − 1 buah simpul

anting, maka sedikitnya terdapat nmaks−1 buah kelas partisi berbeda di Π. Dengan

38

demikian, p ≥ nmaks − 1.

Sekarang, definisikan suatu partisi pembeda Π = {S1, S2, · · · , Snmaks−1} untuk

V (F (m;n1, n2, · · · , nm)) sedemikian hingga mengikuti algoritma berikut:

a. Hitung jumlah subgraf K1,nmaksdan 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 partisi

Snmaks−1, Snmaks−2, · · · , Snmaks−p,

d. Setiap simpul anting pada Kk1,nmaks

, secara berurut diletakkan pada kelas partisi

S1, S2, S3, · · · , Snmaks−1,

e. Definisikan A1 sebagai selang terbuka sebelum subgraf K11,nmaks

, Ak+1 sebagai

selang antaraKk1,nmaks

danKk+11,nmaks

, dengan 1 ≤ k ≤ p, danAp+1 sebagai selang

setelah subgraf Kp1,nmaks

,

f. Definisikan himpunan T = {semua kombinasi-(nmaks − 2) dari nmaks − 1 buah

kelas partisi di Π}, sedemikian hingga T = {T1, T2, · · · , Tnmaks−1} dengan Ti ∈

T , dengan Ti adalah kombinasi yang tidak memuat kelas partisi Si,

g. Identifikasi letak K1,nmaks−1pada selang sebagaimana didefinisikan pada item e,

h. Jika K1,nmaks−1terletak pada selang A1 atau A2 maka setiap simpul anting pada

K1,nmaks−1secara berurut diletakkan pada kelas partisi yang berasosiasi dengan

T1,

i. Jika K1,nmaks−1terletak pada selang Ak, dengan 3 ≤ k ≤ p + 1 maka setiap

simpul anting pada K1,nmaks−1secara berurut diletakkan pada kelas partisi yang

berasosiasi dengan Tk−1

j. Jika Ki1,nmaks−1

dan Kj1,nmaks−1

berjarak sama, dengan i 6= j, berdasarkan Lema

III.4, maka cl, xl ∈ X dan cm, xm ∈ Y sedemikian hingga kelas partisi X, Y ∈Π dan X 6= Y ,

Untuk memastikan bahwa Π adalah partisi pembeda untuk F (m;n1, n2, · · · , nm),

pandang sebarang dua simpul berbeda u, v ∈ V (F (m;n1, n2, · · · , nm)) sedemikian

hingga u dan v dalam kelas partisi yang sama. Jika simpul anting u ∈ V (K1,nmaks)

dan v ∈ V (K1,nmaks), maka u dan v dibedakan oleh sebuah kelas partisi yang

memuat ci atau cj . Jika simpul u = ci dan v = xi, maka d(u,X) = 1 untuk

semua kelas partisi X di Π kecuali kelas partisi yang mememuat ci dan sedikitnya

39

terdapat suatu kelas partisi X sedemikian d(v,X) = 2, yaitu kelas partisi di Π yang

tidak memuat ci (atau xi), dan tidak memuat simpul yang bertetangga dengan xi.

Dengan demikian, r(u|Π) 6= r(v|Π).

Sekarang, pandang dua simpul anting berbeda u ∈ V (K1,ni) dan v ∈ V (K1,nj

),

dengan ni = nj < nmaks. Jika K1,nidan K1,nj

berjarak sama, maka u dan v

dibedakan oleh sebuah kelas partisi yang memuat ci atau cj . Sebaliknya, jika K1,ni

dan K1,njberjarak tidak sama maka u dan v dibedakan oleh sebuah kelas partisi Z

sedemikian hingga Z memuat simpul dari K1,nmaksdan tidak memuat simpul dari

K1,nimaupun K1,nj

. Demikian pula halnya jika u = ci dan v = xi maka u dan v

dibedakan oleh kelas partisi Z.

Selanjutnya, jika u ∈ V (K1,nmaks) dan v ∈ V (K1,nmaks

) dan kedua subgraf

tersebut terletak pada selang yang berbeda, maka simpul-simpul dari K1,nidan

K1,njdibedakan oleh sebuah kelas partisi Y , yaitu sebuah kelas partisi yang memuat

simpul dari K1,nitetapi tidak memuat simpul dari K1,nj

, atau sebaliknya. Dengan

demikian, r(u|Π) 6= r(v|Π).

Kasus 2: p > nmaks − 1

Kami akan menunjukkan bahwa pd(F (m;n1, n2, · · · , nm)) = nmaks. Misalkan

terdapat suatu partisi pembeda Π untuk V (F (m;n1, n2, · · · , nm)) dengan nmaks −1 buah kelas partisi, yaitu Π = {S1, S2, · · · , Snmaks−1}. Jika p > nmaks − 1,

maka sedikitnya terdapat dua simpul pusat, katakan ci dan cj , termuat dalam kelas

partisi yang sama. Oleh karena itu, Lema III.3 tidak terpenuhi. Dengan demikian,

pd(F (m;n1, n2, · · · , nm)) ≥ nmaks.

Selanjutnya akan ditunjukkan batas atas dimensi partisi untuk graf kembang

api F (m;n1, n2, · · · , nm). Definisikan suatu partisi pembeda Π = {S1,

S2, · · · , Snmaks} untuk graf F (m;n1, n2, · · · , nm) sedemikian hingga mengikuti

algoritma berikut ini:

a. Setiap simpul anting pada K1,ni, secara berurut diletakkan pada kelas partisi

S1, S2, S3, · · · , Sni, dengan 1 ≤ i ≤ m,

b. Letakkan simpul pusat c1 pada kelas partisi S1,

c. Letakkan simpul pusat x1 pada kelas partisi Snmaks,

c. Letakkan simpul c2 dan x2 pada kelas partisi S1, c3, x3 pada kelas partisi S2,

c4, x4 pada kelas partisi S3, c5, x5 pada kelas partisi S1 dan seterusnya dengan

pola pengulangan yang sama.

40

DD

D

1 2

1

D

3

DD

D

1 2

1

D

2

DD

D

1 3

1

D

3

DD

D

1 3

2

D

2

D D

2 2

(b)(a)

Gambar III.8: a.Partisi pembeda minimum dari graf F (2; 3) dan b.Partisi pembedaminimum dari graf F (2; 4)

Pandang sebarang dua simpul berbeda u, v ∈ V (F (m;n1, n2, · · · , nm)) sedemikian

hingga 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, x1) 6= d(v, x1). Selan-

jutnya, d(u, Snmaks) 6= d(v, Snmaks

) dan oleh karena itu r(u|Π) 6= r(v|Π). Jika

simpul u, v ∈ V (K1,ni), untuk sebuah i dalam selang tertutup 1 ≤ i ≤ m,

maka satu di antara dua simpul tersebut adalah simpul anting dan yang lainnya

adalah sebuah simpul pusat. Tanpa mengurangi keumuman, misalkan u = ci dan

v ∈ V (K1,ni) − {xi, ci}. Oleh karena itu, d(u,H) = 1 dan jarak d(v,H) = 2,

dengan H adalah kelas partisi yang tidak memuat simpul u maupun v. Dengan

demikian, r(u|Π) 6= r(v|Π). Demikian pula halnya jika u = xi dan v = xj , dengan

i 6= j, representasi kedua simpul tersebut dibedakan oleh jaraknya terhadap kelas

partisi Snmaks. Dengan demikian, pd(F (m;n1, n2, · · · , nm)) ≤ nmaks. �

Sekarang, pandang beberapa kasus khusus dari graf kembang api, yaitu F (1;n)

dan F (2;n). Graf kembang api F (1;n) isomorfik dengan graf bintang K1,n. Oleh

karena dimensi partisi pd(K1,n) = n (Chartrand dkk., 1998), maka partisi dimensi

pd(F (1;n)) = pd(K1,n) = n.

Selanjutnya, pandang F (2;n) untuk n = 1, 2, 3, 4. Graf kembang api F (2; 1) dan

F (2; 2) adalah graf yang isomorfik dengan graf lintasan P4 dan P6, berturut-turut.

Dengan demikian dimensi partisi pd(F (2; 2)) = pd(F (2; 3)) = 2. Lebih jauh,

kami menunjukkan bahwa pd(F (2; 3)) = pd((2; 4)) = 3. Batas bawah untuk

dimensi partisi kedua graf tersebut adalah 3 karena graf F (2; 3) dan F (2; 4) adalah

graf terhubung dan bukan graf lintasan. Menurut Chartrand, Salehi dan Zhang

(2000), pd(G) = 2 jika dan hanya jika graf G adalah sebuah graf lintasan. Dengan

demikian, pd(F (2; 3)) = pd((2; 3)) ≥ 3. Batas atas pd(F (2; 3)) dapat ditunjukkan

dengan mendefinisikan Π = {S1, S2, S3} sebagai partisi pembeda untuk V (F (2; 3))

sedemikian hingga S1 = {a11, a21, c1, c2}, S2 = {a12, a22, x2} dan S3 = {x1}.Hasil pemeriksaan menunjukkan bahwa setiap simpul v ∈ V (F (2; 4)) mempunyai

41

DD

1

DD

DD

DD

DD

DD

1 11 11

3 2 22 22

D D DD DD

2 22 222

Gambar III.9: Partisi pembeda minimum graf F (6; 2, 2, 2, 2, 2, 2)

representasi unik. Jadi, pd(F (2; 3)) ≤ 3. (Lihat Gambar III.8.a).

Demikian pula halnya dengan batas atas dimensi partisi graf F (2; 4). Defini-

sikan Π = {S1, S2, S3} sebagai partisi pembeda untuk V (F (2; 4)) sedemikian

hingga S1 = {a11, a21, c1}, S2 = {a12, a22, c2, x2} dan S3 = {a13, a23, x1}. Hasil

pemeriksaan menunjukkan bahwa setiap simpul v ∈ V (F (2; 4)) mempunyai repre-

sentasi berbeda. Jadi, pd(F (2; 4)) ≤ 3. (Lihat Gambar III.8.b).

Teorema III.4. ♦ Jika m ≤ 3 maka pd(F (m; 1)) = pd(F (m; 2)) = 3.

Bukti. (Chartrand, Salehi dan Zhang, 2000) membuktikan bahwa dimensi partisi

graf terhubung pd(G) = 2 jika dan hanya jika G adalah graf lintasan. Karena graf

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

Karena graf F (m; 1) isomorf dengan graf C(m; 1), maka menurut Teorema III.2

pd(F (m; 1) ≤ 3. Sekarang, definisikan partisi pembeda Π = {S1, S2, S3} untuk

V (F (m; 2)) sedemikian hingga

Sq =

{ai1|2 ≤ i ≤ m} , jika q = 1,

{ci, xi|1 ≤ i ≤ m} , jika q = 2,

{a11} , jika q = 3.

Setiap simpul anggota S1 dibedakan oleh kelas partisi S3 dan setiap simpul di S2

dibedakan oleh oleh kelas partisi S1 dan S3. Oleh karena S3 merupakan kelas partisi

singleton, maka x1 ∈ S3 dengan sendirinya unik. Dengan demikian untuk sebarang

dua simpul berbeda u, v ∈ C(m; 2), r(u|Π) 6= r(v|Π). Jadi, pd(F (m; 2)) ≤ 3.

(Lihat Gambar III.9.

�

42

Sekarang, pandang kasus khusus graf kembang api F (m;n), dengan n = 3, 4. Dari

pemeriksaan diperoleh bahwa pd(F (m, 3)) = 3 jika m ≤ 3, dan pd(F (m, 3)) = 4

jika m > 3. Selanjutnya, pd(F (m, 4)) = 3 jika m ≤ 2, dan pd(F (m, 3)) = 4

jika m > 2. Sementara itu, untuk dimensi partisi graf kembang api tak-homogen

dengan nmaks ≤ 4 masih merupakan masalah terbuka.

III.3 Dimensi partisi graf pohon pisang

Sebuah graf pohon pisang (banana tree)B(m;n) adalah sebuah graf yang diperoleh

dengan menghubungkan satu simpul anting dari setiap m buah kopi graf bintang

K1,n ke sebuah simpul baru yang disebut simpul akar r (Chen dkk., 1997). Oleh

karena graf bintang yang menyusun graf B(m;n) mempunyai order yang sama,

graf B(m;n) disebut graf pohon pisang homogen. Graf pohon pisang B(m;n)

terdiri atas himpunan simpul V (B(m;n)) = {ci|1 ≤ i ≤ m} ∪ {aij|1 ≤ i ≤m, 1 ≤ j ≤ n − 1} ∪ {xi|1 ≤ i ≤ m} ∪ {r} dan himpunan sisi E(B(m;n)) =

{ciaij|1 ≤ i ≤ m, 1 ≤ j ≤ n−1}∪{xici|1 ≤ i ≤ m}∪{rxi|1 ≤ i ≤ m}. Gambar

III.10 adalah graf pohon pisang homogen B(3; 5).

Selanjutnya, didefinisikan subgraf Ki1,n ⊂ B(m;n) adalah kopi ke-i dari graf

bintang K1,n di B(m;n) sedemikian hingga V (Ki1,n) = {xi, ci, aij|1 ≤ i ≤ m, 1 ≤

j ≤ n− 1} dan E(Ki1,n) = {xici, ciaij|1 ≤ i ≤ m, 1 ≤ j ≤ n− 1}.

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

Akibat III.4. ♦ Misalkan terdapat suatu partisi pembeda Π untuk graf pohon

pisang B(m;n). Jika sebarang dua simpul anting berbeda u, v ∈ V (Ki1,n) maka u

dan v harus termuat dalam kelas partisi yang berbeda di Π.

Bukti. Misalkan sebarang dua simpul berbeda u, v ∈ V (Ki1,n). Karena d(u,w) =

d(v, w) untuk semua w ∈ V (B(m;n))−{u, v}, maka menurut Lema II.1 simpul u

dan v harus berada pada kelas partisi berbeda di Π. �

Lema III.5. ♦Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Sn−1}untuk V (B(m;n)). Misalkan Ki

1,n dan Kj1,n adalah kopi ke-i dan ke-j dari bintang

K1,n di B(m;n). Jika ci dan cj masing-masing adalah simpul pusat Ki1,n dan Kj

1,n

maka ci dan cj harus termuat dalam kelas partisi yang berbeda di Π.

43

DDDD

D

2

24232221DDDD

1

31 32 33 34DDDD

11 12 13 14

3

D D

D

D D

1 2

D

3

Gambar III.10: Graf pohon pisang homogen B(3; 5)

Bukti. Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Sn−1} untuk

V (B(m;n)) yang terdiri atas n − 1 buah kelas partisi. Akibat III.4 memastikan

bahwa setiap simpul anting di Ki1,n termuat dalam kelas partisi yang berbeda di Π.

Oleh karena itu, setiap simpul anting di Ki1,n, dengan 1 ≤ i ≤ m, dapat diasosi-

asikan dengan n − 1 buah kelas partisi di Π. Misalkan simpul pusat ci dan cj

termuat dalam kelas partisi yang sama, katakan ci, cj ∈ X dan X ∈ Π. Karena

d(ci, X) = d(cj, X) = 0 dan d(ci, Y ) = d(cj, Y ) = 1, dimana Y adalah kelas

partisi di Π dan X 6= Y , maka r(ci|Π) = r(cj|Π), kontradiksi. �

Lema III.6. ♦Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Sn−1}untuk V (B(m;n)). Jika r dan ci, dengan 1 ≤ i ≤ m, masing-masing adalah simpul

akar dan simpul pusat subgrafKi1,n ⊂ B(m;n), maka r dan ci harus termuat dalam

kelas partisi yang berbeda di Π.

Bukti. Misalkan simpul r, ci ∈ X , dengan X adalah sebuah kelas partisi di Π.

Pandanga subgraf Ki1,n. Karena kardinalitas Π adalah n − 1, maka terdapat n − 1

buah kelas partisi untuk simpul-simpul padaKi1,n. Lebih jauh, simpul xi dan sebuah

simpul anting Ki1,n, katakan aij , harus termuat dalam kelas partisi yang sama,

misalkan Y . Oleh karena itu, d(xi, Y ) = d(aij, Y ) = 0, d(xi, X) = d(aij, X) = 1

dan d(xi, Z) = d(aij, Z) = 2, dengan Z adalah kelas partisi di Π selain X dan Y .

Dengan demikian, r(aij|Π) = r(xi|Π), kontradiksi. �

Teorema III.5 berikut ini menunjukkan dimensi partisi graf pohon pisang B(m;n).

Teorema III.5. ♦ Untuk n ≥ 2, dimensi partisi dari graf pohon pisang B(m;n)

adalah sebagai berikut:

pd(B(m;n)) =

{n− 1 , jika m ≤ n− 2,

n , jika n− 2 < m ≤(

nn−1

)(n− 1),

44

DDD D D

D

DDD D D

D

DDD D D

D

DDD D D

D

1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5

D

1 2 3 4

5

Gambar III.11: Partisi pembeda minimum graf pohon pisang B(3; 5)

Bukti. Kasus 1: m ≤ n− 2

Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , Sp} untuk V (B(m;n)).

Akibat III.4 memastikan setiap simpul anting di Ki1,n harus termuat dalam kelas

partisi yang berbeda. Oleh karena itu, p ≥ n− 1.

Sekarang, pandang graf pohon pisang B(m;n), dengan m ≤ n − 2. Definisikan

sebuah partisi pembeda Π = {S1, S2, · · · , Sn−1} untuk V (B(m;n)) sedemikian

hingga

Sq =

{a1q, a2q, · · · , anq, cq, xq} , jika 1 ≤ q ≤ n,

{a1q, a2q, · · · , anq} , jika m ≤ q ≤ n− 2,

{a1q, a2q, · · · , anq, r} , jika q = n− 1.

Pandang sebarang dua simpul berbeda u, v ∈ V (B(m;n)) yang termuat dalam

kelas partisi yang sama. Jika u dan v, masing-masing, adalah simpul anting di

Ki1,n dan Kj

1,n, untuk i 6= j, maka simpul u dan v dibedakan oleh kelas partisi

yang memuat kedua simpul ci maupun cj (Lema III.5). Jika u adalah simpul anting

di Ki1,n dan v = xi, maka kedua simpul tersebut dibedakan oleh kelas partisi yang

memuat simpul akar r (Lema III.6). Jika u = ci dan v = xi, maka u dan v dibedakan

oleh kelas partisi yang tidak memuat r. Oleh karena itu, r(u|Π) 6= r(v|Π) untuk

semua simpul u, v ∈ V (B(m;n)). Dengan demikian, pd(B(m;n)) ≤ n− 1 untuk

m ≤ n− 2. (Lihat Gambar III.11).

Kasus 2: n− 2 < m ≤(

nn−1

)(n− 1)

Misalkan terdapat suatu partisi pembeda Π untuk V (B(m;n)) dengan n − 1 buah

kelas partisi, yaitu Π = {S1, S2, · · · , Sn−1}. Karena m > n − 2, maka terdapat

sedikitnya sebuah simpul ci, untuk 1 ≤ i 6= j ≤ m, sedemikian hingga ci dan r

termuat dalam kelas partisi yang sama. Oleh karena itu, Lema III.6 tidak terpenuhi.

Dengan demikian, pd(B(m;n)) ≥ n.

45

DD DD

2 3 4

DD DD

2 3 4

DD DD

2 3 4

DD DD

1 3 4

DD DD

1 3 4

DD DD

1 3 4

DD DD

1 2 4

DD DD

1 2 4

DD DD

1 2 4

1 2 3 1 2 3 1 2 3

D

4

Gambar III.12: Partisi pembeda minimum graf pohon pisang B(16; 4)

Selanjutnya, pandang graf pohon pisangB(m;n) denganm ≤(

nn−1

)(n−1). Defini-

sikan sebuah himpunan T yang beranggotakan semua kombinasi-(n−1) dari n buah

kelas partisi di Π, yaitu T = {T1, T2, · · · , Tn} dengan Ti ∈ T adalah kombinasi-

(n − 1) yang tidak memuat kelas partisi Si untuk sebuah i dalam selang tertutup

[1, n]. Definisikan suatu partisi pembeda Π = {S1, S2, · · · , Sn} untuk V (B(m;n))

dengan mengikuti algoritma berikut:

a. Definisikan n buah himpunan, katakan A1, A2, · · · , An, yang masing-masing

beranggotakan paling banyak n − 1 buah kopi subgraf Ki1,n. Subgraf Ki

1,n pada

himpunan Ak dinotasikan dengan Kki1,n,

b. Pandang himpunan Aj , dengan 1 ≤ j ≤ n. Simpul anting pada setiap kopi

subgraf Kji1,n, pada himpunan Aj , secara berurut diletakkan pada kelas partisi

yang berasosiasi dengan Ti,

c. Simpul pusat setiap kopi subgraf Kki1,n, pada kelompok Ak, diletakkan secara

berurut pada kelas partisi S1, S2, · · · , S|Ak|, dengan 1 ≤ k ≤ n,

d. Simpul xij pada setiap subgraf Kki1,n pada kelompok Ak diletakkan pada kelas

partisi Sk.

e. Simpul akar r diletakkan ke dalam kelas partisi Sn.

Selanjutnya, akan ditunjukkan bahwa Π adalah partisi pembeda dari V (B(m;n)).

Pandang sebarang dua simpul berbeda u, v ∈ V (B(m;n)) sedemikian hingga u, v

dalam kelas patisi yang sama di Π. Jika simpul u dan v, masing-masing, adalah

simpul anting dari Kki1,n dan Kkj

1,n, dengan Kki1,n dan Kkj

1,n masing-masing adalah

subgraf Ki1,n dan Kj

1,n dalam himpunan yang sama Ak , maka u dan v dibedakan

oleh sebuah kelas partisi yang memuat simpul pusat cki atau ckj . Jika simpul u

dan v, masing-masing, adalah simpul anting pada Kki1,n dan K li

1,n, dengan subgraf

Kki1,ndanK

li1,n tidak dalam himpunan yang sama, katakan Ak dan Al, maka u dan

v dibedakan oleh Sk (atau Sl). Jika simpul u adalah simpul anting pada Kki1,n dan

v = xki (atau v = xkj), dengan i 6= j, maka u dan v dibedakan oleh Sn, yaitu kelas

46

partisi yang memuat simpul r. Oleh karena itu, r(u|Π) 6= r(v|Π) dan Π adalah

partisi pembeda untuk V (B(m;n)), dengan n − 2 < m ≤(

nn−1

)(n − 1). (Lihat

Gambar III.12). �

Dimensi partisi graf pohon pisang B(m;n) ditentukan oleh m dan n, yang masing-

masing menyatakan banyak subgraf Ki1,n pada graf B(m;n), dan banyak simpul

anting pada subgraf graf Ki1,n. Dalam hal m ≥

(n

n−1

)(n − 1), dimensi partisi dari

graf B(m;n) masih menjadi masalah terbuka.

47

Bab IV Dimensi Partisi Graf Multipartit

Graf bipartit digunakan dalam beberapa bidang aplikasi, seperti menentukan

jenis pekerjaan yang tepat bagi para pelamar sesuai dengan kualifikasi yang

dimilikinya, dan dalam penjejakan (tracking) sejumlah objek (misalkan kapal selam

dan peluru kendali) yang bergerak dalam suatu selang waktu tertentu) (Gross

dan Yellen, 2004). Dalam Teori Graf, Chartrand, Salehi dan Zhang (2000)

mengkaji graf bipartit untuk mendapatkan dimensi partisinya. Pada Subbab III.1

ini dibahas dimensi partisi graf multipartit dan merupakan perumuman dari hasil

dari Chartrand, Salehi dan Zhang (2000).

Selanjutnya, pada Subbab III.2 dan Subbab III.3 dikaji lebih lanjut dimensi dari graf

bipartit dan tripartit minus sisi matching, berturut-turut.

IV.1 Dimensi partisi graf multipartit lengkap

Suatu graf multipartit adalah sebuah graf yang himpunan simpulnya dapat

dipartisi ke dalam sejumlah subhimpunan simpul sedemikian hingga setiap sisinya

mempunyai simpul ujung pada subhimpunan simpul yang berbeda. Jika graf multi-

partit mempunyai r buah subhimpunan simpul, yaitu V1, V2, · · · , Vr, maka graf

tersebut disebut graf r-partit dan dinotasikan denganG((V1, V2, · · · , Vr), E). Setiap

sisi pada G((V1, V2, · · · , Vr), E) mempunyai simpul ujung di Vi dan Vj , dengan

i 6= j.

Pandang sebarang dua simpul berbeda u ∈ Vi dan v ∈ Vj , dengan 1 ≤ i 6=j ≤ r. Jika simpul u dan v selalu bertetangga maka graf r-partit disebut graf

r-partit lengkap dan disimbolkan dengan Kn1,n2,··· ,nr , dengan n1 = |V1|, n2 =

|V2|, · · · , nr = |Vr|. Sebuah simpul ke- j dalam subhimpunan simpul Vi disim-

bolkan dengan vi,j dengan 1 ≤ i ≤ r dan 1 ≤ j ≤ ni.

Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , St} untuk graf

Kn1,n2,··· ,nr . Untuk setiap subhimpunan simpul Vi didefinisikan sebuah himpunan

berindeks Ii sedemikian hingga j ∈ Ii jika dan hanya jika (Vi ∩ Sj) 6= ∅, dengan

1 ≤ i ≤ r dan 1 ≤ j ≤ t. Jika j ∈ Ii maka j merepresentasikan sebuah

simpul x ∈ Vi dan x ∈ Sj . Gambar IV.1.a adalah graf tripartit K4,4,4 dan Gambar

48

a24

a23

a22

a21

a31 a32 a33 a34

D

D

D

Da11

a12

a13

a14D

D

D

D

D D D D

V1 V2

V3

V1 V2 V3

D D D

D D D

D D D

D D D

S1

S2

S3

S4 S5 S6

(a) (b)

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

IV.1.b contoh partisi graf K4,4,4. Himpunan indeks yang terkait dengan Gambar

IV.1 adalah I1 = {1, 2, 3, 4}, I2 = {1, 2, 3, 5} dan I3 = {1, 2, 3, 4}.

Lema IV.1. ♦ Jika Π adalah sebuah partisi pembeda untuk V (Kn1,n2,··· ,nr),

dimana n1 = n2 = · · · = nr = n, maka terdapat sebuah partisi pembeda Π′

sedemikian hingga:

a. Setiap himpunan berindeks mempunyai sebuah anggota yang termuat dalam

sebuah kelas partisi singleton, dan

b. Kardinalitas dari Π′ sama dengan kardinalitas dari Π.

Bukti. Misalkan Π adalah partisi pembeda sebarang untuk V (Kn1,n2,··· ,nr). Jika

setiap himpunan berindeks Ii, dengan 1 ≤ i ≤ r, telah memuat sebuah

anggota yang termuat ke dalam kelas partisi singleton, maka Π′ = Π. Jika

tidak, maka terdapat sedikitnya satu himpunan berindeks, katakan Ij , yang tidak

mempunyai kelas partisi singleton. Untuk setiap partisi berindeks Ij , tanpa mengu-

rangi keumuman, ambil anggota terakhir dari Ij , misalkan m. Karena Ij tidak

mempunyai kelas partisi singleton, maka setidaknya terdapat sebuah himpunan

berindeks lainnya yang memuat m, katakan Ik, dengan j 6= k. Gantilah m ∈ Ik

dengan sebuah nilai lain, misalkan o, sedemikian hingga o 6= m dan o /∈ Ik .

Prosedur tersebut diulang untuk setiap himpunan berindeks yang tidak mempunyai

kelas partisi singleton sampai terdapat kelas partisi singleton di setiap subhim-

punan simpul V1, V2, · · · , Vr. Partisi pembeda yang diperoleh setelah menjalankan

prosedur tersebut disimbolkan dengan Π′.

Karena kedua nilai m dan o pada prosedur penggantian di atas adalah anggota dari

I1 ∪ I2 ∪ · · · ∪ Ir, maka penggantian itu tidak mengubah banyak indeks dalam

I1 ∪ I2 ∪ · · · ∪ Ir. Karena banyak indeks menyatakan kardinalitas partisi pembeda,

49

maka |Π′| = |Π|.

Setiap simpul v ∈ Kn1,n2,··· ,nr mempunyai representasi terhadap Π′ yang unik,

karena mereka dibedakan oleh kelas partisi singleton. Dengan demikian, Π adalah

partisi pembeda. �

Akibat IV.1 berikut ini merupakan akibat dari Lema II.1.

Akibat IV.1. ♦ Misalkan Π adalah suatu partisi pembeda untuk V (Kn1,n2,··· ,nr)

dengan subhimpunan simpul V1, V2, · · · , Vr. Jika u, v ∈ Vi, dengan 1 ≤ i ≤ r

maka u dan v harus termuat dalam kelas partisi yang berbeda di Π.

Bukti. Misalkan sebarang dua simpul berbeda u, v ∈ Vi, untuk suatu i pada

selang 1 ≤ i ≤ r. Karena jarak d(u,w) = d(v, w) untuk semua simpul

w ∈ V (Kn1,n2,··· ,nr) − {u, v}, maka berdasarkan Lema II.1, simpul u dan v harus

termuat dalam kelas partisi yang berbeda di Π. �

Dimensi partisi graf multipartit lengkap Kn1,n2,··· ,nr ditunjukkan oleh Teorema IV.1

berikut ini:

Teorema IV.1. ♦ Dimensi partisi graf lengkap r-partit Kn1,n2,··· ,nr adalah

pd(Kn1,n2,··· ,nr) =

{n+ r − 1 , jika ni = n untuk 1 ≤ i ≤ r,

n+ r − 2 , jika n = n1 ≥ n2 ≥ · · · > nr.

Bukti. Misalkan terdapat suatu partisi pembeda Π = {S1, S2, · · · , St} untuk

V (Kn1,n2,··· ,nr). Pandang dua kasus berikut:

Kasus 1: ni = n untuk 1 ≤ i ≤ r.

Lema IV.1 memastikan bahwa terdapat sebuah kelas partisi singleton pada setiap

himpunan berindeks. Oleh karena itu, pada setiap subhimpunan simpul Vi, dengan

1 ≤ i ≤ r, terdapat sebuah simpul yang termuat dalam kelas partisi singleton.

Berdasarkan Akibat IV.1, setiap simpul di Vi, dengan 1 ≤ i ≤ r, harus termuat

dalam kelas partisi yang berbeda di Π. Dengan demikian, partisi pembeda Π terdiri

atas r + n− 1 buah kelas partisi. Oleh karena itu, t ≥ r + n− 1.

50

Selanjutnya, definisikan partisi pembeda Π = {S1, S2, · · · , Sr+n−1} untuk

Kn1,n2,··· ,nr sedemikian hingga

Sj =

{{v1,j, v2,j, v3,j, · · · , vr,j} , jika 1 ≤ j ≤ n− 1,

{v(j−n+1),n} , jika n ≤ j ≤ r + n− 1.

Untuk memastikan bahwa Π adalah partisi pembeda, pandang sebarang dua simpul

berbeda u, v ∈ V (Kn1,n2,··· ,nr) sedemikian hingga u dan v dalam kelas partisi yang

sama. Jika u ∈ Vi dan v ∈ Vj , untuk 1 ≤ i 6= j ≤ r, maka d(u,X) = 2

dan d(v,X) = 1, dengan X adalah sebuah kelas partisi singleton yang memuat

satu simpul di Vi atau d(u, Y ) = 1 dan d(v, Y ) = 2, dengan Y adalah sebuah

kelas partisi singleton yang memuat satu simpul di Vj . Oleh karena itu, r(u|Π) 6=r(v|Π). Simpul dalam kelas partisi singleton dengan sendirinya mempunyai repre-

sentasi yang unik. Dengan demikian, Π adalah sebuah partisi pembeda untuk

V (Kn1,n2,··· ,nr).

Kasus 2: n = n1 ≥ n2 ≥ · · · > nr.

Kardinalitas maksimum Vi, dimana 1 ≤ i ≤ r, adalah n. Pandang subhimpunan

simpul V1 dan Vr, dengan kardilatas V1 maksimum dan kardinalitas Vr minimum.

Dengan Lema IV.1, terdapat kelas partisi singleton sebanyak r di Π. Dengan Akibat

IV.1, sisa simpul dalam himpunan berindeks I1 harus didistribusikan ke dalam n−1

buah kelas partisi yang berbeda. Oleh karena itu, partisi pembeda Π terdiri atas

r+n−1 buah kelas partisi. Selanjutnya, dengan mengganti Ir dengan I ′r ⊆ Ij−{c}untuk sebuah j ∈ {1, 2, · · · , r − 1}, dan c adalah anggota yang termuat dalam

sebuah kelas partisi singleton, seluruh simpul diKn1,n2,··· ,nr masih dapat dibedakan.

Dengan demikian, t ≥ (r + n− 1)− 1 = r + n− 2.

Untuk menunjukkan bahwa pd(Kn1,n2,··· ,nr) ≤ r+n−2, definisikan partisi pembeda

Π = {S1, S2, · · · , Sr+n−2} dengan Si = {vi,ni}, untuk i = 1, 2, · · · , r − 1; dan

S(r−1)+j ⊇ {v1,j} untuk j = 1, 2, · · · , n − 1 dan seluruh simpul lainnya dalam

V2∪V3∪ · · · ∪Vn didistribusikan ke dalam S(r−1)+j sedemikian hingga Akibat IV.1

terpenuhi. Dengan demikian, setiap simpul dalam setiap kelas partisi mempunyai

representasi berbeda terhadap Π karena simpul-simpul tersebut dibedakan oleh

kelas partisi singleton. �

51

DDDD

1 2 3 4

D DDD

2 3 41

DDDD

1 2 3 4

D DDD

2 3 41

D D

5 6

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

minus maximum matching

IV.2 Dimensi partisi graf bipartit minus matching

Sebuah graf bipartit lengkap dengan subhimpunan simpul V1 dan V2, dengan |V1| =m dan |V2| = n, disimbolkan dengan Km,n. Dimensi partisi dari graf bipartit telah

ditunjukkan oleh (Chartrand, Salehi dan Zhang, 2000) sebagaimana telah ditun-

jukkan dalam Teorema II.16 dan II.17. Pada subbab ini akan ditunjukkan dimensi

partisi graf bipartit minus sebuah matching.

Sebuah matching dalam grafG adalah subhimpunanM ⊆ E(G) sedemikian hingga

tidak ada dua sisi di M mempunyai titik ujung bersama. Perfect matching, disim-

bolkan dengan Mp adalah sebuah matching sedemikian hingga setiap simpul v ∈V (G) merupakan simpul ujung dari sisi-sisi matching. Matching dengan banyak

sisi terbesar pada sebuah graf G disebut maximum matching dan disimbolkan

dengan Mq. Misalkan V1 = {ai|i = 1, 2, · · · , n} dan V2 = {bi|i = 1, 2, · · · , n}adalah subhimpunan simpul graf bipartit Kn,n. Sebuah perfect matching dari graf

Kn,n adalah himpunan sisiMp sedemikian hinggaM = {aibi|i = 1, 2, · · · , n}. Sisi

putus-putus Gambar IV.2.a menunjukkan sebuah perfect matching Mp pada graf

bipartit K4,4 dan sisi putus-putus Gambar IV.2.b menunjukkan sebuah maximum

matching Mm pada graf bipartit K4,6.

Pandang sebuah graf bipartit minus sebuah perfect matching, yaitu G ∼= Kn,n−M .

Andaikan terdapat suatu partisi pembeda Π untuk V (G). Untuk setiap simpul v ∈V (G), notasi [v] dimaksudkan untuk menyatakan bahwa sebuah kelas partisi di Π

yang memuat simpul v. Dengan demikian, untuk dua simpul sebarang u, v ∈ V (G),

jika [u] = [v] maka simpul u dan v termuat dalam kelas partisi yang sama, katakan

u, v ∈ X dimana X ∈ Π.

Lema IV.2. ♦ Misalkan Kn,n adalah graf bipartit order 2n dengan dua subhim-

52

punan V1 dan V2. Misalkan simpul ai, aj ∈ V1 dan bi, bj ∈ V2, dengan 1 ≤ i 6= j ≤n. Jika [ai] = [aj], dimana 1 ≤ i 6= j ≤ n, maka [bi] 6= [bj].

Bukti. Misalkan [bi] = [bj]. Karena simpul bi dan bj termuat dalam kelas partisi

yang sama, katakan bi, bj ∈ X dengan X ∈ Π, maka d(ai, X) = d(aj, X) = 1.

Lebih jauh, d(ai, Y ) = d(aj, Y ) = 1 untuk semua kelas partisi Y ∈ Π. Dengan

demikian, r(ai|Π) = r(aj|Π), sebuah kontradiksi. �

Lema IV.3. ♦ Misalkan Kn,n adalah graf bipartit order 2n dengan dua subhim-

punan V1 dan V2. Misalkan simpul ai, aj, ak, al ∈ V1 dan bi, bj, bk, bl ∈ V2,

dengan 1 ≤ i 6= j 6= k 6= l ≤ n. Jika [ai] = [aj] dan [ak] = [al], dengan

1 ≤ i 6= j 6= k 6= l ≤ n, maka simpul bi, bj, bk dan bl harus termuat dalam kelas

partisi yang berbeda di Π.

Bukti. Misalkan terdapat sedikitnya dua simpul bi, bj, bk dan bl termuat dalam kelas

partisi yang sama. Tanpa kehilangan keumuman, misalkan [bj] = [bk] = X dengan

X ∈ Π. Oleh karena itu, d(bj, X) = d(bk, X) = 0. Selanjutnya, karena [ai] =

[aj], katakan [ai] = [aj] = Y dengan Y ∈ Π, maka d(bj, Y ) = d(bk, Y ) = 1.

Demikian pula halnya dengan d(bj, Z) = d(bk, Z) untuk sebuah kelas partisi Z di

Π sedemikian hingga X 6= Y 6= Z. Dengan demikian, r(bj|Π) = r(bk|Π), sebuah

kontradiksi. �

Teorema IV.2 berikut ini menunjukkan dimensi partisi sebuah graf bipartit minus

sebuah perfect matching.

Teorema IV.2. ♦ Misalkan Kn,n adalah graf bipartit order 2n dengan dua

subhimpunan V1 dan V2 dan Mp adalah sebuah perfect matching di Kn,n. Maka,

untuk n ≥ 3,

pd(Kn,n −Mp) =

{bn

2c+ 2 , jika n gasal,

bn2c+ 1 , jika n genap.

Bukti. Misalkan terdapat suatu partisi pembeda Π = {S1, S2,· · · , Sk} untuk

V (Kn,n −Mp) sedemikian hingga:

53

Untuk n gasal:

Sk =

{a1, a2, · · · , adn

2e} , jika k = 1,

{bdn2e, bdn

2e+1, · · · , bn} , jika k = 2,

{adn2e+k−2, bk−2} , jika 3 ≤ k ≤ bn

2c+ 2.

Untuk n genap:

Sk =

{a1, a2, · · · , an

2, bn

2, bn

2+1, · · · , bn} , jika k = 1,

{an} , jika k = 2,

{an2+k−2, bk−2} , jika 3 ≤ k ≤ bn

2c+ 1.

Untuk memastikan bahwa Π adalah partisi pembeda, pandang sebarang dua simpul

berbeda u, v ∈ V (Kn,n − Mp) sedemikian hingga u, v dalam kelas partisi yang

sama. Tinjau dua kasus berikut:

Kasus 1: n gasal

Jika u = ai dan v = aj sedemikian hingga u, v ∈ S1 maka u dan v dibedakan oleh

[bi] dan [bj]. Demikian pula jika u = bi dan v = bj sedemikian hingga u, v ∈ S2

maka u dan v dibedakan oleh [ai] dan [aj]. Selanjutnya, jika u = ai dan v = bj

sedemikian hingga u, v ∈ Sq, dimana 3 ≤ q ≤ bn2c+2 maka u dan v dibedakan oleh

S1 dan S2. Oleh karena itu, untuk setiap v ∈ V (Kn,n −Mp), simpul v mempunyai

representasi unik.

Kasus 2: n genap

Pandang sebarang dua simpul berbeda u dan v sedemikian hingga u, v ∈ S1. Jika

u = ai dan v = aj (atau u = bi dan v = bj) maka u dan v dibedakan oleh [bi] dan

[bj] atau [ai] dan [aj]. Jika u = ai dan v = bj maka u dan v dibedakan oleh kelas

partisi S2. Kelas partisi S2 adalah kelas partisi singleton, dengan demikian simpul

yang termuat dalam S2 mempunyai representasi yang unik. Selanjutnya, jika u = ai

dan v = bj sedemikian hingga u, v ∈ Sq, dimana 3 ≤ q ≤ bn2c + 1, maka u dan v

dibedakan oleh S2. Oleh karena itu, untuk setiap dua simpul u, v ∈ V (Kn,n−Mp),

maka r(u|Π) 6= r(u|Π).

Dengan demikian, pd(Kn,n −Mp) ≤ bn2c+ c, dengan c = 2 jika n gasal dan c = 1

jika n genap.

54

Selanjutnya, untuk menunjukkan batas bawah dimensi partisi untuk graf Kn,n −Mp, misalkan Π = {S1, S2, · · · , Sr} suatu partisi pembeda dari V (Kn,n − Mp).

Definisikan A1 = {S ∈ Π : |S ∩ V1| = 1} dan A2 = {S ∈ Π : |S ∩ V1| > 1}.Karena setiap simpul v ∈ V1 harus termuat dalam sebuah kelas partisi, maka simpul

v termuat dalam A1 atau A2. Sekarang, pandang tiga kasus berikut:

Kasus 1: |A1| ≥ bn2c+ 1

Jika n genap maka |Π| ≥ |A1| = bn2c + 1 dan oleh karena itu, Kasus 1 terpenuhi.

Sekarang, pandang n gasal untuk n ≥ 5. Maka, A2 harus mempunyai paling sedikit

satu anggota yang berbeda dengan seluruh anggota A1. Oleh karena itu, ketika

digabung dengan seluruh kelas partisi di A1 diperoleh |Π| ≥ |A1| + 1 = bn2c + 2.

Jika n = 3 maka |A1| haruslah bernilai tiga. Oleh karena itu, dalam kasus ini juga

diperoleh |Π| ≥ bn2c+ 2.

Kasus 2: |A1| = bn2c

Karena A2 mempunyai paling sedikit satu anggota, maka untuk kasus dengan n

genap diperoleh |Π| ≥ |A1|+|A2| = bn2c+1 dan, oleh karena itu, Kasus 2 terpenuhi.

Sekarang, misalkan n adalah sebuah bilangan gasal dan [a1], [a2], · · · , [abn2c]

anggota dari A1. Jika A2 mempunyai dua anggota maka |Π| ≥ bn2c + 2 dan,

oleh karena itu, Kasus 2 terpenuhi. Asumsikan A2 mempunyai satu anggota, dan

misalkan T ∈ A2. Perhatikan bahwa T = [abn2c+1] = {abn

2c+1, abn

2c+2, · · · , an}.

Sekarang, kami menunjukkan bahwa himpunan yang membentuk Π bukan hanya T

dan himpunan di A1. Asumsikan Π = A1 ∪ {T}. Misalkan K1 = {1, 2, · · · , bn2c}

dan K2 = {bn2c + 1, bn

2c + 2, · · · , n}. Berdasarkan Lema IV.2, [bi] 6= [bj]

untuk sebarang i, j ∈ K2 yang berbeda. Oleh karena itu, terdapat suatu bijeksi

f : K2 → K1 ∪ {bn2c + 1} sedemikian hingga [bx] = [af(x)] untuk setiap x ∈ K2.

Hal ini berarti terdapat satu simpul bj0 , untuk suatu j0 ∈ K2, yang harus termuat

dalam kelas partisi T . Oleh karena itu, r(bj0|Π) = r(aj0|Π), suatau kontradiksi,

karena terdapat dua simpul berjarak 1 ke seluruh himpunan kelas partisi yang lain

di Π. Dengan demikian, pd(G) ≥ bn2c+ c, dengan c = 2 jika n gasal dan c = 1 jika

n genap.

Kasus 3: 1 ≤ |A1| ≤ bn2c − 1

Banyaknya simpul yang tidak termuat dalam A1 paling sedikit sebesar bn2c + c,

dengan c = 2 jika n gasal dan c = 1 jika n genap. Simpul-simpul ini membentuk

kelas partisi tidak singleton ( di A2). Oleh karena itu, berdasarkan Lemma IV.3,

simpul yang bersesuaian di V2 haruslah termuat dalam kelas partisi yang berbeda.

55

Oleh karena itu, |Π| ≥ bn2c + c, dengan c = 2 jika n gasal dan c = 1 jika n

genap. �

Untuk n = 1 dan n = 2, graf Kn,n − Mp, yaitu graf K1,1 − Mp dan K2,2 −Mp merupakan graf tak terhubung. Dengan demikian, dimensi partisi kedua graf

tersebut tidak didefinisikan.

Sekarang, pandang sebuah graf bipartit Km,n, dengan m > n. Karena setiap sisi

pada Km,n mempunyai satu simpul ujung di ai ∈ V1 dan simpul ujung lainnya di

bj ∈ V2 untuk suatu i dan j pada selang tertutup 1 ≤ i ≤ m dan 1 ≤ j ≤ n, maka

maksimum matching Mq di Km,n mempunyai kardinalitas n. Tanpa kehilangan

keumuman, misalkan Mq = {aibi|ai ∈ V1, bi ∈ V2 dan 1 ≤ i ≤ n}.

Akibat IV.2 berikut ini merupakan akibat dari Lema II.1.

Akibat IV.2. ♦ Misalkan Π adalah suatu partisi pembeda untuk V (Km,n −Mq)

dengan kardinalitas subhimpunan simpul |V1| = m dan |V2| = n. Jika ai, aj ∈ V1,

dengan n+1 ≤ i 6= j ≤ m, maka ai dan aj harus termuat dalam kelas partisi yang

berbeda di Π.

Bukti. Misalkan ai, aj ∈ V1 sedemikian hingga n + 1 ≤ i 6= j ≤ m.

Karena d(ai, w) = d(aj, w) untuk semua simpul w ∈ V (Km,n) − {ai, aj}, maka

berdasarkan Lema II.1, simpul ai dan aj harus termuat dalam k

graf theory

Documents