모저 스핀들

Moser spindle
모저 스핀들
Moser spindle pseudotriangulation.svg
이름을 따서 명명됨레오 모저, 윌리엄 모저
정점7
가장자리11
반지름2
지름2
둘레3
자동형성8
색수4
색도 지수4
특성.평면의
단위 거리
라만 그래프
그래프 및 모수 표

그래프 이론에서 수학의 한 분야인 모저 스핀들(모저스의 스핀들 또는 모저 그래프라고도 함)은 수학자 레오 모저와 그의 동생 윌리엄의 이름을 딴 무방향 그래프로서 7개의 정점과 11개의 가장자리를 가지고 있다.[1]어떤 그래프 컬러링에도 4가지 색상이 필요한 단위 거리 그래프로, 그 존재는 평면의 색수가 최소 4개라는 것을 증명하는 데 사용할 수 있다.[2]

모세르 스핀들은 하조스 건설의 한 예라고 볼 수 있기 때문에 하조스의 이름을 따서 하조스 그래프로 불리기도 했다.[3]그러나 육각형 안에 새겨진 삼각형 형태의 다른 그래프에도 '하조스 그래프'라는 이름이 적용됐다.[4]

건설

모저 스핀들은 평면에 7가지 색상과 함께 단위 거리 그래프로 삽입된다.

단위 거리 그래프로서 모저 스핀들은 60도, 120도 각도의 2 rhombi에 의해 형성되어, rhombi의 옆면과 짧은 대각선이 등각 삼각형을 형성한다.나머지 두 개의 급각 정점이 서로 한 단위 거리만큼 떨어져 있도록 두 개의 rhombi는 그들의 급각 정점 중 하나를 공유하면서 평면에 배치된다.그래프의 11개의 가장자리는 8개의 회전수 면, 두 개의 짧은 대각선, 그리고 단위 거리 쌍의 급성 각도 정점 사이의 가장자리들이다.

모저 스핀들 하조스 건설

또한 Moser 스핀들은 기하학적 내장 없이 4개의 꼭지점에 두 개의 완전한 그래프로 시작하는 Hajos 구조를 사용하여 이론적으로 그래프로 구성될 수 있다.이 구성은 각 전체 그래프에서 가장자리를 제거하고, 제거된 가장자리의 끝점 중 두 개를 두 개의 가장자리에서 공유하는 단일 꼭지점으로 병합하며, 제거된 가장자리의 나머지 두 끝점을 연결하는 새 가장자리를 추가한다.[5]

Moser Spindle을 구성하는 또 다른 방법은 유틸리티3,3 그래프 K에서 가장자리 중 하나를 세분화하여 그래프의 보완 그래프로 만드는 것이다.[6]

Hadwiger-Nelson 문제에 대한 적용

하드와이거-넬슨 문제는 유클리드 평면의 점을 서로 단위 거리의 각 점 쌍에 다른 색상이 할당되도록 색칠하는 데 몇 가지 색상이 필요한지 묻는다.즉, 끝점이 평면의 모든 점이고 가장자리가 모두 단위 거리의 점 쌍인 무한 그래프의 색수를 요구한다.[2]

Moser Spindle은 어떤 그래프 색상에서든 4가지 색상을 필요로 한다. 즉, 그것이 형성되는 두 개의 rhombi 중 하나의 3가지 색상에서, rhombi의 두 개의 급각 정점들은 반드시 서로 같은 색상을 가질 것이다.그러나 두 rhombi의 공유 정점이 두 개의 반대쪽 급성 각도 정점과 동일한 색상을 갖는다면, 이 두 정점은 서로 동일한 색상을 가지며, 정점을 연결하는 가장자리의 끝점이 서로 다른 색으로 되어 있다는 요건을 위반한다.이 모순은 세 가지 색은 불가능하므로 적어도 네 가지 색은 필요하다는 것을 보여준다.모저 스핀들에 색칠을 할 수 있는 색도 4가지로 충분하며, 이는 그 퇴보성이 3가지라는 사실에서 비롯된다.

모저 스핀들이 4가지 색상을 요구한다는 대안적인 증거는 하조스 건설에서 나온다.Moser Spindle이 형성되는 전체 그래프에는 모두 4가지 색상이 필요하며, Hajos 구조는 이 특성을 보존한다.[5]더욱 직접적으로, Moser Spindle의 각 독립형 세트는 최대 두 개의 정점을 가지고 있기 때문에 [7]7개의 정점을 모두 커버하기 위해서는 최소 네 개의 독립형 세트가 필요하다.

모저 스핀들은 평면의 무한 단위 거리 그래프의 하위 그래프이기 때문에, 평면의 그래프 역시 어떤 색채에도 최소한 4가지 색상이 필요하다.de Bruijn-Erdős 정리(선택의 공리가 참이라는 가정 하에)에 의해 평면의 색채 수는 유한 서브그래프 중 가장 큰 색채 숫자와 동일하다; 2018년에 5색 단위 거리 그래프의 가족이 발견되기 전까지 무한 단위 거리 그래프의 하위 그래프는 발견되지 않았다.s Moser 스핀들보다 더 많은 수의 색상.그러나 평면의 색도 수에 대한 최적의 상한은 7로 모저 스핀들에 필요한 색의 수보다 현저히 높다.[2]

기타 속성 및 응용 프로그램

모저 스핀들은 평면 그래프로, 비행기에서 교차 없이 그릴 수 있다는 뜻이다.단, 단위 거리 도면인 직선 가장자리로는 그러한 도면을 형성할 수 없다. 즉, 즉 매치스틱 그래프가 아니다.모저 스핀들 역시 라만 그래프로, 평면에 삽입했을 때 최소 강체 시스템을 형성한다는 것을 의미한다.[8]평면형 라만 그래프로서 뾰족한 가성형 그래프로, 즉 내장이 없는 얼굴이 임베딩의 볼록한 선체가 되고 모든 경계형 얼굴이 볼록한 3개의 정점만을 가진 가성형인 방식으로 평면에 박힐 수 있다는 뜻이다.[9]

모저 그래프의 보완 그래프는 삼각형이 없는 그래프다.따라서 Moser 그래프의 단위 거리 포함은 점의 세 쌍이 서로 단위 거리에 최소한 한 쌍씩 포함되도록 평면에 7점을 배치하는 문제를 해결하는 데 사용될 수 있다.[2][10]

Moser 스핀들에 엣지를 추가하면 단위 거리 그래프로 평면에 삽입할 수 없는 그래프가 생성되며, Moser 스핀들에서 더 작은 단위 거리 그래프까지 그래프 동형성이 존재하지 않는다.Moser 스핀들의 이 두 특성은 Horvat, Kratochvil & Pisanski(2011)가 주어진 그래프의 2차원 단위 거리 표현 여부를 테스트하는 NP 경도를 보여주기 위해 사용했으며, 증거는 Moser 스핀들을 감소의 중심 진실 설정 기기로 사용하는 3SAT로부터의 축소를 사용한다.[8]

Moser 스핀들은 또한 유클리드 램지 이론의 결과를 증명하는데 사용될 수 있다: T가 평면의 어떤 삼각형이고, 평면의 지점이 두 가지 색상의 흑백이라면, T의 검정 번역이나 서로로부터 단위 거리에 한 쌍의 흰 점이 있다.M을 Moser Spindle의 단위 거리 임베딩으로 하고, M + T를 M과 T의 Minkowski 합으로 한다.M + T에 흰색 단위 거리 쌍이 없는 경우, M + T의 Moser 스핀들 3개 사본 각각은 최대 2개의 흰색 점을 가져야 한다. 각 사본의 흰색 점은 독립 세트를 형성해야 하고 Moser 스핀들 중 가장 큰 독립 세트는 크기가 2이기 때문이다.따라서 Moser Spindle의 7개의 정점 중 M + T에 흰색 사본이 있는 것이 기껏해야 6개가 있으므로, 모두 검은 사본이 있는 7개의 정점 중 하나가 있어야 한다.하지만 이 꼭지점의 세 복사본은 T의 번역을 형성한다.[7]

참고 항목

참조

  1. ^ Moser, L.; Moser, W. (1961), "Solution to problem 10", Can. Math. Bull., 4: 187–189.
  2. ^ a b c d Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, pp. 14–15, ISBN 978-0-387-74640-1.
  3. ^ Bondy, J. A.; Murty, U. S. R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 358, doi:10.1007/978-1-84628-970-5, ISBN 978-1-84628-969-9.
  4. ^ Berge, C. (1989), "Minimax relations for the partial q-colorings of a graph", Discrete Mathematics, 74 (1–2): 3–14, doi:10.1016/0012-365X(89)90193-3, MR 0989117.
  5. ^ a b Hajós, G. (1961), "Über eine Konstruktion nicht n-färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 116–117.
  6. ^ Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008), "Planar unit-distance graphs having planar unit-distance complement", Discrete Mathematics, 308 (10): 1973–1984, doi:10.1016/j.disc.2007.04.050, MR 2394465.
  7. ^ a b Burkert, Jeffrey; Johnson, Peter (2011), "Szlam's lemma: mutant offspring of a Euclidean Ramsey problem from 1973, with numerous applications", Ramsey theory, Progr. Math., vol. 285, Birkhäuser/Springer, New York, pp. 97–113, doi:10.1007/978-0-8176-8092-3_6, MR 2759046. Soifer(2008), 문제 40.26, 페이지 496을 참조하십시오.
  8. ^ a b Horvat, 보리스. Kratochvíl, 얀, Pisanski, Tomaž(2011년),"그 해석을 위한 복잡함 디제너레이트 단위 거리 Representations Graphs의", 것이 Combinatorial알고리즘:21세기 국제 워크숍 IWOCA 2010년 영국 런던 7월 26-28일, 2010년에는 선택된 논문 개정된, 강의 노트 컴퓨터 과학으로,,를 대신하여 서명함. 274–285, arXiv:1001.0886, Bibcode 6460 vol..:2011LNCS.6460..274H, doi:10.1007/978-3-642-19222-7_28, 아이 에스비엔 978-3-642-19221-0.
  9. ^ Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications, 31 (1–2): 31–61, arXiv:math/0307347, doi:10.1016/j.comgeo.2004.07.003, MR 2131802.
  10. ^ Winkler, Peter (November 2011), "Puzzled: Distances Between Points on the Plane", Communications of the ACM, 54 (11): 120, doi:10.1145/2018396.2018422.솔루션, 이슈 12, 2011년 12월, doi:10.1145/2043174.2043200.

외부 링크