A couple of discrete structure questions

[devilazy]

1. Explain how to find a shortest path between any given pair of vertices, given the length of edges connecting the vertices and the shortest distance between vertices (after doing the shortest-path calculation)

So I am given a two matrices, as said one with length of edges connecting and the other with shortest distance after calculation (they both have a total of 15 vertices). So I looked at the first matrix and since I see no infinity signs I concluded that all the vertices are connected and there is no directions. I then look at the second matrix and concluded that the if the shortest path is the same as the other matrix, then the shortest path is a direct path between the vertices. Now as to how to find the shortest path for vertices that are not direct, here's my "educated" gues, by testing out different combination. Let's say we want to find the shortest path for x to y (assuming that the direct path x to y is not the shortest path). So with the second matrix I know what the shortest distance between x and y is, so then I look at the first matrix and remove and paths that are greater than the shortest distance. From then just test out like from x to a (a different vertex) is blah, and from a to y is blah. IF they both add up to the shortest distance then x>a>y is the shortest path. So that's my guess and I think it's dumb, because it takes too much time to work out but at the same time I can't figure out what else I can do. So just a little pointer or two to which direction I should look at would be great.


2. Given f(x) = 10(x-1)(x-2) and h(x)= x!
Prove that f(x)=O(h(x))based on the definition of the big O notation.

My try: first I put the equations out straight.
10(x-1)(x-2)= O(x!)
So next I just try to simplify the equation (I think this step is completely wrong.)
10(x-1)(x-2)=O(x(x-1)(x-2)(x-3)!)
10(x-1)(x-2)=O(x-1)(x-2)(x(x-3)!)
10=O(x(x-3)!)
And I conclude that since 10 being a constant will never change, while x(x-3)! will constantly increase and be greater than 10 eventually. Therefore, f(x) is bounded by h(x).


3. Using proof by contradiction, show that any tree with 2 or more vertices must have at least 2 vertices of degree 1. In other words, show that it is contradictory in any tree with 2 or more vertices if at most one of the vertices has a degree of 1 while others have degrees of 2 or more.

First off, I have to let you know my that my English is not very good, this question took me a while to understand and I am still uncertain what exactly it's asking for. First I figured out I should prove that a tree with 2 or more vertices can't have only 1 vertex with degree of 1. So I pointed out with example that the smallest tree to be made with this context is one with 2 vertices, and they must be connected to be a tree. So in this case both vertices would have a degree of just 1, since they can't have paths going to nowhere. But then I looked at a tree with 3 vertices, all connected together. This tree has 3 vertices which all have 2 degrees then. Now I'm just confused in general if the question wants me to prove it's true or false.

That's mainly the questions I have, so if you can help me out with the questions, even if it's just one or two of them, please do. Thank you.

 

[Tedjn]

1.
Have you seen Dijkstra's algorithm for calculating the shortest path? If so, you can modify it slightly in order to also return such a path. Think about what the algorithm would need to remember as it visits each vertex.

2.
Your method can be made rigorous. To do that, you need to use the definition of big-O notation. What is it? Start with that.

3.
Your argument for the 2-vertex tree is correct, because there is only one possible tree with 2 vertices. For trees with 4 or more vertices, there can be many different trees. With 4 vertices, one tree is 4 vertices in a row. Another is 3 leaf vertices connected to one root. You need to prove that for all those possible trees that at least 2 vertices have degree 1.

In order to start, I would first call one vertex of your tree the root. After doing this, what degrees must all leaf vertices have? What is the minimum number of leaf nodes in a tree? What degrees must all non-leaf, non-root nodes have? What about the root node?

 

[devilazy]

First off, thank you Tedjn for your reply. It really helped me understand the question better.

1. I didn't know about the Dijkstra's algorithm and that really helped me with question 1.

2. I read the definition of the big o notation and here's my second try:
10(x-1)(x-2)= O(x!)
10(x-1)(x-2)=O(x(x-1)(x-2)(x-3)!)
10(x-1)(x-2)=O(x-1)(x-2)(x(x-3)!)
Now since f(x) is only 10*[(x-1)(x-2)] whereas g(x) is x(x-3)!*[(x-1)(x-2)],
f(x)=O(g(x)) is true.

