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.
Ankehitriny ianao Tsy misy milina fanisana afaka mamaha io olana io, saingy azo atao ny maminavina ny ampahany amin'io. Andramo ny iray eto ambany, na soraty ny anao manokana.
Ny kaonty maimaimpoana dia mampiditra ny fanamarihana amin'ny lesona tsirairay, ny tahirin'ny zavatra vitanao, ny olana voavahao ao amin'ny toerana iray, ary ny mpampianatra iray izay azonao anontanio momba ity pejy ity. misokatra ho an'ny rehetra ny matematika, na efa niditra na tsy niditra.
Misoratra anarana FidiranaMarika ampiasaina eto
Tsindrio ny marika iray mba hahitana ny famaritana feno, sary, ary ny dikan'ny litera tsirairay ao aminy.
Fanontaniana napetrak'ireo olona
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.
Nalaina avy amin'ny Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Nofafana sy nanazavana indray eto; ny hadisoana dia antsika.
Mbola maro ao 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