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