高等数学 课件 第十五章 图论基础_第1页
高等数学 课件 第十五章 图论基础_第2页
高等数学 课件 第十五章 图论基础_第3页
高等数学 课件 第十五章 图论基础_第4页
高等数学 课件 第十五章 图论基础_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第十五章

图论基础第一节图的基本概念第一节图的基本概念一、图的定义和表示1.图的定义

二、图和边的分类1.有向图——2.无向图——3.混合图

——

4.环——5.带环图——6.平行边——每条边均有方向的图，一般用D表示

。每条边均是无向边的图，一般用G表示

。既含有有向边又含有无向边的图

。若一条边连接同一个点，则称该边为环。允许有环的图称为带环图。在无向图中，若两条或两条以上的边都与同一对结点相连，称这些边为平行边；而在有向图中，若两条或两条以上方向相同的有向边连接着同一对结点，也称这些边为平行边

。7.多重图——8.线图

——

9.简单图——

10.权——允许有平行边的图称为多重图。不含平行边的图称为线图

。即不包含环，又不包含平行边的图称为简单图

。一个图中，结点或边上还带有一些数字信息，这样的图叫带权图。其中边上的数字叫边的权，结点上的数字叫点的权。三、图的相关概念及定理1.

邻接

——

同类元素的关系2.

关联

——

异类元素的关系3.

孤立点

——

不与任何边关联的点

。4.

零图

——

只有点，没有边的图

。5.

平凡图

——

最简单的零图。（只有一个点）6.

无向完全图

——

任意两点间都有边关联的无向图，简称完全图，记为

，其

中

为结点数。7.

有向完全图

——

任意两点间都有两条相向的边连接的有向图。8.无向图的度

——

无向图中，结点

的度数就是与

相关联的边的条数，记为

。9.有向图的度

ⅰ出度

——

在有向图中，以结点

为起点的边的条数，记为

；

ⅱ入度

——

在有向图中，以结点

为终点的边的条数，记为

；

ⅲ度

——

结点

的入度、出度之和，记为

。

10．K-正则图——一个图如果各点的度数都为

。

零图中各点的度数为多少呢？完全图

的各个点的度数是多少呢？（各点度数都是0）（各点度数都是n-1）定理1

（基本定理，握手定理）设图G=<V,E>是(n,m)图，则有

。推论一个图中奇点的个数一定是偶数

。(度数为奇数的结点，简称为奇点；度

数为偶数的结点，简称为偶点.

)定理1.2在有向图中，各结点的出度之和等于各结点的入度之和

。11.

子图ⅰ子图——图

与

，如果有

且

则称

是

的子图；ⅱ生成子图——若

是

的子图，并且

，则称

是

的生成子图；ⅲ导出子图——若

是

的子图，并且边集

继承了所有以

中的点为端点（即两端点均在

中）属于原图

中的所有边，则称

是

的导出子图。12.补图

——

设图

有

个结点，在完全图

中删去

中的所有边

（点不变）后剩下的

的生成子图，称为

的补图。四、图的同构1.同构的图

——

两个图，

与

，所含的结点相同，结点与结点的连接关

系也相同，则称

与

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论