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.

Töötatud näide · 5 choose 2

Discrete-Math · Counting

5 choose 2

5,\ 2

Samm-sammult

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

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

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

Vastuse avalikustamine
\binom{5}{2} = 10

Nüüd sina. Vali probleem, või kirjuta või joonista oma. Iga samm, pilt, vastus peidetud, kuni küsid.

Hoia oma töö

Tasuta konto lisab märkmeid igale õppetunnile, ülestähenduse, oma lahendatud probleemide kohta ühes kohas ja juhendaja kohta, kellelt võid küsida selle lehekülje kohta. Matemaatika ise on avatud kõigile, allkirjastatud või mitte.

Registreeru Sisselogimine

Siin kasutatavad sümbolid

Koputage kõiki sümboleid, mis on mõeldud täieliku definitsiooni, pildi ja iga tähe all.

Kuidas: Paths, cycles, trees, Euler and Hamilton

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

Küsimusi, mida inimesed küsivad

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.

Rohkem Combinatorics & Graph Theory

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