Results 1 to 3 of 3

Thread: What kind of graph do I have?

  1. #1
    Newbie
    Joined
    Feb 2018
    From
    Draper, Utah
    Posts
    2

    What kind of graph do I have?

    Greetings! I'm an old programmer who occasionally has a math question I need help with. I'm currently working with some data structures which form some kind of graph, and I'm trying to figure out exactly what kind of graph it is so that I can look up algorithms that might apply. I'm hoping if I describe the properties of the nodes and edges, someone will recognize it and let me know what official name applies.

    The nodes are connected by directed edges; that is, each edge is connected to a left node and a right node. A node may have an arbitrary number of edges to their left and an arbitrary number of edges to their right. An edge may be traversed in either direction, but the value of an associated function of the edge depends on the direction it is traversed. There are no cycles. Each node connects directly to at least one other node. Between any two nodes, there is always exactly one unique path.

    I want to say this is a directed acyclic graph but I don't know if it's something more specific than that. Conceptually, my task is to construct a table of every pair of nodes (i, j) and compute the sum of functions of all the edges along the path between i and j, (and also the inverse path from j to i).

    If there are N nodes, there are N^2 pairs of nodes (and therefore N^2 paths) to be computed. Each path would have an average of about N/2 edges, so a naive approach would involve considering on the order of (N^3)/2 edges. I am hoping to find an algorithm that will grow more slowly than this as a function of N.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,387
    Thanks
    1345

    Re: What kind of graph do I have?

    Quote Originally Posted by mheins57 View Post
    Greetings! I'm an old programmer who occasionally has a math question I need help with. I'm currently working with some data structures which form some kind of graph, and I'm trying to figure out exactly what kind of graph it is so that I can look up algorithms that might apply. I'm hoping if I describe the properties of the nodes and edges, someone will recognize it and let me know what official name applies.

    The nodes are connected by directed edges; that is, each edge is connected to a left node and a right node. A node may have an arbitrary number of edges to their left and an arbitrary number of edges to their right. An edge may be traversed in either direction, but the value of an associated function of the edge depends on the direction it is traversed. There are no cycles. Each node connects directly to at least one other node. Between any two nodes, there is always exactly one unique path.

    I want to say this is a directed acyclic graph but I don't know if it's something more specific than that. Conceptually, my task is to construct a table of every pair of nodes (i, j) and compute the sum of functions of all the edges along the path between i and j, (and also the inverse path from j to i).

    If there are N nodes, there are N^2 pairs of nodes (and therefore N^2 paths) to be computed. Each path would have an average of about N/2 edges, so a naive approach would involve considering on the order of (N^3)/2 edges. I am hoping to find an algorithm that will grow more slowly than this as a function of N.
    Based on your description, the graph is connected (as there is always a path between every two nodes, and the path is unique). It sounds to me like you have a tree.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2018
    From
    Draper, Utah
    Posts
    2

    Re: What kind of graph do I have?

    Thanks, you must be right about it being a tree. It has no distinguished root though. Here's an example:

    What kind of graph do I have?-example-graph.png

    I guess I could just pick a node at random and call it the root (Is there a better way?). I'll need to calculate a sort of distance function between every pair of nodes, so I should be able to sweep through the tree once and store distances from each node to the root, and calculate the distance from A to B as a distance from A to root plus distance from root to B minus 2 * distance from the lowest common ancestor to the root. Any advice on a quick way to locate the lowest common ancestor of A and B?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. What kind of graph would y^2 + 8x = 0 be?
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Aug 14th 2011, 11:02 AM
  2. 3 of a kind
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 15th 2010, 06:02 AM
  3. Three of a kind
    Posted in the Statistics Forum
    Replies: 1
    Last Post: May 8th 2009, 01:40 AM
  4. What kind of a graph is this?
    Posted in the Calculus Forum
    Replies: 4
    Last Post: Apr 30th 2009, 05:53 AM

Search Tags


/mathhelpforum @mathhelpforum