Доказательство расстояния редактирования между графиками без ребер является метрикой

Question

Проблема в том, чтобы найти минимальное расстояние редактирования между двумя графиками без ребер, учитывая, что могут быть разные затраты на добавление, удаление или замену вершин.

Мне сказали, что это расстояние является метрикой, и есть простой способ доказать это. Это так? Как это можно сделать?

Answer 1

Я назову расстояние между двумя графами G и H, d (G, H).

1. Для любого графа G, d (G, G) = 0. Покапоскольку все затраты строго положительны, то для любого G! = H, d (G, H)> 0. Таким образом, неотрицательность удовлетворяется.

2. Пока стоимостьудаление вершины равно стоимости добавления вершины для любых двух графов G, H, d (G, H) = d (H, G).Таким образом, симметрия выполняется.

3. Наконец, для любых трех графиков G, H, K, d (G, K) не более d (G, H) + d (H, K) потому что можно отредактировать G в K, сначала отредактировав его в H.

Приведенные выше критерии определяют метрику.