Results 1 to 2 of 2

Math Help - Messages in a graph structure

  1. #1
    Newbie
    Joined
    Jul 2011
    Posts
    9

    Messages in a graph structure

    Hello

    Suppose we have a graph, with unknown number of nodes and edges. It is required to implement a simple broadcast algorithm, where

    -One node, as the initiator, sends one message to its neighbors.

    -Each neighbour, sends the message received to its neighbors, but not the node it initially got it from

    - If a node receives two messages, it will only forward the first copy to its neighbors, and ignore the 2nd message.

    I am trying to find an exact formula for

    Number of messages exchanged = function of number of nodes and edges.


    #### Note: I have heard that the no of msg might be equal to (2*Edges) - n + 1. Not sure if this is right, still trying to figure out a way to prove it.... If you think it is right, please let me know how to prove it ....

    Could someone help me please?

    Many Thanks
    Last edited by suzanne; September 30th 2011 at 04:32 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jul 2011
    Posts
    9

    Re: Messages in a graph structure

    A related question which might help me find the answer .... Does anyone know how to compute the exact number of steps required to traverse a tree in BFS or DFS? Is it 2(nodes-1)?

    Thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Cryptic Messages
    Posted in the Math Topics Forum
    Replies: 5
    Last Post: May 25th 2008, 02:45 AM

Search Tags


/mathhelpforum @mathhelpforum