단위 디스크 그래프

Unit disk graph
단위 원의 집합과 해당 단위 디스크 그래프.

기하학 그래프 이론에서 단위 원반 그래프는 유클리드 평면에 있는 단위 원반군의 교차 그래프이다.즉, 패밀리의 각 디스크에 대해 하나의 정점이 있고 대응하는 정점이 서로 단위 거리 내에 있을 때마다 두 정점 사이에 가장자리가 있는 그래프입니다.

일반적으로 포아송 점 공정에서 생성되므로 랜덤 구조의 단순한 예가 됩니다.

정의들

단위 디스크 그래프에는 스케일 팩터 선택까지 서로 동등한 몇 가지 정의가 있습니다.

  • 단위 디스크 그래프는 유클리드 평면의 점 집합에서 형성된 그래프이며, 각 점에 대한 정점과 거리가 고정된 임계값보다 낮은 각 점 쌍을 연결하는 모서리가 있습니다.
  • 단위 디스크 그래프는 등반경 원 또는 등반경 디스크의 교차 그래프입니다.이러한 그래프에는 각 원 또는 디스크에 대한 정점과 빈 교차가 없는 원 또는 디스크의 각 쌍을 연결하는 가장자리가 있습니다.
  • 단위 원반 그래프는 한 원이 다른 원의 중심을 포함할 때마다 두 개의 원을 가장자리로 연결함으로써 등반경의 원의 집합과는 다른 방법으로 형성할 수 있다.

특성.

단위 디스크 그래프의 유도 서브그래프는 모두 단위 디스크 그래프이기도 합니다.유닛 디스크 그래프가 아닌 그래프의 예로는 별 1, 6이 있으며, 중앙 노드가 6개의 리프에 연결되어 있습니다. 6개의 유닛 디스크 각각이 공통의 유닛 디스크에 닿으면 6개의 디스크 중 2개가 서로 닿아야 합니다.따라서 단위 디스크 그래프에는 된 K, 6 하위 [1]그래프를 포함할 수 없습니다.그 밖에도 엄청나게 많은 금지 유도 서브그래프가 [2]알려져 있다.

라벨이 붙은의 꼭지점에서의 디스크그래프 수는 n n[3]의 내에 있습니다.이러한 급격한 성장은 단위 디스크 그래프가 제한된 트윈 [4]너비를 가지지 않음을 의미합니다.

적용들

Huson & Sen(1995년)의 연구를 시작으로, 단위 디스크 그래프는 컴퓨터 과학에서 애드혹 무선 통신 네트워크의 토폴로지를 모델링하기 위해 사용되어 왔다.이 응용 프로그램에서는 노드가 기지국 없이 직접 무선 연결을 통해 연결됩니다.모든 노드가 균질하고 전방향 안테나를 갖추고 있다고 가정합니다.노드 위치는 유클리드 점으로 모델링되고, 한 노드로부터의 신호가 다른 노드에 의해 수신될 수 있는 영역은 원으로 모델링된다.모든 노드에 동일한 전력의 송신기가 있는 경우, 이러한 원은 모두 동일합니다.랜덤하게 생성된 디스크 중심을 가진 단위 디스크 그래프로 형성된 랜덤 기하학 그래프는 침투 및 기타 다양한 [5]현상의 모델로 사용되어 왔다.

계산의 복잡성

고정된 치수의 공간에 단위 디스크(또는 그 중심)의 컬렉션이 주어진 경우, 해시 테이블을 사용하여 서로 일정한 거리 내에 있는 모든 중심 쌍을 찾고 결과 목록을 필터링하여 해당 단위 디스크 그래프를 선형 시간 내에 구성할 수 있습니다.원들이 교차하는 한 쌍이 될 수 있습니다.이 알고리즘에서 고려하는 쌍 수와 최종 그래프의 에지 수의 비율은 상수이며 선형 시간 한계를 제공합니다.그러나 이 상수는 [6]차원의 함수로 기하급수적으로 증가합니다.

기하학 없이 주어진 그래프를 단위 디스크 [7]그래프로 나타낼 수 있는지 여부를 결정하는 것은 NP-hard(구체적으로는 실재론의 완전성)입니다.또한 단위 디스크 그래프 표현의 명시적 좌표를 출력하는 것은 다항식 시간에는 불가능할 수 있습니다. 이러한 [8]표현에 기하급수적으로 많은 비트의 정밀도를 필요로 하는 단위 디스크 그래프가 존재합니다.

그러나 이들 [9]그래프의 기하학적 구조를 사용함으로써 최대 독립 집합, 그래프 컬러링 및 최소 지배 집합과 같은 중요하고 어려운 그래프 최적화 문제를 효율적으로 근사화할 수 있으며 디스크 [10]표현에 따라 이들 그래프에 대해 최대 클리크 문제를 정확하게 다항식 시간에 해결할 수 있다.디스크 표현을 알 수 없고 추상 그래프가 입력으로 주어져도 다항식 시간 내에 최대 클리크 또는 그래프가 단위 [11]디스크 그래프가 아님을 증명하는 것이 가능하며, 탐욕 컬러링 [12]알고리즘을 이용하여 최적의 컬러링을 3근사할 수 있다.

