Networks - Exam Question

[Daenerys Targaryen]

On the MAV 2012 Trial Exam there was a question some-what like this:

When there are 4 vertices what is the maximum and minimum amount of two step dominances are there possibly?

Is there a specific way to figure this out or is it general knowledge?

[Felicity Wishes]

Out of curiosity, what was the answer?

[Daenerys Targaryen]

Have no idea. We had some compulsory practice exam and it was on it. That question really bugged me

[Yendall]

General knowledge I think.

So you have four points: A, B C, D.
If you use formulas you can determine how many edges the graph will have.



So we have 4 vertices:





So we know we have 4 vertices and 6 edges.



How i see this is from each vertex, how many two step dominances are possible, so:

x 2
x 2
x 2

Then this would work for all vertices, so there would be different two step-dominance's.

I'm not sure if that's right or not, this question is pretty complicated.

[Daenerys Targaryen]

Well yeah, i know how many edges there are... but... argh crap question lol

[Yendall]

Well yeah, i know how many edges there are... but... argh crap question lol

Yeah I know, but if you know how many edges there are you can assume that it is a complete graph where every node can reach every other node. So you set it up like I did, and figure out that every node can access every other node twice.

[Daenerys Targaryen]

Haha cool. Thanks bud

[Felicity Wishes]

Did a Further practice exam and had that same question!

[Daenerys Targaryen]

Was it the MAV2012; Last networks question?

[Felicity Wishes]

Was it the MAV2012; Last networks question?

Yes. I had no idea what to do at all. At least the matrices questions were easy enough.

[oneialex]

The question doesn't even specify if the graph is complete or not.. 4 vertices could imply that they're not even connected. Very bad question if that's all there is to it.

[julie9300]

Did this for my trial exam at school and absolutely hated that question.

anyways so i checked the solutions and it says:

Maximum=8
This will occur when the competition is as even as possible i.e. with 2 players having 2 wins and 2 players having 1 win (as in the original scenario)

Minimum=4
This will occur when the competition is as 'one-sided' as possible i.e. when 1 player has 3 wins (giving 3 two-step dominances), 1 player having 2 wins (giving 1 two-step dominance), 1 player having 1 win (no two-step dominances) and 1 player have 0 wins (no two-step dominances)