3. I came across a theory and explanation of a tree after posting the question and think it's related to this question. So, for a graph G to be a tree, it has to have n>1 vertices and all of them must be connected but it cannot form a cycle, also the tree will have n-1 edges. With that said, I applied it to your root and leaf idea and figured that if a tree with n vertices has n edges, then that would imply that a cycle is formed. So with a few examples it's clear to me (n=2, 1 edge connecting both thus both with 1 degree // n=3, 2 edges and its either all connected to one root, or all connected in a straight line, either way there will at least two vertices with degree of 1 // n=4, 3 edges, this time it's either all connected to one root, all connected in a line, or 2 vertices connected to root while one connects off one of the two, again there will be at least 2 vertices with degree of 1) So, I concluded that since the minimum few examples all require at least two vertices with a degree of 1, it only makes sense that as n increases the number of vertices with degree of 1

Does my reasoning to question 2 and 3 make sense?

New Question:
4. Is there an integer solution in the range of [0,144) (eg. 0<=y<=144) to the linear congruence equation 289*x=100(mod 144)? If so, give such a y. If not explain why.

So before this question I was asked to find the gcd(289, 144), which I found is 1. Now based off that, I found that 289x+144y=gcd(289,144), x=1 and y=(-2).
Now here's my attempt:
289*x=100(mod 144)
289*x=1(mod 144)
289x+144y=1
x=1, y=(-2)
so, s*b = 1*100
and since s*b is less than 144, there is no solution for 289*x=100(mod 144) in the range of [0, 144)
Is this correct?

5. How many integers x in [1,1000] can satisfy the linear congruence equation 289*x=100(mod 144)? Explain how you got the number.
I think, because 289*x=1(mod 144) is a of ax=1(mod m) where a and m are relatively prime, therefore there's only one unique solution. I was messing around and found that x=100 works but I have no idea how to prove it other than saying it's random testing.

Again, thanks in advance.

 

[Tedjn]

2.
You again have the right idea but you are not using the formal definition very cleanly. In order for f(x) to be O(h(x)), for all sufficiently large x, we need f(x) <= M*h(x) for some M. (I've dropped some absolute values, perhaps, but the definition is in that spirit). To be rigorous, you must specify what M is and what "sufficiently large" is. There may be many candidates for M and "sufficiently large," but you need to provide one of each and show that they work.

3.
It's good that you've run through some small n candidates. However, it is still does not convince me for all n. What if n = 2018 and there are many different trees to try? How can you convince me then?

A better way is to think what the statement is saying if it is true. There would be at least two nodes of degree 1. What could they be? Could they be leaf nodes? Must they all be leaf nodes? Break it down like that. If you can identify two nodes with degree 1 no matter what tree, then you have convinced me.

4.
It's true that gcd(289,144) = 1 implies that there exist integers with 289x + 144y = 1. But mod 144, this just means that there exists x such that 289x = 1 - 144y = 1 (mod 144). You are looking instead to prove or disprove whether there exists an x such that 289x = 100 (mod 144).

One way to think about this is to look at 100(289x + 144y) = 100. What does that tell you about any x that satisfies that? Another simpler way to approach this is to consider what 289 mod 144 is. You will find that there is a solution.

5.
Ah, now I see that you did find 100 works. You can find the same thing with both approaches to problem 4. In order for 289x to equal 100 (mod 144), what does that say about x (mod 144)? Do all of those x work? If so, how many are there between 1 and 1000?

 

[devilazy]

*I failed horribly. First I had everything typed up and was about to post, but it failed because I accidentally typed in the wrong password. Then when I was retyping everything, I accidentally hit back and lost everything again. I am really frustrated now and I hope you won't mind my answers being short.*

2. 10(x-1)(x-2)= O(x!)
To be true, 10(x-1)(x-2)<(x!)
Now after a few experiments, 10(x-1)(x-2)<4*(x!) for x = 1,2,3,4,5,6
So, assuming that 10(x-1)(x-2)<4*(x!) is true for all x.
10(x)(x-1)<4*(x+1!) -> 10(x)(x-1)<4*(x+1)(x!) which is true for x= 1,2,3,4,5,6
so with that, I conclude that if M=4, then f(x)=o(h(x)) is true for all x.

3. For any tree with n>1 vertices, there has to be a root vertex which can either have a degree of 1 or a degree up to n-1. Then branching off the root there are the leaves vertices which can only have a direct path to or from another vertex. With that, it's clear to see that a tree will have at least 2 leaves vertices that has a degree of 1, since a tree graph needs to have at least two vertices that are not connected or the graph would become a cycle.

4.289(1)=1(mod 144)
289(100)=100(mod 144)
for any integer k, x=100+144k
The unique solution in 0<=x<144 is
x= 100 mod 144 = 100

5. Since I found that in 4, 100 in a solution for 289x=100(mod144). I opened up the range and used the x=100+144k equation and find that I can have k up to 6 for the equation to stay true and within the range. So in the range of 1 to 1000, there are 6 integers for x that satisfies the equation.

I looked around and tried different methods and these are my newest approach to solving the questions. Once again thank you Tedjn for helping, seems like you're the only one so far so thanks!

 

[Tedjn]

2.
Almost. You need to be careful you don't start with 10x(x-1) < 4*(x+1)! since that is what you are trying to prove by induction. Instead, you would write, 10x(x-1) = x/(x-2)*10(x-1)(x-2) < x/(x-2)*4*(x!) (by induction hyp.) < (x+1)*4*(x!) = 4*(x+1)!, which proves what you want. The only step you might need to justify for yourself is the step after the induction hypothesis, where we claim x/(x-2) < x+1. Otherwise, your solution is fine.

3.
"a tree graph needs to have at least two vertices that are not connected or the graph would become a cycle"

Are you sure that is true? You're on the right track. Each leaf node would have degree 1, so what if the graph has only one leaf node? This is possible. But if this happens, and if all other nodes have degree > 1, would there be a contradiction (something with cycles)?

4./5. Seems to be right.

 

[devilazy]

Oh you have no idea how glad I am to hear that I have finally at least gotten a few more questions on the right track and even two of them right.
Now, I think I know where you're heading with number 2. I just have to prove that x/(x-2) < x+1 then I can conclude that f(x)=O(h(x)).

With number three, I think I just truly understood what you meant by leaf node, I was thinking of branching nodes instead. But yes, if according to the question, there is a contradiction with the statement of having one node with a degree of 1 while others have degrees 2 or more. Now let me see if I can put the answer into a more acceptable form.
For a tree, there has to be a root node which will be the starting point and leaves nodes which will be ends of the tree graph. According to the definition of a tree diagram, the graph has to be connected but can not form cycles. If in a tree graph, all but one node has degree of 2 or more, then there's a contradiction. Let's take a branch of a tree with all nodes with degree of 2+ (assuming that it is possible for now), and just look at one of the end branches with a degree of 2. In this node, it can only span out to two leaves nodes (2 nodes with degree of 1) since this is the last branch of the tree diagram. Even if we allow it to have one of the leaf nodes to branch out again, the same problem occurs as the next branch would have at least 2 nodes of degree of 1. Therefore, a tree has to have at least 2 vertices with a degree of 1 for the graph to be a cycle-free tree.
How does that explanation sound? I think I understand what you want me to prove now but I am not sure if I put the word in right.

4. & 5. :) THANKS!

 

[Tedjn]

I do believe you know why it's true and that you have the right idea. The way I would answer this is first claim that every tree has at least one leaf node. Then, suppose my tree only does have one leaf node, and that every other node has degree at least 2. The root node needs to have at least 2 branches separating from it, each extending into two subtrees. These subtrees cannot be connected to each other, otherwise we have a cycle going back to the root. Hence, we have at least 2 leaf nodes (at least one from each subtree). In other words, we cannot have only one leaf node and a root node of degree >= 2 at the same time. If we have one leaf node, the root node has degree 1 as well, and if we have more than one vertex in the tree, these are different.

 

[devilazy]

thank you tedjn, you helped me answer my questions and I understand the questions better now.