The Student Room Group

Combinatorics digraphs question

A digraph G=G(V,E)G = G(V,E) on the set of vertices VVis a graph where every edge eEe ∈ Eis directed. (Note that double arrows are not allowed in a digraph.) How many digraphs on nnvertices are there?

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

EDIT: Just read a definition that for complete graphs KnK_nthere are (n2)n\choose2edges. So the number of possible graphs on nnvertices is basically the number of ways to choose a set of edges from a maximum of (n2)n\choose2 edges.

Let E=E={e1,...,e(n2)e_1,...,e_{n\choose2}}. So the number of subsets of this is 2(n2)2^{n\choose2}which is the number of graphs on nnvertices right?

But how do I delete the ones that can't be digraphs?? I have no idea.
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 v1v2v_1v_2, but not the arc v2v1v_2v_1 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?
Original post by ghostwalker
The nC2 number of edges refers to an undirected graph, and so would, for example, include the arc v1v2v_1v_2, but not the arc v2v1v_2v_1 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
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
(edited 9 years ago)
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
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 E=ijEij\displaystyle |E|=\prod_{i\not= j} |E_{ij}| would enumerate all possible digraphs, but include ones where you had directed edges ei,je_{i,j} as well as ej,ie_{j,i}, 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 iji\not= j

E=ijEij=i<jEijEji\displaystyle |E|=\prod_{i\not= j} |E_{ij}|=\prod_{i< j} |E_{ij}E_{ji}|

And restrict the number of combinations in our product Ei,jEj,i|E_{i,j}E_{j,i}| to just valid combinations for a digraph, i.e. just 3.
(edited 9 years ago)
Original post by ghostwalker
OK. It's possible to adapt that final example, with a bit of messing around.

The product E=ijEij\displaystyle |E|=\prod_{i\not= j} |E_{ij}| would enumerate all possible digraphs, but include ones where you had directed edges ei,je_{i,j} as well as ej,ie_{j,i}, 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 iji\not= j

E=ijEij=i<jEijEji\displaystyle |E|=\prod_{i\not= j} |E_{ij}|=\prod_{i< j} |E_{ij}E_{ji}|

And restrict the number of combinations in our product Ei,jEj,i|E_{i,j}E_{j,i}| 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
(edited 9 years ago)
Or a simpler solution

Posted from TSR Mobile
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.

ijEi,j\prod_{i\not= j}E_{i,j} is the product of n(n-1) elements.

i<jEi,j\prod_{i< j}E_{i,j} is the product of n(n-1)/2 = nC2 elements.
Original post by ghostwalker
At first glance, I think there is an error in your working and the book.

ijEi,j\prod_{i\not= j}E_{i,j} is the product of n(n-1) elements.

i<jEi,j\prod_{i< j}E_{i,j} 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.
Original post by ghostwalker
At first glance, I think there is an error in your working and the book.

ijEi,j\prod_{i\not= j}E_{i,j} is the product of n(n-1) elements.

i<jEi,j\prod_{i< j}E_{i,j} 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


You have the same problem as before. If you take the product over iji\not= j there are n(n-1) sets, not nC2, and the sets Ei,j,Ej,iE_{i,j},E_{j,i} 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.
(edited 9 years ago)
Original post by ghostwalker
You have the same problem as before. If you take the product over iji\not= j there are n(n-1) sets, not nC2, and the sets Ei,j,Ej,iE_{i,j},E_{j,i} 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.
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.
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

Quick Reply

Latest