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.
À vous Aucune calculatrice ne tranche celle-ci, mais ses éléments sont calculables. Essayez-en un ci-dessous, ou tapez le vôtre.
Un compte gratuit ajoute des notes sur chaque leçon, un enregistrement de ce que vous avez terminé, vos problèmes résolus en un seul endroit, et un tuteur que vous pouvez demander sur cette page. Les maths eux-mêmes sont ouverts à tout le monde, signé ou non.
Inscription ConnexionSymboles utilisés ici
Appuyez sur n'importe quel symbole pour la définition complète, une image et ce que signifie chaque lettre.
Questions posées par les gens
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.
Certaines parties de cette page sont adaptées de Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Condensés et réexpliqués ici ; les erreurs sont les nôtres.
Plus en 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