maths.free › Combinatorics & Graph Theory › Partially Ordered Sets › Linear Extensions of Partially Ordered Sets
Linear Extensions of Partially Ordered Sets
Let \PXP be a partially ordered set. A linear order L on X is called a linear extension (also, a topological sort) of P, if x\lt y in L whenever x\lt y in P.
Linear Extensions of Partially Ordered Sets
Let \(\PXP\) be a partially ordered set. A linear order \(L\) on \(X\) is called a linear extension (also, a topological sort) of \(P\), if \(x\lt y\) in \(L\) whenever \(x\lt y\) in \(P\). For example, the table displayed in shows that our familiar example \(\bfP_3\) has11 linear extensions.
The classical sorting problem studied in all elementary computer science courses is to determine an unknown linear order \(L\) of a set \(X\) by asking a series of questions of the form: Is \(x\lt y\) in \(L\)? All the well known sorting algorithms (bubble sort, merge sort, quick sort, ) proceed in this manner.
Here is an important special case: determine an unknown linear extension \(L\) of a poset \(\bfP\) by asking a series of questions of the form: Is \(x \lt y\) in \(L\)?
ഇപ്പോള്‍ നീ ഒരു കോംപൌണ്ടും ഇത് ഉറപ്പിക്കുന്നില്ല, പക്ഷേ അതിന്റെ കഷ്ണങ്ങള്‍ ചേര്‍ന്നു തീർക്കാന്‍ പറ്റും. താഴെയൊന്ന് ശ്രമിക്കൂ അല്ലെങ്കില്‍ നിങ്ങള്‍ക്കുതന്നെ ടൈപ്പ് ചെയ്യുക.
ഒരു സ്വതന്ത്ര അക്കൗണ്ട്, നിങ്ങൾ പഠിച്ച കാര്യങ്ങൾ, നിങ്ങളുടെ പ്രശ്‌നങ്ങൾ പരിഹരിച്ചിരിക്കുന്ന പ്രശ്‌നങ്ങൾ, ഒരു സ്ഥലത്ത്‌ ഒരു ടീച്ചർ, ഈ പേജിനെ കുറിച്ച് ചോദിക്കാവുന്നതാണ്‌.
മുകളില്‍ ഒപ്പ് വയ്ക്കുക ലോഗിന്ഇവിടെ ഉപയോഗിച്ചിരിക്കുന്ന ചിഹ്നങ്ങള്‍
ഒരു പ്രത്യേക പത്രികയിൽ, ഒരു ചിത്രത്തിന്‍റെ പ്രതീകം, അതിലുള്ള എല്ലാ അക്ഷരങ്ങൾ എന്നിവയ്‌ക്കും വേണ്ടിയുള്ളതാണ്‌.
ആളുകൾ ചോദിക്കുന്നു
Permutation or combination?
Ask whether order matters. A lock code is a permutation (order matters); a hand of cards is a combination (it does not).
What is a graph in this sense?
Dots (vertices) joined by lines (edges), not a plot. Road maps, social networks and molecules are graphs; questions like "is there a route" and "how few colours" are graph theory.
ഈ താളിലെ ഭാഗങ്ങൾ മാറ്റുന്നു Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). ഇവിടെ വളച്ചൊടിച്ച്, വീണ്ടും പ്രഹരം, തെറ്റുകള്‍ നമ്മുടേതാണ്.
കൂടുതല്‍ Combinatorics & Graph Theory
The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesPaths, cycles, trees, Euler and HamiltonColouring and planar graphs