금지 그래프 특성화

Forbidden graph characterization
"미성년자 강제입국"은 여기로 방향을 바꾼다.금지된 미성년자도 연령 제한을 언급할 수 있다.

수학의 한 분야인 그래프 이론에서, 많은 중요한 그래프 패밀리는 패밀리에 속하지 않는 유한한 개별 그래프 집합에 의해 설명될 수 있으며, 또한 이러한 금지된 그래프를 (유인) 하위 그래프 또는 마이너 그래프로 포함하는 모든 그래프를 패밀리에서 추가로 제외할 수 있다.이러한 현상의 원형적인 예가 쿠라토프스키의 정리인데, 두 개의 금지된 그래프, 즉 완전한 그래프 K와5 완전한 양분 그래프 K를3,3 포함하지 않는 경우에만 그래프를 평면(평면에 교차하지 않고 그릴 수 있다)이라고 기술하고 있다.쿠라토프스키의 정리에서 격납의 개념은 그래프 동형성의 개념으로, 한 그래프의 하위분열이 다른 그래프의 하위그래프로 나타나는 것이다.따라서 모든 그래프에는 평면도면이 있거나(이 경우 평면도 그래프 계열에 속함) 하위 그래프로서 이 두 그래프 중 적어도 하나의 하위분할이 있다(이 경우 평면도 그래프에 속하지 않음).

정의

보다 일반적으로 금지된 그래프 특성화는 해당 패밀리의 그래프 내에 존재하는 것이 금지된 하위 구조를 지정하여 그래프 패밀리나 구조물의 하이퍼그래프를 지정하는 방법이다.가족마다 금지된 것의 성격에 따라 다르다.일반적으로 구조 G는 G에 금지된 하부 구조가 포함되지 않은 경우에만 계열의 구성원이다.금지된 하부 구조는 다음 중 하나일 수 있다.

  • 하위 그래프, 큰 그래프의 정점과 가장자리의 부분 집합에서 얻은 작은 그래프,
  • 유도 하위 그래프, 정점의 부분 집합을 선택하고 해당 부분 집합에서 양쪽 끝점이 있는 모든 가장자리를 사용하여 얻은 더 작은 그래프,
  • 동형 하위 그래프(위상학적 하위 그래프라고도 함), 두 꼭지점 경로를 단일 가장자리로 접음으로써 하위 그래프에서 얻은 더 작은 그래프 또는
  • 그래프 마이너, 임의의 가장자리 수축에 의해 하위 그래프에서 얻은 더 작은 그래프.

주어진 그래프 패밀리에 속하지 못하도록 금지된 구조 집합을 해당 패밀리에 대한 장애물 세트라고도 할 수 있다.

금지된 그래프 특성은 그래프가 특정 패밀리에 속하는지 여부를 테스트하기 위한 알고리즘에 사용될 수 있다.많은 경우, 주어진 그래프가 장애물 집합의 구성원을 포함하는지 여부를 다항 시간 내에 테스트할 수 있으며, 따라서 해당 장애물 집합에 의해 정의된 패밀리에 속하는지 여부를 테스트할 수 있다.

특정 유형의 하부 구조와 함께 가족이 금지된 그래프 특성을 가지려면 하위 구조 아래 가족을 닫아야 한다.즉, 패밀리 내 그래프의 모든 하위 구조(특정 유형의)는 패밀리 내 다른 그래프여야 한다.마찬가지로 그래프가 패밀리의 일부가 아닌 경우, 그래프를 하위 구조로 포함하는 모든 큰 그래프도 패밀리에서 제외되어야 한다.이것이 사실일 때는 항상 방해물 집합(패밀리에 있지 않지만 더 작은 하위 구조가 모두 패밀리에 속하는 그래프 집합)이 존재한다.그러나 하부 구조가 무엇인지에 대한 일부 개념의 경우 이 장애물 집합은 무한할 수 있다.더 로버슨-시모어 정리는 그래프 미성년자의 특정한 경우, 미성년자 아래에서 닫힌 가족은 항상 유한한 방해물 세트를 가지고 있다는 것을 증명한다.

그래프 및 하이퍼그래프의 금지된 특성 목록

