Results 1 to 5 of 5

Math Help - how many orientations does a simple graph g have?

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    38

    how many orientations does a simple graph g have?

    hi

    I'm stuck on the followinq question

    How many orientations does a simple graph g have?

    for one vertex there is one, just the isolated vertex

    for two vertices there are 3, i think...two isolated vertices u and v, a digraph with arc uv and a digraph with arc vu.

    i'm not sure where to go from here

    thanks for your help
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Check definition of "simple" graph

    Your description of your calculation already lets you count how many directed graphs there are. Between each pair of points, there seem to be 3 possibilities - no edge, an edge directed one way, an edge directed the other. You can count how many pairs of points there are - n choose 2 - points. So you've counted
    <br />
3 ^ { \binom{n}{2} }<br />
    graphs.

    However there is another definition of simple graph that doesn't allow for directed vertices. If so, your calculation overcounts because there's only 2 possibilities - no edge, or yes, there's an edge.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2008
    Posts
    38
    hi, i just want to check i understand

    i'm working from the definition of a simple graph which states that g contains no loops or multiple edges, so i don't think i need to worry about overcounting

    i understand now that i need to divide into the three cases for each pair of vertices

    using your formula i get

    n number of orientations
    1 1
    2 3
    3 9
    4 24
    ....

    are these values correct?


    thanks again for your help
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Nov 2009
    Posts
    277
    Thanks
    2

    Definition of simple graph

    I'm still not sure if you're working with simple graphs or simple directed graphs. The definition I'm getting from the web for simple graph is: "unweighted, undirected" graph. Please note the "undirected"!

    The formula is not being interpreted correctly. The
    <br />
\binom {n}{m} = \frac {n!}{m!(n-m)!}<br />

    so the first few values are:
    <br />
\binom {2}{2} = 1, \implies 3^{\binom{2}{2}} = 3<br />
    <br />
\binom {3}{2} = 3, \implies 3^{\binom{3}{2}} = 27<br />
    <br />
\binom {4}{2} = 6, \implies 3^{\binom{4}{2}} = 729<br />
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    Posts
    38
    I need the graphs to be directed since i'm looking for the number of orientations.

    i think that if i have 3 vertices and and a directed edge (arc) between 1 pair i count this once not 6 times for alternate direction and the choice of the two other pairs.

    this means that for n=1,2,3,4,5,.... i get 1,2,7,42,582

    (this sequence is from wolfram mathworld)

    im trying to find the formula for this sequence, does anyone know it?

    thank you
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. k-regular simple graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 14th 2010, 05:54 AM
  2. simple graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 29th 2010, 11:54 AM
  3. A simple graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 1st 2009, 01:38 PM
  4. Very simple graph question
    Posted in the Geometry Forum
    Replies: 1
    Last Post: April 20th 2009, 11:17 AM
  5. Vertices of a simple graph
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 8th 2007, 04:37 PM

Search Tags


/mathhelpforum @mathhelpforum