What is traversable network?

Network Graphs

In the 18th century in the town of Königsberg, Germany, a favorite pastime was walking along the Pregel River and strolling over the town's seven bridges (Fig. 1). During this period a natural question arose: Is it possible to take a walk and cross each bridge only once? Before reading further, can you determine the answer? This question was solved by the Swiss mathematician Leonard Euler. His solution was the beginning of network theory.






圖片參考：http://www.mhhe.com/math/ltbmath/bennett_nelson/conceptual/netgraphs/gifs/fig1.gif




Figure 1.





Euler represented the four land areas of Königsberg (A, B, C, and D in Figure 2) as four points and the seven bridges as seven lines joining these points. For example, the island of Kneiphoff (A) can be reached by five bridges, and in the diagram in Figure 2 there are five lines to point A. The three lines from point D represent three bridges, etc. This kind of diagram is called a network graph, or more simply, a network. Notice that Euler was concerned not with the size and shape of the bridges and land regions but rather with how the bridges were connected.






圖片參考：http://www.mhhe.com/math/ltbmath/bennett_nelson/conceptual/netgraphs/gifs/fig2.gif




Figure 2.





A network is a collection of points, called vertices, and a collection of lines, called arcs, connecting these points. A network is traversable if you can trace each arc exactly once by beginning at some point and not lifting your pencil from the paper. The problem of crossing each bridge exactly once reduces to one of traversing the network representing these bridges.



Euler made the remarkable discovery that whether a network is traversable depends on the number of odd vertices. In the Königsberg network, there are an odd number of arcs at point A, so A is called an odd vertex. If the number of arcs meeting at a point is even, the point is called an even vertex. Euler found that the only traversable networks are those that have either no odd vertices or exactly two odd vertices. Since the Königsberg network has four odd vertices, it is not traversable. Therefore, it is not possible to take a walk over the bridges of Königsberg and cross each bridge only once.









Example A





Which of the following networks are traversable?






圖片參考：http://www.mhhe.com/math/ltbmath/bennett_nelson/conceptual/netgraphs/gifs/exa.gif








Solution Network 1 has two odd vertices, so it is traversable. Network 2 has no odd vertices, so it is traversable. Networks 3 and 4 have four and six odd vertices, respectively, so they are not traversable.

We now know how to determine if a network is traversable. But is it possible to predict where you ought to begin in order to trace the network exactly once, and where you will end up? The following example considers this problem.











Traversable Networks



1. A network with exactly two odd vertices is traversable. Either odd vertex may be the beginning point, and the other odd vertex is the ending point.



2. A network with no odd vertices is traversable. Any vertex may be the beginning point, and the same vertex will also be the ending point.



3. A network with more than two odd vertices is not traversable.

Hi, 我試着回答一下, traversable network 意思是有一個圖案, 如果你可以一筆就把它畫出來, 又不翻筆 (即是在畫過的地方再畫) 那個圖案所代表的就是 traversable network. 要注意啊! 畫的時候是不可以拿起筆的.

例: http://homepage.mac.com/efithian/Geometry/Activity-16.html
A & B 都是 traversable, 其他沒研究.

希望可以幫到你
Eric