iv. triangle inequality ,
\(d\left(x,y\right)\le d\left(x,z\right)+d\left(z,y\right)\)
\(\triangle\left(G_1,G_2\right)\) gives the cost of transformation of one graph to another.
Clearly \(\triangle\left(G_x,G_z\right)+\triangle\left(G_z,G_y\right)\) is greater than \(\triangle\left(G_x,G_{y\ }\right)\ \because\ \) cost of converting a graph x to another graph z and and then to graph y can at best be equal to converting x to y and that too would happen when z is either equal to x of y. Therefore we can say that d(x,y) is the minimum distance between points x and y.Therefore triangle inequality holds.
Since the function satisfies all 4 properties it is a metric
Part 2
G1, G2, . . . , Gn
Centroid of a cluster would be defined as a graph with the least sum of edit distance to the rest of the graph i.e. which requires the least cost to be transformed to rest of the graphs and therefore is a good representation of all the clusters
To find the centroid we assume each graph as the centroid and computer the sum of its edit distances(\(\triangle\)) to all other graphs(\(G_1....G_n\)). The centroid \(G^{\ast}\) is the graph with the minimum value of sums calculated in the previous step.This can be represented mathematically as below.
\(Centroid=G^{\ast}=\arg\min_{x\epsilon G_1...G_n}\Sigma_{i=1}^n\triangle\left(G_i,G_{ }\right)\)
We can be sure that the centroid calculated in the previous step is the centroid because there is no other graph which would have a lower cost of transformation(edit distance) to all other graphs.
References: