计算机数学基础 何春江 第13章 图论初步

《计算机数学基础 何春江 第13章 图论初步》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第13章图论初步1本章学习目标我们在前面曾介绍过二元关系的图形表示，即关系图。在关系图中，我们主要关心研究对象之间是否有连线（图论中称为边），这样的图正是图论的主要研究对象。图论中还根据实际需要，将这类图进行了推广，并且把它当作一个抽象的数学系统来进行研究。通过本章学习，读者应该掌握以下内容：2本章学习目标无向图、有向图的定义，图的基本术语的含义子图、生成子图的概念无向连通图及有向连通图的有关概念通路、回路的概念图的矩阵表示赋权图的概念及应用欧拉通路、欧拉回路、欧拉图和半欧拉图的概念哈密尔顿通路、哈密尔顿回路、哈密尔顿和半哈密尔顿的概念树的定义最小生成树的求法最优树的

2、求法3主要内容13.1图的基本概念13.2图的矩阵表示13.3路与回路13.4树及其应用413.1图的基本概念13.1.1图的定义定义13.1.1图G是一个三元组，G=，其中V(G)是一个非空的顶点集合，E（G）是边的集合，φG是从边集合E到顶点无序偶或有序偶集合上的函数。由定义可知，图G中的每条边都与图中顶点的无序偶或有序偶相联系，若边eE与顶点无序偶[vi，vj]相联系，则φG（e）=[vi，vj]，此时边e称为无向边，有时简称边；若边eE与顶点有序偶相联系，则φG（e）=，此时边e称为有向边或弧。vi称

3、为弧的始点，vj称为弧的终点，有向边的箭头方向自始点指向终点。513.1图的基本概念13.1.1图的定义例13.1.1画出下面二图的图形（1）无向图　　　　　　　　，其中613.1图的基本概念13.1.1图的定义例13.1.1画出下面二图的图形（２）有向图　　　　　　　　，其中713.1图的基本概念13.1.1图的定义例13.1.1画出下面二图的图形解：(1)的图形为13.1-3（a）所示，（2）的图形为13.1-3（b）所示。813.1图的基本概念定义设无向图（1）如果在顶点ｕ和顶点ｖ之间存在一条边，即若存ｅ∈Ｅ在且ｅ=(u,v)，则称顶点u和顶点v是彼此相邻的，简

4、称相邻的，并称顶点u和顶点v是边e的端点，e与u（或e与v）是彼此关联的。（2）若ek,el至少有一个公共端点，则称边ek,el是彼此相邻的，简称相邻的。913.1图的基本概念13.1.2顶点的度数定义13.1.2设无向图G，v是图G中的顶点，所有与v关联的边的数目，称为顶点v的度数，记作deg(v)。度数为零的点称为孤立点，度数为1的点称为悬挂点，与悬挂点关联的边称为悬挂边。定理13.1.1设图G是具有n个点，m条边的无向图，其中顶点集合为V={v1，v2，…，vn}，则推论度数为奇数的顶点个数为偶数。1013.1图的基本概念定义13.1.3设有向图G，v是图G中的

5、顶点，以v为始点的有向边的数目，称为v的出度，记个deg+(v)，以v为终点的有向边的数目，称为v的入度，记作deg-(v)。定理13.1.2设有向图G具有n个顶点，m条边，其中顶点集合V={v1，v2，…，vn}，则有证明因为每一条有向边为始点提供1个出度，为终点提供1个入度，而所有各顶点的出度之和及入度之和均由m条有向边提供，所以定理得证。1113.1图的基本概念13.1.3多重图、简单图与完全图定义13.1.4如果两个顶点之间存在多条边（对于有向图，则有多条同方向的边），则称这些边为平行边，两相顶点a，b间平行边的条数称为边的重数。含有平行边的图称为多重图，不含

6、平行边和自回路的图称为简单图。当图中顶点的数目为有限个数时，称为有限图，否则称为无限图。本章仅讨论有限图。定义13.1.5在n阶无向（无向）图中，如果任意两个不同的顶点之间都有一条边关联，则称此图为n阶无向（无向）完全图，记作Kn。1213.1图的基本概念13.1.2多重图、简单图与完全图如在图13.1-5中（a）和（b）均为4阶完全图。1313.1图的基本概念13.1.2多重图、简单图与完全图定理13.1.3n阶无向完全图Kn的边数为证明在Kn中，因为任意两个顶点间都有边联结，所以Kn的边数为n个顶点中取两个顶点的组合数：即，Kn的边数为。定理13.1.3n阶无向完

7、全图Kn的边数为。1413.1图的基本概念13.1.4子图定义13.1.6设G=和G=是两个图，（1）若V'V且E'E，则称G'是G的子图；（2）若G'是G的子图，但V'≠V或E'≠E，则称G'是G的真子图；（3）若G'是G的子图，且V'=V，则称G'是G的生成子图或支撑子图。从上面的定义可以看出，对图G=，G本身和零图G'=都是它的生成子图，它们称为G的平凡生成子图。1513.1图的基本概念13.1.4子图如图13.1-6，（a）是（b）的子图且是真子图。1613.1图的基本概念13.1.4子图若且