교차수(그래프 이론)

그래프 이론에서 그래프 G의 교차 번호 cr(G)는 그래프 G의 평면 도면의 가장 낮은 에지 교차 수입니다.예를 들어, 그래프는 교차 번호가 0인 경우에만 평면형이다.사용자 연구에서 교차점이 거의 없는 그래프를 그리면 사람들이 그리기를 더 쉽게 이해할 수 있다는 것을 보여주었기 때문에 그래프 그리기에서 교차 수를 결정하는 것은 매우 중요하다.^[1]

건널목 수에 대한 연구는 Pal Turan이 벽돌 가마와 저장지를 연결하는 선로 사이의 건널목 수를 최소화하는 공장 계획을 요청한 Turan의 벽돌 공장 문제에서 비롯되었다.수학적으로 이 문제는 완전한 초당적 그래프의 교차 번호를 묻는 것으로 공식화할 수 있다.^[2]사회문헌의 구축과 관련하여 거의 동시에 사회학에서도 같은 문제가 독자적으로 발생했다.^[3]전체 초당적 그래프의 교차 숫자에 대한 투란의 추정 공식은 전체 그래프에 대한 유사한 공식과 마찬가지로 검증되지 않은 상태로 남아 있다.

교차 번호 불평등은 가장자리 수 e가 정점 수 n보다 충분히 큰 그래프의 경우 교차 번호가 적어도 e³/n에² 비례한다고 명시한다.VLSI 설계와 입사 기하학에서 응용이 가능하다.

추가 적격성 없이 교차 번호는 가장자리가 임의 곡선으로 표현될 수 있는 도면을 허용한다.이 개념의 변화인 직선 교차 수는 모든 가장자리가 직선 세그먼트여야 하며 교차 번호와 다를 수 있다.특히 전체 그래프의 직선 교차 수는 일반 위치의 n개 점 집합에 의해 결정되는 볼록 사분면 측정의 최소 수와 본질적으로 동일하다.이 숫자를 결정하는 문제는 해피엔딩 문제와 밀접한 관련이 있다.^[4]

정의들

교차 숫자를 정의할 때, 방향하지 않은 그래프의 도면은 그래프의 꼭지점에서 평면 내 연결점 분리까지의 매핑이며, 그래프의 가장자리에서 두 끝점을 연결하는 곡선으로의 매핑이다.어떤 꼭지점도 끝점이 아닌 가장자리에 매핑되어서는 안 되며, 두 가장자리가 교차하는 곡선을 가질 때마다(공유 끝점이 아닌) 교차점은 두 곡선이 횡방향인 적절한 교차점의 유한 집합을 형성해야 한다.교차점은 교차하는 각 가장자리 쌍에 대해 이러한 교차점에 대해 별도로 계산된다.그래프의 교차 번호는 모든 도면에 걸쳐 도면의 교차 횟수에 대한 최소값이다.^[5]

일부 저자들은 도면의 정의에 더 많은 제약조건을 부가한다. 예를 들어 각 가장자리 쌍은 최대 하나의 교차점(공유 끝점 또는 교차점)에 있다.위에서 정의한 교차 숫자의 경우 교차 최소 도면에 다중 교차점이 있는 가장자리가 있을 수 없으므로 이러한 제약조건은 차이를 보이지 않는다.공유 끝점 교차점이 있는 두 모서리가 있는 경우 교차점에서 도면을 로컬로 변경하여 나머지 도면은 변경하지 않고 한 개의 교차점이 적은 다른 도면을 생성할 수 있다.그리고 마찬가지로 두 개의 가장자리가 두 번 이상 교차할 경우 두 개의 교차점에서 국소적으로 도면을 변경하여 두 개의 교차점이 적은 다른 도면을 만들 수 있다.단, 이러한 제약조건은 교차점 수보다는 교차하는 가장자리 쌍의 수만을 계산하는 교차점 숫자의 변형 정의와 관련이 있다.^[5]

특례

2015년 4월 현재 교차 번호는 극히 일부 그래프 계열로 알려져 있다.특히 일부 초기 사례를 제외하고 전체 그래프, 초당적 전체 그래프, 사이클의 곱의 교차 수는 하한선에서 어느 정도 진전이 있었지만 모두 알 수 없는 상태로 남아 있다.^[6]

완전한 초당적 그래프

