하이퍼그래프의 폭

그래프 이론에서, 하이퍼그래프의 "폭"이라고 불리는 두 가지 관련 속성이 있다.하이퍼그래프 H = (V, E)를 고려할 때, F의 모든 에지가 K의 어떤 에지와 교차할 경우, 에지의 세트 K는 또 다른 세트 F의 에지를 핀으로 고정한다고 말한다.^[1]다음:

• w(H)로 표시된 H의 너비는 E를 핀으로 고정하는 E의 하위 집합 중 가장 작은 크기이다.^[2]
• MW(H)로 표시된 H의 일치 폭은 M을 고정하는 E의 하위 집합의 최소 크기인 H의 모든 일치 항목 M에 대한 최대 폭이다.^[3]

E는 E의 모든 일치를 포함하므로, 모든 H: w(H) ≥ mw(H)에 대해.

하이퍼그래프의 폭은 하이퍼그래프를 위한 홀형 이론에 사용된다.

예

H를 정점 집합 V = {A,B, a,b} 및 에지가 설정된 하이퍼그래프로 설정:

E = {A,a}, {B,b}, {A,b}, {B,a} }

H의 폭은 다음과 같다.

• w(H) = 2. 예를 들어 E가 {A,a}, {B,b} 집합에 의해 고정되고 더 작은 집합에 의해 고정될 수 없으므로.
• mw(H) = 1. 모든 일치가 단일 에지로 고정될 수 있기 때문이다.{{A,a},{B,b}}이(가) 고정되고(예: {A,b}}이) {A,b}이(가) 고정되고(예: {A, a}이) {B,a}이(가) 고정되어(예: {A, a}).

특성화

D(H)로 표시된 H의 절연 그래프는 H의 각 가장자리가 D(H)의 꼭지점이고, H의 각 절연 가장자리가 D(H)에 인접해 있는 그래프다.H의 성냥은 D(H)의 성냥에 해당한다.Meshulam은^[2] D(H)의 성질에 있어 하이퍼그래프 H의 폭을 특징으로 했다.임의의 양의 정수 r:

• w(H) > r 만약 D(H)가 P(r, ∞)라는 속성을 만족한다면, 이는 D(H)의 모든 r 정점 집합에 공통적인 이웃이 있음을 의미한다.왜냐하면 w(H) > r iff H는 크기 r의 핀셋이 없기 때문이고, if는 H의 r 가장자리의 모든 부분 집합에 대해 H의 모든 부분 집합에 D(H)에 공통적인 인접성이 있다면 그것에 의해 핀이 되지 않는 가장자리가 있기 때문이다.
• mw(H) > r 만약 D(H)가 P(r,0)라는 속성을 만족한다면, 이는 D(H)의 모든 r 정점 집합에 공통의 이웃이 있다는 것을 의미하며, 또한 D(H)에는 그러한 모든 집합의 공통 이웃을 포함하는 C파(C)가 있다는 것을 의미한다.

L(H)로 표시된 H의 선 그래프는 H의 각 가장자리가 L(H)의 정점이고, H의 두 교차 가장자리가 모두 L(H)에 인접해 있는 그래프다.H의 일치점은 L(H)의 독립된 집합에 해당한다.L(H)은 D(H)의 보완물이므로, 위의 특성화는 L(H)로 번역할 수 있다.

• w(H) > r (L(H)의 모든 r 정점 집합에 대해 그것들 중 어느 하나에도 인접하지 않은 정점이 있는 경우에만 해당된다.
• mw(H) > r 만일 L(H)의 모든 r 정점 집합에 대해 그 중 어느 하나에도 인접하지 않은 정점이 있고, 또한 L(H)에는 그러한 집합에 인접하지 않은 정점을 포함하는 독립된 집합 I가 있는 경우에만 해당된다.

g(G)로 표시된 그래프 G의 지배 번호는 G의 모든 정점을 지배하는 정점 집합의 가장 작은 크기이다.하이퍼그래프의 폭은 지배 번호 또는 그 선 그래프와 같다: w(H) = γ(L(H)).왜냐하면 E의 가장자리는 L(H)의 정점이기 때문이다. H에서 E를 핀으로 하는 E의 모든 부분 집합은 모든 L(H)을 지배하는 L(H)에 설정된 정점에 해당한다.

iγ(G)로 표시된 그래프 G의 독립성 지배 번호는 A를 지배하는 가장 작은 집합의 모든 독립성 집합 A에 대해 최대값이다.^[4]하이퍼그래프의 일치 폭은 독립적 지배 번호 또는 라인그래프: mw(H) = iγ(L(H))와 같다.왜냐하면 H의 모든 일치 M은 L(H)의 독립된 집합 I에_M 해당하고, H의 M을 핀으로 하는 E의 모든 하위 집합은 L(H)에서 I를_M 지배하는 집합에 해당하기 때문이다.

참고 항목

• 그래프 이론에서 "너비"라고 하는 다른 개념은 너비(동음이의)를 참조하십시오.#그래프 이론.

참조