맨위로가기

거리 (그래프 이론)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

그래프 거리(Graph distance)는 그래프 이론에서 그래프 상의 정점 집합에 대해 정의된 거리 공간을 의미한다. 그래프의 편심, 반지름, 지름은 그래프의 구조를 나타내는 중요한 지표로, 편심은 특정 정점과 다른 모든 정점 간의 최대 거리를, 반지름은 모든 정점의 최소 편심을, 지름은 그래프 내 임의의 두 정점 간의 최대 거리를 뜻한다. 중심 정점은 반지름과 같은 편심을 가진 정점이며, 주변 정점은 지름과 같은 편심을 가진 정점이다. 유사 주변 정점은 주변 정점을 찾는 것이 어려울 때 사용될 수 있다. 가중 그래프에서는 가중치를 고려한 가중 최단 경로 거리를 사용하며, 측지 그래프는 모든 정점 쌍 사이에 유일한 최단 경로가 존재하는 그래프이다.

더 읽어볼만한 페이지

  • 계량기하학 - 거리
    거리는 수학에서 두 점 사이를 측정하는 함수, 물리학에서 물체의 위치 변화량, 일상생활에서 두 지점 사이의 길이를 의미하며, 국제단위계에서는 길이로 표현된다.
  • 계량기하학 - 코시 열
    코시 열은 무한수열에서 항들이 뒤로 갈수록 서로 가까워지는 수열로, 수렴열은 항상 코시 열이지만 그 역은 성립하지 않을 수 있으며, 실수의 완비성 정의 및 무한급수 수렴성 판정에 중요한 역할을 하는 개념이다.
  • 그래프 이론 - 다이어그램
    다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
  • 그래프 이론 - 쾨니히스베르크의 다리 문제
    쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
거리 (그래프 이론)
그래프 거리 정보
정의그래프의 두 꼭짓점 사이의 최단 경로의 길이
다른 이름그래프 측지선
측지선 거리
기호d(u, v)
변수u: 꼭짓점
v: 꼭짓점
속성d(u, v) = d(v, u)
추가 정보
참고그래프에서 거리는 꼭짓점 사이의 최단 경로의 길이로 정의된다.

2. 그래프 거리

그래프에서 두 정점 사이의 거리는 최단 경로의 길이로 정의된다. 연결된 그래프에서만 거리 함수가 정의되며, 무방향 그래프의 경우 거리 공간을 형성한다. 그래프 상의 거리를 기준으로 점의 집합에 대해 정의된 거리 공간을 '''그래프 거리'''라고 한다.

3. 편심, 반지름, 지름

정점 의 '''편심''' 는 와 다른 모든 정점 사이의 최대 거리이다. 이는 그래프에서 어떤 정점이 가장 멀리 떨어진 정점으로부터 얼마나 떨어져 있는지를 나타낸다.

:\epsilon(v) = \max_{u \in V}d(v,u).

그래프의 '''반지름''' 은 모든 정점의 편심 중 최소값이다.

:r = \min_{v \in V} \epsilon(v) = \min_{v \in V}\max_{u \in V}d(v,u).

그래프의 '''지름''' 는 그래프 내 모든 정점의 편심 중 최대값이다. 즉, 임의의 두 정점 사이의 거리 중 가장 큰 값이다.

:d = \max_{v \in V}\epsilon(v) = \max_{v \in V}\max_{u \in V}d(v,u).

그래프의 지름을 구하려면 각 정점 쌍 사이의 최단 경로를 모두 찾은 후, 이 경로들 중 가장 긴 경로의 길이를 선택해야 한다.

3. 1. 중심 정점과 주변 정점

중심 정점은 편심이 그래프의 반지름과 같은 정점이다. 즉, 가장 멀리 떨어진 정점과의 거리가 반지름과 같은 정점을 의미하며, 로 표현된다.[4]

주변 정점은 편심이 그래프의 지름과 같은 정점이다. 다시 말해, 가장 멀리 떨어진 정점과의 거리가 지름과 같은 정점을 뜻하며, 로 나타낼 수 있다.[4]

유사 주변 정점 는 다음 조건을 만족한다. 임의의 정점 에 대해, 가 로부터 가능한 한 멀리 떨어져 있으면, 도 로부터 가능한 한 멀리 떨어져 있다. 즉, 를 갖는 각 정점 에 대해 가 성립하면 정점 는 유사 주변 정점이 된다.[4] 주변 정점을 찾기 어려울 때 대신 사용될 수 있다.

4. 가중 그래프에서의 거리

가중 그래프에서는 간선에 가중치가 부여되어 있어, 이 가중치를 고려하여 거리를 계산한다. 가중 최단 경로 거리는 두 정점 사이의 경로들 중 가중치의 합이 가장 작은 경로의 길이를 의미한다. 예를 들어, 복잡한 네트워크에서는 간선의 가중치가 상호 작용의 '비용'을 나타낼 수 있다. 가중 최단 경로 거리 는 와 를 연결하는 모든 경로에 대해 가중치의 합을 최소화하여 계산한다. 이와 관련된 더 자세한 내용과 알고리즘은 최단 경로 문제에서 확인할 수 있다.

5. 유사 주변 정점 찾기 알고리즘

주변 희소 행렬 알고리즘은 높은 편심도를 가진 시작 정점을 필요로 한다. 주변 정점이 완벽하지만, 계산하기 어려운 경우가 많다. 대부분의 경우 의사 주변 정점을 사용할 수 있다. 의사 주변 정점은 다음 알고리즘을 사용하여 쉽게 찾을 수 있다.[1]

1. 정점 u를 선택한다.

2. u로부터 가능한 멀리 떨어져 있는 모든 정점들 중에서, 최소 차수를 가진 정점을 v라고 하자.

3. 만약 \epsilon(v) > \epsilon(u)이면, u=v로 설정하고 2단계를 반복하고, 그렇지 않으면 u는 의사 주변 정점이다.

6. 측지 그래프

'''측지 그래프'''는 임의의 두 정점 사이에 유일한 최단 경로가 존재하는 그래프이다. 모든 트리는 측지 그래프의 예시이다.[4]

참조

[1] 간행물 Geodesic distance in planar graphs 2003-07
[2] 웹사이트 Graph Geodesic http://mathworld.wol[...] Wolfram Research 2008-04-23
[3] 서적 Graph Theory Addison-Wesley 1969
[4] 서적 Theory of graphs American Mathematical Society 1967
[5] 저널 Geodesic distance in planar graphs http://www.sciencedi[...] 2008-04-23
[6] 웹인용 Graph Geodesic http://mathworld.wol[...] Wolfram Research 2008-04-23
[7] 서적 Graph Theory Addison-Wesley 1969



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com