나무의 지옥 속성을 증명하는 방법 [중복]

Question

하위 트리 집합이 트리 T의 Helly 속성을 충족한다는 것을 귀납 방식으로 어떻게 증명할 수 있습니까? 즉, T의 하위 트리 집합에 이러한 하위 트리 중 두 개가 비어 있지 않은 공통 교차점을 갖는 속성이있는 경우 모든 하위 트리의 교차점도 비어 있지 않습니다.

이것이 사실임을 증명하기 위해 나무를 몇 개 그렸지만 공식적으로 증명을 작성하는 방법을 모르겠습니다

Answer 1

먼저 하위 트리 중 하나에 꼭지점이 하나만 있으면 사실이라는 것을 간단하게 보여줍니다. 그런 다음에있는 정점 수를 유도하여 다음 결과를 증명합니다.$T$:

허락하다 $T$ 나무가되어서 $\mathscr{T}$ 유한 한 하위 트리 패밀리 $T$ 각각 $S\in\mathscr{T}$ 최소한 두 개의 정점이 있고 모든 나무 쌍이 $\mathscr{T}$비어 있지 않은 교차점이 있습니다. 그때$\bigcap\mathscr{T}\ne\varnothing$.

이것이 기껏해야 모든 나무에 대해 사실이라고 가정합니다. $n$ 정점, 그리고 $T$ 나무가되다 $n+1$정점. 허락하다$\mathscr{T}$ 하위 트리의 가족이되다 $\mathscr{T}$정리의 조건을 충족합니다. 허락하다$v_0$ 펜던트 꼭지점 $T$, 허락하다 $v_1$ 독특한 이웃이 $T$, 그리고 $T'=T-v_0$. 허락하다$\mathscr{T}'=\{S-v_0:S\in\mathscr{T}\}$.

• 만약 $S_0',S_1'\in\mathscr{T}'$, 다음 $S_0'\cap S_1'\ne\varnothing$.

이제 유도 가설을 $T'$ 그리고 가족 $\mathscr{T}'$ 결론을 내리기 위해 $\bigcap\mathscr{T}'\ne\varnothing$ 따라서 $\bigcap\mathscr{T}\ne\varnothing$.