균형 하이퍼그래프

Balanced hypergraph

그래프 이론에서 균형 하이퍼그래프는 초당적 그래프의 그것과 유사한 몇 가지 속성을 가진 하이퍼그래프다.

균형 잡힌 하이퍼그래프는 초당적 그래프의 자연스러운 일반화로서 버지에[1] 의해 도입되었다.그는 두 가지 동등한 정의를 제시했다.

2색상으로 정의

하이퍼그래프 H = (V, E)는 그 정점이 2색일 수 있고 그래서 그 정점이 단색일 수 없다면 2색이라고 불린다.모든 초당적 그래프 G = (X+Y, E)는 2색이다. 각 가장자리는 X의 꼭지점 하나와 Y의 꼭지점 하나를 정확히 포함하고 있기 때문에 예를 들어 X는 파란색으로, Y는 노란색으로 칠할 수 있고 가장자리는 단색화되지 않는다.

일부 변종 성형이 단골격인 하이퍼그래프는 분명히 2색상이 아니다. 2색성에 대한 사소한 장애물을 피하기 위해 기본적으로 2색인 하이퍼그래프를 고려하는 것이 일반적이다. 즉, 단일 톤 성형을 모두 삭제하면 2색상이 된다.[2]: 468

하이퍼그래프는 기본적으로 2색이면 균형이라고 하며, 정점을 몇 개라도 삭제해도 기본적으로 2색인 상태를 유지한다.형식적으로 V의 각 부분 집합 U에 대해 H ~ U의 제한을 하이퍼그래프U H = (, EU)로 정의하십시오. 서 U={ e U } U 그런 다음, 만일U H가 V의 모든 서브셋 U에 대해 본질적으로 2-색상이 가능하다면 H는 균형잡힌 것으로 불린다.단순 그래프는 2색이면 2색이면 2색이면 2차 그래프를 사용할 수 있다는 점에 유의하십시오.

홀수 사이클에 의한 정의

하이퍼그래프의 사이클(또는 회로)은 (v1, e1, v2, v, e2, ..., vk, e, vk+1, ek, v=v1), 모든 꼭지점i v가i−1 e와 ei 모두에 포함되어 있는 구별되는 정점과 축성의 순환 순서다.숫자 k를 사이클의 길이라고 한다.

하이퍼그래프는 H의 모든 홀수 길이 사이클 C가 최소한 3개의 꼭지점을 포함하는 가장자리를 갖는 경우 균형을 이룬다.[3]

단순 그래프에서 모든 에지는 두 개의 꼭지점만 포함한다는 점에 유의하십시오.따라서 단순 그래프는 홀수 길이 사이클을 전혀 포함하지 않으면 균형을 이루며, 이 사이클이 초당적인 경우 이를 지탱한다.

Berge는[1] 두 가지 정의가 동등하다는 것을 증명했다; 여기서도 증명할 수 있다.[2]: 468–469

특성.

초당적 그래프에 대한 일부 이론들은 균형잡힌 하이퍼그래프로 일반화되었다.[4][2]: 468–470

  • 모든 균형 잡힌 하이퍼그래프에서, 최소 꼭지점 커버는 그것의 최대 일치점과 같은 크기를 가진다.이것은 초당적 그래프에 대한 Kőnig-Egervary 정리를 일반화한다.
  • 모든 균형잡힌 하이퍼그래프에서 도(= 하나의 꼭지점을 포함하는 최대 변종 수)는 색지수(= 같은 색상의 두 변종류가 공통적으로 정점을 가지지 않도록 변종 색상에 필요한 최소 색상 수)와 같다.[5]이것은 초당적 그래프에 대한 Konig의 정리를 일반화한다.
  • Every balanced hypergraph satisfies a generalization of Hall's marriage theorem:[3] it admits a perfect matching iff for all disjoint vertex-sets V1, V2, if for all edges e in E, then V2 ≥ V1 . See Hall-type theorems for hypergraphs.
  • 최대 도 D의 모든 균형 하이퍼그래프는 D 가장자리-분리 매칭으로 분할할 수 있다.[1]: Chapter 5 [3]: Corollary 3

균형 잡힌 하이퍼그래프의 k-폴드 횡단면은 k 쌍-분할 변환의 조합으로 표현할 수 있으며, 그러한 분할은 다항 시간 내에 얻을 수 있다.[6]

초당적 개념의 다른 개념과의 비교

균형 외에도 초당적 그래프의 대체 일반화가 있다.하이퍼그래프는 그것의 꼭지점 세트 V를 X와 Y의 두 세트로 분할할 수 있다면 초당파라고 부른다. 그래서 각 혼합물은 X의 정확히 하나의 요소를 포함한다(양당 하이퍼그래프 참조).분명히 모든 초당적 그래프는 2색이다.

초당성과 균형이라는 특성이 서로를 암시하는 것은 아니다.

균형은 초당성을 의미하지 않는다.H를 하이퍼그래프로 두십시오.[7]

{ {1,2} , {3,4} , {1,2,3,4} }

그것은 2색이며, 그것에서 정점을 제거해도 2색이다.그러나, 그것은 양립할 수 없다. 왜냐하면 처음 두 개의 성화에서 각각 정확히 하나의 녹색 꼭지점을 가지기 위해서는 마지막 성화에서 두 개의 녹색 꼭지점이 있어야 하기 때문이다.양당성이 균형을 의미하는 것은 아니다.예를 들어 H를 정점이 {1,2,3,4}이고 가장자리가 있는 하이퍼그래프로 두십시오.

