You are Here: Home >< Maths

# Combinatorics digraphs question watch

1. A digraph on the set of vertices is a graph where every edge is directed. (Note that double arrows are not allowed in a digraph.) How many digraphs on vertices are there?

I am trying to think how many possible graphs there can be with vertices but I don't know how many there can be because how can you know what the maximum possible edges there can be with vertices?

EDIT: Just read a definition that for complete graphs there are edges. So the number of possible graphs on vertices is basically the number of ways to choose a set of edges from a maximum of edges.

Let {}. So the number of subsets of this is which is the number of graphs on vertices right?

But how do I delete the ones that can't be digraphs?? I have no idea.
2. (Original post by cooldudeman)

But how do I delete the ones that can't be digraphs?? I have no idea.
The nC2 number of edges refers to an undirected graph, and so would, for example, include the arc , but not the arc since they are they same; hope that made sense.

I would try a slightly different method.

There are nC2 possible pairings of vertices.

Then for any given pair, how many possible ways can they relate, or not, in the digraph?
3. (Original post by ghostwalker)
The nC2 number of edges refers to an undirected graph, and so would, for example, include the arc , but not the arc since they are they same; hope that made sense.

I would try a slightly different method.

There are nC2 possible pairings of vertices.

Then for any given pair, how many possible ways can they relate, or not, in the digraph?
3? Say we have edges u and v, either an edge is directed from u to v, edge is directed from v to u or no edge between u and v.
I THINK we are meant to use the product rule but i have no idea how that comes in
4. (Original post by cooldudeman)
3? Say we have edges u and v, either an edge is directed from u to v, edge is directed from v to u or no edge between u and v.
I THINK we are meant to use the product rule but i have no idea how that comes in
Yep 3 choices for each pair and nC2 pairs, hence 3^(nC2) digraphs.

Which product rule are you refering to? Is this what you were doing with the power set, if so, I don't see how it can relate
5. (Original post by ghostwalker)
Yep 3 choices for each pair and nC2 pairs, hence 3^(nC2) digraphs.

Which product rule are you refering to? Is this what you were doing with the power set, if so, I don't see how it can relate
Nah nothing to do with the power sets. Its this.

Posted from TSR Mobile
Attached Images

6. (Original post by cooldudeman)
Nah nothing to do with the power sets. Its this.

Posted from TSR Mobile
OK. It's possible to adapt that final example, with a bit of messing around.

The product would enumerate all possible digraphs, but include ones where you had directed edges as well as , i.e. 2-loops, which are not allowed.

So how to remove these - perhaps this what you were aiming at originally.

One way is to rearrange our original product and pair up the sets. Since

And restrict the number of combinations in our product to just valid combinations for a digraph, i.e. just 3.
7. (Original post by ghostwalker)
OK. It's possible to adapt that final example, with a bit of messing around.

The product would enumerate all possible digraphs, but include ones where you had directed edges as well as , i.e. 2-loops, which are not allowed.

So how to remove these - perhaps this what you were aiming at originally.

One way is to rearrange our original product and pair up the sets. Since

And restrict the number of combinations in our product to just valid combinations for a digraph, i.e. just 3.
Im finding it hard to understand your penultimate line... the i < j stuff.

How would I set it out like tgat example though? Would I let E_ij={0,1,2} instead? So 0 reps that no edge exists between i and j, 1 means edge directed from i to j, 2 means edge directed from j to i. But if that's the case, where would you ytet the nC2 from since it wont be in line with the solution since in the solution, they used the fact that E_ij={0,1}...

Here is the full solution to that example btw.

Posted from TSR Mobile
Attached Images

8. Or a simpler solution

Posted from TSR Mobile
Attached Images

9. (Original post by cooldudeman)
Or a simpler solution

Posted from TSR Mobile
At first glance, I think there is an error in your working and the book.

is the product of n(n-1) elements.

is the product of n(n-1)/2 = nC2 elements.
10. (Original post by ghostwalker)
At first glance, I think there is an error in your working and the book.

is the product of n(n-1) elements.

is the product of n(n-1)/2 = nC2 elements.
oh sorry, that was the same solution to that example in the pic. I just wanted to know how to answer this one with the same layout if its possible.
11. (Original post by ghostwalker)
At first glance, I think there is an error in your working and the book.

is the product of n(n-1) elements.

is the product of n(n-1)/2 = nC2 elements.
I tried it again. I labelled the 0, 1 and 2 so that it would make sense. What do you think?

Posted from TSR Mobile
12. Posted from TSR Mobile
Attached Images

13. You have the same problem as before. If you take the product over there are n(n-1) sets, not nC2, and the sets are related; if one is {0}, so must the other be, and if one is {1}, the other must be {2}.

The confusion comes from the fact that the book in incorrect, IMO.
14. (Original post by ghostwalker)
You have the same problem as before. If you take the product over there are n(n-1) sets, not nC2, and the sets are related; if one is {0}, so must the other be, and if one is {1}, the other must be {2}.

The confusion comes from the fact that the book in incorrect, IMO.
Are you saying the solution to egII on post 7 is incorrect? just wanna confirm.
15. (Original post by cooldudeman)
Are you saying the solution to egII on post 7 is incorrect? just wanna confirm.
The final answer is correct, but the methodology isn't - unless I'm being totally stupid.
16. (Original post by ghostwalker)
The final answer is correct, but the methodology isn't - unless I'm being totally stupid.
Oh man, now im totally confused. I guess ill just ask my lecturer.

Thanks a lot though.

Posted from TSR Mobile

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: February 1, 2015
Today on TSR

### The most controversial member on TSR?

Who do you think it is...

### Is confrontation required?

Discussions on TSR

• Latest
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams

## Groups associated with this forum:

View associated groups
Discussions on TSR

• Latest

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE