프톨레마이오스 그래프
Ptolemaic graph그래프 이론에서 프톨레마이오스 그래프는 최단 경로 거리가 프톨레마이오스의 불평등을 따르는 비방향 그래프로, 그리스 천문학자 겸 수학자 프톨레마이오스의 이름을 따서 명명되었다. Ptolemaic 그래프는 정확히 코드와 거리-계통 그래프를[1] 모두 포함하는 그래프로서, 블록 그래프를 포함하고 완벽한 그래프의 하위 등급이다.
특성화
그래프는 다음과 같은 동등한 조건을 준수하는 경우에만 Ptolemaic이다.
- 최단 경로 거리는 프톨레마이오스의 불평등을 따른다: 4개의 꼭지점 u, v, w, x마다 불평등 d(u,v)d(w,x) + d(u,x)d(v,w) , d(u,w)d(v,x) hold.[1] 예를 들어 이 그래프 d(u,w)d(v,x) = 4, d(u,v)d(w,x) + d(u,x)d(v,w) = 3보다 크기 때문에 그림의 보석 그래프(3-fan)는 Ptolemaic이 아니다.
- 겹치는 두 개의 최대 패거리에 대해 두 패밀리의 교차점은 두 패밀리의 차이를 분할하는 분리형이다.[2] 보석 그래프의 그림에서 이것은 사실이 아니다: clique uvy와 wxy는 교차로에 의해 분리되지 않는다. clique를 연결하지만 교차로에는 교차를 피하는 엣지 vw가 있기 때문이다.
- 모든 k-vertex 사이클에는 적어도 3(k - 3)/2개의 대각선이 있다.[2]
- 그래프는 코드(길이 3보다 큰 모든 사이클은 대각선으로 표시됨)와 거리 계통(연결된 모든 유도 하위그래프는 전체 그래프와 동일한 거리를 가진다)[2]이다. 표시된 보석은 화음이지만 거리-계통은 아니다: ubwx에 의해 유도된 서브그래프에서 u에서 x까지의 거리는 3으로 전체 그래프에서 동일한 정점 사이의 거리보다 크다. 왜냐하면 화음 그래프와 거리 계통 그래프는 모두 완벽한 그래프이기 때문에 프톨레마이오스 그래프도 마찬가지다.[3]
- 그래프는 화음이며 유도된 보석을 포함하지 않는다. 이 그래프는 두 개의 교차하지 않는 대각선을 오각형에 추가함으로써 형성된다.[3]
- 그래프는 거리 계통이며 유도 4 사이클을 포함하지 않는다.[4]
- 그래프는 새로운 도원(진자) 정점을 추가하거나 기존 정점을 중복(승자)하는 일련의 연산에 의해 단일 정점에서 구성할 수 있으며, 예외적으로 새로운 중복 정점이 쌍둥이에 인접하지 않는 쌍둥이 연산은 쌍둥이의 이웃이 패거리를 형성할 때만 적용할 수 있다. 이 세 가지 작업은 예외 없이 모든 거리-연속 그래프를 형성한다. 모든 Ptolemaic 그래프를 형성하기 위해, 펜던트 정점과 트윈스를 사용하는 것만으로는 충분하지 않다; 때때로 거짓 쌍둥이의 예외적인 사례도 필요하다.[5]
- 최대 집단의 비어 있지 않은 교차점에 대한 부분 집합 관계의 Hasse 다이어그램은 지향적인 트리를 형성한다.[6]
- 정점의 볼록 부분 집합(부분집합에서 두 정점 사이의 모든 최단 경로를 포함하는 하위 집합)은 볼록 형상을 형성한다. 즉, 모든 볼록 세트는 나머지 정점 사이의 어떤 최단 경로에도 속하지 않는 극한 정점을 반복적으로 제거함으로써 설정된 전체 정점에서 도달할 수 있다.[7] 보석에서 볼록 세트 uxy는 v도 w도 극단적이지 않기 때문에 이런 식으로 도달할 수 없다.
계산 복잡성
지향적인 나무에 의한 특성화를 바탕으로 프톨레마이오스 그래프를 선형적으로 인식할 수 있다.[6]
열거
Ptolemaic 그래프의 생성 함수는 상징적으로 설명할 수 있어 이러한 그래프의 수를 신속하게 계산할 수 있다. 방법에 따라, =1, ,,…에 대해 정점이 n개인 Ptolemaic 그래프의 수는 과[8] 같은 것으로 밝혀졌다
- 1, 1, 4, 4, 35, 481, 9042, 216077, 6271057, 214248958, 8424002973, 374708368981, 18604033129948, 10199156831963, …(OEIS의 경우 연속 A2878866)
참조
- ^ a b Kay, David C.; Chartrand, Gary (1965), "A characterization of certain ptolemaic graphs", Canadian Journal of Mathematics, 17: 342–346, doi:10.4153/CJM-1965-034-0, hdl:10338.dmlcz/126208, MR 0175113.
- ^ a b c Howorka, Edward (1981), "A characterization of Ptolemaic graphs", Journal of Graph Theory, 5 (3): 323–331, doi:10.1002/jgt.3190050314, MR 0625074.
- ^ a b "Graphclass: ptolemaic", Information System on Graph Classes and their Inclusions, retrieved 2016-06-05.
- ^ McKee, Terry A. (2010), "Clique graph representations of Ptolemaic graphs", Discussiones Mathematicae Graph Theory, 30 (4): 651–661, doi:10.7151/dmgt.1520, MR 2761626.
- ^ Bandelt, Hans-Jürgen; Mulder, Henry Martyn (1986), "Distance-hereditary graphs", Journal of Combinatorial Theory, Series B, 41 (2): 182–208, doi:10.1016/0095-8956(86)90043-2, MR 0859310.
- ^ a b Uehara, Ryuhei; Uno, Yushi (2009), "Laminar structure of Ptolemaic graphs with applications", Discrete Applied Mathematics, 157 (7): 1533–1543, doi:10.1016/j.dam.2008.09.006, MR 2510233.
- ^ Farber, Martin; Jamison, Robert E. (1986), "Convexity in graphs and hypergraphs", SIAM Journal on Algebraic and Discrete Methods, 7 (3): 433–444, doi:10.1137/0607049, hdl:10338.dmlcz/127659, MR 0844046.
- ^ Bahrani, Maryam; Lumbroso, Jérémie (2018), "Enumerations, forbidden subgraph characterizations, and the split-decomposition", Electronic Journal of Combinatorics, 25 (4)