측지 그래프

그래프 이론에서 측지 그래프는 두 꼭지점 사이에 고유(비중치) 최단 경로가 존재하는 방향되지 않은 그래프다.

측지 그래프는 1962년 외이스테인 오레에 의해 도입되었는데, 이들은 나무의 특성(거리와 상관없이 각 정점 사이에 고유한 경로가 존재하는 곳)을 일반화한다고 관찰하고 특성화를 요청했다.^[1]이러한 그래프는 다항식 시간에 인식될 수 있지만, "60년 이상 지난 후에도 완전한 특성화는 여전히 이해하기 어렵다."^[2]

예

모든 트리,^[1] 모든 전체 그래프,^[3] 모든 홀수 길이 사이클 그래프는 측지학적이다.^[4]

$G{\displaystyle }$ ${\displaystyle G}$이 측지 그래프인 경우 $G{\displaystyle }$ ${\displaystyle G}$의 모든 가장자리를 동일한 홀수 길이의 경로로$$ 교체하면 또 다른 측지 그래프가 생성된다.^[5]전체 그래프의 경우 경로별로 대체하는 보다 일반적인 패턴이 가능하다. 즉, 각 $꼭지점{\displaystyle }$ v ${\displaystyle$v}에 $대해$ 음이 $아닌{\displaystyle }$ 정수 f${\displaystyle (}$${\displaystyle v}$${\displaystyle }$)$${\$displaystyle$$f($u$)$ + f$v$ ) ${\displaystystyle$ $u$$}$을($v)$ 정점을$$ 추가하여$$ 각 에지 ${\displaystyle v}$ ${\displaysty$ $u{\displaystyle }$}을 세분화한다.그러면 결과적으로 세분화된 전체 그래프는 측지학적이며, 모든 측지학적 분할된 전체 그래프는 이러한 방식으로 얻을 수 있다.^[6][7]

관련 그래프 클래스

그래프의 모든 이코넥트 성분이 측지학이라면 그래프 자체는 측지학이다.특히 모든 블록 그래프(바이콘넥트 구성요소가 완성된 그래프)는 측지학적이다.^[3]마찬가지로, 주기 그래프는 길이가 홀수일 때 측지학적이기 때문에, 주기들이 홀수 길이를 갖는 모든 선인장 그래프도 측지학적이다.이 선인장 그래프들은 정확히 모든 주기의 길이가 홀수인 연결된 그래프들이다.더욱 강하게, 평면 그래프는 그것의 모든 결합 구성요소가 홀수 길이 주기 또는 4-Vertex 계열의 측지학적 세분화된 경우에만 측지학적이다.^[4]

계산 복잡성

측지학적 그래프는 그래프의 각 꼭지점에서 시작하여 여러 개의 최단 경로를 감지할 수 있는 폭의 첫 번째 검색을 사용하여 다항식 시간에 인식될 수 있다.측지그래프는 유도 4Vertex 사이클 그래프나 유도 다이아몬드 그래프를 포함할 수 없다. 이 두 그래프는 측지그래프가 아니기 때문이다.^[3]특히, 다이아몬드가 없는 그래프의 부분집합으로서 측지 그래프는 모든 가장자리가 고유한 최대 집단에 속하는 속성을 가지고 있다. 이러한 맥락에서 최대 집단은 선이라고도 불린다.^[8]최대 편파, 즉 최대 가중 편파 찾기 문제는 측지 그래프의 다항 시간 내에 모든 최대 편파를 나열하여 해결할 수 있다.유도 4 사이클이나 다이아몬드가 없는 더 광범위한 종류의 그래프를 "약하게 측지학"이라고 부른다; 이것들은 서로 정확히 두 개의 거리에 있는 정점이 독특한 최단 경로를 갖는 그래프들이다.^[3]

지름 2

지름 2의 그래프(즉, 모든 정점이 서로 최대 두 개의 거리에 있는 그래프)의 경우 측지 그래프와 약하게 측지 그래프가 일치한다.지름 2의 모든 측지학적 그래프는 다음 세 가지 유형 중 하나이다.

• 풍차 그래프를 포함하여 모든 최대 패가 단일 공유 정점에서 결합되는 블록 그래프,
• 매개변수 $\mu {\displaystyle }$ ${\displaystyle \mu }($각 정점의 비인접 쌍에 대한 공유 이웃 수)가 1 또는 같은 매우 정규적인 그래프
• 꼭지점이 정확히 두 개 다른 그래프

매우 규칙적인 측지 그래프에는 5-Vertex 사이클 그래프, 피터슨 그래프, 호프만-싱글턴 그래프가 포함된다.그러한 그래프가 가지고 있어야 할 특성에 대한 추가 연구에도 불구하고,^[9][10] 이러한 그래프가 더 많은지, 아니면 무한히 많은 그래프가 있는지 알 수 없다.^[8]

직경이 2도, 서로 다른 2도인 측지 그래프는 두 도 모두 정점으로 구성된 삼각형을 가질 수 없다.이들은 평면의 점선 발생 그래프를 추가하여 각 두 평행선에 해당하는 정점 사이에 가장자리를 추가함으로써 모든 유한 아핀 평면에서 생성될 수 있다.3개의 평행한 쌍으로 4개의 점과 6개의 2개의 점선이 있는 이진 아핀 평면의 경우, 이 구성의 결과는 Petersen 그래프지만, 고차 유한 아핀 평면의 경우 2개의 다른 각도로 그래프를 만든다.유한 기하학에서 나온 측지 그래프의 다른 관련 구조도 알려져 있지만, 이러한 구조들이 직경이 2도, 2도가 다른 측지 그래프를 모두 소진하는지는 알려지지 않았다.^[8]

참조