제2차 세계 대전 동안 헝가리 수학자 팔 투란은 벽돌 공장에서 일해야 했고, 가마에서 창고로 벽돌을 실은 짐마차를 밀었다.공장에는 각 가마에서 각 저장장소까지 자국이 있었고, 마차들은 서로 교차하는 지점에서는 밀기가 더 어려웠는데, 이 지점에서 투란은 벽돌 공장 문제를 묻게 되었다: 가마, 저장장소, 선로가 총 건널목 수를 최소화하기 위해 어떻게 배열될 수 있을까?수학적으로 가마와 저장 부지는 완전한 초당적 그래프의 정점으로 공식화할 수 있으며, 선로는 가장자리를 이룬다.공장 배치도는 이 그래프의 도면으로 나타낼 수 있기 때문에 문제는 완전한 초당적 그래프의 도면에서 가능한 최소 교차 수는 얼마인가?^[7]

Kazimierz Zarankiewicz는 Turan의 벽돌 공장 문제를 해결하려고 시도했다;^[8] 그의 증명에는 오류가 포함되어 있었지만, 그는 유효한 상한을 설정했다.

${\displaystyle {\textrm {cr}}(K_{m,n})\leq \left\lfloor {\frac {n}{2}}\right\rfloor \left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {m}{2}}\right\rfloor \left\lfloor {\frac {m-1}{2}}\right\rfloor }$

전체 초당 그래프 K의_m,n 교차 번호에 대해.이 한계치는 모든 완전한 양분 그래프에 대한 최적의 교차 수로 추측되었다.^[9]

전체 그래프 및 그래프 컬러링

전체 그래프의 교차번호를 결정하는 문제는 앤서니 힐이 처음 제기했고, 1960년 인쇄에 등장했다.^[10]힐과 그의 협력자 존 어니스트는 수학에 매료된 두 명의 건축가였다.그들은 이 문제를 공식화했을 뿐만 아니라 이 교차점 숫자에 대한 추측 공식을 만들어냈는데, 이 공식을 리차드 K가 만들었다. 1960년에 출판된 남자.^[10]즉, 항상 도면이 있는 것으로 알려져 있다.

${\displaystyle {\textrm {cr}}(K_{p})\leq {\frac {1}{4}}\left\lfloor {\frac {p}{2}}\right\rfloor \left\lfloor {\frac {p-1}{2}}\right\rfloor \left\lfloor {\frac {p-2}{2}}\right\rfloor \left\lfloor {\frac {p-3}{2}}\right\rfloor }$

건널목이 공식은 p = 5, ..., 12에 대해 1, 3, 9, 18, 36, 60, 100, 150의 값을 제공하며, 온라인 정수 백과사전 A000241을 참조한다.추측에 따르면 더 나은 그림은 없을 것이고, 그래서 이 공식은 전체 그래프에 대한 최적의 교차 수를 제공한다.1964년 토마스 L. Saaty에 의해 같은 추측의 독립적인 공식화가 이루어졌다.^[11]

Saaty는 또한 이 공식이 p ≤ 10에 대해 최적의 교차 횟수를 제공한다는 것을 검증했고 Pan과 Richter도 p = 11, 12에 최적임을 보여주었다.^[12]

마이클 오가 공식화한 앨버트슨 추측.2007년 Albertson은 색수 n을 가진 모든 그래프 중에서 전체 그래프 K는_n 최소 교차 횟수를 가지고 있다고 말한다.즉, 전체 그래프의 교차 숫자에 대한 추측 공식이 정확하다면, 모든 n-색깔 그래프는 최소한 동일한 공식과 같은 교차 수를 갖는다.알버트슨 추측은 현재 n≤ 16을 지탱하고 있는 것으로 알려져 있다.^[13]

입방 그래프

교차 번호 1-8과 11을 가진 가장 작은 입방형 그래프가 알려져 있다(OEIS에서 순서 A110507).가장 작은 1크로싱 입방 그래프는 6개의 정점을 가진 완전한 초당적 그래프 K이다_3,3.가장 작은 2 교차 입방 그래프는 10개의 정점을 가진 피터슨 그래프다.가장 작은 3 교차 입방 그래프는 히우드 그래프인데 14개의 정점을 가지고 있다.가장 작은 4크로싱 입방 그래프는 뫼비우스-칸토르 그래프로 16개의 꼭지점이 있다.가장 작은 5크로싱 입방 그래프는 파푸스 그래프인데 18개의 꼭지점이 있다.가장 작은 6크로싱 입방 그래프는 데스아게스 그래프인데, 정점이 20개 있다.정점이 22개인 7크로스 입방형 그래프 4개 중 잘 알려진 것은 없다.^[14]가장 작은 8-크로싱 입방형 그래프에는 나우루 그래프와 맥기 그래프 또는 (3,7)-케이지 그래프가 있으며, 꼭지점이 24개 있다.^[15]가장 작은 11 교차 입방 그래프에는 28개의 정점이 있는 Coxeter 그래프가 포함된다.^[16]

