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