가족 장애물 관계 참조
숲 루프, 병렬 에지 쌍 및 모든 길이의 사이클 서브그래프 정의
다중 그래프용 루프 또는 삼각형3 K(단순 그래프용) 그래프 부차 정의
발톱이 없는 그래프 별 K1,3 유도 서브그래프 정의
비교가능성 그래프 유도 서브그래프
삼각형이 없는 그래프 트라이앵글3 K 유도 서브그래프 정의
평면 그래프 K와53,3 K 동형하분포도 쿠라토프스키의 정리
K와53,3 K 그래프 부차 바그너의 정리
외부 평면 그래프 K와42,3 K 그래프 부차 다이어스텔(2000),[1] 페이지 107
외부 1평형 그래프 금지된 미성년자 6명 그래프 부차 아우어 외 연구진(2013년)[2]
고정속 그래프 유한 장애물 세트 그래프 부차 디에스텔(2000),[1] 페이지 275
에이펙스 그래프 유한 장애물 세트 그래프 부차 [3]
연결 없이 내장 가능한 그래프 피터슨 가문 그래프 부차 [4]
초당적 그래프 홀수 사이클 서브그래프 [5]
화음 그래프 길이 4 이상 주기 유도 서브그래프 [6]
완벽한 그래프 홀수 길이 5 이상 또는 그 보완물의 주기 유도 서브그래프 [7]
그래프의 선 그래프 금지된 서브그래프 9개 유도 서브그래프 [8]
선인장 그래프의 그래프 전체 그래프 K에서4 가장자리를 제거하여 형성된 네 개의 Vertex 다이아몬드 그래프 그래프 부차 [9]
래더 그래프 K2,3 및 그 이중 그래프 동형하분포도 [10]
그래프 분할 유도 서브그래프 [11]
2-연결된 직렬-직렬(트리 너비 ≤ 2, 분기 너비 ≤ 2) K4 그래프 부차 디에스텔 (2000),[1] 페이지 327
나무폭 ≤ 3 K5, 팔면체, 오각형 프리즘, 바그너 그래프 그래프 부차 [12]
분기폭 ≤ 3 K5, 팔면체, 큐브, 바그너 그래프 그래프 부차 [13]
보완 축소 가능한 그래프(곡선) 4-버텍스 경로4 P 유도 서브그래프 [14]
소소하게 완벽한 그래프 4-버텍스 경로 P 및4 4-버텍스 사이클4 C 유도 서브그래프 [15]
분계점 그래프 4-베르텍스 경로 P4, 4-베르텍스 사이클 C4, C의 보완4 유도 서브그래프 [15]
3-균일 선형 하이퍼그래프 선 그래프 최소 19도 이상의 금지된 유도 하위 그래프의 유한 목록 유도 서브그래프 [16]
K-균일 선형 하이퍼그래프의 선 그래프, k > 3 최소 2k2 - 3k + 1의 최소 에지도를 갖는 금지 유도 서브그래프의 유한 목록 유도 서브그래프 [17][18]
그래프 ΔY-단일 정점으로 축소 가능 최소 680억 개 이상의 고유값 합계 유한 목록 그래프 부차 [19]
일반론
유도 계통 속성에 의해 정의된 가족 A, 마감되지 않았을 가능성이 있는 장애물 세트 유도 서브그래프
미성년자 상속 재산에 의해 정의된 가족 유한 장애물 세트 그래프 부차 로버트슨-세이모어 정리

참고 항목

