Presentasi Matsim

Diagram Poset

( Partially Ordered Set )

Disusun oleh :

Nama : Fdlilatul Qodriah

Firman Disasatra

M.Rafiyudin

Kelas : 2ka10

Materi : Diagram Poset ( Matematika Sistem Informasi )

Fakultas Ilkom ( Sistem Informasi)

Universitas Gunadarma

2009 / 2010

POSET (Partially Ordered Set)

Himpunan Terurut Parsial

Sebelum melanjutkan pembahasan tentang diagram poset,sebaiknya kita tahu dulu tentang apa itu poset (himpunan terurut secara parsial.Dikatakan poset yaitu jika suatu relasi R pada himpunan P urut secara parsial pada P, jika R tersebut bersifat reflexive (mementul),antisymmertic(tolak setangkup),dan transitive (menghantar)

1. Reflexive dengan syarat a R a untuk setiap a є P.

2. Antisymmetric dengan syarat a R b dan b R a maka a = b.

3. Transitive dengan syarat a R b dan b R c maka a R c

Dalam suatu relasi R pengurutan parsial,dua benda saling berhubungan.Jika salah satunya lebih kecil (<) atau lebih besar (>) daripada atau lebih pendek (lebih tinggi) daripada lainnya menurut sifat atau kriteria tertentu.Istilah pengurutan (ordering) berarti bahwa benda-benda didalam himpunan itu diurutkan menurut kriteria atau sifat tersebut.Akan tetepi ada kemungkinan bahwa dua benda dalam himpunan tersebut tidak ada hubungan dalam relasi pengurutan parsial.Dalam hal demikian,kita tidak dapat membedakan keduanya dan tidak dapat mengidentifikasi mana yang lebih kecil atau mana yang lebih rendah. Itulah alasan digunakan istilah “pengurutan parsial (partial ordering)” atau bisa disebut dengan Poset yang dilambangkan dengan (A,R).

Pengurutan parsial yang paling sering digunakan adalah relasi ≤ atau ≥ pada himpunan A dan R.Karena jika kita berbicara secara umum tentang pengurutan parsial R pada himpuna P maka yang akan sering kita lihat atau sering kita gunakan adalah symbol ≥ dan ≤.

Pada subab ini akan dijelaskan tentang diagram poset.Pendefinisian tentang diagram poset ini adalah sebuah grafik berarah yang vertex-verteksny adalah elemen-elemen dari S dan terdapat sebuah edge (titik atau bulatan) dari a ke b kapan saja a < b dalam S.Karena menggambarkan panah dari a ke b,kita seringkali menempatkan b lebih tinggi dari a dan menggambarkan sebuah garis di antara mereka.Ini kemudian diartikan bahwa pergerakan maju (ke atas) menyatakan succession (rangkaian).Dalam diagram yang dibuat,ada sebuah path (gris edar) berarah dari sebuah verteks (puncak) ke verteks y jika dan hanya jika x < y.Juga,mungkin tidak ada cycle (putaran) berarah dalam diagram S karena relasi urutannya antisimetris.Perhatikan juga bahwa diagram tidak harus terhubung. Misal (P,≤) adlah sebuah poset.Jika P hingga,maka (P,≤) dapat dinyatakan dalam bentuk diagram hasse yang tiap elemen diwakili oleh sebuah bulatan kecil atau titik.

Jika x < y,maka lingkaran x є P digambar dibawah lingakran yang mewakili y є P.Contoh :

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.

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 :

<!–[if mso & !supportInlineShapes & supportFields]> <![endif]–>

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 ).

<!–[if mso & !supportInlineShapes & supportFields]> <![endif]–>

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 :

<!–[if mso & !supportInlineShapes & supportFields]> <![endif]–>

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:

<!–[if mso & !supportInlineShapes & supportFields]> <![endif]–>

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 membuat diagram 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 :

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

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.

v 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

a) Gambar diagram hasse dari (X,≤)

b) Cari batas atas dari (2,3)

c) Cari batas bawah dari (24,36)

Jawab :

a) Diagram hasse untuk (X,≤)

 

<!–[if mso & !supportInlineShapes & supportFields]> <![endif]–>

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

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

v 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,≤)

<!–[if mso & !supportInlineShapes & supportFields]> <![endif]–>

b) 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 = a * b

Sumber :

· POSET by Muhammad Win Afgani

· Matematika diskrit by ZK Abdurahman Baizal Sekolah Tinggi Teknologi Telkom

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: