매치스틱 그래프

Matchstick graph
고유한 가장 작은 큐빅 매치스틱 그래프
항만 그래프
Harborth graph vector.svg
정점52
가장자리104
반지름6
지름9
둘레3
그래프 및 모수 표
3-정규 매치스틱 그래프
Winkler 3-reg girth5 54.svg
정점54
가장자리81
둘레5
그래프 및 모수 표

수학의 한 가지인 기하학적 그래프 이론에서 성냥개비 그래프는 가장자리가 서로 교차하지 않는 길이 1의 선분할을 갖는 선분할을 하도록 평면에 그릴 수 있는 그래프다.즉, 단위 거리 그래프와 평면 그래프를 동시에 포함하는 그래프다.이러한 이유로 매치스틱 그래프는 평면 단위 거리 그래프라고도 불린다.[1]비공식적으로 성냥개비 그래프는 평평한 표면에 성냥개비가 아닌 성냥개비를 배치하여 만들 수 있으며, 따라서 이름이다.[2]

일반 매치스틱 그래프

성냥개비 그래프에 대한 많은 연구는 각각의 꼭지점에 동일한 수의 이웃이 있는 규칙적인 그래프와 관련이 있다.이 숫자를 그래프의 정도라고 한다.

최대 4까지 어느 정도 규칙적인 성냥개비 그래프가 있는 것으로 알려져 있다.정점 1개, 2개, 3개의 정점(단일 꼭지점, 단일 에지, 삼각형)이 있는 전체 그래프는 모두 매치스틱 그래프로서 각각 0, 1-, 2- 정규 그래프다.가장 작은 3-정규 성냥개 그래프는 정점이 서로 단위 거리에 있도록 배치된 다이아몬드 그래프의 두 복사본으로부터 형성된다. 그것의 초당적 이중 커버는 8-크로스 프리즘 그래프다.[2]

1986년, 하이코 하버스는 그의 이름인 하버스 그래프를 표시할 그래프를 제시했다.104개의 가장자리와 52개의 정점을 가진, 4-정규 매치스틱 그래프의 가장 작은 예다.[3]그것은 경직된 그래프다.[4]

매 4개의 규칙적인 성냥개비 그래프에는 적어도 20개의 꼭지점이 들어 있다.[5]4-정규 매치스틱 그래프의 예는 현재 53, 55, 56, 58, 59, 61, 62를 제외한 모든 정점 수 52 52에 대해 알려져 있다.54, 57, 65, 67, 73, 74, 77, 85 정점을 가진 그래프는 2016년에 처음 출판되었다.52, 54, 57, 60 및 64 정점의 경우 하나의 예만 알려져 있다.이 5개의 그래프 중 60개의 꼭지점이 있는 그래프만 유연하고 나머지 4개는 경직적이다.[6]

일반 성냥개비 그래프의 도수가 4보다 큰 것은 불가능하다.[5]삼각형이 없는 가장 작은 3정형 매치스틱 그래프(거스 ≥ 4)는 쿠르츠와 마쯔오콜로가 증명하듯 정점이 20개다.[7]3정형 성냥개비 그래프의 가장 작은 예는 54정점을 가지며 2019년 마이크 윙클러가 처음 제시한 것이다.[8]

계산 복잡성

주어진 비방향 평면 그래프를 매치스틱 그래프로 실현할 수 있는지 여부를 테스트하는 것은 NP-힘든 일이다.[9][10]더 정확히 말하면, 이 문제는 실존자의 실존이론에 대해서는 완전한 것이다.[11]커즈(2011년)는 그래프가 성냥개비 그래프가 되는 데 필요한 몇 가지 기준을 쉽게 제시하지만, 이것들 역시 충분한 기준은 아니다. 즉, 그래프가 커즈의 테스트를 통과해도 성냥개비 그래프는 아닐 수 있다.[12]