참조

  1. ^ a b c Diestel, Reinhard (2000), Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer-Verlag, ISBN 0-387-98976-5.
  2. ^ 아우어, 크리스토퍼, Bachmaier, 크리스티안, 브란덴부르크, 프란츠 J.;Gleißner, 안드레아스, 하나워, Kathrin, 뉴워스, 다니엘;Reislhuber, 요제프(2013년),"선형 시간에 외부1-planar 그래프를 파악하는 것.", Wismath, Stephen은, 볼프, 알렉산더(eds.), 21일 국제 심포지엄, 승무원 2013년, 보르도, 프랑스, 9월 23일부터 25일까지, 2013년 선택 기술, L. 수정Ecture 메모 컴퓨터 과학으로, 8242,를 대신하여 서명함 vol.. 107–118, doi:10.1007/978-3-319-03841-4_10.
  3. ^ Gupta, A.; Impagliazzo, R. (1991), "Computing planar intertwines", Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91), IEEE Computer Society, pp. 802–811, doi:10.1109/SFCS.1991.185452, S2CID 209133.
  4. ^ Robertson, Neil; Seymour, P. D.; Thomas, Robin (1993), "Linkless embeddings of graphs in 3-space", Bulletin of the American Mathematical Society, 28 (1): 84–89, arXiv:math/9301216, doi:10.1090/S0273-0979-1993-00335-5, MR 1164063, S2CID 1110662.
  5. ^ 벨라 볼로바스(1998) "현대 그래프 이론", 스프링거, ISBN 0-387-98488-7 페이지 9
  6. ^ 가시와바라, Toshinobu(1981년),"일부 교차로 그래프에 알고리즘", 사이토, Nobuji에;.Nishizeki, 다카오(eds.), 그래프 이론과 알고리즘, 17일 심포지엄 연구소 전기 통신, 도호쿠 대학, 센다이, 일본, 10월 24-25, 1980년의 회보, 강의 노트 컴퓨터 과학으로 108vol., Springer-Verlag,를 대신하여 서명함. 171–181, doi:10.1007/3-540-10704-5_15.
  7. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem" (PDF), Annals of Mathematics, 164 (1): 51–229, arXiv:math/0212070v1, doi:10.4007/annals.2006.164.51, S2CID 119151552.
  8. ^ Beineke, L. W. (1968), "Derived graphs of digraphs", in Sachs, H.; Voss, H.-J.; Walter, H.-J. (eds.), Beiträge zur Graphentheorie, Leipzig: Teubner, pp. 17–33.
  9. ^ El-Mallah, Ehab; Colbourn, Charles J. (1988), "The complexity of some edge deletion problems", IEEE Transactions on Circuits and Systems, 35 (3): 354–362, doi:10.1109/31.1748.
  10. ^ Takamizawa, K.; Nishizeki, Takao; Saito, Nobuji (1981), "Combinatorial problems on series–parallel graphs", Discrete Applied Mathematics, 3 (1): 75–76, doi:10.1016/0166-218X(81)90031-7.
  11. ^ Földes, Stéphane; Hammer, Peter Ladislaw (1977a), "Split graphs", Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, vol. XIX, Winnipeg: Utilitas Math., pp. 311–315, MR 0505860
  12. ^ Bodlaender, Hans L. (1998), "A partial k-arboretum of graphs with bounded treewidth", Theoretical Computer Science, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4, hdl:1874/18312.
  13. ^ Bodlaender, Hans L.; Thilikos, Dimitrios M. (1999), "Graphs with branchwidth at most three", Journal of Algorithms, 32 (2): 167–194, doi:10.1006/jagm.1999.1011, hdl:1874/2734.
  14. ^ Seinsche, D. (1974), "On a property of the class of n-colorable graphs", Journal of Combinatorial Theory, Series B, 16 (2): 191–193, doi:10.1016/0095-8956(74)90063-X, MR 0337679
  15. ^ a b Golumbic, Martin Charles (1978), "Trivially perfect graphs", Discrete Mathematics, 24 (1): 105–107, doi:10.1016/0012-365X(78)90178-4.
  16. ^ Metelsky, Yury; Tyshkevich, Regina (1997), "On line graphs of linear 3-uniform hypergraphs", Journal of Graph Theory, 25 (4): 243–251, doi:10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K, MR 1459889
  17. ^ Jacobson, M. S.; Kézdy, Andre E.; Lehel, Jeno (1997), "Recognizing intersection graphs of linear uniform hypergraphs", Graphs and Combinatorics, 13 (4): 359–367, doi:10.1007/BF03353014, MR 1485929, S2CID 9173731
  18. ^ Naik, Ranjan N.; Rao, S. B.; Shrikhande, S. S.; Singhi, N. M. (1982), "Intersection graphs of k-uniform hypergraphs", European Journal of Combinatorics, 3: 159–172, doi:10.1016/s0195-6698(82)80029-2, MR 0670849
  19. ^ Yu, Yanming (2006), "More forbidden minors for wye-delta-wye reducibility", The Electronic Journal of Combinatorics, 13, doi:10.37236/1033 웹사이트