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.

Isibonelo esisebenza · 5 choose 2

Discrete-Math · Counting

5 choose 2

5,\ 2

Isigaba

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

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

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

Bonisa impendulo
\binom{5}{2} = 10

Manje Khetha izinkinga, noma ubhale noma udwebe zakho. Isigaba ngasinye, isithombe, impendulo ifihlakele kuze kube ubuza.

Qhubeka usebenza

I-akhawunti emahhala ifaka iziphawulo kulesifundo ngasinye, irekhodi lokuthi yini oqedile, izinkinga zakho ezixazululiwe endaweni eyodwa, nodokotela owaziyo ongabuza mayelana nalekhasi. I-matematics ivulekile kubo bonke, noma ngabe babhalise noma cha.

Bhala Ngena

Amaphawu asetshenziswa lapha

Chofoza noma yiluphi uphawu lwesibonakaliso ukuze uthole ukuchaza okuphelele, isithombe, kanye nokuthi iyiphi inhlamvu ekhona ekhuluma ngaso.

Indlela: Paths, cycles, trees, Euler and Hamilton

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

Imibuzo abantu bebuza

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.

Okuningi Combinatorics & Graph Theory

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