《图论及其应用》学习笔记（树）

树的概念与性质：

树：连通的无圈图。树也是森林。

平凡图就是平凡树。

度数大于1的顶点为分支点。等于1为树叶。

ps：因为至多只有一片树叶，则剩下的n-1个顶点的度均≥2，所以有

 

最小连通图：减去任意一条边，均会使得图不连通。

ps：无圈的连通图就是树。

 

树的中心与形心：

v的离心率：取离v最远的顶点的距离。

r(G)图的半径：取每个顶点的离心率最小的值。

图G的直径：G的最大离心率。

v点中心点：若某点v的离心率等于图的半径。

中心：G中全体中心点的集合。

 ps：每个节点能够触及到的最远的点，必在叶子节点处。删除叶子节点后，每个点的离心率也相继地减一，意味着，中心点还一直是中心点。

点u的权：点u的所有分支中，具有最多边的分支，它的边数。

形心：具有权值最小的点。

 

生成树：

生成树：图G某个生成子图T是一棵树。

生成森林：图G某个生成子图T是森林。

树枝：生成树的边。

破圈法：

只有当图G本身是树时，其生成树才唯一。

连通图的生成树的棵树：

边收缩：

ps：分别从不包含某条边，和包含某条边上证明。若生成树包含某条边e，将它收缩了，在生成树也会对应被收缩。

 

最小生成树：

Kruskal算法：不断得挑选最小的边，只要不会形成圈就行。

ps：是中选取的，一定是非公共边中最小的。在和T中，它不是，下标比k小的边，也都在，所以只可能>k

算法2：

保证图G连通的情况下，逐次删掉图G中权值最大的边，直到获得生成树为止。