무관심 그래프

Indifference graph
거리가 최대 1인 점 쌍을 연결하여 실제 선의 점 집합에서 형성된 무관심 그래프

수학의 한 분야인 그래프 이론에서 무관심 그래프는 각 꼭지점에 실제 숫자를 할당하고 그 숫자가 서로 하나의 단위 안에 있을 때 가장자리 두 정점을 연결하여 구성한 비방향 그래프다.[1]무관심 그래프는 단위 간격 집합의 교차 그래프 또는 적절히 중첩된 간격의 교차 그래프(이 중 어느 것도 다른 것을 포함하지 않음)이기도 하다.이러한 두 가지 유형의 구간 표현을 바탕으로 이러한 그래프를 단위 구간 그래프 또는 적절한 구간 그래프라고도 하며 구간 그래프의 하위 클래스를 형성한다.

등가 특성화

무관심 그래프에 대해 금지된 유도 하위 그래프: 발톱, 태양 및 네트(위, 왼쪽-오른쪽) 및 길이 4개 이상의 사이클(아래쪽)

유한 무관심 그래프는 다음과 같은 특성을 가질 수 있다.

  • 단위 구간교차 그래프,[1]
  • 두 구간이 내포되지 않은 구간 집합의 교차 그래프(하나에는 다른 구간이 포함됨)[1][2]
  • 발톱이 없는 간격 그래프,[1][2]
  • 유도 하위 그래프가 집게 K1,3, 그물(각 삼각형 꼭지점에 인접한 도 1 꼭지점이 있는 삼각형), 태양(각각 중심 삼각형과 하나의 가장자리를 공유하는 세 개의 다른 삼각형으로 둘러싸인 삼각형) 또는 구멍(길이 4 이상의 주기)[3]에 대해 이형성이 없는 그래프
  • 세미 오더비교가능성 그래프,[1]
  • 개의 꼭지점마다 u {\ – v {\v} – w {\를) 정렬하는 선형 순서가 있는 비방향 그래프는 인 경우
  • 세 번째 꼭지점을 회피하고 [5]세 번째 꼭지점의 연속된 이웃 두 개를 포함하지 않는 경로로 쌍으로 연결된 세 개의 꼭지점이 없는 그래프
  • 연결된 각 구성요소가 연속적인 하위 경로를 형성하는 경로를 포함하는 그래프,[6]
  • 모든 최단 경로가 단조로운 시퀀스를 형성하도록 정점에 번호를 매길 수 있는 그래프,[6]
  • 인접 행렬을 정렬할 수 있는 그래프는 각 행과 열에서 행렬의 비저로가 행렬의 주 대각선에 인접한 인접 간격을 형성한다.[7]
  • 코드 없는 경로의 힘에 대한 유도 하위 그래프.[8]
  • 잎의 힘은 애벌레인 잎 뿌리를 가지고 있다.[8]

무한 그래프의 경우 이러한 정의 중 일부는 다를 수 있다.

특성.

그것들은 구간 그래프의 특별한 경우이기 때문에 무관심 그래프는 구간 그래프의 모든 속성을 가지고 있다. 특히 그것들은 현악 그래프완벽한 그래프의 특별한 경우다.그것들은 또한그래프의 특별한 경우로서, 구간 그래프에는 일반적으로 해당되지 않는다.

랜덤 그래프 Erdds-Rény 모델에서 가장자리 수가 n / 보다 유의하게 적은 n n2/3보다 작은 그래프는 확률의 무관심 그래프일 것이다가능성이 높은 무관심 그래프가 아니다.[9]

임의 그래프 대역폭 을(를) 하위 그래프로 포함하는 무관심 그래프에서 최대 클라이크의 크기보다 1보다 작으며 최대 클라이크의 크기를 최소화하기 위해 선택된다.[10]이 속성은 경로 너비구간 그래프, 그리고 나무 너비화음 그래프 사이의 유사한 관계를 평행하게 한다.너비에 대한 더 약한 개념인 clique-width는 무관심 그래프에서 임의로 클 수 있다.[11]그러나 유도 하위 그래프에 의해 닫히는 무관심 그래프의 모든 적절한 하위 등급은 클라이크 너비에 경계를 두었다.[12]

모든 연결된 무관심 그래프에는 해밀턴의 경로가 있다.[13]무관심 그래프는 만약 그것이 양방향으로 연결되어 있다면 해밀턴 사이클을 가진다.[14]

무관심 그래프는 재구성 추측에 따른다: 그것들은 정점 삭제된 서브그래프에 의해 독특하게 결정된다.[15]

알고리즘

고차원 단위 디스크 그래프의 경우와 마찬가지로, 출력 그래프의 크기로 측정했을 때 점 집합을 무관심 그래프로 변환하거나 단위 간격의 집합을 단위 간격 그래프로 변환할 수 있다.알고리즘은 점(또는 간격 중심)을 가장 가까운 작은 정수로 반올림하고, 해시 테이블을 사용하여 둥근 정수가 서로 한 쌍 안에 있는 모든 점 쌍(주변 고정 반지름 문제)을 찾아내고, 비원형 값도 서로 안에 있는 점 쌍의 결과 목록을 필터링한다.[16]

PQ 트리를 사용하여 그래프의 간격 표현을 구성한 다음 이 표현에서 도출된 정점 순서가 무관심 그래프의 특성을 만족하는지 테스트함으로써 주어진 그래프가 선형적으로 무관심 그래프인지 여부를 테스트할 수 있다.[4]또한 코드 그래프 인식 알고리즘을 기반으로 무관심 그래프의 인식 알고리즘이 가능하다.[14]몇 가지 대안적인 선형 시간 인식 알고리즘은 무관심 그래프와 구간 그래프 사이의 관계보다는 폭 우선 검색 또는 사전 편찬우선 검색에 기초한다.[17][18][19][20]

일단 정점이 무관심 그래프를 설명하는 숫자 값(또는 구간 표시에서 단위 간격의 순서에 의해)에 의해 정렬되면 동일한 순서를 사용하여 이러한 그래프에 대한 최적의 그래프 색상을 찾고, 최단 경로 문제를 해결하며, 모두 line에 있는 Hamiltonian 경로와 최대 일치를 구성할 수 있다.귀로 듣는 [4]시간해밀턴 사이클은 시간 O n[13]의 그래프의 적절한 간격 표현에서 찾을 수 있지만, 그래프 자체가 입력으로 주어졌을 때, 동일한 문제가 구간 그래프에 일반화될 수 있는 선형 시간 솔루션을 인정한다.[21][22]

리스트 컬러링은 무관심 그래프에 제한되어도 NP-완전하다.[23]단, 입력의 총 색상 수에 의해 매개변수로 지정되면 고정 매개변수를 추적할 수 있다.[12]

적용들

수학 심리학에서 무관심 그래프는 효용함수로부터 발생하는데, 한 단위가 개인이 무관심하다고 가정할 수 있을 정도로 작은 효용 차이를 나타내도록 함수를 확장하는 것이다.이 애플리케이션에서 전력회사의 차이가 큰 품목 쌍은 전력회사의 상대적 순서에 의해 부분적으로 주문될 수 있으며, 준차이를 제공한다.[1][24]

생물정보학에서 컬러 그래프를 적절한 색상의 단위 간격 그래프로 증강하는 문제는 완전한 다이제스트에서 DNA 시퀀스 어셈블리의 거짓 음의 검출 모델을 만드는 데 사용될 수 있다.[25]

참고 항목

  • 분계점 그래프, 레이블의 차이가 아니라 정점 레이블의 합계에 의해 가장자리가 결정되는 그래프
  • 모든 구간 쌍이 적절히 교차하지 않고 내포되거나 분리되는 사소한 완벽한 그래프

참조

  1. ^ a b c d e f Roberts, Fred S. (1969), "Indifference graphs", Proof Techniques in Graph Theory (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968), Academic Press, New York, pp. 139–146, MR 0252267.
  2. ^ a b Bogart, Kenneth P.; West, Douglas B. (1999), "A short proof that "proper = unit"", Discrete Mathematics, 201 (1–3): 21–23, arXiv:math/9811036, doi:10.1016/S0012-365X(98)00310-0, MR 1687858.
  3. ^ Wegner, G. (1967), Eigenschaften der Nerven homologisch-einfacher Familien im Rn, Ph.D. thesis, Göttingen, Germany: Göttingen University. Hell & Huang(2004)이 인용한 바와 같다.
  4. ^ a b c Looges, Peter J.; Olariu, Stephan (1993), "Optimal greedy algorithms for indifference graphs", Computers & Mathematics with Applications, 25 (7): 15–25, doi:10.1016/0898-1221(93)90308-I, MR 1203643.
  5. ^ Jackowski, Zygmunt (1992), "A new characterization of proper interval graphs", Discrete Mathematics, 105 (1–3): 103–109, doi:10.1016/0012-365X(92)90135-3, MR 1180196.
  6. ^ a b Gutierrez, M.; Oubiña, L. (1996), "Metric characterizations of proper interval graphs and tree-clique graphs", Journal of Graph Theory, 21 (2): 199–205, doi:10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M, MR 1368745.
  7. ^ Mertzios, George B. (2008), "A matrix characterization of interval and proper interval graphs", Applied Mathematics Letters, 21 (4): 332–337, doi:10.1016/j.aml.2007.04.001, MR 2406509.
  8. ^ a b Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics, 310: 897–910, doi:10.1016/j.disc.2009.10.006.
  9. ^ Cohen, Joel E. (1982), "The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph", Discrete Mathematics, 40 (1): 21–24, doi:10.1016/0012-365X(82)90184-4, MR 0676708.
  10. ^ Kaplan, Haim; Shamir, Ron (1996), "Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques", SIAM Journal on Computing, 25 (3): 540–561, doi:10.1137/S0097539793258143, MR 1390027.
  11. ^ Golumbic, Martin Charles; Rotics, Udi (1999), "The clique-width of unit interval graphs is unbounded", Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), Congressus Numerantium, vol. 140, pp. 5–17, MR 1745205.
  12. ^ a b Lozin, Vadim V. (2008), "From tree-width to clique-width: excluding a unit interval graph", Algorithms and computation, Lecture Notes in Comput. Sci., vol. 5369, Springer, Berlin, pp. 871–882, doi:10.1007/978-3-540-92182-0_76, MR 2539978.
  13. ^ a b Bertossi, Alan A. (1983), "Finding Hamiltonian circuits in proper interval graphs", Information Processing Letters, 17 (2): 97–101, doi:10.1016/0020-0190(83)90078-9, MR 0731128.
  14. ^ a b Panda, B. S.; Das, Sajal K. (2003), "A linear time recognition algorithm for proper interval graphs", Information Processing Letters, 87 (3): 153–161, doi:10.1016/S0020-0190(03)00298-9, MR 1986780.
  15. ^ von Rimscha, Michael (1983), "Reconstructibility and perfect graphs", Discrete Mathematics, 47 (2–3): 283–291, doi:10.1016/0012-365X(83)90099-7, MR 0724667.
  16. ^ 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.
  17. ^ Corneil, Derek G.; Kim, Hiryoung; Natarajan, Sridhar; Olariu, Stephan; Sprague, Alan P. (1995), "Simple linear time recognition of unit interval graphs", Information Processing Letters, 55 (2): 99–104, CiteSeerX 10.1.1.39.855, doi:10.1016/0020-0190(95)00046-F, MR 1344787.
  18. ^ Herrera de Figueiredo, Celina M.; Meidanis, João; Picinin de Mello, Célia (1995), "A linear-time algorithm for proper interval graph recognition", Information Processing Letters, 56 (3): 179–184, doi:10.1016/0020-0190(95)00133-W, MR 1365411.
  19. ^ Corneil, Derek G. (2004), "A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs", Discrete Applied Mathematics, 138 (3): 371–379, doi:10.1016/j.dam.2003.07.001, MR 2049655.
  20. ^ Hell, Pavol; Huang, Jing (2004), "Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs", SIAM Journal on Discrete Mathematics, 18 (3): 554–570, doi:10.1137/S0895480103430259, MR 2134416.
  21. ^ Keil, J. Mark (1985), "Finding Hamiltonian circuits in interval graphs", Information Processing Letters, 20 (4): 201–206, doi:10.1016/0020-0190(85)90050-X, MR 0801816.
  22. ^ Ibarra, Louis (2009), "A simple algorithm to find Hamiltonian cycles in proper interval graphs", Information Processing Letters, 109 (18): 1105–1108, doi:10.1016/j.ipl.2009.07.010, MR 2552898.
  23. ^ Marx, Dániel (2006), "Precoloring extension on unit interval graphs", Discrete Applied Mathematics, 154 (6): 995–1002, doi:10.1016/j.dam.2005.10.008, MR 2212549.
  24. ^ Roberts, Fred S. (1970), "On nontransitive indifference", Journal of Mathematical Psychology, 7: 243–258, doi:10.1016/0022-2496(70)90047-7, MR 0258486.
  25. ^ Goldberg, Paul W.; Golumbic, Martin C.; Kaplan, Haim; Shamir, Ron (2009), "Four strikes against physical mapping of DNA", Journal of Computational Biology, 2 (2), doi:10.1089/cmb.1995.2.139, PMID 7497116.

외부 링크