第一章 图的基本概念

第一章图教学安排的说明章节题目：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算学时分配：共2课时本章教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），会进行图的运算，会用图论的方法描述一些简单的实际问题．其它：由于离散数学中已介绍过相关内容，本章以复习为主课 堂 教 学 方 案课程名称：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算授课时数：2学时授课类型：理论课教学方法与手段：讲授法教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），会进行图的运算，会用图论的方法描述一些简单的实际问题．教学重点、难点：（1） 理解图、简单图、子图以及图的同构等概念，并能够用图表示简单的现实问题；（2） 掌握途径、链和道路的概念及其区别；（3） 理解图的连通性概念；（4） 掌握图的四种运算。

教学内容：第一章 图§1.1图的概念引例例1.下面是五城市之间的航线图，若两城市间有航线，则连线，否则不连如图1.1（a ）：由图中可知，北京与广州间没有航线，而大连到上海间有航线北京 大连 上海 广州 昆明 9 6 4 8 10 （a ） （b ）图1.1例2.数4，6，8，10，9五个数，若有公因子则连线，，否则不连，如上图1.1(b) 通常人们认为，过去我们所学的微积分是属于连续数学，而本章所要讨论的图论是离散数学的重要分支．首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统．也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系．因此在图论中，顶点之间的距离、弯曲、以及顶点间的位置关系都是无关紧要的，即图的概念是抽象化的,它是数学中经常采用的抽象直观思维方法的典型代表．下面给出图作为代数结构的一个定义。

