위상 그래프

수학에서 위상학 그래프는 평면에서 그래프의 정점을 나타내는 것으로, 그래프의 정점은 구별되는 점으로 표시되며, 가장자리는 조던 호(요르단 곡선의 연결된 조각)가 해당 점 쌍의 점을 결합하는 것이다.그래프의 정점을 나타내는 점과 그 가장자리를 나타내는 호를 위상 그래프의 정점과 가장자리라고 한다.위상학 그래프의 어떤 두 가장자리도 한정된 횟수를 교차하고, 어떤 가장자리도 끝점과 다른 정점을 통과하지 않으며, 두 가장자리가 서로 접촉하지 않는다고(교차하지 않고) 가정한다.위상학적 그래프는 그래프의 그리기라고도 한다.

위상학적 그래프의 중요한 특수 등급은 기하학적 그래프의 등급이며, 여기서 가장자리는 선 세그먼트로 표현된다.(기하학적 그래프라는 용어는 더 넓고 다소 모호한 의미로 쓰이기도 한다.)

위상학적 그래프의 이론은 그래프 이론의 한 영역으로, 특히 가장자리의 교차 패턴과 함께 위상학적 그래프의 결합 특성에 주로 관련된다.그것은 보다 응용 지향적인 분야인 그래프 그리기와 표면(즉, 교차 없는 도면)에 그래프를 내장하는 위상학적 그래프 이론과 밀접한 관련이 있다.

위상학 그래프의 극단적 문제

