Метрика для сравнения графов с упорядоченными вершинами на основе максимального общего подграфа

Работа посвящена методам сравнения и классификации графов. Данное направление известно под названием «graph matching». Приводится обзор метрик для сравнения графов, основанных на максимальном общем подграфе. Предложена модификация расстояния на основе максимального общего подграфа, которое учитывает упорядоченность вершин. Показано, что эта функция удовлетворяет всем свойствам метрики (неотрицательность, тождественность, симметричность, неравенство треугольника).