치거 상수(그래프 이론)

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않다. 좀 더 정확한 인용문을 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2013년 2월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

수학에서 그래프의 치거 상수(Cheeger number 또는 Isoperimetric number)는 그래프에 "병목"이 있는지 여부를 나타내는 숫자 측도다."병목 현상"의 척도로서 치거 상수는 많은 분야에서 큰 관심을 가지고 있다. 예를 들어, 잘 연결된 컴퓨터 네트워크 구축, 카드 섞기 등이 그것이다.그래프 이론적 개념은 치거가 리만 다지관의 등측 상수 이후에 생겨난 것이다.

치거 상수는 수학자 제프 치거의 이름을 따서 명명되었다.

정의

G를 정점 집합 V(G) 및 에지 집합 E(G)로 된 비방향 유한 그래프로 한다.정점 A ⊆ V(G)의 경우, ∂A는 A의 꼭지점에서 A의 바깥 정점(A의 가장자리 경계라고도 함)까지 이어지는 모든 가장자리 집합을 나타내도록 한다.

$\displaystyle \partial A:=\{x,y\}\in E(G)\ :\ x\in A,y(G)\setminus A\}$

가장자리는 순서가 지정되지 않았음을 유의하십시오. 즉$,{\displaystyle }$ {${\displaystyle x}$ , y${\displaystyle \}}$ = { ${\displaystyle y}$, ${\displaystyle x}$ ${\displaystyle \}}$ ${\displaystyle \{x,y\}=\{y,x$H(G)로 표시된 G의 체거 상수는 다음과 같이 정의된다^[1].

$(\displaystyle h(G):=\min \left\{\frac {\partial A}{{\partial A}{{}}}{{}}}}{{}}}}{A\subseteq V(G),0< A \leq {\tfrac {1}{1}{2}} V(G) \rig\}}.}$

치거 상수는 G가 연결된 그래프일 경우에만 엄격히 양수다.직관적으로 체거 상수가 작지만 양수라면, 그 사이에 "few" 링크(edge)가 있는 두 개의 "큰" 정점 세트가 있다는 점에서 "병목"이 존재한다.체거 상수는 두 하위 집합으로 설정된 정점을 "많은" 연결로 분할할 수 있는 경우 "크다"이다.

예: 컴퓨터 네트워킹

이론 컴퓨터 과학에 응용할 때, 사람들은 V(G) (네트워크의 컴퓨터 수)가 큰 경우에도 치거 상수가 높은 네트워크 구성(적어도 0에서 경계)을 고안하고자 한다.

예를 들어, 그래프 G로_N 생각되는 N ≥ 3 컴퓨터의 링 네트워크를 생각해 보십시오. 컴퓨터 1, 2, ..., N을 링 주위에 시계 방향으로 번호를 매기십시오.수학적으로 정점 집합과 에지 집합은 다음과 같이 주어진다.

${\displaystyle {\begin{aligned}V(G_{N})&=\{1,2,\cdots ,N-1,N\}\\E(G_{N})&={\big \{}\{1,2\},\{2,3\},\cdots ,\{N-1,N\},\{N,1\}{\big \}}\end{aligned}}}$

A를 연결된 체인에 있는$$ $\lfloor {\displaystyle }$ ${\displaystyle N\frac{}{}}$ ${\displaystyle \frac{2}{}}$ ${\displaystyle \rfloor }$ ${\$의 모음으로 사용하십시오$.$

${\displaystyle A=\좌측\{1,2,\cdots,\좌측\lfloor {\tfrac {n}{2}}\우측\rfloor \우측\}}$

그렇게

${\displaystyle \partial A=\left\{\reft\lfloor,\\tfrac {\n1}{{n}\prefloor,\\{n,1\}}}}$

그리고

${\displaystyle {\frac {\partial A}{{}}={\frac {2}{\\lfloor{\tfloor{{}}}{{{}\n\tfloor{{{\mbox{{}}}}}에서 \flotto.}}}}}}$

이 예는 체거 상수 h(G_N)에 대한 상한선을 제공하며, 이 상수는 N → ∞로도 0이 되는 경향이 있다.따라서, 우리는 링 네트워크를 큰 N의 경우 "병목"이 높은 것으로 간주할 것이며, 이는 실제적인 측면에서 매우 바람직하지 않다.우리는 링 위의 컴퓨터 중 한 대만 고장나면 되고, 네트워크 성능도 크게 저하될 것이다.만약 두 대의 비인접 컴퓨터가 고장나면, 네트워크는 두 개의 분리된 구성요소로 분할될 것이다.

체거 불평등

치거 상수는 그래프의 가장자리 확장을 측정하는 방법이기 때문에 익스팬더 그래프의 맥락에서 특히 중요하다.이른바 치거 불평등은 그래프의 고유값 격차와 치거 상수를 연관시킨다.더 명시적으로

${\displaystyle 2h(G)\geq \lambda \geq {\h^{2}(G)}{2\Delta(G)}}}}$

여기서 $\Delta {\displaystyle \mathrm{}(G}$) ${\displaystyle \Delta(G)}$은 $G{\displaystyle }$ ${\displaystyle$ G$}$의 $노드$에 대한 최대 도이고 degree ${\displaystyle$\lambda}은 그래프의$$라플라시안$$ 행렬의 스펙트럼 갭이다.^[2]

참고 항목

• 대수연결성
• 체거 바운드
• 전도성(그래프)
• 연결성(그래프 이론)
• 익스팬더 그래프

참조

• Donetti, L.; Neri, F. & Muñoz, M. (2006). "Optimal network topologies: expanders, cages, Ramanujan graphs, entangled networks and all that". J. Stat. Mech. 2006 (08): P08007. arXiv:cond-mat/0605565. Bibcode:2006JSMTE..08..007D. doi:10.1088/1742-5468/2006/08/P08007.
• Lackenby, M. (2006). "Heegaard splittings, the virtually Haken conjecture and property (τ)". Invent. Math. 164 (2): 317–359. arXiv:math/0205327. Bibcode:2006InMat.164..317L. doi:10.1007/s00222-005-0480-x.