교차로 번호(그래프 이론)

Intersection number (graph theory)

그래프 이론의 수학적 분야에서 그래프 G = (V,E)의 교차로 번호는 유한 집합의 교차로 그래프로서 G를 나타내는 원소의 최소 수이다.동등하게 G의 모든 가장자리를 덮는 데 필요한 가장 적은 수의 군집이다.[1][2]

교차로 그래프

F의 교차 그래프는 F의 각 멤버에 대한 정점과 비어 있지 않은 교차점이 있는 각 멤버 사이의 가장자리가 있는 비방향 그래프다.모든 그래프는 이런 식으로 교차 그래프로 나타낼 수 있다.[3]그래프의 교차로 번호는 F의 조합이 k 요소를 갖는 이 유형의 표현이 존재할 수 있는 가장 작은 수 k이다.[1]주어진 수의 요소가 있는 그래프의 교차점 표현을 찾는 문제를 교차로 그래프 기반 문제라고 한다.[4]

클라이크 엣지 커버

네 번째 교차점이 있는 그래프.음영 영역 4개는 그래프의 모든 가장자리를 덮는 부류를 나타낸다.

그래프를 G의intersection 수의 대체 정의 파벌이 G에서 가장 작은 번호(G의 완전한 subgraphs)그 모든 이 속성에 파벌이 G.[1][5]A세트 가장자리의 덮개를 덮은 패거리 가장자리나 덮개 가장자리 고질적인 패거리 위장하는데 이런 이유 때문이 교차로 수는 때때로 있는 것으로 알려져 있다. 그 교육ge clique cover [6]number

교차로 번호와 가장자리 클라이크 커버 번호의 동일성은 입증하기가 쉽다.한 방향에서 G가 조합 U가 k 요소를 갖는 집합 F의 교차 그래프라고 가정한다.그런 다음 U의 어떤 원소 x의 경우, x를 포함하는 집합에 해당하는 G의 정점 부분 집합은 하나의 패를 형성한다: 이 부분 집합의 정점 두 개는 x를 포함하는 비어 있지 않은 교차점을 가지기 때문에 인접한다.또한, G의 모든 가장자리는 이들 중 하나에 포함되는데, 그 이유는 가장자리는 비빈 교차로에 해당하고, 가장자리는 U의 요소 하나 이상 포함하면 비어 있지 않은 교차로에 해당하기 때문이다. 따라서 G의 가장자리는 U의 요소 하나당 한 개씩인 kclik로 덮을 수 있다. 다른 방향에서 그래프 G는 kclik로 덮을 수 있다면 각 vert가 된다.G의 ex는 그 꼭지점을 포함하는 clique 집합으로 나타낼 수 있다.[5]

상한

사소한 경우, m 가장자리가 있는 그래프는 최대 m의 교차로 번호를 가지는데, 각 가장자리는 패거리를 형성하고 이러한 패거리들이 모든 가장자리를 함께 덮기 때문이다.[7]

정점이 n개인 모든 그래프에는 최대 n2/4의 교차로 번호가 있는 것도 사실이다.더 강하게 말하면, 모든 n-vertex 그래프의 가장자리는 최대2 n/4개의 크립크로 분할할 수 있으며, 이들 모두 단일 가장자리 또는 삼각형이다.[2][5]이것은 삼각형이 없는 그래프가 최대 n2/4 에지를 갖는 맨텔의 정리를 일반화하는데, 삼각형이 없는 그래프의 경우 최적의 클라이크 에지 커버는 에지당 하나의 클라이크를 가지며, 따라서 교차로 번호는 에지 수와 같다.[2]

가장자리 수가 n2/4보다 확실히 클 때 더욱 엄격한 경계는 가능하다.p는 주어진 그래프 G에서 에지로 연결되지 않은 꼭지점 쌍의 수로 하고, (t - 1)t t p < t(t + 1)의 고유한 정수로 한다.그러면 G의 교차로 번호는 최대 p + t이다.[2][8]

희소성 그래프의 보완인 그래프에는 작은 교차점 번호가 있다. n-vertex 그래프 G의 교차로 번호는 최대 2e2(d + 1)2ln n이며, 여기서 e는 자연 로그의 기저값이고 d는 G의 보완 그래프의 최대 수준이다.[9]

계산 복잡성

주어진 그래프 G에 주어진 숫자 k가 교차로 번호가 있는지 여부를 검정하는 것은 NP-완전이다.[4][10][11]따라서 주어진 그래프의 교차로 번호를 계산하는 것도 NP-힘들다.

그러나 교차로 번호를 계산하는 문제는 고정 매개변수 추적가능하다. 즉, 교차로 번호가 k일 때 계산하는 시간이 기껏해야 f(k)의 산물이고 n은 다항식인 함수 f가 있다.이것은 그래프에 적어도 두 개의k 구별되는 폐쇄된 이웃이 있다는 것을 관찰함으로써 보여질 수 있다. 즉, 동일한 분류 집합에 속하는 두 정점들은 같은 근방을 가지고 있다. 그리고 닫힌 이웃당 하나의 꼭지점을 선택하여 형성된 그래프는 원래 그래프와 동일한 교차로 번호를 가지고 있다.따라서 다항식 시간에는 입력을 정점이 최대 2개인k 작은 커널로 줄일 수 있다. 이 커널에 지수적인 시간 역추적 검색 절차를 적용하면 k의 이중 지수인 함수 f가 된다.[12]다항식 계층구조가 무너지지 않는 한 k에 대한 이중외상 의존도를 다항식 크기의 커널화에 의해 단일 지수화로 줄일 수 없으며,[13] 지수적 시간 가설이 사실이라면 커널화의 사용 여부에 관계없이 이중외상 의존이 필요하다.[14]

