哈尔滨工业大学图论-总结_图论正则图资源-CSDN文库

共2个文件

pdf：2个

需积分: 10 152 浏览量 2018-03-09 16:48:02 上传评论收藏 364KB ZIP 举报

资源详情

资源评论

收起资源包目录

package

哈尔滨工业大学图论-总结.zip （2个子文件）

images.pdf 3KB

哈尔滨工业大学图论-总结.pdf 392KB

第二篇图论

1.图、图论

由点和线组成的图表称之为图。

系统地研究图的性质就构成了一门学科，被称

为图论。

2.与上篇的关系：

图论虽然是一门单独的学科，但实际上，图论可

以看成是集合论的继续．就是在有限的集合上（V）

上定义的一个反自反、对称的二元关系（E）。

3. 在图论的解题过程中常常使用两种解题方法：

一是反证法，另一个是数学归纳法。

第6章

第一节图论发展概述-----了解

第二节图的基本定义

设V是一个非空集合，V的一切二个元素所构成子集记为

P

2

(V)，即P

2

(V)={A|AV且|A|=2}；

２.１无向图

定义1 设V是一个非空有限集合，EP

2

(V)，二元组(V,E)称

为一个无向图。

2.2 顶点的度

定义2 设v为图G=(V，E)的任一顶点，G中与v邻接的边的条

数称为顶点v的度，记为degv。

定理1 (握手定理)设G=(V,E)是一个具有p个顶点q条边的图,

则G中各顶点度的和等于边的条数q的两倍，即∑degv=2q。

推论1任一图中，度为奇数的顶点的数目必为偶数。

定义3 设G是图，若Δ(G)=δ(G)=r，即G的每个顶点的

度都等于r，则G称为r度正则图。

(1) 若Δ(G)=δ(G)=3，则称3-度正则图,也叫做三次

图。

(2) 若Δ(G)=δ(G)=0，则称为零图，即0-度正则图。

(3) 若Δ(G)=δ(G)=p-1，则称为p-1度正则图，即

degv=p-1。

(4) p-1度正则图也称为p个顶点的完全图，记为Kp。

在Kp中，每个顶点与其余各顶点均邻接。

显然，Kp有p(p-1)/2条边。

2.5 子图

子图、生成子图、真子图、极大子图、导出的子图

2.6 同构

第三节路、回路（圈）、连通图

3.1 通道、迹、路

3.2 连通

定义2 设G=(V,E)是图，若G中任两个不同顶点

间至少有一条路联结，则称G是一个连通图。

3.3 几个定理

定理2 设G=(V,E)是一个有p个顶点的图。若对G

的任两个不邻接的顶点u和v,有

degu + degv≥p-1，

则G是连通的。[这个定理是一个充分条件]

定理3 设G=(V,E)是至少有一个顶点不是弧立顶

点的图。若对任意v∈V，degv为偶数，则G中

有回路。

定理4 若图G中的两个不同顶点u与v间有两条不

同的路联结，则G中有回路。

内容反馈

评论0

最新资源

普通网友

粉丝: 0
资源:
1

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip