A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Metrization of Weighted Graphs
Tekijät: Dovgoshey O, Martio O, Vuorinen M
Kustantaja: SPRINGER BASEL AG
Julkaisuvuosi: 2013
Journal: Annals of Combinatorics
Tietokannassa oleva lehden nimi: ANNALS OF COMBINATORICS
Lehden akronyymi: ANN COMB
Numero sarjassa: 3
Vuosikerta: 17
Numero: 3
Aloitussivu: 455
Lopetussivu: 476
Sivujen määrä: 22
ISSN: 0218-0006
DOI: https://doi.org/10.1007/s00026-013-0192-7
Tiivistelmä
We find a set of necessary and sufficient conditions under which the weight on the graph G = (V, E) can be extended to a pseudometric d : V x V -> R+. We describe the structure of graphs G for which the set of all such extensions contains a metric whenever w is strictly positive. Ordering by the pointwise order, we have found that the posets contain the least elements rho (0,w) if and only if G is a complete k-partite graph with . In this case the symmetric functions f : V x V -> R+, lying between rho (0,w) and the shortest-path pseudometric, belong to for every metrizable w if and only if the cardinality of all parts in the partition of V is at most two.
We find a set of necessary and sufficient conditions under which the weight on the graph G = (V, E) can be extended to a pseudometric d : V x V -> R+. We describe the structure of graphs G for which the set of all such extensions contains a metric whenever w is strictly positive. Ordering by the pointwise order, we have found that the posets contain the least elements rho (0,w) if and only if G is a complete k-partite graph with . In this case the symmetric functions f : V x V -> R+, lying between rho (0,w) and the shortest-path pseudometric, belong to for every metrizable w if and only if the cardinality of all parts in the partition of V is at most two.
Turun yliopiston Tutkimustietojärjestelmän portaali