图的定义:一个图是一个三元组〈)(G V ，)(G E ，G ϕ〉，其中)(G V 是一个非空的点集合，)(G E 是有限的边集合，G ϕ是从边集合E 到点集合V 中的有序偶或无序偶的映射。

例3 图G =〈)(G V ，)(G E ，G ϕ〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ，),()(1b a e G =ϕ，),()(2c a e G =ϕ，),()(3d b e G =ϕ，),()(4c b e G =ϕ，),()(5c d e G =ϕ，),()(6d a e G =ϕ。

图1.2由于在不引起混乱的情况下，图的边可以用有序偶或无序偶直接表示。

因此，图也可以简单的表示为：,G V E=,其中，V是非空点集，E是连接点的边集。

若边i e与点无序偶),(kjvv相关联，则称该边为无向边（Undirected Edge）。

若边i e与点有序偶><kjvv,相关联，则称该边为有向边（Directed Edge），其中jv称为i e的起点（Initial Vertex），k v称为i e的终点（Terminal Vertex）。

定义：每一条边都是无向边的图称为无向图（Undirected Graph），每一条边都是有向边的图称为有向图（Directed Graph），本课主要介绍无向图（无向图的定义）图的定义;一个图（Graph）G定义为一个偶对(),V E，记作(),G V E=。

其中：1）V是一个集合，其中的元素称为顶点2）E是无序积V V⨯中的一个子集合，其元素称为边，我们分别用()V G和()E G表示的G顶点集合与边的集合。

如果()V G和()E G都是有限集合，则称为G有限图。

本书只研究有限图。

以下从边和顶点及其关系对图的有关基本概念加以介绍：从“点”的角度考虑，有限图中顶点的个数称作图的阶没有任何边的图称为空图,记作φ,只有一个顶点的图叫做平凡图.在一个图中，不与任何点相邻接的点，称为孤立点（Isolated Vertex）。

关联于同一点的一条边称为自闭途径或环（Loop）。

如图1.3中的1e与2e，1e与4e 是邻接边，5e是环。

一个有p 个顶点和q 条边的图称为(),p q 图,一个(),p q 图,若它的p 个顶点标以不同的名称,则称为标定的,否则称为非标定的..图1-3二分划：图G 顶点集合()V G 分成两个不相交且并为()V G 的两个子集1V 和2V ,记为()12,V V二部图：若G 有二分划()12,V V ，且G 的每一条边的一个端点在1V 中，另一个端点在2V 中，则称G 为二部图，记作()12,;G V V E =。

完全二部图：若()12,;G V V E =，12,,V m V n ==且1V 中每一个点与和2V 中每一个点都邻接，则称G 为完全二部图，记作：,m n K完全图:任意两个点间都有边相连的简单图称为完全图（Complete Graph ）。

n 个点的无向完全图记为n K 。

显然n 个点的无向完全图n K 的边数为2n C 。

图1-4分别给出了1个点、2个点、3个点、4个点和5个点的无向完全图。

15K K -的图示图1-4图1-5从“边”的角度考虑， 若连接同一对顶点的边数大于1，则称这样的边为多重边，其边数称为边的重数。

从“边”和“点”的关系考虑，如图1.6(c)点A 与边AB 、AC 关联，点A 与点B 、C 邻接;边AB 与AC 邻接含有重边的任何图，称为多重图（Multigraph ）。

不含有重边和环的图称为简单图（Simple Graph ）。

(c)图1-6如图1-6()a 、(b )不是简单图,(c)不是简单图从“度”的角度考虑，图的同构在图论中我们只关心点间是否有连线，而不关心点的位置和连线的形状。

因此，对于给定的图而言，如果将图的各点安排在不同的位置上，并且用不同形状的弧线或直线表示各边，则可以得到各种不同图形。

所以，由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。

图1-7为了描述看起来不同，而其结构完全相同的图，引入了图的同构的概念。

图的同构：设>=<E V G ,和>=<''',E V G 是两个图，如果存在着一一对应':V V →ϕ使得E v v j i >∈<,（或E v v j i ∈),(）当且仅当')(),(E v v j i >∈<ϕϕ（或 AC B'))(),((E v v j i ∈ϕϕ），，记作'G G ≅。

也称G 与'G 是同构的。

显然图1-7是同构的。

通过定义可以看出，对于同构的图G 与'G 来说，存在着一一对应，将V 中的点对应到'V 中的点，将E 中的边对应到'E 中的边，且保持着关联关系，即边e 关联着点i v 和j v ，当且仅当e 对应到'E 中的边'e 也关联着i v ，j v 对应到'V 中的点)(),(j i v v ϕϕ。

在有向图的情况下，这种对应关系不但应该保持点间的邻接关系，而且还应保持边的方向。

图1-9 同构图示例图1-10与群、格、布尔代数一样，利用这个等价关系可以把图分解成等价类，使得同类中的图相互同构，而不同类中的图互不同构。

这样，我们就可以在图的同构类中选一个图来代表它们。

由于图本质上与点和边的标记无关，因此，选出的这个图常常略去点和边的标记，这个图就称为无标记图。

如图1-10所示的(a )、(b )、(c )、(d )四个图形均相互同构，它们属于同一个同构的等价类。

而图1-10(d )就是该类的一个无标记图。

三、例题精讲寻找一种简单而有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。

握手定理得应用10个人参加会议，会后统计出各人的朋友数为（ⅰ）3，3，3，3，5，6，6，6，6，6；（ⅱ）1，1，3，3，3，3，5，6，8，9.证明:两组统计数据都有误.【分析】该问题仅仅是统计每个人的朋友数，并且隐含了人与人之间或是朋友或不是朋友这种二元关系，这正好符合用图论方法研究问题的特征。

可用10个点1021,,,A A A 表示这10个点，若两人是朋友关系，就在相应点之间联结一条边，从而可形成一个图，而每个人的朋友数就转化为相应顶点的度数。

从而可以利用图论中关于顶点度数的有关概念和性质进行解决。

§1.2 子图给定任意一个含有n 个点的图G ，我们总可以把它补成一个具有同样点的完全图，方法是把那些没有联上的边添加上去。

定义给定一个图G ，由G 中所有点和所有能使G 成为完全图的添加边组成的图，称为图G 相对于完全图的补图（Complement ），或简称为G 的补图，记作G 。

如图1-14中(a )和(b )互为补图。

图1-14下面为了给出子图的概念，首先介绍图的两种操作。

删边：删去图G 的某一条边，但仍保留边的端点。

删点：删去图G 的某一点以及与该点所关联的所有的边。

例如，图1-16(a )删去边1e 和2e 后所得的图为图1-16(c )。

图1-16(a )删去点4v 后所得的图为图1-16(d )。

定义:设,G V E =和,G V E '''=是两个图。

（1）若E E ⊆'，V V ⊆'，则称'G 是G 的子图（Subgraph ）。

（2）若'G 是G 的子图，且E E ⊂'或V V ⊂'，则称'G 是G 的真子图。

（3）若E E ⊆'且V V ='，则称'G 是G 的生成子图或支撑子图（Spanning Subgraph ）。

（4）若'G 是G 的子图，且'G 中没有孤立点，则称'G 为图G 的由边集'E 导出的子图（Derived Subgraph ）。

（5）设V V ⊆'，在图G 中删去'V 中所有点后所得的图称为图G 的由点集'V V -导出的子图。

例如，图1-16 (b )、(c )、(d )都是图1-16(a )的子图，也是真子图。

图1-16 (b )、(c )是图1-16(a )的生成子图。

图1-16(b )和图1-16(c )互为补图。