ppt做的最好的网站有哪些,网站建设图片改不了,icp备案 网站备案,快速建设房产网站文章目录 1、树1.1 树的定义1.2 树的性质1.3 极小连通图1.4 树的中心1.5 生成树1.5.1 最小生成树 2、 割点和桥THE END 1、树
1.1 树的定义 \qquad 定义#xff1a; 一个连通的无圈的图称为树。 \qquad 只有一个顶点的树叫做平凡树。 \qquad 树中度为1的节点称为叶子结点。… 文章目录 1、树1.1 树的定义1.2 树的性质1.3 极小连通图1.4 树的中心1.5 生成树1.5.1 最小生成树 2、 割点和桥THE END 1、树
1.1 树的定义 \qquad 定义 一个连通的无圈的图称为树。 \qquad 只有一个顶点的树叫做平凡树。 \qquad 树中度为1的节点称为叶子结点。 \qquad 推论1 非平凡树中至少有两个叶子结点。 \qquad 推论2 树是双图。 \qquad 定义 一个无圈的图称为森林。
1.2 树的性质 \qquad 定理1 设 G ( V , E ) G(V, E) G(V,E)是一个 ( p , q ) (p,q) (p,q)图则下列命题是等价的 G G G是树 G G G中任意两个顶点之间有唯一的一条路 G G G是连通的且 p q 1 pq1 pq1 G G G中无圈且 p q 1 pq1 pq1 G G G中无圈 G G G中任意两个不相邻的顶点之间加一条边则得到一个有唯一圈的图 \qquad 要证明上述定理成立需要证明任意两个结论之间互为充分必要条件则可以将5条结论围成一圈依次证明前一条结论是后一条结论的充要条件即可。在证明第二条到第三条的结论时可以使用数学归纳法进行证明。证明第三条到第四条结论从第四条结论到第一条结论和从第五条结论到第一条结论时可以使用反证法进行证明。
1.3 极小连通图 \qquad 定义 去掉一条边就不连通的连通图叫做极小连通图。 \qquad 定理 G G G是树的充要条件为 G G G是极小连通图。
1.4 树的中心 \qquad 偏心率 给定一个树 G ( V , E ) G(V,E) G(V,E)和任意一个 v ∈ V v \in V v∈V定义节点 v v v的偏心率为 e ( v ) m a x u ∈ V { d ( u , v ) } e(v)max_{u \in V}\{d(u,v)\} e(v)maxu∈V{d(u,v)}。 \qquad 树的半径 树中所有顶点的最小偏心率为树的半径 r ( G ) m i n v ∈ V { e ( v ) } r(G)min_{v \in V}\{e(v)\} r(G)minv∈V{e(v)}。 \qquad 树的中心 树的中心表示为一个节点集合 H { v ∣ v ∈ V , e ( v ) r ( v ) } H\{v|v \in V, e(v)r(v)\} H{v∣v∈V,e(v)r(v)}。
1.5 生成树 \qquad 给定一个图 G ( V , E ) G(V,E) G(V,E), 若 G G G的一个生成子图是树则称其为 G G G的生成树。 \qquad 图 G ( V , E ) G(V,E) G(V,E)生成树存在的充要条件 G G G是连通图。 \qquad 给定一个图 G ( V , E ) G(V,E) G(V,E)是一个 ( p , q ) (p,q) (p,q)图 G G G中至多有 p p − 2 p^{p-2} pp−2个生成树(上界)。
1.5.1 最小生成树 \qquad 对于一个图 G ( V , E ) G(V,E) G(V,E)中所有的生成树其中权值最小的生成树叫做最小生成树求最小生成树的两个算法如下 \qquad Prime 算法随机从图中选择一个顶点加入到最小生成树树集合中之后选择和最小生成树集合中已经存在的顶点相邻接的其他顶点中边权值最下的顶点添加到最小生成树集合中(在此过程中判断是否有圈存在排除生成圈的顶点)直到所有的顶点都检查完毕其算法复杂度为 O ( p 2 ) O(p^2) O(p2)。 \qquad Kryscal 算法 将图中所有的边按照权值进行从小到大排序依次向生成树集合中添加权值最小的边每添加一条边需要判断是否有圈产生跳过有圈生成的边直到所有的边均检查完毕为止算法复杂度为 O ( q ∗ l o g q ) O(q*log\ q) O(q∗log q)。
2、 割点和桥 \qquad 割点定义 给定一个图 G ( V , E ) G(V,E) G(V,E) v ∈ V v \in V v∈V假如 G − v G-v G−v的分支数大于 G G G的分支数则称 v v v为 G G G的一个割点。 \qquad 每一个非平凡的图中至少有两个顶点不是割点(从最长路来证明)。哈密顿图中一定没有割点从哈密顿图的定义来证明哈密顿图中一定有哈密顿回路。 \qquad 定理1(割点的特征性质) 给定一个图 G ( V , E ) G(V,E) G(V,E) v ∈ V v \in V v∈V则下述命题等价 v v v是割点 ∃ u , v ∈ V , u ≠ w \exist u, v \in V, u \neq w ∃u,v∈V,uw, u u u和 v v v之间的所有的路均通过 v v v. ∃ V / { v } \exist V /\ \{v\} ∃V/ {v}的一个划分 { U , W } \{U, W\} {U,W}使得 ∀ u ∈ U , ∀ v ∈ V \forall u \in U, \forall v \in V ∀u∈U,∀v∈V u , v u, v u,v之间的路均通过 v v v \qquad 桥定义 给定一个图 G ( V , E ) G(V,E) G(V,E) x ∈ E x \in E x∈E假如 G − x G-x G−x的分支数大于 G G G的分支数则称 x x x为 G G G的一个桥。 \qquad 定理1(桥的特征性质) 给定一个图 G ( V , E ) G(V,E) G(V,E) x ∈ E x \in E x∈E则下述命题等价 x x x是桥 ∃ u , v ∈ V , u ≠ w \exist u, v \in V, u \neq w ∃u,v∈V,uw, u u u和 v v v之间的所有的路均通过 x x x. ∃ E / { x } \exist E /\ \{x\} ∃E/ {x}的一个划分 { U , W } \{U, W\} {U,W}使得 ∀ u ∈ U , ∀ v ∈ V \forall u \in U, \forall v \in V ∀u∈U,∀v∈V u , v u, v u,v之间的路均通过 x x x x x x不在任何圈上
THE END
