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.

Gumagana halimbawa · 5 choose 2

Discrete-Math · Counting

5 choose 2

5,\ 2

Hakbang-hakbang

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

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

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

Ipahayag ang sagot
\binom{5}{2} = 10

Ngayon ikaw Pumili ng isang problema, o i-type o gumuhit ng iyong sarili. Sa bawat hakbang, isang larawan, ang sagot na nakatago hanggang sa hilingin mo.

Panatilihin ang iyong sariling nagtatrabaho

Ang isang libreng account ay nagdaragdag ng mga tala sa bawat aralin, isang tala ng kung ano ang iyong natapos, ang iyong mga nalulutas na problema sa isang lugar, at isang guro na maaari mong tanungin tungkol sa pahinang ito. Ang matematika mismo ay bukas sa lahat, naka-sign in o hindi.

Mag-sign Up Mag-login

Mga simbolong ginagamit dito

I-tap ang anumang simbolo para sa buong kahulugan, isang larawan, at kung ano ang ibig sabihin ng bawat titik sa ito.

Paano: Paths, cycles, trees, Euler and Hamilton

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

Mga katanungan na tanong ng mga tao

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.

Higit pa sa Combinatorics & Graph Theory

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