극단적 그래프 이론의 근본적인 문제는 다음과 같다: 주어진 종류의 금지된 하위 그래프에 속하는 하위 그래프를 포함하지 않을 경우, n 꼭지점 그래프가 가질 수 있는 최대 가장자리 수는 얼마인가?그러한 결과의 프로토타입은 투란의 정리인데, 여기서 하나의 금지된 서브그래프, 즉 k 정점을 가진 완전한 그래프(k는 고정되어 있다.위상학적 및 기하학적 그래프에 대해 유사한 질문이 제기될 수 있으며, 현재 특정한 기하학적 하위 구성이 금지되어 있다는 차이점이 있다.

역사적으로 그러한 정리의 첫 사례는 하인츠 홉프와 에리카 판위츠의 결과를 연장한 폴 에르드스 덕분이다.^[2]그는 두 개의 분리 에지(끝점을 공유할 수도 없는)를 포함하지 않고 정점이 2인 기하학적 그래프가 가질 수 있는 최대 에지 수가 n이라는 것을 증명했다.존 콘웨이는 이 문장이 단순한 위상학적 그래프로 일반화될 수 있다고 추측했다.위상학적 그래프는 어떤 한 쌍의 가장자리가 거의 한 지점에서 공유되는 경우 "단순함"이라고 불리며, 이것은 두 가장자리가 적절하게 교차하는 끝점 또는 공통 내부 지점이다.이제 콘웨이의 엉거주춤한 추측을 다음과 같이 재구성할 수 있다.n > 2 정점이 있고 두 개의 분리 가장자리가 없는 단순 위상학 그래프에는 최대 가장자리가 n개 있다.

그러한 그래프의 가장자리 수에 대한 첫 번째 선형 상한은 Lovász 외 연구진에 의해 설정되었다.^[3]가장 잘 알려진 상한선 1.428n은 풀렉과 파흐에 의해 증명되었다.^[4]기하학적 그래프와는 별도로, x-모노톤 위상학 그래프에 대해 콘웨이의 철통같은 추측이 사실인 것으로 알려져 있다.^[5]위상학 그래프는 모든 수직선이 최대 한 지점에서 모든 가장자리를 교차하는 경우 x-모노톤이라고 한다.

알론과 에르디스는^[6] 금지된 구성이 k 분리 에지(k > 2)로 구성된 경우에 대해 위의 질문의 일반화에 대한 조사를 개시했다.그들은 3개의 불연속 가장자리가 없는 n 꼭지점의 기하학적 그래프의 가장자리 수가 O(n)임을 증명했다.약 2.5n의 최적 경계는 체르노에 의해 결정되었다.^[7]더 큰 k 값의 경우 첫 번째 선형 상한인 O($k{\displaystyle {}^{}}$ $){\displaystyle O(k^{4}n)$은$$Pach와 Töröcsik에 의해 설정되었다.^[8]이것은 Toth에 의해 $O{\displaystyle }$ ${\displaystyle ({}^{}}$ ${\displaystyle {}^{}}$) ${\displaystyle O(k^{2}n)}$로 개선되었다$.$^[9] k 분리 에지가 없는 단순 위상학 그래프의 에지 수는 $O{\displaystyle (n^{}}$ ${\displaystyle {\log }^{}}$ 4 ${\displaystyle {k\mathrm{}}^{}}$- ${\displaystyle 8^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle n}$) ${\displaystyle O(n\log ^4k-8}n)}$ 상한만$$ 알려져 있다.^[10]이는 정점이 n개인 모든 완전한 단순 위상학 그래프에는 최소한 c ${\displaystyle \frac{\mathrm{로그}}{}}$logn ${\displaystyle \frac{\mathrm{로그}}{\mathrm{logn}}}$ 로그${\displaystyle \frac{\mathrm{logn}}{}}$ ${\$ c${\frac{\log$ n$}{\log$ n$}}}$ 쌍$$ 교차 에지가 있음을 의미하며, 이는 Ruiz-vargas에 ${\displaystyle {의해\frac{\mathrm{}}{}}^{}}$ c ${\displaystyle {\frac{1}{}2}^{}}$ - { ${\$로 개선되었다.^[11]c > 0이 상수인 cn으로 이 하한을 더 개선할 수 있다.

준 평면 그래프

첫 번째 가장자리가 두 번째 가장자리의 한 쪽에서 다른 가장자리로 지나가는 두 가장자리의 공통 내부 지점을 교차점이라고 한다.위상 그래프의 두 가장자리가 교차점을 결정하면 교차한다.정수 k > 1에 대해 위상학적 또는 기하학적 그래프는 k 쌍으로 교차하는 가장자리가 없을 경우 k-quasi-planar라고 불린다.이 용어를 사용하여 위상학적 그래프가 2-Quasi-planar이면 평면 그래프다.정점이 2개 이상인 모든 평면 그래프는 최대 3n - 6개의 가장자리를 갖는 오일러의 다면체 공식에 따른다.따라서 정점이 n > 2인 2쿼시 평면 그래프는 최대 3n - 6 에지를 가진다.

pach 등은 정점이 n인 모든 k-quasi-planar 위상학 그래프를 c(k)n 가장자리로 하고, 여기서 c(k)는 k에만 의존하는 상수라고 추측해왔다.^[12]이 추측은 k = 3과^[14] k = 4에 대해 맞는 것으로 알려져 있다.^[15]또한 볼록 기하학 그래프(^[16]정점이 볼록 n-곤의 정점을 이루는 기하학적 그래프)와 가장자리가 x-모노톤 곡선으로 그려지는 k-quasi-planar 위상학 그래프의 경우에도 모두 수직선을 가로지르는 것으로 알려져 있다.^[17][18]마지막 결과는 가장자리가 n개인 모든 k-quasi-planar 위상학 그래프를 의미하며, 가장자리가 x-모노톤 곡선으로 그려지는 경우 적절한 상수 c(k)에 대해 최대 c(k)n 로그 n 에지가 있음을 의미한다.기하학적 그래프의 경우, 이것은 Valtr에 의해 일찍이 증명되었다.^[19]k-quasi-planar 위상학 그래프의 가장자리 수에 대해 가장 잘 알려진 일반 상한은 n ${\displaystyle {\log }^{}}$ O${\displaystyle {(로그}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle k^{}}$) ${\displaystyle {}^{}}$ ${\displaystyle n}$ ${\displaystyle n\log ^{O(\log$ k$)}n}$이다$.$^[20]

교차숫자

Pal Turan이 제2차 세계 대전 중에 벽돌 공장 문제를 창안한 이후, 그래프의 교차 숫자에 대한 결정이나 추정은 그래프 이론과 알고리즘 이론에서 인기 있는 주제였다.^[22]그러나 주제(명백하거나 암묵적으로)의 간행물은 여러 가지 경쟁적인 숫자의 정의를 사용했다.이는 다음과 같은 용어를 도입한 파흐와 토스가 지적한 것이다.^[23]

교차 번호(그래프 G):세 개의 가장자리가 동일한 점을 통과하지 않는 특성을 가진 평면 내 G의 모든 도면(위상학적 그래프로의 모든 표현)에 대한 교차점의 최소 수.cr(G)로 표시된다.

쌍 교차 번호:모든 G 도면에 걸쳐 있는 모서리 교차 쌍의 최소 수입니다.그것은 쌍-cr(G)로 표시된다.

홀수 교차 수:G의 모든 도면에 걸쳐 홀수 횟수를 교차하는 최소 에지 쌍 수입니다.그것은 홀수-cr(G)로 표시된다.

이 매개변수는 관련이 없다.하나는 모든 그래프 G에 대해 홀수-cr(G) ≤ 쌍-cr(G) ≤ cr(G)을 가지고 있다.It is known that cr(G) ≤ 2(odd-cr(G))^2[23] and ${\displaystyle O(\operatorname {pcr} (G)^{\frac {3}{2}}\log ^{2}\operatorname {pcr} (G))}$^[24] and that there exist infinitely many graphs for which pair-cr(G) ≠ odd-cr(G).^[1]교차 번호와 쌍 교차 번호가 같지 않은 예는 알려져 있지 않다.하나니에서 따온 것이다.홀수-cr(G) = 0이 cr(G) = 0을 내포하는 투트 정리^[25]. 또한 k = 1, 2, 3에 대해 홀수-cr(G) = k cr(G)=k를 내포하고 있는 것으로 알려져 있다.^[27] 또 다른 잘 연구된 그래프 매개변수는 다음과 같다.

직선 교차점:세 개의 가장자리가 동일한 점을 통과하지 않는 특성을 가진 평면 내 G의 모든 직선 도면에 걸친 교차점 수(즉, 기하학적 그래프로의 모든 표현)그것은 lin-cr(G)로 표시된다.

정의상 모든 그래프 G에 대해 cr(G) ≤ lin-cr(G)을 가지고 있다.비엔나스톡과 딘에 의해 4번 교차점과 임의로 큰 직선 교차 번호를 가진 그래프가 있음을 보여주었다.^[28]

기하학적 그래프의 Ramsey 유형 문제

전통적인 그래프 이론에서, 전형적인 램지형 결과는 우리가 충분히 큰 완전한 그래프의 가장자리를 정해진 수의 색으로 색칠한다면, 우리는 반드시 특정한 유형의 단색 서브그래프를 찾을 수 있다고 말한다.^[29]기하학(또는 위상학) 그래프에 대해서도 비슷한 문제를 제기할 수 있는데, 지금은 특정한 기하학적 조건을 만족하는 단색(단색) 하부 구조를 찾는다는 점을 제외하면 말이다.^[30]이러한 종류의 첫 번째 결과 중 하나는 가장자리가 두 가지 색으로 색칠된 모든 완전한 기하학적 그래프는 교차하지 않는 단색 스패닝 트리를 포함하고 있다는 것이다.^[31]또한 그러한 기하학적 그래프마다${\displaystyle nn\frac{}{}}$+ ${\displaystyle \frac{\mathrm{}}{}}$ ${\displaystyle \frac{3}{}}$ ${\displaystyle \rceil }$ ${\${\$frac {n+1}{3$이 들어 있는 것도 사실이다.$}}\오른쪽\rceil }$ 같은 색상의 분리$$ 가장자리.^[31]c > 0이 상수인 최소 cn 크기의 비교차 단색 경로의 존재는 오랫동안 열려 있는 문제다.n 정점에 있는 모든 완전한 기하학적 그래프는 적어도 $n{\displaystyle {}^{}}$ 2 ${\displaystyle {\frac{3}{}}^{}}$ ${\$ n$^{\frac{2}{3}}}$ 길이의 비교차 단색 경로를 포함하고 있다는 것만 알려져 있다$.$^[32]

위상학 하이퍼그래프

위상학적 그래프를 1차원 단순화 콤플렉스의 위상학적 실현으로 본다면, 위의 극단적 문제와 램지형 문제가 d차원 단순화 콤플렉스의 위상적 실현에 어떻게 일반화되는지 묻는 것은 당연하다.이러한 방향에는 초기 결과가 있지만, 핵심 개념과 문제점을 파악하기 위해서는 추가 연구가 필요하다.^[33][34][35]

두 꼭지점 분리 단순화는 상대적인 내부 인테리어에 공통점이 있다면 교차한다고 한다.k > 3단계의 단순화 세트는 두 개 중 정점을 공유하지 않으면 강하게 교차하지만, 상대적인 인테리어는 공통점이 있다.

한 쌍의 교차 단순화$$ $없이{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$ d$${\$dplaystyle \mathb{R} ^{d$}}에서 n 포인트로 확장되는 d차원 단순화 집합은 최대 $O{\displaystyle ({}^{}}$ $){\dstaystyle$ O(n$^{d})$의 단순성을 가질 수 있으며 이 바운드는 점증상 타이트하다.^[36]이 결과는 세 가지 강력한 교차 단순화 없이$$ R ${\displaystyle {\mathrm{}}^{}}$ ${\$ 2차원 단순화 집합으로 일반화되었다.^[37]k가 단순성을 강하게 가로지르는 것을 금지하는 경우, 해당 가장 잘 알려진 $상한$은 $일부{\displaystyle }$ = Δ =$$, )< 1 ${\displaystyle \delta =\d)<1}$에 대한 O ${\displaystyle ({n\mathrm{d}}^{}}$ + 1${\displaystyle {}^{}}$- 1 - $delta$ ${\displaystyle {}^{}}$d$+\$delta $\}\}\}$^[36]이다 이 결과는 컬러 티베르그 정리에서 따온 것이다.^[38]$O{\displaystyle ({}^{}}$ $){\displaystyle O(n^{d})$의 추측 경계와는 거리가 멀다$.$^[36]

For any fixed k > 1, we can select at most ${\displaystyle O(n^{\lceil {\frac {d}{2}}\rceil })}$ d-dimensional simplices spanned by a set of n points in ${\displaystyle \mathbb {R} ^{d}}$ with the property that no k of them share a common interior point.^[36][39]이것은 점증상으로는 꽉 낀다.

$R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$의 두 삼각형은 분리되어 있거나 정점 하나만 공유하는 경우에는 거의 분리되어 있다고 한다$$.$R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{}}^{}}$ ${\$$R}{3$}{$}$의 일부 꼭지점에서 선택할 수 있는 거의 분리된 삼각형 수가 가장$$${\displaystyle }$많은지 여부를 결정하는 것은 길칼라이 등의 오래된 문제$.$ 이 숫자가 적어도 어느 정도인$$n개의 점 집합이 존재하는 것으로 알려져 있다$.$${\displaystyle c}$ ${\displaystyle {}^{}}$ 2 ${\displaystyle {\frac{3}{}}^{}}$ ${\$에 적합한$$ c > 0.^[40]

참조