2009년 페그와 엑소는 교차 번호 13을 가진 가장 작은 입방 그래프는 투트-콕시터 그래프, 교차 번호 170을 가진 가장 작은 입방 그래프는 투트 12-케이지라고 추측했다.^[15][17]

복잡성 및 근사치

일반적으로, 그래프의 교차 숫자를 결정하는 것은 어렵다; 게리와 존슨은 1983년에 그것이 NP-hard 문제라는 것을 보여주었다.^[18]사실, 이 문제는 입방형^[19] 그래프와 평면근접 그래프(단일 에지 제거 후 평면도가 되는 그래프)로 제한되어도 NP-hard로 남아 있다.^[20]직선으로 교차하는 숫자를 결정하는 밀접하게 연관된 문제는 실존자의 실존적 이론을 위해 완성된다.^[21]

긍정적인 측면에서는 교차 숫자가 고정 상수 k보다 작은지 여부를 판단하는 효율적인 알고리즘이 있다.즉, 문제는 고정변수(고정변수)를 다루기 쉽다는 것이다.^[22][23]k = V /2와 같이 큰 k의 경우에는 여전히 어렵다.또한 경계도 그래프에 cr(G) 근사치를 위한 효율적인 근사 알고리즘이 있다.^[24]실제에서는 가장자리 없이 시작하고 가능한 가장 적은 추가 교차점을 생성하는 방식으로 각각의 새로운 가장자리를 지속적으로 추가하는 간단한 알고리즘과 같은 경험적 경험적 알고리즘이 사용된다.이러한 알고리즘은 직선 교차 번호 분산 컴퓨팅 프로젝트에서 사용된다.^[25]

건널목의 부등식

n 정점과 e > 7n과 같은 에지가 있는 비방향 단순 그래프 G의 경우 교차 번호는 항상 최소한이다.

${\displaystyle \operatorname {cr}(G)\geq {\frac {e^{3}{29n^{2}}.}$

가장자리, 꼭지점, 교차번호 사이의 이러한 관계는 아제타이, 차바탈, 신생아, 스제메레디와 레이튼에 의해 독립적으로 발견되었다.^[26][27]건널목수 불평등 또는 건널목 보조정리라고 알려져 있다.

상수 29는 현재까지 가장 잘 알려진 것으로 애커맨 덕분이다.^[28]상수 7은 4로 낮출 수 있지만, 29를 더 나쁜 상수 64로 교체하는 비용을 부담해야 한다.^[26][27]

Leighton이 교차 숫자를 연구한 동기는 이론 컴퓨터 과학에서 VLSI 설계에 적용하기 위한 것이었다.^[27]후에 스제켈리는 또한 이러한 불평등이 벡의 정리나 스제메레디-트로터 정리처럼 발생 기하학에서 중요한 몇 가지 이론에 대한 아주 간단한 증거를 산출한다는 것을 깨달았고,^[29] 타말 데이는 그것을 기하학적 k-set에 대한 상한을 증명하는 데 사용하였다.^[30]

변형

임의 곡선이 아닌 직선 세그먼트로 가장자리를 그려야 하는 경우, 일부 그래프에는 더 많은 교차점이 필요하다.직선 교차 번호는 이 형식의 도면의 최소 교차 수로 정의된다.이 값은 항상 최소한 교차 숫자만큼 크며, 일부 그래프에서는 더 크다.K₅ ~ K의₁₂ 직선 교차 번호는 1, 3, 9, 19, 36, 62, 102, 153, (A014540)이며₂₇ K까지의 값은 알려져 있으며₂₈, K는 7233 또는 7234 교차가 필요하다.추가 값은 직선 교차 번호 프로젝트에 의해 수집된다.^[25]

그래프는 가장자리당 최대 k개의 교차점을 사용하여 그릴 수 있는 경우 로컬 교차 번호 k를 가진다.가장자리당 최대 k개의 교차점을 사용하여 그릴 수 있는 그래프를 k-planar라고도 한다.^[31]

교차 번호의 다른 변형에는 쌍 교차 번호(도면에서 교차하는 가장자리의 최소 쌍 수)와 홀수 교차 번호(도면에서 홀수 횟수를 교차하는 가장자리의 쌍 수)가 포함된다.홀수 교차 번호는 최대 한 쌍의 교차 숫자와 같으며, 최대 교차 숫자와 동일하다.그러나 하나니-에 의해투트 정리, 이 숫자 중 하나가 0일 때마다 모두 0이다.^[5]Schaefer(2014, 2018)는 그러한 많은 변종들을 조사한다.^[32][33]

참고 항목

• 평면화, 각 교차점을 새 꼭지점으로 대체하여 형성된 평면 그래프
• 세 개의 유틸리티 문제, 0개의 교차점으로 K를_3,3 그릴 수 있는지 여부를 묻는 퍼즐

참조