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.

አሁን ምንም ዓይነት መሳሪያ ይህን አይቆጣጠርም፤ ነገር ግን ክፍሎቹ ሊቆጠሩ ይችላሉ። በታች ያለውን ይሞክሩ ወይም የራሳችሁን ይጻፉ።

የራስዎን ስራዎች ይያዙ

ነጻ የሆኑት መተግበሪያዎች በየክፍል ውስጥ ማስታወሻዎችን ያካትታሉ፣ የተጠናቀቁትን ነገሮች መዝገብ፣ የተፈቱ ችግሮችን በአንድ ቦታ፣ ስለዚህ ገጽ መጠየቅ የሚችሉትን ረዳት ያካትታሉ፡፡ የቁጥር ትምህርት ለሁሉም ሰው ክፍት ነው፣ ተቀባይነት ያለው ወይም የለም፤

ምዝገባ መግባቱ

ፊደላት

ለሙሉ መግለጫ፣ ምስል፣ እና በውስጡ ያለውን ፊደል ትርጓሜ ለማየት ማንኛውንም ምልክት ይጫኑ።

ጥያቄዎች

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