Dimensi Metrik Graf Bintang

Untuk graf bintang (Sn) dengan jumlah titik = n+1, maka namai kembali titik tsb dengan u0,u1,u2,..,un dengan u sebagai pusatnya sehingga u1,u2,...,un masing2 terhubung dengan u0.

Akan dibuktikan bahwa dim(Sn) = n-1

Karena graf bintang bukan graf path, maka 1<dim(Sn)<=|W|

Andaikan dim(Sn)≠n-1, maka ada 2 kemungkinan yaitu dim(Sn)<n-1 atau dim(Sn)>n-1

(i)                 Untuk dim(Sn)<n-1

Misalkan V(Sn)={ui | i=0,1,2,..,n}

Untuk W={uj | j=0,1,2,..,n-2} maka :

r(u0|w) = (0,1,1,...,1)

r(u1|w) = (1,0,2,2,..,2)

r(u2|w) = (1,2,0,2,..,2)

r(u(n-2)|w) = (1,2,2,..,0)

r(u(n-1)|w) = (1,2,2,..,2)

r(un|w) = (1,2,2,..,2)

karena ada 2 titik yang punya representasi yang sama, sehingga W tidak dapat dikatakan himpunan pembeda.

Untuk W={uj | j=1,2,..,n-2} maka :

r(u0|w) = (1,1,..,1)

r(u1|w) = (0,2,2,..,2)

r(u2|w) = (2,0,2,..,2)

r(u(n-2)|w) = (2,2,2,..,0)

r(u(n-1)|w) = (2,2,2,..,2)

r(un|w) = (2,2,2,..,2)

karena ada 2 titik yang punya representasi yang sama, sehingga W tidak dapat dikatakan himpunan pembeda.

Jadi, untuk dim(Sn)<n-1 terdapat setidaknya 2 titik yang mempunyai representasi yang sama sehingga tidak didapatkan himpunan pembeda dengan |W|<n-1

(ii)               Untuk dim(Sn)>n-1

Karena |V(Sn)|=n+1, maka hanya ada 2 kemungkinan yaitu dim(Sn)=n+1 atau dim(Sn)=n

Akan dicari dim(Sn) yang paling minimal.

Untuk dim(Sn)=n+1

Misalkan W1={uj – u0 | j=0,1,2,..,n} = {uk|k=1,2,..,n}, apakah W1 merupakan himpunan pembeda?

r(u0|w) = (1,1,..,1)

r(u1|w) = (0,2,2,..,2)

r(u2|w) = (2,0,2,..,2)

r(u(n-2)|w) = (2,2,2,..,0,2,2)

r(u(n-1)|w) = (2,2,2,..,0,2)

r(un|w) = (2,2,2,..,0)

karena semua representasinya berbeda, maka W1 adalah himpunan pembeda dengan|W1|=n

Untuk dim(Sn) = n

Misalkan W2={W1 – u1} = {um|m=2,3,..,n}, apakah W2 merupakan himpunan pembeda?

r(u0|w) = (1,1,..,1)

r(u1|w) = (2,2,..,2)

r(u2|w) = (0,2,..,2)

r(u(n-2)|w) = (2,2,..,0,2,2)

r(u(n-1)|w) = (2,2,..,0,2)

r(un|w) = (2,2,..,0)

karena semua representasinya berbeda, maka W2 adalah himpunan pembeda dengan|W2|=n-1

KESIMPULAN: karena untuk setiap W pada dim(Sn)<n-1 bukan himpunan pembeda, maka jelas bahwa W2 merupakan himpunan pembeda yang paling minimal, sehingga dapat disimpulakn bahwa dim(Sn)=n-1