Help with discrete math proofs

>>323006
Bump pls halp, I fucking suck at this stuff

>>323067
>>323006
seeking genius, pls halp

>>323006
3.
(=>)if e in every possible spanning tree and removing e doesn't disconnect G, then there is a spanning tree of (G - e) thus a spanning tree of G that doesn't contain e. contradiction

(<=)if removing e disconnects G, then every spanning tree must contain e since a spanning tree is a connected subgraph

it has been quite a while so I am not sure about these

>>323182
fuck yeah thank you, anything is appreciated future anon

>>323182
>>323184

>future anon
Oh.. nevermind my clocks just wrong on my laptop, lol. It told you me you had posted that tomorrow

File: aa.png (22KB, 640x400px) Image search: [Google]

22KB, 640x400px

>>323184
1.

>>323006
As an update, a simple google search has solved the first one.

File: aa.png (26KB, 640x400px) Image search: [Google]

26KB, 640x400px

>>323191
gah! I bet there are still some I missed

File: Trees_600.gif (5KB, 301x301px) Image search: [Google]

5KB, 301x301px

>>323192
yes nicer

>>323196
>>323195
Nice you got them all! Do you have the slightest clue about how to approach 2?

>>323225
I don't understand the question 2
does it expect to say: less than "depth of leaf" - "depth of vertex" number of edges

>>323230
>In a full binary tree, find the expected value of the number of edges from a randomly chosen vertex to the nearest leaf

My take on it is that we start at a radomly selected vertex, and we want to know how many edges we can expect to travel to the nearest leaf.

However, I don't really know how to approach it, which I think is more of what you were getting at. Considering an infinite tree, we would have an infinite number of branches but no leaves, right? So I don't really know how to start chipping away the problem, unless it's by some crazy form of induction.

>>323196
>>323195
I thought trees were special cases of graphs, in that they were directed graphs where one vertex was designated the root. And that two trees with the same topology aside from a different root node were not isomorphic, because they're trees not general graphs.

For example, should there not be two non-isomorphic trees with three vertices: \
\
and \/?

>>323269
You seem like the kind of guy who can answer #2, it's due by midnight

>>323247
It's a full binary tree, which means that (n+1)/2 of its nodes are leaves, (n+1)/4 are parents of leaves, (n+1)/8 are parents of parents of leaves, and so on.

I suspect if you looked at the sum 0x/2+1x/4+2x/8+3x/16..... you'd find it converges and the limit will be the expected distance (in the probability sense of the term "expected") a random node will be from a leaf.

>>323186
Your timezone is wrong, not your clock. The server sends the time in UTC, then uses JS in the browser to convert it to a local time.

>>323006
>2. In a full binary tree, find the expected value of the number of edges from a randomly chosen vertex to the nearest leaf.

Assuming each node is equally likely, P[node]=1/n

Exp=
root: [log2(n+1)-1]/n
+level 2: 2^1*[log2(n+1)-2]/n
+level 3: 2^2*[log2(n+1)-3]/n
...
+leaves: 2^[log2(n+1)-1] * [log2(n+1)-1-log2(n+1)+1]/n

Exp= 1/n∑2^i [log2(n+1)-1 - i] i from 0 to log2(n+1)-1 = [2^(log2(n+1)-1 + 1) - log2(n+1) - 1]/n = (n-log2(n+1))/n = 1 + log_2(n+1)/n

>>323273
man I've really gotta study a lot more for this upcoming final. Thanks for the response, I just really struggle with this stuff, but I think it's really cool.

File: 1281120094394.png (81KB, 800x600px) Image search: [Google]

81KB, 800x600px

>>323277
>1 + log_2(n+1)/n
1 - log_2(n+1)/n

Damn minus signs.

>>323276
yeah I lazily set up Arch. Clock is right but timezone is wrong would've been a mroe acccurate statement I suppose

>>323277
thank you very much anon, I would like to be able to think this well by the end of the term

>>323247
You can also traverse an infinite tree by recursively visiting the left child (unless you came from there), then the right child then the parent.

If you start doing this from the leftmost leaf node of an infinite binary tree, you'll visit every node, starting with the leftmost leaf, and ending (after visiting an infinite number of nodes) at the root.

So we can observe that an infinite tree can have leaves, whilst still having as many nodes as there are integers.

>>323277
What does Exp mean?

>>323288
expection, nevermind

>>323288
Expected Value which in this case is probability of a node * height of the node above leaf level summed over all the nodes.

File: hmw.png (16KB, 574x228px) Image search: [Google]

16KB, 574x228px

Does this look right?

>>323298
on the line with summation, I've since edited out the "-i"

and fuck I forgot to correct the negative you mentioned, on that now

>>323300
>>323298
wait nvm the i is supposed to be there..

>>323301
>>323300
>>323298
Just changed every log2 to log_2 also so it will come out right on latex

File: Screenshot_2017-05-30_05-05-26.png (16KB, 531x218px) Image search: [Google]

16KB, 531x218px

Third line from the bottom I fixed the fucked up exponent, I think it's looking good I'm kinda following the math.

>>323298
>>323303

If I was the grader, I would fail you. Explain more.

File: aaa.png (32KB, 643x223px) Image search: [Google]

32KB, 643x223px

>>323269
you are thinking about special cases of trees. Definition of a tree is rather simple

>>323380
Interesting. So a tree(graph theory) is what CS would call an acyclic graph, and a tree(CS) is what graph theory would call a directed tree?