七图论.ppt

第四篇 图论 图论不断发展，它在解决运筹学，网络理论，信息论，控制论，博奕论以及计算机科学等各个领域的问题时，显示出越来越大的效果。 对于这样一门应用广泛的学科，其包含的内容是丰富的，本篇我们只准备介绍基本的概念和定理，为今后有关学科及课程的学习和研究提供方便。 第七章 图论 §7.1 图的基本概念 §7.2 路与回路 §7.3 图的矩阵表示 §7.4 欧拉图和汉密尔顿图 §7.5 平面图 §7.6 树与生成树 第七章 图论 教学目的及要求： 深刻理解和掌握图的有关概念和表示。 教学内容： 图的基本概念、路与回路、图的矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树、根树及其应用。 教学重点： 图、路、图的矩阵表示、平面图、对偶图与着色、树与生成树。 教学难点：树与生成树。 §7.1 图的基本概念 1.基本名词和定义 [定义7-1.1] 一个图G是一个三元组V(G),E(G), , 其中V(G)为有限非空结点（或叫顶点）集合, E(G)是边的集合， 是从边集E到结点无序偶（有序偶）集合上的函数。 讨论定义： (1). V(G) ={V1，V2，…，Vn}为有限非空集合, Vi称为结点,简称V是点集。 (2). E(G)={e1，…，em}为有限的边集合,ei称为边， 每个ei都有V中的结点对与之相对应,称E为边集。 即每条边是连结V中的某两个点的。 §7.1 图的基本概念 (3).若Ｇ中每一条边e与有序偶对vi,vj或无序偶对 (vi,vj)相关系，则可说边e连接结点vi和vj (4).可用e＝ vi,vj或e＝ (vi,vj)，以结点来表示图的边，这样可把图简化成：Ｇ＝Ｖ，Ｅ。 例：有图如下，试写成定义表达式 Ｇ＝〈Ｖ，Ｅ〉， 其中Ｖ＝{v1,v2,v3,v4,v5} Ｅ＝{x1,x2,x3,x4,x5,x6} §7.1 图的基本概念 例：对有向图可表示为： Ｇ＝〈Ｖ、Ｅ〉，其中： Ｖ＝｛a、b、c、d｝ Ｅ＝{a,b,b,a,b,d,d,a,d,d,c,c} §7.1 图的基本概念 §7.1 图的基本概念 §7.1 图的基本概念 §7.1 图的基本概念 §7.1 图的基本概念 §7.1 图的基本概念 [定义7-1.2] 在图G=V，E中，与结点v（v∈V）关联的边数，称作是该结点的度数，记作deg(v)。 讨论定义： （1）每个环在其对应结点上度数增加2； （2）最大度记作：△（G）=max{deg(v)|v ∈V(G)} （3）最小度记作：（G）=min{deg(v)|v ∈V(G)} §7.1 图的基本概念 [定理7-1.1] 每个图中，结点度数的总和等于边数的两倍。 §7.1 图的基本概念 例：若图Ｇ有n个顶点，（n+1）条边，则Ｇ中至少有一个结点的度数≥３。 §7.1 图的基本概念 [定理7-1.2] 在任何图中，所有度数之和必为偶数，度数为奇数的结点必定是偶数个。 §7.1 图的基本概念 [定义7-1.3] 在有向图中，射入一个结点的边数称为该结点的入度，由一个结点射出的边数称为该结点的出度。结点的出度和入度之和就是该结点的度数。 [定理7-1.3] 在任何有向图中，所有结点的入度之和等于所有结点的出度之和。 §7.1 图的基本概念 §7.1 图的基本概念 [定义7-1.4]含有平行边的图称为多重图，非多重图称为线图。 （13）简单图：无自回路的线图称为简单图。由定义可见，简单图是没有自回路和多重边的图。 §7.1 图的基本概念 有n个结点的无向完全图记作Kn。 §7.1 图的基本概念 §7.1 图的基本概念 §7.1 图的基本概念 （15）有权图（赋权图）Ｇ是一个三元 组〈Ｖ、Ｅ、ｇ〉或四元组〈Ｖ、Ｅ、ｆ、ｇ〉，其中Ｖ为结点集合，Ｅ为边的集合，f是定义在Ｖ上的函数，g是定义在边集合Ｅ上的函数。 实际上，有权图可以用一句话概括：每一条边或结点均注上数字的图（数字可以为整数、正实数） 例：给出一个有权图 Ｇ＝〈Ｖ、Ｅ、ｆ、ｇ〉，其图如下： 其中Ｖ＝ {v1,v2,v3} Ｅ＝{e1,e2} §7.1 图的基本概念 ２．子图和图的同构： [定义7-1.7] 设Ｇ＝Ｖ,Ｅ,Ｇ’＝Ｖ’,Ｅ’是二个图 若Ｖ’?Ｖ,Ｅ’?Ｅ,则称Ｇ’是Ｇ的子图，记作Ｇ’ ?Ｇ； 若Ｇ’ ?Ｇ，且Ｇ’ ≠Ｇ（即Ｖ’?Ｖ或Ｅ’?Ｅ），则称Ｇ’是Ｇ的真子图； 若Ｖ’＝Ｖ,Ｅ’?Ｅ,则称Ｇ’是Ｇ的生成子图(支撑子图)。 §7.1 图的基本概念 ２．子图和图的同构： 例：Ｇ图如下：Ｇ的真子图： 生成子图：