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
चरणद्वारा चरण
- \binom{5}{2} = \frac{5!}{2!\,(5-2)!}
Unordered selections: n! / (k! (n−k)!).
- = \frac{120}{2 \times 6} = 10
जवाफ प्रकट गर्नुहोस्
अब तपाईँ समस्या रोज्नुहोस्, वा टाइप गर्नुहोस् वा तपाईँको आफ्नै रेखाचित्र गर्नुहोस् । प्रत्येक चरण, एउटा तस्वीर, तपाईँले सोध्नु अघि उत्तर लुकेको छ ।
एक निःशुल्क खाता प्रत्येक पाठ मा नोट थप्छ, तपाईं के समाप्त गरेको छ को एक रेकर्ड, एक ठाउँमा आफ्नो समाधान समस्या, र एक शिक्षक तपाईं यो पृष्ठ बारेमा सोध्न सक्नुहुन्छ. गणित आफैलाई सबैलाई खुला छ, मा साइन इन वा छैन.
साइन अप गर्नुहोस् लगइनयहाँ प्रयोग गरिएको प्रतीक
पूर्ण परिभाषा, एउटा तस्वीर, र यो प्रत्येक अक्षर अर्थ के लागि कुनै पनि प्रतीक ट्याप गर्नुहोस्।
कसरी: Paths, cycles, trees, Euler and Hamilton
- 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