求证:对于一颗树的任意一点,与它距离最远的点是该树的直径的两端点之一。
证明:
如图所示为一颗树的直径和挂在直径上的两颗子树。
显然,子树的任意一点到连接处的距离都不会超过直径的两端到连接处距离最大值,否则直径应经过该点。
所以,dis(子树1一点,子树2一点)=dis(子树1一点,子树2连接处)+dis(子树2连接处,子树2一点)<dis(子树1一点,子树2连接处)+dis(子树2连接处,直径一端)\text{dis}(子树1一点,子树2一点)=\text{dis}(子树1一点,子树2连接处)+\text{dis}(子树2连接处,子树2一点)<\text{dis}(子树1一点,子树2连接处)+\text{dis}(子树2连接处,直径一端)dis(子树1一点,子树2一点)=dis(子树1一点,子树2连接处)+dis(子树2连接处,子树2一点)<dis(子树1一点,子树2连接处)+dis(子树2连接处,直径一端)。
证毕。