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.

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,

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.

Relevance
• Anonymous
7 years ago

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.