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

Discrete-Math · Counting

5 choose 2

5,\ 2

一步

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

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

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

发送答案
\binom{5}{2} = 10

现在轮到你 选择问题, 输入或绘制您自己的 。 每一步, 图片, 答案隐藏到您询问 。

保持你自己的工作

免费账户在每一课上都添加注解, 记录你完成的, 在一个地方解决的, 以及您可以询问的关于此页的导师。 数学本身向每个人开放, 是否签名 。

签名上签名 登录

此处所用符号

输入完整定义、图片和其中每个字母的含义的符号。

如何: Paths, cycles, trees, Euler and Hamilton

  1. 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