Line Graph L(G) can be considered as an operator on an undirected graph G just like Complementary Graph and Dual Graph. Rikka generalizes Line Graph to edge-weighted undirected graphs. For a graph G=
Line Graph L(G) can be considered as an operator on an undirected graph G just like Complementary Graph and Dual Graph. Rikka generalizes Line Graph to edge-weighted undirected graphs. For a graph G=⟨V,E⟩G=langle V,ErangleG=⟨V,E⟩, L(G) is still an edge-weighted undirected graph which is constructed in the following way: 1. L(G) has |E| vertices and the ith vertex corresponds to the ith edge in G. 2. There is an edge between i,j in L(G) if and only if edge i and j have at least one common vertices in G. And the edge weight is equal to the sum of the weights of edge i and j in G. For example, in the following picture, the right graph is the line graph of the left one. Vertex 1,2,3,4 in L(G) correspond to edge (1,2),(1,4),(1,3),(3,4) in G. And if all edges in the left graph have weight 1, the edges in the right graph will have weight 2. Now, Rikka has an edge-weighted undirected complete graph G with n vertices. And she constructs a graph G'=L(G). It is clear that G' is connected. Let d(i,j) be the length of the shortest path between vertex i,j in G'(the length of each edge is equal to its weight), K be the number of vertices in G', Rikka wants you to calculate ∑i=1K∑j=i+1Kd(i,j)sum_{i=1}^K sum_{j=i+1}^K d(i,j)∑i=1K∑j=i+1Kd(i,j).
