Lewati ke konten utama

Latihan 6.10 Latihan

1.

Kita mengatakan bahwa suatu relasi \(R\) pada himpunan \(X\) bersifat simetris jika \((x,y)\in R\) mengakibatkan \((y,x)\in R\) untuk setiap \(x,y\in X\text{.}\) Jika \(X=\{a,b,c,d,e,f\}\text{,}\) ada berapa relasi simetris pada \(X\text{?}\) Berapa banyak di antaranya yang refleksif?

2.

Suatu relasi \(R\) pada himpunan \(X\) merupakan relasi ekuivalensi jika \(R\) bersifat refleksif, simetris, dan transitif. Tetapkan suatu bilangan bulat \(m\geq 2\text{.}\) Tunjukkan bahwa relasi pada himpunan bilangan bulat \(\ints\) yang didefinisikan oleh \(aRb\) (\(a,b\in\ints\)) jika dan hanya jika \(a\equiv b\pmod{m}\) merupakan relasi ekuivalensi. (Ingat bahwa \(a\equiv b\pmod{m}\) berarti bahwa pembagian \(a\) oleh \(m\) dan pembagian \(b\) oleh \(m\) menghasilkan sisa yang sama.)

3.

Apakah relasi biner
\begin{equation*} P=\{(1,1),(2,2),(3,3),(4,4),(1,3),(2,4),(2,5),(4,5),(3,5),(1,5)\} \end{equation*}
merupakan urutan parsial pada himpunan \(X=\{1,2,3,4,5\}\text{?}\) Jika ya, bahas sifat-sifat yang Anda periksa dan cara memeriksanya. Jika tidak, daftarkan pasangan terurut yang harus ditambahkan ke \(P\) agar relasi itu menjadi urutan parsial, atau jelaskan mengapa relasi tersebut tidak dapat dijadikan urutan parsial dengan menambahkan pasangan terurut.

4.

Gambarkan diagram poset \(\bfP=(X,P)\) dengan \(X=\{1,2,3,5,6,10,15,30\}\) dan \(x\leq y\) dalam \(P\) jika dan hanya jika \(x|y\text{.}\) (Ingat bahwa \(x|y\) berarti \(x\) membagi \(y\) secara habis tanpa sisa. Dengan kata lain, \(x|y\) jika dan hanya jika \(y\equiv 0\pmod{x}\text{.}\))

5.

Gambarkan diagram poset \(\PXP\) dengan
\begin{equation*} X=\{\{1,3,4,5,6\},\{1,2,4,5,6\},\{1,2,3,6\},\{1,2,3\},\{1,5,6\},\\\{1,3,6\},\{1,2\},\{1,6\},\{3,5\},\{1\},\{3\},\{4\}\} \end{equation*}
dan \(P\) merupakan urutan parsial pada \(X\) yang diberikan oleh relasi “merupakan subhimpunan dari”.

6.

Suatu perluasan linear dari poset \(\bfP=(X,P)\) adalah urutan total \(L\) pada \(X\) sedemikian sehingga jika \(x\leq y\) dalam \(P\text{,}\) maka \(x\leq y\) dalam \(L\text{.}\) Berikan satu perluasan linear untuk masing-masing dari tiga poset yang ditampilkan dalam Gambar 6.8. Jika Anda merasa sangat tertantang, cobalah menghitung banyaknya perluasan linear dari poset di sisi kiri gambar. Jangan daftarkan semuanya; cukup berikan sebuah bilangan bulat sebagai jawaban Anda.

7.

Alice dan Bob sedang meninjau poset \(\bfP\) dan \(\bfQ\text{.}\) Mereka segera menyadari bahwa \(\bfQ\) isomorfik dengan \(\bfP^d\text{.}\) Setelah bekerja selama \(10\) menit, mereka menemukan bahwa \(\bfP\) memiliki tinggi \(5\) dan lebar \(3\text{.}\) Bob tidak ingin mencari tinggi dan lebar \(\bfQ\) karena ia memperkirakan bahwa diperlukan (setidaknya) \(10\) menit lagi untuk menjawab pertanyaan-pertanyaan tentang \(\bfQ\text{.}\) Alice mengatakan bahwa Bob keliru dan bahwa ia sudah mengetahui tinggi dan lebar \(\bfQ\text{.}\) Siapa yang benar, dan mengapa?

8.

