Results 1 to 2 of 2

Math Help - Transversing Paths

  1. #1
    Member
    Joined
    May 2008
    Posts
    101

    Transversing Paths

    Hi, here I have a problem with how to travel across a shape without going alone the same line twice. Capitalization and 'lower case-alization' of single letters (except I) are intentional in this question. Capitals represent a destination, lower case represents a path between two destinations.

    In question 1) below, a path of c, b*, b, c* will start at 'B', follow path 'c' etc and follow 'c*' back to B. This means it uses 4 paths.

    1)


    What is the longest trail possible on this and why does it need to start on 'B' or 'C'?

    2)


    Prove that the longest track possible is '5', when you start at 'A'

    3)


    What is the longest continuous trail possible, justifying your reason.

    Thanks for any help and advice.
    Last edited by BG5965; May 16th 2009 at 04:14 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,242
    Thanks
    1795
    You can divide the points into three types: the point where you start, the point where you stop, and the points you just pass through.
    It takes two paths to pass through a point which means that any point that you "just pass through" must have an even number of paths leading to it. The point you start at must have the one path through which you leave and then an even number of paths you "pass through" on- an odd number of paths total. Similarly, the point you end at must have the one path through which you enter and then an even number of paths you "pass through" on- an odd number of paths total. An exception to that is if you start and end at the same point: then that point also must have an even number of paths connected to it. There can be, of course, at most one point at which you start and one point at which you end.

    That leads to the conclusion of Euler's famous analysis of the "Konigsberg bridges" problem- such an "Euler circuit" of a graph is possible if and only if the number of nodes of odd degree- that is, the number of points with an odd number of bridges connected- is either 0 or 2.

    In your problem (1), B and C both have degee 3 while A has degree 4 so this is possible. Any circuit must start at either B or C because, as I said, with an odd degree we cannot only "pass through"- that would require an even number of bridges. We must start at one and end at the other. And it is easy to find such a circuit that uses all paths. Indeed, for the example you give, "a path of c, b*, b, c* will start at 'B', follow path 'c' etc and follow 'c*' back to B", just add a to make make a circuit that uses all 5 paths.

    In problem (2), A, B, C, and D all have degree 3 so a complete circuit is impossible. But it is easy see that the path A, C, D, A, B, D covers every path except BC.

    In problem (3), A, B, C, G, H, and I all have degree 3 so a complete circuit is possible. It looks to like the best you could do is, say start at A, go around the "loop", B, C, A, out to D, around E, F, D, then out to G, then around H, I, G, using all paths except the 4 other "radial" paths.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Number of paths
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 10th 2010, 01:07 PM
  2. Number of Paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 30th 2010, 07:07 AM
  3. Help on Graphs and Paths
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 26th 2009, 04:29 AM
  4. 3d Object paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 25th 2009, 11:17 PM
  5. How many paths...?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 14th 2008, 08:54 AM

Search Tags


/mathhelpforum @mathhelpforum