Dots and lines: networks and puzzles

इस पर आधारित

कोई पूर्वापेक्षा नहीं — यहीं से शुरू करें!

आप सीखेंगे

• Decide by experiment which figures can be traced in one stroke without retracing a line.
• Count the line ends at each dot and notice the pattern behind traceable figures.
• Find shortest routes in a small road network with distances marked.

परिभाषा

• A network (graph) is a collection of dots (vertices) with lines (edges) joining some pairs of them.
• The degree of a dot is the number of line ends at it.

प्रमेय

• The degrees of all the dots add up to an even number: twice the number of lines.
• A connected figure can be traced in one stroke exactly when it has either no dots or exactly two dots of odd degree.

आम भ्रांतियाँ

• Thinking whether a figure can be traced depends on its overall shape rather than on the degrees of its dots.
• Believing the shortest route is always the one with the fewest roads.

आगे ले जाता है

वैकल्पिक खोजें

• Algorithm design and analysis Finding shortest routes in huge networks, such as road maps, uses efficient algorithms such as Dijkstra's.