maths.free › Combinatorics & Graph Theory › Paths, cycles, trees, Euler and Hamilton

Paths, cycles, trees, Euler and Hamilton

Connectivity, spanning trees, Euler circuits and the bridges of Königsberg.

A tree is a connected graph with no cycles: n vertices, n − 1 edges. Euler proved a graph has a circuit using every edge once exactly when every degree is even. The Königsberg bridges failed. Picture it: the seven bridges; four land masses with odd degree. Think it: Euler's condition is local (degrees) yet decides a global question, the first theorem of topology.

Иштөө мисалы · 5 choose 2

Discrete-Math · Counting

5 choose 2

5,\ 2

Аткаруу

  1. \binom{5}{2} = \frac{5!}{2!\,(5-2)!}

    Unordered selections: n! / (k! (n−k)!).

  2. = \frac{120}{2 \times 6} = 10

Жауап
\binom{5}{2} = 10

Эми сиз Задание выберите, нажмите на него или нарисуйте его. Каждый шаг, рисунок, ответ скрыт до тех пор, пока вы не спросите.

Өзүңүздүн иштөөңүздү улантыңыз

Бесплатный аккаунт добавляет заметки к каждому уроку, записывает завершенные и решенные задачи в одном месте, а также позволяет задавать вопросы учителю по этой странице. Математика өзү бардык окуучуларга ачык, ал компьютерге киргенде да, кирбегенде да.

Каттоо Кирүү

Бул жерде колдонулган символдор

Бардык символдорду басып, толук аныктамасын, сүрөтүн жана ар бир тамгасынын маанисин көрсөңүз болот.

Кантип: Paths, cycles, trees, Euler and Hamilton

  1. Unordered selections: n! / (k! (n−k)!).

Кээ бирлердин суроосу

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.

Кээ бирлери Combinatorics & Graph Theory

The counting principlesPigeonhole principle and inclusion, exclusionBinomial coefficients and Pascal's triangleRecurrences and generating functionsGraphs: vertices, edges, degreesColouring and planar graphs