하이퍼 트리

Hypertree
그 외의 용도는, 하이퍼 트리(동음이의인 설명)를 참조해 주세요.
하이퍼 트리(파란색 꼭지점 및 노란색 하이퍼지) 및 호스트 트리(빨간색

그래프 이론의 수학 분야에서 하이퍼그래프 H는 호스트 그래프 T를 받아들여 T가 트리인 경우 하이퍼트리라고 불린다.즉, H의 모든 하이퍼지([1]hyperedge)가 T의 연결된 서브트리의 정점 집합이 되도록 트리 T가 존재하는 경우 H는 하이퍼트리이다.하이퍼트리는 수목형 하이퍼그래프[2] 또는 트리 [3]하이퍼그래프라고도 불립니다.

모든 트리 T는 그 자체가 하이퍼 트리입니다.T 자체는 호스트 그래프로 사용할 수 있으며 T의 모든 가장자리는 이 호스트 그래프의 하위 트리입니다.따라서 하이퍼트리는 [4]하이퍼그래프용 트리의 개념을 일반화한 것으로 볼 수 있습니다.여기에는 연결된 Berge-비순환 하이퍼그래프가 포함되어 있으며 하이퍼그래프용 트리의 (다른) 일반화로도 사용되고 있습니다.

특성.

모든 하이퍼트리는 Helly 속성(2-Helly 속성)을 가지고 있습니다.하이퍼지의 서브셋S가 S의 2개의 하이퍼지마다 비어 있지 않은 교차를 갖는 속성을 가지고 있는 경우, S 자체는 비어 있지 않은 교차점(S의 [5]모든 하이퍼지에 속하는 정점)을 가지고 있습니다.

Duchet의 결과에 따라 Flament 및 Slater[6] 하이퍼트리는 다음과 같은 방법으로 동등하게 특징지을 수 있다.

하이퍼트리(알파 비순환 하이퍼그래프의 이중)를 [9]선형 시간에 인식할 수 있습니다.정확한 커버 문제(모든 정점을 커버하는 오버랩되지 않는 하이퍼트리의 집합 찾기)는 하이퍼트리의 경우 다항식 시간으로 해결 가능하지만 알파 비순환 하이퍼그래프의 [10]경우 NP-완전인 채로 남아 있습니다.

「 」를 참조해 주세요.

메모들

  1. ^ Brandstédt 등(1998년)
  2. ^ Berge (1989)
  3. ^ McKee & McMorris (1999년)
  4. ^ Berge (1989년); Voloshin (2002년)
  5. ^ Berge (1989년); Voloshin (2002년)
  6. ^ 참조: Brandstédt, Le & Spinrad(1999년), McKee & McMorris(1999년)
  7. ^ Berge (1989)
  8. ^ 페이긴(1983년)
  9. ^ Tarjan & Yannakakis(1984년).
  10. ^ Brandstédt, Leitert & Rautenbach (2012)

레퍼런스

  • 를 클릭합니다Berge, Claude (1989), Hypergraphs: Combinatorics of Finite Sets, North-Holland Mathematical Library, vol. 45, Amsterdam: North Holland, ISBN 0-444-87489-5, MR 1013569.
  • 를 클릭합니다Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually chordal graphs" (PDF), SIAM Journal on Discrete Mathematics, 11: 437–455, doi:10.1137/s0895480193253415, MR 1628114.
  • 를 클릭합니다Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X, MR 1686154.
  • Brandstädt, 안드레아스, Leitert, 아르네;Rautenbach, 디터(2012년),"그래프와 hypergraphs의 효율적인 지배적이고 가장자리를 세트", 알고리즘과 계산:23일 국제 심포지엄, 아이작 2012년, 타이페이, 대만, 12월 19-21, 2012년, 회보, 강의 노트 컴퓨터 과학으로,,를 대신하여 서명함 7676 vol.. 267–277, arXiv:1207.0953,. doi:10.1007/978-3-642-35261-4_30, MR3065639.
  • 를 클릭합니다Fagin, Ronald (1983), "Degrees of acyclicity for hypergraphs and relational database schemes", Journal of the ACM, 30: 514–550, doi:10.1145/2402.322390, MR 0709831.
  • 를 클릭합니다McKee, T.A.; McMorris, F.R. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR 1672910.
  • 를 클릭합니다Tarjan, Robert E.; Yannakakis, Mihalis (1984), "Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs" (PDF), SIAM Journal on Computing, 13 (3): 566–579, doi:10.1137/0213035, MR 0749707.
  • 를 클릭합니다Voloshin, Vitaly (2002), Coloring Mixed Hypergraphs: Theory, Algorithms and Applications, Fields Institute Monographs, vol. 17, Providence, RI: American Mathematical Society, ISBN 0-8218-2812-6, MR 1912135.