第8章 图论 Topics in Graph Theory周二Word文件下载.docx

第8章 图论 Topics in Graph Theory周二Word文件下载.docx

《第8章 图论 Topics in Graph Theory周二Word文件下载.docx》由会员分享，可在线阅读，更多相关《第8章 图论 Topics in Graph Theory周二Word文件下载.docx（10页珍藏版）》请在冰点文库上搜索。

连接一个顶点的圈loop算两度。

孤立点isolatedvertex：

度数为0的点。

两个顶点相邻adjacent：

有一边相连。

定理1.（握手定理）TD＝TD（vi）=2m.

推论.任意图的奇数度顶点必有偶数多个。

完全图completegraph：

任意两点都相邻简单图。

定理2.n个顶点的完全图有n（n-1）/2条边。

正则图regulargraph：

每个顶点都有相同的度数。

E={<

vi,vj>

|vi,vj∈V}有向边集有向图

有向边<

，

vi起点弧尾，vj终点弧头

TD（vi）:

顶点的度degree:

以vi为端点的边的数目。

OD（vi）:

出度,以vi为起点的边的数目。

ID（vi）:

入度，以vi为终点的边的数目。

TD（vi）=OD（vi）+ID（vi）

OD=ID,TD=2|E|，E|=1/2*TD

TDODID为整个图的总度,出度,入度数。

路径path：

vi·

vj，以vi为起点vj为终点的顶点序列，相邻顶点相邻。

路径的长length:

路径上边的数目，

简单路径simplepath:

点都不重复的路径，

回路circuit:

首尾相接的路径，

简单回路simplecircuit:

除起点和终点以外都不重复的路径，

vivj连通connected:

有路径vi·

vj相连。

连通图:

任意两点都连通的图。

例

左图a,c,d,g是简单路径

右图a,d,b,c,e是简单路径。

f,e,a,d,b,a,f是简单回路。

f,e,d,c,e,f不是简单回路。

有向图

vivj强连通vivj连通vjvi也连通，

强连通图任意两点都强连通。

子图和商图SubgraphandQuotientGraph

G=（V,E）,G’=（V’,E’）

如果V’V,E’E,

就称G’是G的子图subgraph。

G’的补图：

＝（V,E\E’）,G的边集中去掉E’的边。

Ge＝（V，E’）,E’=E\{e}.

连通分量connectedcomponents:

一个图的极大连通子图。

一个图可以划分成几个不相交的连通分量。

强连通分量strongconnectedcomponents:

一个有向图的极大强连通子图。

商图quotientgraph

R是V上等价关系，

V/R={[v]|v∈V}

E/R={（[v],[w]）|[v],[w]中有相邻的顶点}

GR＝G/R=（V/R,E/R）,称为G模R的商图。

把R相关的顶点粘合成一点，相关的边粘合成一边，就得到商图。

HomeworkP285

10，12，13，18，22

7.4无向树undirectedtrees

无向图连通不含回路的图叫无向树

无向树：

有向树的对称闭包。

定理1.R是对称关系。

则下列命题等价

thefollowingstatementareequivalent：

（TFAE）

（a）R是无向树。

（b）R连通connected，无回路acycle。

定理2.R是对称关系。

TFAE

（b）R无回路，每增加一条边，都产生一个新的回路。

（c）R连通，去掉任意一条边都不连通。

定理3.n个顶点的树R，有n－1条边。

连通图的生成树spanningtree:

含有所有顶点的极小连通图.

n个顶点连通图至少有n-1条边。

m条边的连通图去掉m－n＋1条边可以得到生成树。

从连通图中如有回路，去掉回路中的一条边，继续直至没有回路，就得到生成树。

从m条边的连通图中得到生成树，要去掉m－n＋1条边

T是连通图G的生成树，G的每一条不属于T的边e，叫弦。

m条边的连通图共有m－n＋1条弦。

基本回路：

每条弦加到T中得到一个回路，叫基本回路。

m条边的连通图共有m－n＋1个基本回路。

割集：

G的边集，去掉后G不连通。

一条边组成的割集叫桥bridge。

树的每条边都是桥。

基本割集：

生成树T中每一条边，和G中对应于T的所有的弦，组成一个割集，叫基本割集。

最小生成树：

权重最小的生成树。

带权的边：

带边长的边。

带权的图：

每边都带权。

Prim算法：

设G=<

V,E>

1.令U={v0},T={}.

2.对任意u∈U,v∈V-U,（u,v）∈E,

找到权最小的边（u1,v1）,

令U=U∪{v1},T=T∪{（u1,v1）}

3.重复2，直至U=V.

得到T就是最小生成树。

T中共有n-1条边

Kruskal克鲁斯卡尔算法

G=（V,E）连通图

令T=（V,{}）是G的所有顶点而无边的非连通图。

1.选择E中权值最小的边，

若该边连接T的两个连通分量，将它加入T,

这时T的连通分量减少1；

否则选下一条权值最小的边。

2.重复1n-1次直到T连通。

T就是最小生成树

Homework

P270－27114，18

P275－2764，8

8.2欧拉路径和欧拉回路

哥尼斯堡七桥问题。

一笔画问题。

欧拉路径Eularpath：

通过图的所有边，每个边恰好一次的路径。

欧拉回路Eularcircuit：

构成回路的欧拉路径。

定理1.G有欧拉回路当且仅当G连通且没有奇数度顶点。

定理2.G有欧拉路径当且仅当G连通且至多有两个奇数度顶点。

Fleury’s算法：

留作练习。

1－8，14

8.3Hamilton路径和Hamilton回路

8.4运输网络TransportNetworks

8.5匹配问题MatchingProblem

8.6染色图ColoringGraphs