📂그래프이론

그래프와 그래프 사이의 편집 거리

정의 ¹

버텍스의 유한집합 $X$ 와 유한한 알파뱃의 집합을 $\alpha$ 이라 하자. 여기서 알파뱃은 공백 혹은 널^null을 포함한다고 간주한다. 버텍스 라벨링^{vertex labeling} $V : X \to \alpha$ 와 에지 라벨링^{edge labeling} $E : X \times X \to \alpha$ 에 대해 트리플 $G = (X, V, E)$ 를 그래프라 한다. $\hat{G} = \left( \hat{X}, \hat{V}, \hat{E} \right)$ 가 $G$ 의 서브 그래프라는 것은 다음의 세 가지 조건을 만족하는 것을 의미한다:

• $\hat{X} \subset X$
• $\forall x \in \hat{X}$ 에 대해 $\hat{V}(x) = V(x)$
• $\forall (x, y) \in \hat{X} \times \hat{X}$ 에 대해 $\hat{E} \left( x , y \right) = E \left( x , y \right)$

ecgm

$G_{1} = \left( X_{1}, V_{1}, E_{1} \right)$ 과 $G_{2} = \left( X_{2}, V_{2}, E_{2} \right)$ 가 두 그래프라고 하자. 이들의 서브그래프 $\hat{G}_{1} = \left( \hat{X}_{1}, \hat{V}_{1}, \hat{E}_{1} \right)$ 와 $\hat{G}_{2} = \left( \hat{X}_{2}, \hat{V}_{2}, \hat{E}_{2} \right)$ 에 대해 전단사 $f : \hat{X}_{1} \to \hat{X}_{2}$ 를 $G_{1}$ 에서 $G_{2}$ 로의 에러-정정 그래프 매칭^{error-correcting graph matching}이라 한다.

ecgm의 코스트

편의상 에지 라벨링의 레인지 $\hat{E}_{k} \left( \hat{X}_{k} \times \hat{X}_{k} \right)$ 를 $\hat{E}_{k}$ 이라 나타내자. $G_{1}$ 에서 $G_{2}$ 로의 ecgm $f: \hat{X}_{1} \to \hat{X}_{2}$ 의 코스트^cost $c(f)$ 는 다음과 같이 정의된다.

$$ \begin{align*} c(f) :=& \sum_{x \in \hat{X}_{1}} c_{\text{vs}} (x) + \sum_{x \in X_{1} \setminus \hat{X}_{1}} c_{\text{vd}} (x) + \sum_{x \in X_{2} \setminus \hat{X}_{2}} c_{\text{vi}} (x) \\ & + \sum_{e \in \hat{E}_{1}} c_{\text{es}} (x) + \sum_{e \in E_{1} \setminus \hat{E}_{1}} c_{\text{ed}} (x) + \sum_{e \in E_{2} \setminus \hat{E}_{2}} c_{\text{ei}} (x) \end{align*} $$

• $c_{\text{vs}} (x)$ 는 $x \in \hat{X}_{1}$ 을 $f(x) \in \hat{X}_{2}$ 으로 바꾸는 비용이다.
• $c_{\text{vd}} (x)$ 는 $x \in X_{1} \setminus \hat{X}_{1}$ 을 $G_{1}$ 에서 삭제하는 비용이다.
• $c_{\text{vi}} (x)$ 는 $x \in X_{2} \setminus \hat{X}_{2}$ 을 $G_{2}$ 에 추가하는 비용이다.
• $c_{\text{es}} (x)$ 는 $e = (x,y) \in \hat{E}_{1}$ 을 $\left( f(x), f(y) \right) \in \hat{E}_{2}$ 으로 바꾸는 비용이다.
• $c_{\text{ed}} (x)$ 는 $e \in E_{1} \setminus \hat{E}_{1}$ 을 $G_{1}$ 에서 삭제하는 비용이다.
• $c_{\text{ei}} (x)$ 는 $e \in E_{2} \setminus \hat{E}_{2}$ 을 $G_{2}$ 에 추가하는 비용이다.

편집 거리

두 그래프 $G_{1}$ 와 $G_{2}$ 의 편집 거리^{edit distance} $d \left( G_{1} , G_{2} \right)$ 는 $G_{1}$ 에서 $G_{2}$ 로의 ecgm의 코스트 중 최소값으로 정의된다: $$ d \left( G_{1} , G_{2} \right) := \min \left\{ c(f) : f \text{ is an ecgm from } G_{1} \text{ to } G_{2} \right\} $$

설명

일반적인 정의를 따라가다보니 말이 지나치게 장황해진 느낌이 있는데, 개념적으로는 아주 쉽고 간단하다.

예로써 위와 같은 두 그래프가 있고 추가, 삭제, 교체의 코스트가 모두 $1$ 이라면 한 쪽 그래프에 버텍스와 에지를 추가, 삭제, 교체하며 다른 쪽 그래프를 만들 수 있는 방법 중 가장 최소 횟수가 바로 그래프 편집 거리다. 위 경우엔 왼쪽에서 오른쪽 그래프를 만들기 위해 하나의 버텍스를 추가해야하며, 이미 있던 에지 중 하나를 새로운 노드로 잇는 교체가 필요하므로 그래프 편집 거리는 $2$ 다.

같이보기

• 문자열의 편집 거리
• 그래프와 그래프 사이의 스펙트럴 거리