求证无边图间编辑距离为度量的简便方法探究

Great question! Let's break this down clearly—yes, the minimum edit distance between two edgeless graphs (which are essentially just labeled vertex sets, since there are no edges to modify) does qualify as a metric, provided we impose a few reasonable constraints on the costs of vertex operations. Here's a straightforward proof, step by step:

First, Let's Formalize the Setup #

• An edgeless graph is just a set of labeled vertices: let’s denote graph ( G ) as ( (V_G, \emptyset) ) and graph ( H ) as ( (V_H, \emptyset) ).
• The allowed edit operations (with non-negative costs) are:
  • Delete a vertex ( v \in V_G ): cost ( c_{\text{del}}(v) \geq 0 )
  • Add a vertex ( u ): cost ( c_{\text{add}}(u) \geq 0 )
  • Replace a vertex ( v \in V_G ) with ( u ): cost ( c_{\text{replace}}(v, u) \geq 0 ), with ( c_{\text{replace}}(v, v) = 0 ) (replacing a vertex with itself costs nothing)
• For symmetry to hold (a required metric property), we’ll assume:
  • ( c_{\text{del}}(v) = c_{\text{add}}(v) ) for all vertices ( v )
  • ( c_{\text{replace}}(v, u) = c_{\text{replace}}(u, v) ) for all pairs ( v, u )

The minimum edit distance ( d(G, H) ) is the lowest total cost of any sequence of operations that transforms ( G ) into ( H ).

Proof That ( d ) Is a Metric #

A metric must satisfy four core properties; let’s verify each one:

1. Non-negativity (( d(G, H) \geq 0 ))

All operation costs are non-negative by definition. Any sequence of operations will have a total cost that’s the sum of non-negative values, so the minimum possible cost (our edit distance) can’t be negative. Done.

2. Identity of Indiscernibles (( d(G, H) = 0 \iff G = H ))

• If ( G = H ): We can use a trivial sequence of operations (replace each vertex with itself, costing 0, or do nothing). The total cost is 0, so ( d(G, H) = 0 ).
• If ( d(G, H) = 0 ): The optimal sequence has total cost 0. Since every operation’s cost is non-negative, every individual operation in the sequence must cost 0. That means:
  • No deletions or additions (their costs are ≥0, so any such operation would make the total cost >0)
  • All replacements are of a vertex with itself (since ( c_{\text{replace}}(v, u) = 0 ) only when ( v = u ))
    This implies ( V_G = V_H ), so ( G = H ).

3. Symmetry (( d(G, H) = d(H, G) ))

Take the optimal sequence of operations that transforms ( G ) to ( H ) (costing ( d(G, H) )). We can reverse this sequence to get a valid sequence for transforming ( H ) to ( G ):

• Swap "delete ( v )" with "add ( v )" (costs are equal by our symmetry assumption)
• Swap "add ( u )" with "delete ( u )" (again, costs are equal)
• Swap "replace ( v ) with ( u )" with "replace ( u ) with ( v )" (costs are equal)

The reversed sequence has the same total cost as the original. Since ( d(H, G) ) is the minimum cost for ( H \to G ), we know ( d(H, G) \leq d(G, H) ). By the same logic, ( d(G, H) \leq d(H, G) ), so they must be equal.

4. Triangle Inequality (( d(G, K) \leq d(G, H) + d(H, K) ) for any edgeless graphs ( G, H, K ))

Let ( S_1 ) be the optimal sequence for ( G \to H ) (cost ( d(G, H) )) and ( S_2 ) be the optimal sequence for ( H \to K ) (cost ( d(H, K) )). If we concatenate ( S_1 ) followed by ( S_2 ), we get a valid sequence that transforms ( G ) directly to ( K ), with total cost ( d(G, H) + d(H, K) ).

Since ( d(G, K) ) is the minimum cost of any such sequence, it can’t be larger than the cost of this concatenated sequence. Thus, ( d(G, K) \leq d(G, H) + d(H, K) ).

All four metric properties are satisfied, so the minimum edit distance is indeed a metric.

内容的提问来源于stack exchange，提问作者Sérgio Mergen