Untuk latihan ini, perhatikan poset \(\bfP\) dalam Gambar 6.5.
  1. Daftarkan elemen-elemen maksimal \(\bfP\text{.}\)
  2. Daftarkan elemen-elemen minimal \(\bfP\text{.}\)
  3. Temukan suatu rantai maksimal berisi dua titik dalam \(\bfP\text{.}\)
  4. Temukan suatu rantai dalam \(\bfP\) yang berisi tiga titik tetapi bukan rantai maksimal. Jelaskan mengapa rantai Anda tidak maksimal.
  5. Temukan suatu antirantai maksimal berisi empat titik dalam \(\bfP\text{.}\)

9.

Tentukan tinggi \(h\) dari poset \(\PXP\) yang ditampilkan di bawah, beserta suatu rantai maksimum dan suatu partisi \(X\) menjadi \(h\) antirantai dengan menggunakan algoritme dari bab ini.
dijelaskan secara terperinci setelah gambar
Diagram urutan suatu poset dengan 26 titik berlabel 1 sampai 26. Pasangan relasi penutup (titik bawah–titik atas) ialah 22–3, 3–4, 4–5, 5–20, 20–9, 9–7, 7–26, 26–15, 18–2, 2–25, 25–9, 25–8, 21–8, 18–21, 8–15, 23–4, 13–20, 23–13, 6–1, 6–14, 11–14, 12–11, 23–11, 26–14, 20–6, 11–1, 22–13, 23–17, 17–5, 10–14, 13–10, 24–9, 4–24, 2–24, 16–6, dan 16–7.

10.

Untuk masing-masing dari dua poset yang berbeda hingga isomorfisme dalam Gambar 6.8, tentukan lebarnya \(w\text{,}\) suatu antirantai berukuran \(w\text{,}\) dan suatu partisi himpunan dasarnya menjadi \(w\) rantai.

11.

Seorang koki restoran telah merancang sekumpulan hidangan baru untuk menunya. Kumpulan itu memuat \(10\) hidangan utama, dan setiap malam ia akan memilih suatu subhimpunan hidangan untuk disajikan pada menu. Demi menjamin keragaman hidangan utama bagi para pelanggan, ia ingin memastikan bahwa menu suatu malam tidak seluruhnya termuat dalam menu malam lain dan juga tidak seluruhnya memuat menu malam lain. Berapa banyak menu paling banyak yang dapat ia rencanakan dengan \(10\) hidangan utama tersebut dengan memenuhi syarat ini?

12.

Gambarkan diagram urutan interval yang direpresentasikan dalam Gambar 6.34.
dijelaskan secara terperinci setelah gambar
Representasi interval pada sembilan elemen berlabel c sampai k. Pasangan relasi penutup (elemen bawah–elemen atas) yang ditentukan oleh interval ialah d–i, d–k, e–c, e–h, e–k, f–i, f–k, i–c, i–h, c–j, h–g, h–j, dan k–j.
Gambar 6.34. Suatu representasi interval

13.

Gambarkan diagram urutan interval yang direpresentasikan dalam Gambar 6.35.
dijelaskan secara terperinci setelah gambar
Representasi interval pada empat belas elemen berlabel c sampai p. Pasangan relasi penutup (elemen bawah–elemen atas) yang ditentukan oleh interval ialah k–l, k–d, k–h, e–m, e–o, e–n, f–e, f–l, f–c, f–h, l–i, l–j, l–p, i–m, i–o, i–n, d–e, d–c, d–p, c–i, c–j, j–o, j–n, h–i, h–j, h–p, p–o, p–n, dan n–g.
Gambar 6.35. Suatu representasi interval

14.

Temukan suatu representasi interval untuk poset dalam Gambar 6.36, atau berikan alasan mengapa representasi semacam itu tidak ada.
dijelaskan secara terperinci setelah gambar
Diagram urutan suatu poset pada delapan titik berlabel 1 sampai 8. Pasangan relasi penutup (titik bawah–titik atas) ialah 1–2, 1–5, 1–6, 1–3, 8–3, 8–2, 5–7, 2–7, 2–4, 5–4, dan 3–4.
Gambar 6.36. Apakah poset ini merupakan urutan interval?

15.

Temukan suatu representasi interval untuk poset dalam Gambar 6.37, atau berikan alasan mengapa representasi semacam itu tidak ada.
dijelaskan secara terperinci setelah gambar
Diagram urutan suatu poset pada sembilan titik berlabel 1 sampai 9. Pasangan relasi penutup (titik bawah–titik atas) ialah 6–1, 6–3, 1–7, 7–5, 2–5, 3–2, 8–2, 1–2, 9–3, 4–8, dan 4–9. Subposet pada titik 1, 3, 4, dan 7 membentuk dua rantai yang saling tidak dapat dibandingkan, yaitu 1–7 dan 4–3.
Gambar 6.37. Apakah poset ini merupakan urutan interval?

