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
Крок за кроком
- \binom{5}{2} = \frac{5!}{2!\,(5-2)!}
Unordered selections: n! / (k! (n−k)!).
- = \frac{120}{2 \times 6} = 10
Показати відповідь
Тепер ти Виберіть проблему або наберіть її на зразок. Кожен крок, малюнок, відповідь, сховану до того часу, доки ви не запитаєте.
Вільний рахунок додає нотатки до кожного уроку, запису того, що ви завершили, ваших розв' язаних проблем у одному місці, і репетитора, який ви можете запитати про цю сторінку. Сама математика відкрита для всіх, підписані чи ні.
Підписування ВхідСимволи, що тут використовуються
Взяти будь-який символ до повного визначення, зображення і що означає кожна літера.
Як це зробити?: Paths, cycles, trees, Euler and Hamilton
- 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