The diameter of an undirected unweighted graph G, denoted by diam (G), is the maximum distance...

  

Transcribed Image Text:

The diameter of an undirected unweighted graph G, denoted by diam (G), is the maximum distance between any pair of nodes in G. Equivalently, it is the longest of the shortest paths between all pairs of nodes. (a) A related quantity is the average pairwise distance in G, denoted by apd(G), and defined distance(u, v) as (u, v) EV apd(G)= (2) i. (10 points) Give the simplest graph you can for which diam (G) apd(G). ii. (15 points) Prove or disprove that there exists a positive constant c such that for all connected graphs diam (G) apd(G) c. Activate Window The diameter of an undirected unweighted graph G, denoted by diam (G), is the maximum distance between any pair of nodes in G. Equivalently, it is the longest of the shortest paths between all pairs of nodes. (a) A related quantity is the average pairwise distance in G, denoted by apd(G), and defined distance(u, v) as (u, v) EV apd(G)= (2) i. (10 points) Give the simplest graph you can for which diam (G) apd(G). ii. (15 points) Prove or disprove that there exists a positive constant c such that for all connected graphs diam (G) apd(G) c. Activate Window

Answer rating: 100% (QA)

For the given question i 10 points The simplest graph for which diamG apdG is a star graph Explanati... View the full answer