Measuring closeness of graphs -- the Hausdorff distance

Andrej Taranenko
Faculty of Natural Sciences and Mathematics, University of Maribor

Iztok Banič
Faculty of Natural Sciences and Mathematics, University of Maribor

PDF

Minisymposium: GENERAL SESSION TALKS

Content: We introduce an apparatus to measure closeness or relationship of two given objects. This is a topology based apparatus that uses graph representations of the compared objects. In more detail, we obtain a metric on the class of all pairwise non-isomorphic connected simple graphs to measure closeness of two such graphs. To obtain such a measure, we use the theory of hyperspaces from topology to introduce the notion of the Hausdorff graph $2^G $ of any graph $G$. Then, using this new concept of Hausdorff graphs combined with the notion of graph amalgams, we present the Hausdorff distance, which proves to be useful when examining the closeness of any two connected simple graphs. We also present many possible applications of these concepts in various areas.

Back to all abstracts