Sign in to follow this  
Nicholas Kong

Finding a path of length n in a graph

Recommended Posts

[url=http://s33.photobucket.com/user/warnexus/media/path_zpsb4b2abdd.png.html]path_zpsb4b2abdd.png[/URL]

 

[url=http://s33.photobucket.com/user/warnexus/media/K4_zpse47064df.png.html]K4_zpse47064df.png[/URL]

 

I am doing part a of Ex 19. The answer has 2 but I can list at least 11 paths.

 

Here are the paths:

1) {a,b,d}

2) {a,d,c}

3) {a,c,d}

4) {b,a,c}

5) {b,d,c}

6) {b,c,d}

7) {c,a,b}

8) {c,d,b}

9) {d,b,a}

10) {d,c,a}

11) {d,b,c}

 

The complete graph k4 graph does not have labeled vertices a,b,c,d.

So I am not sure if I can label a,b,c,d anywhere I want.

Edited by warnexus

Share this post


Link to post
Share on other sites

Sure you can label them as you want.

 

I think you are misunderstanding the problem, though. I would interpret it as, “Pick two fixed vertices. Tell me how many paths of length 2 there are between them.” The beauty here is that you should get the same answer no matter which two vertices you pick – this is thanks to your graph being a complete one; the question would be ill-formed if it were for a different kind of graph.

Share this post


Link to post
Share on other sites

Assuming the diagonals count as 1, if you pick any 2 vertices, there will be only 2 paths of length 2 between them. This is what i assume you were supposed to do.

I think I get what you saying. So the 11 paths I listed are not correct.

Share this post


Link to post
Share on other sites

Sure you can label them as you want.

 

I think you are misunderstanding the problem, though. I would interpret it as, “Pick two fixed vertices. Tell me how many paths of length 2 there are between them.” The beauty here is that you should get the same answer no matter which two vertices you pick – this is thanks to your graph being a complete one; the question would be ill-formed if it were for a different kind of graph.

Well there are 2 edges between any two vertices you pick so 2 paths of length. Now that I am doing part b. I do not get the same answer as the textbook so I think I am struggling with what the question is actually saying

Share this post


Link to post
Share on other sites

I count

a) 2

b) 7

c) 20

d) 61

 

That's assuming that it's OK to repeat nodes and edges in the paths: I am not sure what precise definition you are using.

 

If you want more terms,

 

A(0) = 0, A(1) = 1, A(n) = 3*A(n-2) + 2*A(n-1) if n>1

Edited by Álvaro

Share this post


Link to post
Share on other sites

I count

a) 2

b) 7

c) 20

d) 61

 

That's assuming that it's OK to repeat nodes and edges in the paths: I am not sure what precise definition you are using.

 

If you want more terms,

 

A(0) = 0, A(1) = 1, A(n) = 3*A(n-2) + 2*A(n-1) if n>1

You did get them all correct. You mention you counting the edges, so you do not need to write them down on a piece of paper?

 

Can you explain how you get 7 for part b?

 

I think if I understand how 7 was acheived I should be able to get part c and d intuitively. part a seems to do a poor job of figuring out how the thought process should be approached.

Edited by warnexus

Share this post


Link to post
Share on other sites

A(0) = 0, A(1) = 1, A(n) = 3*A(n-2) + 2*A(n-1) if n>1

To find a path with length n you need to find a path with length n-1 to any of the other nodes. You have 2 options:
1. Find a path to a node other than the start node. So 2 possible nodes, and you need a path of length n-1 to get to them. This is the 2*A(n-1) term.

2. Find a n-1 path to the start node. To do that, you need a n-2 path to any of the other 3 nodes. That's the 3*A(n-2) term.

Share this post


Link to post
Share on other sites

 

A(0) = 0, A(1) = 1, A(n) = 3*A(n-2) + 2*A(n-1) if n>1

To find a path with length n you need to find a path with length n-1 to any of the other nodes. You have 2 options:
1. Find a path to a node other than the start node. So 2 possible nodes, and you need a path of length n-1 to get to them. This is the 2*A(n-1) term.

2. Find a n-1 path to the start node. To do that, you need a n-2 path to any of the other 3 nodes. That's the 3*A(n-2) term.

 

Oh I get it now. I was doing it wrong the whole time. Thanks for the explaination.

Share this post


Link to post
Share on other sites

You start at `a' and then you have three choices at each step. Of the possible paths, only 1/4 of them will end at the right spot, so the formula is pow(3,n)/4. Well, powers of 3 are not usually divisible by 4, so you need to do some rounding. </mostly kidding>

Once you have the recursive formula, you can find the explicit formula by trying to find the numbers x such that pow(x,n) satisfies the recursive formula.

pow(x,n) = 3*pow(x,n-2) + 2*pow(x,n-1)

Dividing by pow(x,n-2), you get

x^2 = 3 + 2*x => x^2 - 2*x - 3 = 0

Solving the quadratic equation, you find out that 3 and -1 are the roots. Now all the sequences that satisfy the recursive formula form a vector space of dimension 2 (because the one that starts (1,0,...) and the one that starts (0,1,...) are a basis), and you just found two independent vectors. If you don't know what on Earth I am talking about, don't worry. It means that any sequence that satisfies the recursive formula can be expressed as a*pow(3,n) + b*pow(-1,n), for appropriate values of a and b. Since we know A(0)=0 and A(1)=1,

a*pow(3,0) + b*pow(-1,0) = 0 => a + b = 0
a*pow(3,1) + b*pow(-1,1) = 1 => 3*a - b = 1

Solving that system of linear equations, you get a=1/4, b=-1/4, and that gives us the explicit formula.

This may look like magic if you haven't seen it before, but it's just a procedure you learn.

Edited by Álvaro

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this