（二）

1.2节 Paths, Cycles, and Trees讲了关于路、圈、树的几个基本成果。

定理：

TH3：关于连通分量的断言

TH4：图是二分图 iff 它不含奇数长的圈。

TH5：图是森林 iff 每个顶点对(x,y)包含至多一条x-y路。

TH6：关于树的断言

书中给出两种建生成树的方式。一是广度优先，从而引出了直径的概念: diamG = maxx,yd(x,y)，顶点：radG=minx maxy d(x,y)；二是从一个顶点开始，每次加一条边建立。不难证明推论8：A tree of order n has size n-1.

下面的部分是产生一个图的最经济生成树的算法（也就是最小生成树）。分为四种：

1. 每次都加入最小的边，不能成圈

2. 每次都删去最大的边，保持连通

3. Prim算法

4. （没有相等两权时适用）每个点都选择连接最小边。这一过程重复进行

不难证明，当没有边权相等时，所形成的最小生成树是唯一的。

祝大家新年快乐！