MATH1081 Discrete Maths (3 Viewers)

[seanieg89]

Re: Discrete Maths Sem 2 2016

Definitely not a reduction or a heuristic, the rewording has exactly the same mathematical content. An abstraction perhaps. When we count things in combinatorics, we are almost always counting sets or functions between sets. Sometimes the concept behind such a problem is clearer if you throw away all the irrelevant information and work with these abstract objects.

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Is it just me, or do any of you subconsciously say "such that" after saying "there exists"?

 

[Shadowdude]

Re: Discrete Maths Sem 2 2016

Is it just me, or do any of you subconsciously say "such that" after saying "there exists"?

example?

 

[leehuan]

Re: Discrete Maths Sem 2 2016

example?

Whilst i don't necessarily "write" s.t. without good reason, I just end up saying (exists some x in S such that...)

 

[Shadowdude]

Re: Discrete Maths Sem 2 2016

Whilst i don't necessarily "write" s.t. without good reason, I just end up saying (exists some x in S such that...)

i always write s.t. because that looks really schematic

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Yeah fair enough. I'm not too sure why some past paper questions don't have s.t. there

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Only problem is sometimes s.t. could also mean "subject to". Best to just write the full thing if you want/need to avoid ambiguity (from the context it'll often be clear though which was meant).

 

[leehuan]

Re: Discrete Maths Sem 2 2016

Only problem is sometimes s.t. could also mean "subject to". Best to just write the full thing if you want/need to avoid ambiguity (from the context it'll often be clear though which was meant).

Ah really? Didn't expect that one coming.

Well I was also told that 'such that' can also be replaced with either : or |
Need confirmation though

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Ah really? Didn't expect that one coming.

Well I was also told that 'such that' can also be replaced with either : or |
Need confirmation though

('Subject to' will often be seen in areas like constrained optimisation, for example.)

 

[leehuan]

Re: Discrete Maths Sem 2 2016

('Subject to' will often be seen in areas like constrained optimisation, for example.)

Ah right... Lagrange multiplier theorem...

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

Not sure if this is what you mean, but say you know the vertex degrees are 2, 2, 2, 2, 3, 4, 4, then to test if such a graph exists then do this:

Write the degrees in ascending order:

2 2 2 2 3 4 4

Take the last number, get rid of it, and subtract 1 from the previous N numbers (where N is the last number).

In this case, get rid of the 4, then subtract 1 from the previous 4 numbers.

2 2 1 1 2 3

Re-order into ascending order:

1 1 2 2 2 3

Repeat:

1 1 1 1 1

You continue doing this until you either get a contradiction or a possible graph. In this case it is clear you can not graph this as the sum of the degrees is odd, contradiction.

What's the point of doing all this when you can just use the handshaking theorem at the beginning to see if the graph exists?

 

[leehuan]

Re: Discrete Maths Sem 2 2016

I realised a bit later on that the method was for graphs in general.

Yeah, I kinda wanted the existence of a simple graph, not any graph

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

I realised a bit later on that the method was for graphs in general.

Yeah, I kinda wanted the existence of a simple graph, not any graph

My tutor said something along the lines of : No simple graph if biggest vertex degree >= # vertices or or something like that. Not too sure havn't tried it out yet.

 

[leehuan]

Re: Discrete Maths Sem 2 2016

My tutor said something along the lines of : No simple graph if biggest vertex degree >= # vertices or or something like that. Not too sure havn't tried it out yet.

Is that necessary and sufficient?

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

Is that necessary and sufficient?

Not too sure. Haven't even tried any questions about it yet.

 

[leehuan]

Re: Discrete Maths Sem 2 2016

See I was kinda hoping for a cheat way out; a necessary AND sufficient condition :')

Not like those damn Hamilton circuits

 

[Drsoccerball]

Re: Discrete Maths Sem 2 2016

Okay figured it out:
- First we check if the graph exists by checking if all the degrees of each vertex sum to an even number.
- We then follow RealiseNothing's approach.
- We take note that if the vertex with highest degree is equal to or greater than the amount of vertices's if this is true a simple graph does not exist.
- You eliminate the vertex with the higher degree and subtract 1 from each of the vertex degrees until the number of times you subtract equal to the degree of the vertex you deleted. (I don't think this needs an explanation)
- You keep doing this and if at any point the max degree is greater than or equal to the amount verticies then there is no simple graph.
- If you reach 0 then a simple graph exists

Example:

4, 4, 3, 2, 2, 1

3, 2, 1, 1, 1

1, 1

0

Therefore a simple graph exists.

5, 5, 3, 2, 2, 1

4, 2, 1, 1

Therefore since the highest degree is equal to the total number of vertices's there is no simple graph.

 

[leehuan]

Re: Discrete Maths Sem 2 2016








So, admittedly it took me a bit too long to figure out that phi(x) = exp(ix). But now I'm a bit stumped.

Without assuming anything such as d/dx exp(ix) = i.exp(ix) (or rather preferably not, as discrete maths isn't expected to know this), how would you prove the injective and surjective part properly? Cause the answers just restated what we were trying to prove and that was just unconvincing

 

[InteGrand]

Re: Discrete Maths Sem 2 2016

Main idea is that exp(ix) will be onto because clearly any complex number on the unit circle can be written in the form e^{ix}, and it'll be one-to-one because two "essentially different" x's clearly yield two different points on the unit circle (as they'll have essentially different angles).

 

[seanieg89]

Re: Discrete Maths Sem 2 2016