Contoh Soal Dan Pembahasan Himpunan Urut Parsial

1. Jika a,b є P, a ≤ b, a = b dan tak ada anggota lain c sedemikian hingga a ≤ b ≤ c maka relasi a ≤ b dinyatakan dengan rantai langsung dengan posisi b diatas a.

gmbr himpunan urut parsial

2. A = {1,2,3,4} dan ≤ didefinisikan sebagai relasi “lebih kecil ata sama dengan”.Dapat diperiksa bahwa ( A , ≤ ) merupakan sebuah rantai.

Diagram hasse untuk ( P,≤ ) adalah :

gmbr soal himpunan urut parsial 2

Dari diagram diatas dapat disimpulkan bahwa A sebuah himpunan dengan relasi ≤,dan merupakan poset (himpunan terurut secara pasial.Karena A “lebih kecil atau sama dengan” maka diurutkan dari 1 sampai 4 dengan arah ke atas,dan karena garis panah telah diasumsikan ke atas maka tanda panah kita hapus dan diganti dengan bulatan-bulatan saja.

3. Misal didefinisikan sebuah parsial order R ={ (a,b)| a ≤ b } pada himpunan { 1 , 2 , 3 , 4 } kita dapat membuat representasinya dalam bentuk graf berarah sebagai berikut (dalam hal ini , arah panah selalu ke atas ).

cntoh gmbr soal himpunan urut parsial 3

Pada gambar diatas,karena sifat parsial order (poset) reflexive (mementul),maka kita tidak perlu menunjukan loop untuk masing-masing simpul.Sehingga diagram akan berubah menjadi seperti dibawah ini :

cnth soal 4 himpunan urut parsial

Kemudian karena partial order (poset) bersifat transitive (menghantar),maka kita tidak perlu menunjukan edge (garis tepi) yang harus disajikan karena ke-transitive-an dari partial order tersebut,sehingga garis tepi pada ( 1,3 ),( 1,4 ),( 2,4 ) dihapus dan diagram akan menjadi seperti berikut:

garis hmpunan urut parsial

Jadi jika kita telah mengasumsikan bahwa semua sisi mengarah ke atas,maka kita tidak perlu lagi menunjukan arah sisi.Dengan demikian diagram yang dihasilkan adalah diagram yang berisi informasi yang cukup untuk memenuhi partial order yang kemudian disebut dengan Diagram Hasse.

Untuk lebihjelasnya berikut adalah langkah-langkah membuatdiagram hasse :

  1. Hapus loop untuk masing-masing simpul
  2. Hapus semua sisi yang harus disajikan karena sifat poset yang ke-transitive-an. Contoh jika ada (a,b) dan (b,c),maka hapus sisi (a,c).Jika ternyata ada (c,d) maka hapus sisi (a,d).
  3. Atur masing-masing sisi,hingga simpul awalnya (initial vertex-nya ) berada dibawah simpul terminal (terminal vertex) .Dengan kata lain,buat agar tanda panahnya mengarah ke atas.
  4. Langkah terakhir adalah hapus semua panahnya sehingga hanya akan ada bulatan kecil saja.

Selain itu ada juga diagram untuk urutan invers.Diagram ini adalah diagram awal yang edge-edgenya dibalik.Contohnya yaitu :

Misal terdapat himpunan D = {1,2,3,4,5} yang terurut secara linear yang diurutkan seperti gambar dibawah ini :

foto diagram urut parsial

Dari beberapa contoh diatas,dapat kita ambil kesimpulan bahwa diagram poset adalah diagram dengan elemen-elemen dari suatu himpunan dengan relasi R yang mempunyai syarat reflexive,transitive,dan antisymmetrice yang terurut parsial (poset) dengan kriteria dan sifat tertentu,serta mempunyai arah yang kemudian dapat digambarkan dengan bulatan atau titik.

– Contoh Diagram poset dengan batas atas dan batas bawah .

Misalkan X = { 2,3,6,12,24,36 }.Didefinisikan dengan X ≤ Y sebagai Y habis dibagi X,maka tentukan

  1. a)Gambar diagram hasse dari (X,≤)
  2. b)Cari batas atas dari (2,3)
  3. c)Cari batas bawah dari (24,36)

Pembahasan:

a)Diagram hasse untuk (X,≤)

jwbn diagram urut parsial

Batas atas dari (2,3) adalah 6,12,24,36 .

c) Batas bawah dari (24,36) adalah 12,6,3,2 .

– Contoh diagram poset dengan penentuan batas atas terkecil (supremum) dan batas bawah terbesar (infimum ) .

Misalkan X = { 2,5,10,20,40,100 }.Definisikan X ≤ Y sebagai Y habis di bagi X ,maka tentukan:

a)Diagram hasse untuk (X , ≤)

b)Tentukan batas atas dari (2,5)

c)Tentukan batas bawah dari (40,100)

d)Tentukan supremum dari (2,5)

e)Tentukan infimum dari (40,100)

Jawab :

a)a)  Diagram hasse untuk (X,≤)

jwbn diagram urut parsial 2

b) Batas atas dari (2,5) adalah 10,20,40,100

c)c) Batas bawah dari (40,100) adalah 20,10,5,2

d)d) Supremum dari (2,5) adalah 10

e)e) Infimum dari (40,100) adalah 20

– Jadi jika ada c є P sehingga c batasa atas dari (a,b) dan untuk setiap batas d dari (a,b) berlaku c ≤ d,maka c adalah batas atas terkecil (supremum) dari (a,b) ,dilambangkan dengan C = a O b

– Sebaliknya jika ada p є P sehingga p batas bawah dari (a,b) dan untuk setiap batas q dari (a,b) berlaku q ≤ p,maka q dinamakan batas bawah terbesar (infimum) dan dilambangkan P

Leave a Comment