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.

  1. What is the shortest path from vertex\(E\) to vertex\(B\)?

  2. 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?

  3. 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.

Sasa Hakuna kifaa cha kupigia hesabu kinachoweza kufanya hesabu, lakini kifaa hicho kinaweza kutumiwa katika hesabu.

Keep your own working

Akaunti la bure laongezea mambo makuu juu ya kila somo, rekodi ya yale ambayo umemaliza, matatizo yako ya kutatua katika sehemu moja, na mtunzaji unayeweza kuuliza juu ya ukurasa huu.

Jisajili Login

Ishara zinazotumiwa hapa

Vaa alama yoyote ya ufafanuzi kamili, picha, na maana ya kila herufi.

Maswali ambayo watu huuliza

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.

Sehemu za ukurasa huu zimebadilishwa kutoka kwa Keller & Trotter, Applied Combinatorics (CC BY-SA 4.0). Tumekamatwa na kukosolewa tena hapa; makosa ni yetu.

Mengi zaidi katika 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