Dimensi Partisi Dari Suatu Graf

Konsep dimensi partisi dari suatu graf, pertama kali diperkenalkan oleh Chartrand dkk pada tahun 1998, konsep ini merupakan bentuk lain dari konsep dimensi metrik yang sebelumnya sudah diperkenalkan oleh Slater (1975) dan Melter dkk (1976).
Misalkan G(V,E) adalah graf sederhana dengan V merupakan himpunan titik dan E merupakan himpunan sisi.
Misalkan Π={S_1,S_2,…,S_k} merupakan partisi terurut dari V(G) dan vϵV(G). Representasi dari vϵV(G) terhadap Π didefinisikan dengan pasangan k-terurut (d(v,S_1),d(v,S_2),…,〖d(v,S〗_k)). Misalkan Π={S_1,S_2,…,S_k} adalah partisi terurut dari V (G). Jika uϵS_i dan vϵS_j, dan i≠j, maka jelas bahwa r(v_i |Π)≠r(v_j |Π).
Selanjutnya, diberikan sebuah partisi Π dari V(G). Jika kita menentukan apakah Π adalah partisi pembeda untuk V(G) atau bukan, maka pemeriksaan cukup dilakukan pada semua titik yang termasuk dalam suatu kelas partisi yang sama. Jika semua titik dalam setiap kelas partisi yang sama mempunyai representasi berbeda terhadap Π, maka Π merupakan partisi pembeda. Sebuah kelas partisi yang mempunyai satu anggota disebut kelas partisi singleton. Titik dalam kelas partisi singleton mempunyai representasi yang unik.
Pada contoh berikut, Gambar (a) menunjukkan bahwa Π_1={S_1,S_2} dengan S_1={v_1} dan S_2={v_i} dengan i=2, 3, 4 adalah partisi pembeda dari V (P_4). Oleh karena itu pd(P_4) = 2. Selanjutnya Gambar (b) menunjukkan Π_1={S_1,S_2,…,S_5} dengan S_i={v_i} g dengan i=1,2,..,5 merupakan partisi pembeda dari V (K5), jadi pd(K_5) ≤5. Kemudian, untuk menunjukkan pd(K_5)≥5, andaikan terdapat partisi pembeda dari V (K_5) dan |Π|=4 . Maka setidaknya terdapat dua titik u,v∈V(K_5) sehingga termuat dalam kelas partisi yang sama. Oleh karena d(u,w) = d(v,w) untuk semua w∈V(K_5 )-{u,v}, maka r(u|W) = r(v|W), kontradiksi dengan pemisalan sebagai partisi pembeda, jadi, |Π|≥5. Oleh karena itu pd(K_5 )=5.

Iklan
Pos ini dipublikasikan di Tak Berkategori. Tandai permalink.

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s