离散数学 贾振华 第七章 图

《离散数学 贾振华 第七章 图》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第7章图本章学习目标在前面章节中介绍过二元关系的图形表示，即关系图。在关系图中，我们主要关心研究对象之间是否有连线（图论中称为边），这样的图正是图论的主要研究对象。图论中还根据实际需要，将此类图进行了推广，并且把它当作一个抽象的数学系统来进行研究。通过本章学习，读者应该掌握以下内容：本章学习目标（1）无向图、有向图的定义，图的基本术语（2）子图、生成子图的概念（3）补图、图的同构的概念（4）通路、简单通路、初级通路的概念及相关定理（5）回路、简单回路、初级回路的概念及相关定理（6）无向连通图及有向连通图的有关概念（7）图的矩阵表示（8）带权图及其应用：最短路径问题和关

2、键路径问题主要内容7.1图的基本概念7.2通路与回路7.3图的连通性7.4图的矩阵表示7.5图的应用7.1图的基本概念7.1.1图论的发展(a)(b)哥尼斯堡七桥问题7.1图的基本概念7.1.2图的基本概念(a)(b)定义7.1.1无向图G是由一个顶点（结点）集合V（≠φ）和边E（弧）集合构成，并且每条边e∈Ｅ连接一个无序的顶点对。如果存在唯一的一条边ｅ连接顶点ｕ和ｖ，那么就记作ｅ=（ｕ，ｖ）或ｅ=（ｖ，ｕ）。有向图Ｄ是由一个顶点（结点）集合Ｖ（≠φ）和边（弧）集合Ｅ构成，并且每条边连接一个有序的顶点对。如果存在唯一的一条边ｅ连接顶点的有序对ｕ和ｖ,那么就记作ｅ=＜ｕ

3、，ｖ＞，表示一条从顶点ｕ到顶点ｖ的边。如果图Ｇ（无向图或有向图）由顶点集合Ｖ和边集合Ｅ组成，就记作Ｇ＝＜Ｖ，Ｅ＞。在定义中，常用表示Ｇ无向图，Ｄ表示有向图。7.1图的基本概念7.1.2图的基本概念例7.1.1画出下面二图的图形（1）无向图　　　　　　　　，其中7.1图的基本概念7.1.2图的基本概念例7.1.1画出下面二图的图形（２）有向图　　　　　　　　，其中7.1图的基本概念7.1.2图的基本概念例7.1.1画出下面二图的图形解：(1)的图形为7.1-3（a）所示，（2）的图形为7.1-3（b）所示。7.1图的基本概念7.1.2图的基本概念定义7.1.2设无向图（

4、1）如果在顶点ｕ和顶点ｖ之间存在一条边，即若存ｅ∈Ｅ在且ｅ=(u,v)，则称顶点u和顶点v是彼此相邻的，简称相邻的，并称顶点u和顶点v是边e的端点，e与u（或e与v）是彼此关联的。（2）若ek,el至少有一个公共端点，则称边ek,el是彼此相邻的，简称相邻的。7.1图的基本概念7.1.2图的基本概念定义7.1.3含有平行边的图，称为多重图。定义7.1.4一个没有环又没有平行边的图，称为简单图。定义7.1.5设无向图G=，对于任意的v∈V，将所有与v关联的边的条数，称为v的度数，简称度，记作dG(v)，简记为d(v)。设有向图D，对于任意的v∈V，将

5、v作为D中边的始点的边的条数，称为v的出度，记作，简记为；将v作为D中边的终点的边的条数，称为v的入度，记作，简记为；称+为v的度数，记作，简记为。7.1图的基本概念7.1.2图的基本概念设G为无向图，记=，，分别称为无向图的最大度和最小度。例如在图7.1-5中，=4，=3。7.1图的基本概念7.1.2图的基本概念设D为一个有向图，类似可定义D中的最大度和最小度。另外，令分别称、、、为D的最大出度、最小出度、最大入度、最小入度。7.1图的基本概念7.1.2图的基本概念定理7.1.1设是有m条边的图，则。证明因为G中每一条边（包括环）均有两个端点，而一条边恰好关联2个（

6、可能相同）顶点。因此，在一个图中，顶点度数的总和等于边数的两倍。7.1图的基本概念7.1.2图的基本概念推论在任何图（无向图或有向图）中，度为奇数的顶点的个数为偶数。证明设V1和V2分别是中奇数度数和偶数度数的顶点集，则由定理7.1.1有(m为的边数)由于和2m均为偶数，所以必为偶数，即

7、V1

8、为偶数。7.1图的基本概念7.1.2图的基本概念定理7.1.2任何有向图中，所有顶点的入度之和等于所有顶点的出度之和。证明：设有向图D有m条边，因为每一条有向边为始点提供1个出度，为终点提供1个入度，而所有各顶点的入度之和及出度之和均由m条有向边提供，所以定理得证。7.1图的基

9、本概念7.1.2图的基本概念定义7.1.6设为图G的顶点集，称（，，…,）为G的度数序列。对于顶点标定的无向图，它的度数序列是唯一的。反之，对于给定的非负整数列d=（d1，d2，…，dn），若存在以为顶点集的n阶无向图G，使得d(vi)=di，则称d是可图化的。7.1图的基本概念7.1.2图的基本概念定理7.1.3设非负整数列d=（d1，d2，…，dn），当且仅当为偶数时，d是可图化的。例7.1.2（5，4，3，5）和（3，2，1，1，4）可图化吗？解由于这两个序列中，均为奇数，由定理7.1.3可知，它们都不可图化。7.1图的基本概念7.1.2图的基