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\)?
ಈಗ ನೀವು ಯಾವುದೇ ಕ್ಯಾಲುಕೇಂಟ್ ಇದನ್ನು ಸಚೇತಗೊಳಿಸುವುದಿಲ್ಲ, ಆದರೆ ಅದರ ತುಂಡುಗಳು ಸಹಕಾರಿಯಾಗುತ್ತವೆ. ಕೆಳಗೆ ಯಾವುದನ್ನು ಪ್ರಯತ್ನಿಸಿ ಅಥವಾ ನಿಮ್ಮದನ್ನು ಟೈಪಿಸಿ.
A free account adds notes on every lesson, a record of what you have finished, your solved problems in one place, and a tutor you can ask about this page. The maths itself is open to everyone, signed in or not.
ಮೇಲೆ ಗುರುತು ಹಾಕು ಪ್ರವೇಶ (ಲಾಗಿನ್)ಇಲ್ಲಿ ಬಳಸಲಾದ ಸಂಕೇತಗಳು
ಈ ವಚನದಲ್ಲಿ ಬಳಸಲಾಗಿರುವ ಗ್ರೀಕ್‌ ಪದವು, ಚಿತ್ರ ಮತ್ತು ಚಿತ್ರಗಳನ್ನು ನೀವು ಸುಲಭವಾಗಿ ಅರ್ಥಮಾಡಿಕೊಳ್ಳಲು ಸಹಾಯ ಮಾಡುತ್ತದೆ.
ಜನರು ಕೇಳುವುದು
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