Lewati ke konten utama

Indeks Sblm Naik Lnjt

\(\newcommand{\set}[1]{\{#1\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\text{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\ds}{\displaystyle} \newcommand{\mbf}[1]{\mathbf{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Subbab 6.4 Perluasan Linear Himpunan Terurut Parsial

Misalkan \(\PXP\) merupakan suatu himpunan terurut parsial. Suatu urutan linear \(L\) pada \(X\) disebut perluasan linear (juga disebut pengurutan topologis) dari \(P\) jika \(x\lt y\) dalam \(L\) setiap kali \(x\lt y\) dalam \(P\text{.}\) Sebagai contoh, tabel yang ditampilkan pada Gambar 6.23 memperlihatkan bahwa contoh yang telah kita kenal, \(\bfP_3\text{,}\) memiliki 11 perluasan linear.

dijelaskan secara terperinci setelah gambar — Gambar 6.23. Suatu poset dan perluasan-perluasan linearnya

Diskusi 6.24.

Bob mengatakan bahwa ia belum yakin setiap poset hingga memiliki perluasan linear. Alice mengatakan bahwa hal tersebut mudah dibuktikan. Apakah Alice benar?

Carlos mengatakan bahwa pertanyaan ini memiliki seluk-beluk ketika himpunan dasar \(X\) tak hingga. Anda mungkin ingin menelusuri nama Szpilrajn di web dan membaca sumbangsihnya terhadap persoalan ini.

Masalah pengurutan klasik yang dipelajari dalam semua mata kuliah dasar ilmu komputer adalah menentukan urutan linear \(L\) yang tidak diketahui pada suatu himpunan \(X\) dengan mengajukan serangkaian pertanyaan berbentuk: Apakah \(x\lt y\) dalam \(L\text{?}\) Semua algoritme pengurutan yang terkenal (pengurutan gelembung, urut gabung, pengurutan cepat, etc.) bekerja dengan cara ini.

Berikut ini sebuah kasus khusus yang penting: tentukan perluasan linear \(L\) yang tidak diketahui dari suatu poset \(\bfP\) dengan mengajukan serangkaian pertanyaan berbentuk: Apakah \(x \lt y\) dalam \(L\text{?}\)

Diskusi 6.25.

Dengan poset \(\PXP\) yang ditampilkan pada Gambar 6.5 dan persoalan untuk menentukan suatu perluasan linear yang belum diketahui dari \(P\text{,}\) bagaimana sebaiknya Alice memutuskan pertanyaan mana (berbentuk: Apakah \(x\lt y\) dalam \(L\text{?}\)) yang akan diajukan?

Bagaimana perasaan Anda jika diberi tugas menghitung banyaknya perluasan linear poset ini? Secara umum, seberapa sulit menentukan banyaknya perluasan linear suatu poset? Dapatkah Anda (dan komputer Anda) melakukan penghitungan ini untuk poset dengan \(100,000\) titik?

Sblm Ke Atas Lnjt