16.

Temukan suatu representasi interval untuk poset dalam Gambar 6.38, atau berikan alasan mengapa representasi semacam itu tidak ada.
dijelaskan secara terperinci setelah gambar
Diagram urutan suatu poset pada dua belas titik berlabel 1 sampai 12. Pasangan relasi penutup (titik bawah–titik atas) ialah 7–2, 2–12, 2–5, 2–1, 2–10, 4–10, 5–8, 1–8, 10–8, 12–8, 10–3, 10–6, 1–6, 8–11, 6–11, 8–9, dan 6–9.
Gambar 6.38. Apakah poset ini merupakan urutan interval?

17.

Temukan suatu representasi interval untuk poset dalam Gambar 6.39, atau berikan alasan mengapa representasi semacam itu tidak ada.
dijelaskan secara terperinci setelah gambar
Diagram urutan suatu poset pada empat belas titik berlabel 1 sampai 14. Pasangan relasi penutup (titik bawah–titik atas) ialah 13–10, 13–1, 13–12, 1–8, 12–8, 10–7, 11–7, 11–4, 10–6, 6–9, 6–2, 7–2, 2–5, 8–5, 4–5, 4–14, 14–3, dan 2–3.
Gambar 6.39. Apakah poset ini merupakan urutan interval?

18.

Gunakan algoritme First Fit (dengan mengurutkan interval menurut titik ujung kirinya) untuk menentukan lebar \(w\) dari urutan interval yang ditampilkan dalam Gambar 6.40 dan suatu partisi menjadi \(w\) rantai. Berikan pula suatu antirantai berisi \(w\) titik.
dijelaskan secara terperinci setelah gambar
Representasi lima belas interval berlabel a sampai o. Dalam satuan horizontal gambar, titik ujungnya adalah f=[9.137,54.172], b=[27.137,99.043], g=[39.488,90.070], d=[71.930,144.344], h=[106.062,122.977], n=[111.305,174.637], c=[130.848,152.863], j=[153.086,249.473], l=[161.664,207.164], a=[188.359,278.531], e=[225.211,261.863], k=[255.883,315.223], m=[270.410,293.059], i=[288.359,310.375], dan o=[297.516,319.531].
Gambar 6.40. Suatu representasi interval

19.

Lengkapi pembuktian Teorema 6.30.
Petunjuk.
Gagasan utamanya ialah menunjukkan bahwa jika \(d\) merupakan bilangan bulat positif terkecil yang memungkinkan suatu urutan interval \(\bfP\) memiliki representasi dengan titik-titik ujung dari \(\{1,2,\dots,d\}\text{,}\) maka setiap bilangan bulat \(i\) dalam himpunan ini harus sekaligus menjadi titik ujung kiri suatu interval dan titik ujung kanan suatu interval.

20.

Tunjukkan bahwa setiap poset isomorfik dengan suatu poset dari masing-masing empat jenis yang diilustrasikan dalam Contoh 6.7.
Petunjuk.
Untuk setiap elemen \(x\text{,}\) pilih suatu kunci identifikasi unik berupa elemen/bilangan prima/koordinat/pengamat. Kemudian kaitkan \(x\) dengan suatu struktur yang mengidentifikasi kunci-kunci elemen dalam \(D[x]\text{.}\)

21.

Dimensi suatu poset \(\PXP\text{,}\) yang dilambangkan dengan \(\dim(\bfP)\text{,}\) adalah nilai \(t\) terkecil sedemikian sehingga \(P\) merupakan irisan dari \(t\) urutan linear pada \(X\text{.}\)
  1. Tunjukkan bahwa dimensi suatu poset \(\bfP\) sama dengan dimensi dualnya.
  2. Tunjukkan bahwa jika \(\bfP\) merupakan subposet dari \(\bfQ\text{,}\) maka \(\dim(\bfP)\le \dim(\bfQ)\text{.}\)
  3. Tunjukkan bahwa penghapusan satu titik dapat mengurangi dimensi paling banyak sebesar \(1\text{.}\)
  4. Tentukan dimensi poset-poset dalam Gambar 6.8.
  5. Gunakan Teorema Dilworth untuk menunjukkan bahwa dimensi suatu poset paling besar sama dengan lebarnya.
  6. Gunakan contoh di sisi kiri Gambar 6.33 untuk menunjukkan bahwa bagi setiap \(n\ge2\text{,}\) terdapat suatu poset \(\bfP_n\) pada \(2n\) titik yang lebar dan dimensinya sama dengan \(n\text{.}\)
SblmKe AtasLnjt