그래프의 강도

그래프의 강도: 예제
그래프의 강도: 예제
	강도 2의 그래프: 그래프는 여기서 세 부분으로 분해되며, 부품 사이에 네 개의 가장자리가 있고, 비율이 4/(3-1)=2이다.
	그래프 및 모수 표

그래프 이론이라고 불리는 수학의 가지에서, 방향을 잡지 않은 그래프의 강도는 해당 그래프의 분해에서 생성된 최소 비율 에지/성분에 해당한다.정점 집합의 칸막이를 계산하고 가장자리 농도가 높은 구역을 검출하는 방법으로, 정점 제거에도 비슷하게 정의된 강성을 그래프로 나타낸 것과 유사하다.

정의들

$\sigma (G)$ ( G ) $\sigma (G)$ displaystyle $\sigma (G)}$ 의 $\sigma (G)$ 강도 G = (V, E)는 다음 세 가지 정의를 허용한다.

Let $\Pi$ be the set of all partitions of $V$ , and $\partial \pi$ be the set of edges crossing over the sets of the partition $\pi \in \Pi$ , then ${\displaystyle \displaystyle \si$ $gma (G)=\min _{\pi \in \pi \}{\frac {$ $\partial \pi }{ \pi -1$
${\mathcal {T}}$ T ${\$ 이 ${\mathcal {T}}$ (가) G의 모든 신장 트리의 집합인 경우

\sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ and }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.

그리고 선형 프로그래밍 이중성을 통해

\sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ and }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.

복잡성

그래프의 강도를 계산하는 것은 다항식 시간에 할 수 있으며, 그러한 알고리즘은 커닝햄(1985년)에 의해 처음 발견되었다.The algorithm with best complexity for computing exactly the strength is due to Trubin (1993), uses the flow decomposition of Goldberg and Rao (1998), in time $O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))$ .

특성.

If $\pi =\{V_{1},\dots ,V_{k}\}$ is one partition that maximizes, and for $i\in \{1,\dots ,k\}$ , $G_{i}=G/V_{i}$ is the restriction of G to the set $V_{i}$ , then $\sigma (G_{k})\geq \sigma (G)$ $\sigma (G_{k})\geq \sigma (G)$ ( $\sigma (G_{k})\geq \sigma (G)$ ) ${\displaystyle \sigma (G_{k})\geq \sigma (G$ .
$\lfloor \sigma (G)\rfloor$ 정리: ⌊ ( $\lfloor \sigma (G)\rfloor$ ) $\lfloor \sigma (G)\rfloor$ ⌋ { $\$ $\displaystyle \llfloor \rfloor }$ 은 $\lfloor \sigma (G)\rfloor$ G에 포함될 수 있는 최대 에지 분리관 스패닝 트리 수입니다.
그래프 파티션 문제와 달리 강도를 계산하여 출력하는 파티션의 크기가 반드시 균형이 잡히는 것은 아니다(즉, 크기가 거의 같다).