MATH1081 Discrete Maths (1 Viewer)

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
Re: UNSW MATH1081 Discrete Maths

When creating the table to show a graph is isomorphic... how do I work out what vertex pairs with the second graph's vertex? Does it even matter, as long as their degrees are the same?
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
Re: UNSW MATH1081 Discrete Maths

When creating the table to show a graph is isomorphic... how do I work out what vertex pairs with the second graph's vertex? Does it even matter, as long as their degrees are the same?
Nevermind, I realise it does matter and you can find it by looking at the degree of what that vertex is connected to and then comparing.
 

KingOfActing

lukewarm mess
Joined
Oct 31, 2015
Messages
1,016
Location
Sydney
Gender
Male
HSC
2016
Re: UNSW MATH1081 Discrete Maths

When creating the table to show a graph is isomorphic... how do I work out what vertex pairs with the second graph's vertex? Does it even matter, as long as their degrees are the same?
It does matter - consider these two non-isomorphic graphs with the same degree sequences.



In general I don't think there's a nice way to prove two graphs are isomorphic - the degrees sequences being equal is necessary but not sufficient, and to prove they are isomorphic you usually have to explicitly provide the bijection
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
Re: UNSW MATH1081 Discrete Maths

Show if G is self-complementary then G has 4k or 4k + 1 vertices for some integer k.


So I know for G, edges = [n(n-1)]/4. With n = vertices. Do I use this to show?
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Re: UNSW MATH1081 Discrete Maths

Show if G is self-complementary then G has 4k or 4k + 1 vertices for some integer k.


So I know for G, edges = [n(n-1)]/4. With n = vertices. Do I use this to show?
If we know the no. of edges is n(n-1)/4, since the no. of edges is an integer, what does this tell us about n?
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
edit nvm lol
 
Last edited:

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
Any tips for easily redrawing graphs as planar maps?
 

KingOfActing

lukewarm mess
Joined
Oct 31, 2015
Messages
1,016
Location
Sydney
Gender
Male
HSC
2016
I'm not sure if I've done this question correctly. "Find the number of 20 letter words using the capital English alphabet containing the subword 'MATHS'"

I did:


Since you have to place "MATHS" somewhere, and then choose the remaining 15 letters. But this overcounts when "MATHS" appears twice, so you have to subtract that, which undercounts, etc.
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
Help plssss

How do I simplify this:

SUM[k=2..N+1] k^3 - SUM[k=0..N-1] k^3

I need to show it = (N+1)^3 + N^3 - 1.


I am very confused.
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
Help plssss

How do I simplify this:

SUM[k=2..N+1] k^3 - SUM[k=0..N-1] k^3

I need to show it = (N+1)^3 + N^3 - 1.


I am very confused.
Almost all the terms cancel. If you can't see it immediately, it might help you to write out the terms of each sum in long notation.
 

KingOfActing

lukewarm mess
Joined
Oct 31, 2015
Messages
1,016
Location
Sydney
Gender
Male
HSC
2016
Help plssss

How do I simplify this:

SUM[k=2..N+1] k^3 - SUM[k=0..N-1] k^3

I need to show it = (N+1)^3 + N^3 - 1.


I am very confused.
write them with common upper lower bounds, and take everything else out of the sum

(sum(k=2..n-1)k^3 + n^3 + (n+1)^3) - (0^3 + 1^3 + sum(k=2..n-1)k^3 + 0^3 +1^3) = (n+1)^3 + n^3 - 1
 

leehuan

Well-Known Member
Joined
May 31, 2014
Messages
5,805
Gender
Male
HSC
2015
I'm not sure if I've done this question correctly. "Find the number of 20 letter words using the capital English alphabet containing the subword 'MATHS'"

I did:


Since you have to place "MATHS" somewhere, and then choose the remaining 15 letters. But this overcounts when "MATHS" appears twice, so you have to subtract that, which undercounts, etc.
Yes, you need to use the inclusion exclusion principle.
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
write them with common upper lower bounds, and take everything else out of the sum

(sum(k=2..n-1)k^3 + n^3 + (n+1)^3) - (0^3 + 1^3 + sum(k=2..n-1)k^3 + 0^3 +1^3) = (n+1)^3 + n^3 - 1
Oh thanks lol. For some reason I just forgot how to do all sum questions, but after 2 hours I know get it (fml).
 

Flop21

Well-Known Member
Joined
May 12, 2013
Messages
2,810
Gender
Female
HSC
2015
wtf am I doing wrong??

111x ≡ 75 (mod 321)


I find gcd(111,321) = 3. So divide original equation by 3 -> 37x ≡ 28 (mod 107).

Now applying Euclid's algo, I get, 1 = 9(107) - 26(37). So -26 * 28 = -728.

This does not give me the answer of 99,206,313 mod 321. Why???
 

InteGrand

Well-Known Member
Joined
Dec 11, 2014
Messages
6,109
Gender
Male
HSC
N/A
wtf am I doing wrong??

111x ≡ 75 (mod 321)


I find gcd(111,321) = 3. So divide original equation by 3 -> 37x ≡ 28 (mod 107).

Now applying Euclid's algo, I get, 1 = 9(107) - 26(37). So -26 * 28 = -728.

This does not give me the answer of 99,206,313 mod 321. Why???
75 divided by 3 is not 28.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top