离散数学_图论

开篇： 

        图论是一门很有实用价值的学科，它在自然科学、社会科学等各领域均有很多应用。自上世纪中叶以来，它受计算机科学蓬勃发展的刺激，发展极其迅速，应用范围不断拓广，已渗透到诸如语言学、逻辑学、物理学、化学、电讯工程、计算机科学以及数学的其它分支中。特别在计算机科学中，如形式语言、数据结构、分布式系统、操作系统等方面均扮演着重要的角色。

 9.0 内容提要

 9.2 图的基本概念

        9.2.1 图的定义

                一个图(Graph)是一个序偶，记为G = ，其中： （1）V = {v1, v2, …, vn}是有限非空集合，vi称为结点(Nodal Point)，简称点(Point)，V称为结点集(Nodal Set)。 （2）E是有限集合，称为边集(Frontier Set)。E中的每个元素都有V中的结点对与之对应，称之为边(Edge)。

                 与边相关的几个概念：

                若边e与无序结点对(u,v) 相对应，则称e为无向边 ，记为e = (u, v) = (v, u)， 这时称u、v是边e的两个端点。     若边e与有序结点对 相对应，则称e为有向边 (或弧)， 记为e = ，这时称u为e的始点(或弧尾)， v为e的终点 (或弧头)，统称为e的端点。

        9.2.2 图的表示

                对于一个图G，如果将其记为G = ，并写出V和E的集合表示，这称为图的集合表示。     用小圆圈表示V中的结点，用由u指向v的有向线段或曲线表示有向边，无向线段或曲线表示无向边(u, v)，这称为图的图形表示。

                例9.2.2

设图G = ，这里V = {v1, v2, v3, v4, v5}，E = {e1, e2, e3, e4, e5, e6}，其中e1 = (v1, v2)，e2 = ，e3 = (v1, v4)，e4 = (v2, v3)，e5 = ，e6 = (v3, v3)。试画出图G的图形，并指出哪些是有向边，哪些是无向边？

G中的e1、e3、e4、e6是无向边，e2、e5是有向边

 

例9.2.3

设图G = 的图形如下图所示，试写出G的集合表示。

 

 解  图G的集合表示为G = = <{1, 2, 3, 4, 5}，{<1, 1>，<1, 2>，(1, 4)，(1, 5)，(2, 3)，<3, 5>，<4, 3>，<4, 5>}>。

                定义9.2.2

设图G = ，其中V = {v1, v2, …, vn}，并假定结点已经有了从v1到vn的次序，则n阶方阵AG = (aij)nxn称为G的邻接矩阵(Adjacency Matrix)，其中

 9.2.3 邻接点与邻接边

定义9.2.4  在图G = 中，若两个结点vi和vj是边e的端点，则称vi与vj互为邻接点，否则vi与vj称为不邻接的；

具有公共结点的两条边称为邻接边；

两个端点相同的边称为环或自回路；

图中不与任何结点相邻接的结点称为孤立结点；

仅由孤立结点组成的图称为零图；

仅含一个结点的零图称为平凡图；

含有n个结点，m条边的图，称为(n, m)图。

9.2.4 图的分类

1. 按边有无方向分类

定义9.2.5  每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；有些边是无向边，而另一些边是有向边的图称为混合图。

2. 按有无平行边分类 

定义9.2.6  在有向图中，两结点间(包括结点自身间)若有同始点和同终点的几条边，则这几条边称为平行边；   在无向图中，两结点间(包括结点自身间)若有几条边，则这几条边称为平行边。   两结点a、b间相互平行的边的条数称为边(a, b)或的重数。   含有平行边的图称为多重图；非多重图称为线图；无环的线图称为简单图。

3. 按边或结点是否含权分类

定义9.2.7  赋权图G是一个三重组或四重组，其中V是结点集合，E是边的集合，f是从V到非负实数集合的函数，g是从E到非负实数集合的函数。

9.2.5 图的操作

定义9.2.3  设图G = 。 设e∈E，用G-e表示从G中去掉边e得到的图，称为删除边e。又设EE，用G-E表示从G中删除E中所有边得到的图，称为删除E。 设v∈V，用G-v表示从G中去掉结点v及v关联的所有边得到的图，称为删除结点v。又设VV，用G-V 表示从G中删除V中所有结点及关联的所有边得到的图，称为删除V。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！