독립복합체

그래프의 독립 콤플렉스는 그래프의 독립 집합을 설명하는 수학적 객체다.형식적으로 I(G)가 가리키는 비방향 그래프 G의 독립 콤플렉스는 G의 독립 집합에서 정점 집합에 의해 형성된 추상적 단순 콤플렉스(즉, 서브셋을 취하는 운용에 의해 닫힌 유한 집합의 패밀리)이다.독립 집합의 모든 부분 집합은 그 자체로 독립 집합이므로 I(G)는 실제로 하위 집합을 취하면 닫힌다.

그래프의 모든 독립 집합은 그 보완 그래프에서 하나의 집단이며, 그 반대도 마찬가지다.따라서 그래프의 독립성 콤플렉스는 그 보완 그래프의 클릭 콤플렉스와 같으며, 그 반대도 마찬가지다.

호몰로지 집단

여러 저자들이 그래프 G = (V, E)의 특성과 그 독립 복합체 I(G)의 호몰로지 집단 사이의 관계를 연구했다.^[1]특히 G(G)의 지배적인 집합과 관련된 몇 가지 속성은 I(G)의 일부 축소된 호몰로지 집단이 사소한 것임을 보증한다.

1. $\gamma {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$( ${\displaystyle G}$) ${\displaystyle \gamma _{0}(G$로 표시된 G의 총 지배 번호는 V의 모든 정점이 S의 정점에 인접하도록 설정된 총 지배 집합의 최소 카디널리티다. ( G)> k ${\displaystyle \gamma _{0}(G)>k}$이면 $H{\displaystyle {\stackrel{}{}}_{}}$~ ${\displaystyle {\mathrm{k}}_{}}$- ${\displaystyle 1_{}}$( ${\displaystyle I}$(${\displaystyle }$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle {\tilde{H}_{k-1}(I(G)=0$^[2]

2. G에서 V의 부분집합 A의 총 지배 번호는 $\gamma {\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$( G${\displaystyle }$, ${\displaystyle A}$ $){\displaystyle \gamma _{0}(G,A)}$로 표시되며$,$ A의 모든 꼭지점이 S의 정점에 인접하도록 세트 S의 최소 카디널리티다.G의 독립은 지배 번호, 나는, 있는 최대 모두 독립된 가져오거나 설정하고, AG에, γ 0(G, A){\displaystyle \gamma_{0}(G,A)의}. 만약 제가 γ(G)>k{\displaystyle i\gamma(G)>, k}, H~k− 1(나는(G))=0{\displaystyle{\tilde{H}}(G){\displaystyle i\gamma(G)}γ_{k를 설명-1}(1세$(G)=0}$^[1][3].

3.$$$domination{\displaystyle }$ (${\displaystyle G}$) ${\displaystyle \gamma (G)}$로 표시된 G의 지배 번호는 지배적인 G - 집합 S의 최소 카디널리티로, V \ S의 모든 꼭지점이 S의 꼭지점에 인접하도록 한다.Note that ${\displaystyle \gamma _{0}(G)\geq \gamma (G)}$. If G is a chordal graph and ${\displaystyle \gamma (G)>k}$ then ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$.^[4]

4. 유도 일치수 G, ${\displaystyle \mu }$( G${\displaystyle }$) ${\displaystyle \mu (G)}$는 유도 일치의 가장 큰 카디널리티로, 부분 집합의 어떤 두 정점을 연결하는 모든 에지를 포함한다.If there exists a subset A of V such that ${\displaystyle \gamma _{0}(G,A)>k+\min[k,\mu (G[A])]}$ then ${\displaystyle {\tilde {H}}_{k-1}(I(G))=0}$.^[5] This is a generalization of both properties 1 and 2 above.

5. I'(G)로 표시된 G의 비지배적 독립 콤플렉스는 G의 집합을 지배하고 있지 않은 독립 집합의 추상적 단순화 콤플렉스다.분명히 I'(G)는 I(G)에 포함되어 있다${\displaystyle .{}^{}}$ : I${\displaystyle {}^{}(}$ ${\displaystyle (G}$) →${\displaystyle I}$ (${\displaystyle G}$ ${\displaystyle )}$ ${\displaysty i:$$I'(G)\to I(G)}$. If G is a chordal graph then the induced map ${\displaystyle i_{*}:{\tilde {H}}_{k}(I'(G))\to {\tilde {H}}_{k}(I(G))}$ is zero for all ${\displaystyle k\geq -1}$.^{[1]: Thm.1.4} This is a generalization of property 3 above.

6. $\gamma {\displaystyle {}_{}^{}}$ ${\displaystyle s_{}^{}}$ ${\displaystyle {}_{}^{}}$( $){\displaystyle \gamma _{s}^{*}(G$로 표시된 G의 부분 항성-도밍 번호는 G에 설정된 부분 항성-도밍의 최소 크기다. ( )> ${\displaystyle \gamma _{s}^{*}(G)>}$이면 $H{\displaystyle {\stackrel{}{}}_{}}$~ ${\displaystyle {\mathrm{k}}_{}}$- 1${\displaystyle {}_{}}$( ${\displaystyle I}$( ${\displaystyle G}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle {\tilde{H}_{k-1}(I(G)=0$^{[1]: Thm.1.5}

관련개념

메술람의 게임은 G 그래프에서 하는 게임으로 G의 독립성 복합체의 동질적 연결성에 대한 하한을 계산하는 데 사용할 수 있다.

M(G)으로 표시된 그래프 G의 매칭 콤플렉스는 G의 매칭에 대한 추상적인 단순화 콤플렉스다.G선 그래프의 독립 콤플렉스다.^[6][7]

(m,n)-체스보드 콤플렉스는 전체 초당적 그래프 K의_m 일치 콤플렉스다._n그것은 체스판 위의 모든 포지션의 추상적인 단순화 콤플렉스인데, 체스판에서는 각각이 서로 위협하지 않고도 루크를 투입할 수 있다.^[8][9]

G의 클라이크 콤플렉스는 G의 보완 그래프의 독립 콤플렉스다.

참고 항목

• 레인보우 독립 집합

참조