新浪博客

《图论及其应用》入门——复习纲要和习题解答（3）

2011-05-17 20:16阅读：

http://blog.sina.cn/dpool/blog/u/1712346183

现实世界的许多事例用图形来描写可能是方便的，这种图形是由一个点集以及这个点集中的某些点对的连线构成的。例如，点可以表示人，连线表示一对朋友；或 者，用点表示通讯站，连线表示通讯线路。注意：在这类图形中，人们主要感兴趣的是给定的两点是否有一根线连接，而连接的方式则无关紧要。这类事例的数学抽 象就产生了图的概念。
第二章 树
2.1 树
不包含圈得图称为无圈图，连同的无圈图称为树。
定理2.1 在一棵树中，任意两个顶点均由唯一的路相连。
定理2.2 若 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）是树，则 《图论及其应用》入门——复习纲要和习题解答（3）
推论2.2 每棵非平凡树至少有两个1度顶点。
习题2.1
2.1.1 证明：若无环图 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）的任意两个顶点均由唯一的路连接，则 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）是树。
证：
由于 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）中任意两顶点都被唯一的路相连，故 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）连通。又若 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）含有圈 《图论及其应用》入门——复习纲要和习题解答（3），则 《图论及其应用》入门——复习纲要和习题解答（3）上的两点在 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）中存在两条路相连。这与“唯一道路”的假设矛盾，故 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）中不含圈，由树的定义， 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）是树。
2.1.4 证明：每棵恰有两个1度顶点的树均是路。
证：
设 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）是恰有两个1度顶点的树，则 《图论及其应用》入门——复习纲要和习题解答（3）， 《图论及其应用》入门——复习纲要和习题解答（3）. 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）连通且除两个1度顶点外，其它顶点的度 《图论及其应用》入门——复习纲要和习题解答（3）.若其它定点中有度大于2的顶点，则 《图论及其应用》入门——复习纲要和习题解答（3）.这和上面的推导矛盾，故 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）是树。
2.2 割边和键
 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）的割边是指使得 《图论及其应用》入门——复习纲要和习题解答（3）的边 《图论及其应用》入门——复习纲要和习题解答（3）。
定理2.3 《图论及其应用》入门——复习纲要和习题解答（3）是 《图论及其应用》入门鈥斺敻聪案僖拖疤饨獯穑2）的割边当且仅当 《图论及其应用》入门——复习纲要和习题解答（3）不包含在 《图论及其应用》入门——复习纲要和习题解答（3）

我的更多文章

下载客户端阅读体验更佳

APP专享