또한 그래프의 정점이 모두 문제에 대한 입력의 일부로 주어진 정수 좌표를 갖는 경우에도 매치스틱 그래프가 해밀턴 사이클을 가지는지 여부를 확인하는 것이 NP-완전하다.[13]

콤비네이터 열거

고유(비이성형) 매치스틱 그래프의 수는 1, 2, 3, ... 최대 10개의 가장자리에 대해 알려져 있다. 이 그래프들은 다음과 같다.

1, 1, 3, 5, 12, 28, 74, 207, 633, 2008([14][15]직렬 A066951)

예를 들어, 성냥개비 3개로 만들 수 있는 세 개의 다른 그래프는 집게발, 삼각형 그래프, 그리고 세 개의 가장자리 경로 그래프다.

그래프의 특수 클래스

가장자리 길이의 균일성은 그래프 그리기에서 바람직한 품질로 오랫동안 보여 왔으며,[16] 일부 특정 등급의 평면 그래프는 항상 완전히 균일한 가장자리로 그릴 수 있다.

모든 나무는 나무의 잎 가장자리가 무한 광선으로 대체된다면, 그 그림은 어떤 교차도 없이 평면을 볼록한 폴리곤 영역으로 분할할 수 있는 방식으로 그려질 수 있다.이러한 도면의 경우 가장자리의 기울기를 변경하지 않고 각 가장자리의 길이를 임의로 변경하면 도면이 평면적으로 유지된다.특히 모든 가장자리의 길이가 같도록 선택할 수 있어 성냥개비 그래프로 임의의 트리가 실현된다.[17]

성냥개비 그래프로서의 사각형 그래프 실현

사각형 그래프, 평면 그래프는 모든 경계면이 사방형이고 모든 꼭지점이 한이 없는 얼굴에 놓여 있거나 최소한 네 개의 이웃을 가지고 있는 방식으로 평면에 그려질 수 있다.이러한 그래프는 모든 면의 평행도 문자로 그릴 수 있는데, 만약 모든 면에 평행한 가장자리의 부분집합이 모두 같은 길이를 가지도록 동시에 연장되거나 짧아진다면, 어떤 교차도 도입할 수 없다.특히 가장자리의 길이가 모두 같도록 가장자리를 정상화하는 것이 가능하며, 성냥개비 그래프로 어떤 사각형 그래픽도 실현할 수 있다.[18]

그래프의 관련 클래스

모든 성냥개비 그래프는 단위 거리 그래프다.페니 그래프는 겹치지 않는 단위 원의 접선으로 나타낼 수 있는 그래프다.모든 페니 그래프는 성냥개비 그래프다.그러나 일부 매치스틱 그래프(첫 번째 그림의 8Vertex 세제곱 성냥개 그래프 등)는 페니 그래프가 아니다. 왜냐하면 이를 매치스틱 그래프로 인식하면 일부 비인접 정점이 서로 단위 거리보다 더 가까워지기 때문이다.

