Hey there! Sign in to join this conversationNew here? Join for free
    • Thread Starter
    Offline

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

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

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

    Let E={e_1,...,e_{n\choose2}}. So the number of subsets of this is 2^{n\choose2}which is the number of graphs on nvertices right?

    But how do I delete the ones that can't be digraphs?? I have no idea.
    • Study Helper
    Online

    13
    Study Helper
    (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 v_1v_2, but not the arc v_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?
    • Thread Starter
    Offline

    17
    ReputationRep:
    (Original post by ghostwalker)
    The nC2 number of edges refers to an undirected graph, and so would, for example, include the arc v_1v_2, but not the arc v_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
    • Study Helper
    Online

    13
    Study Helper
    (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
    • Thread Starter
    Offline

    17
    ReputationRep:
    (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
     
    • Study Helper
    Online

    13
    Study Helper
    (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 \displaystyle |E|=\prod_{i\not= j} |E_{ij}| would enumerate all possible digraphs, but include ones where you had directed edges e_{i,j} as well as e_{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 i\not= j

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

    And restrict the number of combinations in our product |E_{i,j}E_{j,i}| to just valid combinations for a digraph, i.e. just 3.
    • Thread Starter
    Offline

    17
    ReputationRep:
    (Original post by ghostwalker)
    OK. It's possible to adapt that final example, with a bit of messing around.

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

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

    And restrict the number of combinations in our product |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
    Attached Images
     
    • Thread Starter
    Offline

    17
    ReputationRep:
    Or a simpler solution

    Posted from TSR Mobile
    Attached Images
     
    • Study Helper
    Online

    13
    Study Helper
    (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.

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

    \prod_{i&lt; j}E_{i,j} is the product of n(n-1)/2 = nC2 elements.
    • Thread Starter
    Offline

    17
    ReputationRep:
    (Original post by ghostwalker)
    At first glance, I think there is an error in your working and the book.

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

    \prod_{i&lt; 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.
    • Thread Starter
    Offline

    17
    ReputationRep:
    (Original post by ghostwalker)
    At first glance, I think there is an error in your working and the book.

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

    \prod_{i&lt; 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
    • Thread Starter
    Offline

    17
    ReputationRep:
    Posted from TSR Mobile
    Attached Images
     
    • Study Helper
    Online

    13
    Study Helper
    You have the same problem as before. If you take the product over i\not= j there are n(n-1) sets, not nC2, and the sets E_{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.
    • Thread Starter
    Offline

    17
    ReputationRep:
    (Original post by ghostwalker)
    You have the same problem as before. If you take the product over i\not= j there are n(n-1) sets, not nC2, and the sets E_{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.
    • Study Helper
    Online

    13
    Study Helper
    (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.
    • Thread Starter
    Offline

    17
    ReputationRep:
    (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
 
 
 
Poll
Do you agree with the PM's proposal to cut tuition fees for some courses?
Useful resources

Make your revision easier

Maths

Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

Equations

How to use LaTex

Writing equations the easy way

Student revising

Study habits of A* students

Top tips from students who have already aced their exams

Study Planner

Create your own Study Planner

Never miss a deadline again

Polling station sign

Thinking about a maths degree?

Chat with other maths applicants

Can you help? Study help unanswered threads

Groups associated with this forum:

View associated groups

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

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.