보다 효율적인 알고리즘은 특정 종류의 그래프로도 알려져 있다.구간 그래프의 교차로 번호는 항상 다항식 시간으로 계산될 수 있는 최대 구획 수와 동일하다.[15][16]보다 일반적으로, 화음 그래프에서 교차점 번호는 그래프의 제거 순서에서 정점을 고려하는 알고리즘으로 계산할 수 있으며, 각 정점 v에 대해 v에 발생한 가장자리 중 적어도 하나가 이전의 어떤 집단에서 다루지 않을 때마다 v와 그 이후의 이웃에 대한 정점을 형성한다.[16]

참고 항목

  • 초당적 치수, 그래프의 모든 가장자리를 덮는 데 필요한 최소의 양수
  • 그래프의 모든 정점을 커버하는 소수의 크레이크를 찾는 NP 하드 문제인 클라이크 커버

참조

  1. ^ a b c Gross, Jonathan L.; Yellen, Jay (2006), Graph Theory and its Applications, CRC Press, p. 440, ISBN 978-1-58488-505-4
  2. ^ a b c d Roberts, Fred S. (1985), "Applications of edge coverings by cliques", Discrete Applied Mathematics, 10 (1): 93–109, doi:10.1016/0166-218X(85)90061-7, MR 0770871
  3. ^ Szpilrajn-Marczewski, Edward (1945), "Sur deux propriétés des classes d'ensembles", Fundamenta Mathematicae (in French), 33: 303–307, doi:10.4064/fm-33-1-303-307, MR 0015448
  4. ^ a b Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, 문제 GT59
  5. ^ a b c Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966), "The representation of a graph by set intersections" (PDF), Canadian Journal of Mathematics, 18 (1): 106–112, CiteSeerX 10.1.1.210.6950, doi:10.4153/CJM-1966-014-3, MR 0186575
  6. ^ Michael, T. S.; Quint, Thomas (2006), "Sphericity, cubicity, and edge clique covers of graphs", Discrete Applied Mathematics, 154 (8): 1309–1313, doi:10.1016/j.dam.2006.01.004
  7. ^ Balakrishnan, V. K. (1997), Schaum's outline of theory and problems of graph theory, McGraw-Hill Professional, p. 40, ISBN 978-0-07-005489-9
  8. ^ Lovász, L. (1968), "On covering of graphs", in Erdős, P.; Katona, G. (eds.), Proceedings of the Colloquium held at Tihany, Hungary, 1966, Academic Press, pp. 231–236; 로버츠가 인용한 것 (1985)
  9. ^ Alon, Noga (1986), "Covering graphs by the minimum number of equivalence relations" (PDF), Combinatorica, 6 (3): 201–206, doi:10.1007/bf02579381
  10. ^ Orlin, J. (1977), "Contentment in graph theory: covering graphs with cliques", Proc. Kon. Ned. Acad. Wet., Series A, 80 (5): 406–424, doi:10.1016/1385-7258(77)90055-5; 로버츠가 인용한 것 (1985)
  11. ^ Kou, L. T.; Stockmeyer, L. J.; Wong, C. K. (1978), "Covering edges by cliques with regard to keyword conflicts and intersection graphs", Communications of the ACM, 21 (2): 135–139, doi:10.1145/359340.359346
  12. ^ Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf (2009), "Data reduction and exact algorithms for clique cover" (PDF), Journal of Experimental Algorithmics, 13 (2): 2–15, doi:10.1145/1412228.1412236.
  13. ^ Cygan, Marek; Kratsch, Stefan; Pilipczuk, Marcin; Pilipczuk, Michal; Wahlström, Magnus (2014), "Clique Cover and Graph Separation: New Incompressibility Results", ACM Transactions on Computation Theory, 6 (2): 6:1–6:19, doi:10.1145/2594439
  14. ^ Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał (2016), "Known algorithms for edge clique cover are probably optimal", SIAM Journal on Computing, 45 (1): 67–83, arXiv:1203.1754, doi:10.1137/130947076, MR 3448348
  15. ^ Opsut, R.J.;로버츠, F.S.(1981년),"그 함대 정비일 이동 전파, 과업 부여, 그리고 교통 단계적 문제", Chartrand, G단조, Alavi, Y, 골드 스미스, D.L.;Lesniak-Foster, L.;리크, D.R.(eds.), 제4회 국제 회의의 이론과 Graphs, 웨스턴 미시간 대학교, Kalamaz의 응용의 회보.Oo, 미시간, 5월 6-9,1980년 뉴욕:Wiley도,를 대신하여 서명함. 479–492, MR0634549했다;로버츠(1985년)에 의해 인용된.
  16. ^ a b Scheinerman, Edward R.; Trenk, Ann N. (1999), "On the fractional intersection number of a graph", Graphs and Combinatorics, 15 (3): 341–351, doi:10.1007/s003730050068, MR 1723018

외부 링크