「 」를 참조해 주세요.

  • 단위 디스크 그래프에서 사이클이 깨지는 알고리즘 문제인 장벽 복원력
  • 단위 디스크 그래프의 1차원 아날로그인 무관심 그래프
  • 페니 그래프, 디스크가 접선할 수 있지만 겹치지 않는 단위 디스크 그래프(접점 그래프)
  • 코인 그래프, (반드시 단위 크기는 아님) 디스크의 접촉 그래프
  • Vietoris-Rips 복합체, 단위 디스크 그래프의 일반화. 단위 거리로부터 단위 공간 내에 고차 위상 공간을 구축합니다.
  • 단위 거리 그래프: (여기서와 같이) 최대 한 개의 임계값이 아닌 정확히 한 개의 거리에 있는 점을 연결한 그래프입니다.

메모들

  1. ^ Dkibski, Junosza-Szaniawski 및 Leszyńska-Nowak(2020).
  2. ^ Atminas & Zamarev (2018).
  3. ^ McDiarmid & Muller (2014).
  4. ^ 보닛 등(2022).
  5. ^ 예를 들어 Dall & Christensen (2002)을 참조하십시오.
  6. ^ Bentley, Stanat & Williams(1977년).
  7. ^ Breu & Kirkpatrick(1998), Kang & Muller(2011).
  8. ^ McDiarmid & Mueller (2013).
  9. ^ 마라테 외(1994년), 마쓰이(2000년).
  10. ^ Clark, Colbourn & Johnson(1990).
  11. ^ Raghavan & Spinrad (2003)
  12. ^ Gréf, Stumpf 및 Weienenfels(1998).

레퍼런스

  • Atminas, Aistis; Zamaraev, Viktor (2018), "On forbidden induced subgraphs for unit disk graphs", Discrete & Computational Geometry, 60 (1): 57–97, doi:10.1007/s00454-018-9968-1, MR 3807349
  • 를 클릭합니다Bentley, Jon L.; Stanat, Donald F.; Williams, E. Hollins, Jr. (1977), "The complexity of finding fixed-radius near neighbors", Information Processing Letters, 6 (6): 209–212, doi:10.1016/0020-0190(77)90070-9, MR 0489084.
  • Bonnet, Édouard; Geniet, Colin; Kim, Eun Jung; Thomassé, Stéphan; Watrigant, Rémi (2022), "Twin-width II: small classes", Combinatorial Theory, 2 (2): P10:1–P10:42, arXiv:2006.09877, doi:10.5070/C62257876, MR 4449818
  • 를 클릭합니다Breu, Heinz; Kirkpatrick, David G. (1998), "Unit disk graph recognition is NP-hard", Computational Geometry: Theory and Applications, 9 (1–2): 3–24, doi:10.1016/s0925-7721(97)00014-x.
  • 를 클릭합니다Clark, Brent N.; Colbourn, Charles J.; Johnson, David S. (1990), "Unit disk graphs", Discrete Mathematics, 86 (1–3): 165–177, doi:10.1016/0012-365X(90)90358-O.
  • 를 클릭합니다Dall, Jesper; Christensen, Michael (2002), "Random geometric graphs", Physical Review E, 66: 016121, arXiv:cond-mat/0203026, Bibcode:2002PhRvE..66a6121D, doi:10.1103/PhysRevE.66.016121.
  • Dębski, Michał; Junosza-Szaniawski, Konstanty; Śleszyńska-Nowak, Małgorzata (2020), "Strong chromatic index of -free graphs", Discrete Applied Mathematics, 284: 53–60, doi:10.1016/j.dam.2020.03.024, MR 4115456
  • 를 클릭합니다Gräf, A.; Stumpf, M.; Weißenfels, G. (1998), "On coloring unit disk graphs", Algorithmica, 20 (3): 277–293, doi:10.1007/PL00009196, MR 1489033.
  • 를 클릭합니다Huson, Mark L.; Sen, Arunabha (1995), "Broadcast scheduling algorithms for radio networks", Military Communications Conference, IEEE MILCOM '95, vol. 2, pp. 647–651, doi:10.1109/MILCOM.1995.483546, ISBN 0-7803-2489-7.
  • 를 클릭합니다Kang, Ross J.; Müller, Tobias (2011), "Sphere and dot product representations of graphs", Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry (SoCG'11), June 13–15, 2011, Paris, France, pp. 308–314.
  • 를 클릭합니다Marathe, Madhav V.; Breu, Heinz; Hunt, III, Harry B.; Ravi, S. S.; Rosenkrantz, Daniel J. (1994), Geometry based heuristics for unit disk graphs, arXiv:math.CO/9409226.
  • 를 클릭합니다Matsui, Tomomi (2000), "Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs", Lecture Notes in Computer Science, Lecture Notes in Computer Science, 1763: 194–200, doi:10.1007/978-3-540-46515-7_16, ISBN 978-3-540-67181-7.
  • McDiarmid, Colin; Mueller, Tobias (2013), "Integer realizations of disk and segment graphs", Journal of Combinatorial Theory, Series B, 103 (1): 114–143, arXiv:1111.2931, Bibcode:2011arXiv1111.2931M, doi:10.1016/j.jctb.2012.09.004
  • McDiarmid, Colin; Müller, Tobias (2014), "The number of disk graphs", European Journal of Combinatorics, 35: 413–431, doi:10.1016/j.ejc.2013.06.037, MR 3090514
  • 를 클릭합니다Raghavan, Vijay; Spinrad, Jeremy (2003), "Robust algorithms for restricted domains", Journal of Algorithms, 48 (1): 160–172, doi:10.1016/S0196-6774(03)00048-8, MR 2006100.