{ {1,2,3} , {1,2,4} , {1,3,4} }

칸막이 X={1}, Y={2,3,4}. 그러나 균형이 맞지 않는다.예를 들어, 정점 1이 제거되면 H에서 {2,3,4}까지의 제한을 받게 되는데, 이 제한은 다음과 같은 변종성을 가지고 있다.

{ {2,3} , {2,4} , {3,4} }

어떤 2색에도 같은 색상의 정점이 적어도 두 개 이상 있고 따라서 적어도 한 개 이상의 격자무늬가 단색이기 때문에 2색상은 아니다.

H가 균형이 맞지 않음을 확인할 수 있는 또 다른 방법은 홀수 길이 사이클 C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2)를 포함하고 C의 어떤 에지도 C의 세 정점 2,3,4를 모두 포함하지 않는다는 것이다.

3중성은 균형을 의미하지 않는다.예를 들어, H를 정점이 {1,2},{3,4},{5,6}이고 가장자리가 있는 삼분법 하이퍼그래프가 되도록 한다.

{ {1,3,5}, {2,4,5}, {1,4,6} }

정점 2,3,6을 제거하면 나머지는 다음과 같기 때문에 균형을 이루지 못한다.

{ {1,5}, {4,5}, {1,4} }

3사이클이라 색칠이 안 된다.

균형이 맞지 않음을 확인할 수 있는 또 다른 방법은 홀수 길이 사이클 C = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1)을 포함하고 C의 어떤 에지도 C의 세 정점 1,4,5를 모두 포함하지 않는다는 것이다.

관련 속성

완전히 균형 잡힌 하이퍼그래프

하이퍼그래프는 최소 3(홀수 길이일 필요는 없음) 길이의 H의 모든 사이클 C가 최소 3개의 정점을 포함하는 가장자리를 갖는 경우 완전히 균형잡힌 것으로 불린다.[8]

만약 H의 모든 하위 계층이 나무-하이퍼그래프라면, 하이퍼그래프 H는 완전히 균형을 이룬다.[8]

일반 하이퍼그래프

하이퍼그래프 H의 Konig 속성은 그것의 최소 꼭지점 커버가 그것의 최대 일치와 같은 크기를 갖는 속성이다.Kőnig-Egervary 정리는 모든 초당적 그래프는 Konig 속성을 가지고 있다고 말한다.

균형 하이퍼그래프는 정확히 하이퍼그래프 H로 H의 모든 부분 하위 하이퍼그래프에는 Konig 속성이 있다(즉, H는 임의의 수의 성질과 정점을 삭제해도 Konig 속성이 있다).

H의 모든 부분적 하이퍼그래프가 Konig 속성을 가지고 있다면(즉, H는 정점이 아닌 임의의 확성기를 삭제해도 Konig 속성을 가지고 있다) H를 일반 하이퍼그래프라고 부른다.[9]

따라서, 완전 균형은 균형을 의미하며, 이것은 정상임을 의미한다.

참조

  1. ^ a b c Berge, Claude (1970). "Sur certains hypergraphes généralisant les graphes bipartites". Combinatorial Theory and Its Applications. 1: 119–133.
  2. ^ a b c Lovász, László; Plummer, M. D. (1986), Matching Theory, Annals of Discrete Mathematics, vol. 29, North-Holland, ISBN 0-444-87916-1, MR 0859549
  3. ^ a b c Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (1996-09-01). "Perfect matchings in balanced hypergraphs". Combinatorica. 16 (3): 325–329. doi:10.1007/BF01261318. ISSN 1439-6912. S2CID 206792822.
  4. ^ Berge, Claude; Vergnas, Michel LAS (1970). "Sur Un Theorems Du Type König Pour Hypergraphes". Annals of the New York Academy of Sciences. 175 (1): 32–40. doi:10.1111/j.1749-6632.1970.tb56451.x. ISSN 1749-6632.
  5. ^ Lovász, L. (1972-06-01). "Normal hypergraphs and the perfect graph conjecture". Discrete Mathematics. 2 (3): 253–267. doi:10.1016/0012-365X(72)90006-4. ISSN 0012-365X.
  6. ^ Dahlhaus, Elias; Kratochvíl, Jan; Manuel, Paul D.; Miller, Mirka (1997-11-27). "Transversal partitioning in balanced hypergraphs". Discrete Applied Mathematics. 79 (1): 75–89. doi:10.1016/S0166-218X(97)00034-6. ISSN 0166-218X.
  7. ^ "coloring - Which generalization of bipartite graphs is stronger?". Mathematics Stack Exchange. Retrieved 2020-06-27.
  8. ^ a b Lehel, Jenö (1985-11-01). "A characterization of totally balanced hypergraphs". Discrete Mathematics. 57 (1): 59–65. doi:10.1016/0012-365X(85)90156-6. ISSN 0012-365X.
  9. ^ Beckenbach, Isabel; Borndörfer, Ralf (2018-10-01). "Hall's and Kőnig's theorem in graphs and hypergraphs". Discrete Mathematics. 341 (10): 2753–2761. doi:10.1016/j.disc.2018.06.013. ISSN 0012-365X.