참조

  1. ^ 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
  2. ^ a b Weisstein, Eric W., "Matchstick graph", MathWorld
  3. ^ Harborth, 하이코(1994년),"비행기에서 막대기를 담고 있습니다.", 가이, R.K.에, 우드 로우, R.E.(eds.), 그 라이터 사이드 수학의:.는 프랑스의 Strens 기념관 회의 휴양 수학의 역사, 캐나다 캘거리, 1986, 워싱턴 DC의 회보:.수학 협회는 미국의, pp. 281–288.으로서 Weisstein, 에릭은 W.,"Matchstick 그래프", 매스 월드:에 인용한.
  4. ^ 자세한 내용은 의 이전 사전 인쇄를 참조하십시오Gerbracht, Eberhard H.-A. (2011), "Symbol-crunching the Harborth graph", Advances in Applied Mathematics, 47 (2): 276–281, doi:10.1016/j.aam.2010.09.003, MR 2803803.
  5. ^ a b Kurz, Sascha; Pinchasi, Rom (2011), "Regular matchstick graphs", American Mathematical Monthly, 118 (3): 264–267, arXiv:1401.4372, doi:10.4169/amer.math.monthly.118.03.264, MR 2800336, S2CID 866740.
  6. ^ Winkler, Mike; Dinkelacker, Peter; Vogel, Stefan (2017), "New minimal (4; n)-regular matchstick graphs", Geombinatorics, 27: 26–44, arXiv:1604.07134.
  7. ^ Kurz, Sascha; Mazzuoccolo, Giuseppe (2010), "3-regular matchstick graphs with given girth", Geombinatorics, 19: 156–175, arXiv:1401.4360.
  8. ^ Winkler, Mike; Dinkelacker, Peter; Vogel, Stefan (2020), "A 3-regular matchstick graph of girth 5 consisting of 54 vertices", Geombinatorics, 29: 116–121, arXiv:1903.04304.
  9. ^ Eades, Peter; Wormald, Nicholas C. (1990), "Fixed edge-length graph drawing is NP-hard", Discrete Applied Mathematics, 28 (2): 111–134, doi:10.1016/0166-218X(90)90110-X.
  10. ^ Cabello, Sergio; Demaine, Erik D.; Rote, Günter (2007), "Planar embeddings of graphs with specified edge lengths" (PDF), Journal of Graph Algorithms and Applications, 11 (1): 259–276, doi:10.7155/jgaa.00145.
  11. ^ 아벨, 재커리, Demaine, 에릭은 D;Demaine, 마틴 L.;Eisenstat, 사라는, 린치, 제이슨, Schardl, 도교는 B(2016년),"누가 건널목이 필요로 하나요?페케테, Sándor, Lubiw, 안나(eds.), 32위 국제 심포지엄에 기하학에(SoCG 2016년)에서 비행기를 그래프의 경도 rigidity", 라이프니츠 국제 담론 정보 과학(LIPIcs)에서, 51, Dagstuhl, 독일:슐로스 Dagstuhl–Leibniz-Zentrum fuer Informatik,를 대신하여 서명함 vol.. 3:1–3:15, doi:10.4230/LIPIcs.SoCG.2016.3, 아이 에스비엔 978-3-95977-009-5.
  12. ^ Kurz, Sascha (2011), "Fast recognition of planar non unit distance graphs", Geombinatorics, 21 (1): 25–33, arXiv:1401.4375, MR 2858668.
  13. ^ Itai, Alon; Papadimitriou, Christos H.; Szwarcfiter, Jayme Luiz (1982), "Hamilton paths in grid graphs", SIAM Journal on Computing, 11 (4): 676–686, doi:10.1137/0211056, MR 0677661.
  14. ^ Salvia, Raffaele (2013), "A catalog for matchstick graphs", arXiv:1303.5965 [math.CO]
  15. ^ Vaisse, Alexis (2015), Matchstick graphs with up to 10 edges
  16. ^ Fruchterman, Thomas M. J.; Reingold, Edward M. (1991), "Graph Drawing by Force-Directed Placement", Software: Practice & Experience, Wiley, 21 (11): 1129–1164, doi:10.1002/spe.4380211102, S2CID 31468174.
  17. ^ 칼슨지라도, 요시야, Eppstein, 데이비드(2006년)," 볼록한 얼굴과 최적의 각도를 이루는 나무들", 카우프만, 마이클에;바그너, 도로시아(eds.), 14국제 심포지엄 Graph도면에, 강의 노트 컴퓨터 과학으로, 회보 pp 4372, Springer-Verlag, vol.. 77–88,arXiv:cs.CG/0607113,doi:10.1007/978-3-540-70904-6_9, 아이 에스비엔 978-3-540-70903-.9, MR2393907, S2CID 12598338.
  18. ^ Eppstein, David; Wortman, Kevin A. (2011), "Optimal angular resolution for face-symmetric drawings", Journal of Graph Algorithms and Applications, 15 (4): 551–564, arXiv:0907.5474, doi:10.7155/jgaa.00238, S2CID 10356432.