maths.free › Combinatorics & Graph Theory › An Introduction to Combinatorics › Combinatorics and Optimization
Combinatorics and Optimization
You likely have already been introduced to optimization problems, as calculus students around the world are familiar with the plight of farmers trying to fence the largest area of land given a certain amount of fence or…
Combinatorics and Optimization
You likely have already been introduced to optimization problems, as calculus students around the world are familiar with the plight of farmers trying to fence the largest area of land given a certain amount of fence or people needing to cross rivers downstream from their current location who must decide where they should cross based on the speed at which they can run and swim. However, these problems are inherently continuous. In theory, you can cross the river at any point you want, even if it were irrational. (OK, so not exactly irrational, but a good decimal approximation.) In this course, we will examine a few optimization problems that are not continuous, as only integer values for the variables will make sense. It turns out that many of these problems are very hard to solve in general.
Example
In , we use letters for the labels on the vertices to help distinguish visually from the integer weights on the edges.
Suppose the vertices are cities, the edges are highways and the weights on the edges represent distance.
What is the shortest path from vertex\(E\) to vertex\(B\)?
Suppose Ariel is a salesperson whose home base is city\(A\). In what order should Ariel visit the other cities so that she goes through each of them at least once and returns home at the endwhile keeping the total distance traveled to a minimum? Can Ariel accomplish such a tour visiting each city exactly once?
Sanjay is a highway inspection engineer and must traverse every highway each month. Sanjay's homebase is City\(E\). In what order should Sanjay traverse the highways to minimize the total distance traveled? Can Sanjay make such a tour traveling along each highway exactly once?
Condensed: the full section is in Keller & Trotter, Applied Combinatorics.
حالا تو هیچ ماشین حسابی این را حل نمی‌کند ، اما تکه‌های آن قابل محاسبه هستند. یکی از زیر را امتحان کنید ، یا خودتان را تایپ کنید.
نمادهای استفاده‌شده در اینجا
هر نماد را برای تعریف کامل، تصویر و معنی هر حرف در آن بزنید.
سوالاتي که مردم ميپرسن
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