📂그래프이론

그래프와 그래프 사이의 스펙트럴 거리

정의

버텍스의 수가 $n$ 인 두 그래프 $G_{1}$, $G_{2}$ 의 인접행렬을 $A_{1}$, $A_{2}$ 라 하자. 이들이 내림차순으로 정렬된 고유값, 즉 스펙트라^spectra를 각각 다음과 같이 나타내자. $$A_{1} \mapsto \lambda_{1}^{(1)} \ge \cdots \ge \lambda_{n}^{(1)} \\ A_{2} \mapsto \lambda_{1}^{(2)} \ge \cdots \ge \lambda_{n}^{(2)}$$ 두 그래프 사이의 스펙트럴 거리^{spectral distance}를 다음과 같이 정의한다^{1 2}. $$d \left( G_{1} , G_{2} \right) := \sqrt{ \sum_{k=1}^{n} \left( \lambda_{k}^{(1)} - \lambda_{k}^{(2)} \right)^{2} }$$

설명

언뜻 생각하기에 그래프의 거리는 인접행렬 그 자체의 해밍 거리로 정의해도 무방할 것 같지만, 단순히 행렬을 성분 별로 비교하는 것은 버텍스의 순서에 취약하다. 반면 스펙트럴 거리는 그 정의 상 라벨링과 무관하게 정의된다는 장점이 있다.

같이보기

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