Yahoo Answers is shutting down on May 4th, 2021 (Eastern Time) and beginning April 20th, 2021 (Eastern Time) the Yahoo Answers website will be in read-only mode. There will be no changes to other Yahoo properties or services, or your Yahoo account. You can find more information about the Yahoo Answers shutdown and how to download your data on this help page.

OK asked in Science & MathematicsMathematics · 7 years ago

GRAPH: Among all possible connected networks with 6 nodes what is the largest and shortest possible diameter?

Hi,

I am kindly asking you the above question.

Thank you very much in advance for your prompt answer.

With kindest regards,

FFF

Update:

• N={1,…,n} nodes, vertices, players;

Graph theory - Please see at http://en.wikipedia.org/wiki/Graph_theory

• Network (N,g) where

- N={1,…,n} nodes, vertices, players, and

- g in {0,1}n×n adjacency matrix

• (N,g) is connected if there is a path between every two nodes

• Walk from i1 to iK: a sequence of nodes (i1,i2,..., iK) and sequence of links (i1i2,i2i3,...,iK‐1iK) such that ik‐1ik in g for each k

• Path is a walk (i1,i2,... iK) with each node ik distinct;

• Diameter is largest geodesic (largest shortest path)

– if unconnected, of largest component... ;

• geodesic is a shortest path between two nodes;

• Path is a walk (i1,i2,... iK) with each node ik distinct

• Component: maximal connected subgraph where

– (N’,g’) is a subset of (N,g)

– (N’,g’) is connected

– i in N’ and ij in g implies j in N’ and ij in g’

Update 2:

Hi freond1,

Thank you for your answer. The two answers should be using permutations or combinations. So, the answer should be among answers:

6, 2 or 6, 4 or 5, 2 or 5, 1

Network is used for the study in real life like for example Social networks or economic networks.

1 Answer

Relevance
  • Anonymous
    7 years ago
    Favorite Answer

    If the 6 nodes were just strung out in a line with each connected to only the adjoining nodes, it would be 5

    If every node was connected to every other node, it would be 1.

    I think those are the max and min. You obviously can't have a minimal path that goes through more than 5 edges, and I've given you an example where 5 are required.

    And you can't have diameter of less than 1, and I've given an example where 1 is all it takes.

    BWDIK--I don't know a lot of graph theory, but these questions are interesting so I try to learn something by attempting an answer.

    What's the difference between a network and a graph? Definitions seem to require a network to have values assigned to edges, but that's not relevant to the question, so I'm wondering if I'm missing some part of the defintion.

Still have questions? Get your answers by asking now.