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.

More in Combinatorics & Graph Theory

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