资源描述
第七章 图论 7.1 图的基本概念图的基本概念 7.2 路与回路路与回路 7.3 图的矩阵表示图的矩阵表示 7.4 欧拉图与汉密尔顿图欧拉图与汉密尔顿图 7.5 树与生成树树与生成树 7.6 根树及其应用根树及其应用 习习 题题 七七7.1 图的基本概念 7.1.1 图的基本概念图的基本概念 7.1.2 图的结点的度数及其计算图的结点的度数及其计算 7.1.3 子图和图的同构子图和图的同构7.1.1 图的基本概念 现现实实世世界界中中许许多多现现象象能能用用某某种种图图形形表表示示,这这种种图图形形是是由由一一些些点点和和一一些些连连接接两两点点间的连线所组成。间的连线所组成。【例例7.1.1】a，b，c，d 4个个篮篮球球队队进进行行友友谊谊比比赛赛。为为了了表表示示个个队队之之间间比比赛赛的的情情况况，我我们们作作出出图图 7.1.1的的图图形形。在在图图中中个个小小圆圆圈圈分分别别表表示示这这个个篮篮球球队队，称称之之为为结结点点。如如果果两两队队进进行行过过比比赛赛，则则在在表表示示该该队队的的两两个个结结点点之之间间用用一一条条线线连连接接起起来来，称称之之为为边边。这这样样利利用用一一个个图图形使各队之间的比赛情况一目了然。形使各队之间的比赛情况一目了然。1.图的定义图的定义 图图 7.1.1 如如果果图图 7.1.1中中的的个个结结点点a，b，c，d分分别别表表示示个个人人，当当某某两两个个人人互互相相认认识识时时，则则将将其其对对应应点点之之间间用用边边连连接接起起来来。这这时时的的图图又又反反映映了了这这个个人人之之间的认识关系。间的认识关系。我我们们也也可可以以点点代代表表工工厂厂,以以连连接接两两点点的的连连线线表表示示这这两两工工厂厂间间有有业业务务往往来来关关系系。这这样样便便可可用用图图形形表表示示某某一一城城市市中中各各工工厂厂间间的的业业务务往往来来关关系系。这这种种用用图图形形来来表表示示事事物物之之间间的的某某种种关关系系的的方方法法我我们们也也曾曾经经在在第第 三三 章章中中使使用用过过。对对于于这这种种图图形形,我我们们的的兴兴趣趣在在于于有有多多少少个个点点和和哪哪些些点点对对间间有有线线连连接接,至至于于连连线线的的长长短短曲曲直直和和点点的的位位置置都都无无关关紧紧要要。对对它它们们进进行行数数学学抽抽象象我我们就得到以下作为数学概念的图的定义。们就得到以下作为数学概念的图的定义。定定义义7.1.1一一个个图图G是是一一个个序序偶偶V(G),E(G)，记记为为GV(G),E(G)。其其中中V(G)是是非非空空结结点点集集合合，E(G)是是边边集集合合，对对E(G)中中的的每每条条边边，有有V(G)中中的的结结点点的的有有序序偶偶或无序偶与之对应。或无序偶与之对应。若若 边边 e所所 对对 应应 的的 结结 点点 对对 是是 有有 序序 偶偶a,b,则则称称e是是有有向向边边。a叫叫边边e的的始始点点,b叫叫边边e的的终终点点,统统称称为为e的的端端点点。若若边边e所所对对应应的的结结点点对对是是无无序序偶偶(a,b),则则称称e是是无无向向边边。这这时时统统称称e与与两两个个结结点点a和和b互互相相关关联联。我我们们将将结结点点a、b的的无无序序结结点点对对记记为为(a，b），有有序序结结点点对对记记为为a，b。一个图一个图G可用一个图形来表示且表示是可用一个图形来表示且表示是不唯一的。不唯一的。【例例7.1.2】设设G=V(G),E(G),其中其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1=(a,b),e2=(a,c),e3=(b,d),e4=(b,c),e5=(d,c),e6=(a,d),e7=(b,b)。则图则图G可用图可用图7.1.2(a)或或(b)表示。表示。图图 7.1.2 图 7.1.2 2.图图G的结点与边之间的关系的结点与边之间的关系邻接点邻接点:同一条边的两个端点。同一条边的两个端点。孤立点孤立点:没有边与之关联的结点。没有边与之关联的结点。邻接边邻接边:关联同一个结点的两条边。关联同一个结点的两条边。孤立边孤立边:不与任何边相邻接的边。不与任何边相邻接的边。自自回回路路（环环）：关关联联同同一一个个结结点点的的一一条条边（边（v，v）或）或v，v）。）。平平行行边边(多多重重边边):关联同一对结点的多条边。如如例例7.1.1中中的的图图，结结点点集集Va，b，c，d，边集边集 Ee1，e2，e3，e4，e5，其中其中 e1（a，b），），e2（a，c），），e3（a，d），e4（b，c），e5（c，d）。d与与a、d与与c是是邻邻接接的的，但但d与与b不邻接，不邻接，边边e3与与e5是邻接的。是邻接的。【例例7.1.3】设设图图GV,E 如如图图7.1.3所示。所示。这里这里Vv1，v2，v3，Ee1，e2，e3，e4，e5，其中其中e1（v1，v2），），e2（v1，v3），e3（v3，v3），），e4（v2，v3），e5（v2，v3）。）。在在这这个个图图中中，e3是是关关联联同同一一个个结结点点的的一一条条边边,即即自自回回路路；边边e4和和e5都都与与结结点点v2、v3关联，关联，即它们是多重边。即它们是多重边。图图 7.1.3 3.图图G的分类的分类(1)按按G的的结结点点个个数数和和边边数数分分为为(n,m)图图,即即n个个结结点点,m条边的图条边的图;特特别别地地,(n,0)称称为为零零图图,(1,0)图图称称为为平凡图平凡图。(2)按按G中中关关联联于于同同一一对对结结点点的的边边数数分分为为多多重重图和简单图图和简单图;多多重重图图:含含有有平平行行边边的的图图（如如图图 7.1.3）。简单图简单图:不含平行边和自环的图。不含平行边和自环的图。(3)按按G的的边边有有序序、无无序序分分为为有有向向图图、无无向向图图和混合图和混合图;有有向向图图：每每条条边边都都是是有有向向边边的的图图称称为为有有向向图（图图（图 7.1.4(b)；无无向向图图：每每条条边边都都是是无无向向边边的的图图称称为为无无向向图；图；混混合合图图：既既有有无无向向边边，又又有有有有向向边边的的图图称为混合图。称为混合图。本书主要研究无向图和有向图。本书主要研究无向图和有向图。(a)(b)(4)按按G的的边边旁旁有有无无数数量量特特征征分分为为边边权权图图(如如图图 7.1.4(a)、无权图、无权图;(5)按按G的任意两个结点间是否有边分为的任意两个结点间是否有边分为完全图完全图Kn(如图如图 7.1.5)和和不完全图不完全图(如图如图 7.1.6)。图图 7.1.4 图图 7.1.6完完全全图图：任任意意两两个个不不同同的的结结点点都都是是邻邻接接的的简简单单图图称称为为完完全全图图。n 个结点的无向完全图记为个结点的无向完全图记为Kn。图图7.1.5给给出出了了K3和和K4。从从图图中中可可以以看看出出K3有有条条边边，K4有条边。有条边。容易证明容易证明Kn有有 条边。条边。图图 7.1.5 K3与与K4示意图示意图 给给定定任任意意一一个个含含有有n个个结结点点的的图图G,总总可可以以把把它它补补成成一一个个具具有有同同样样结结点点的的完完全全图图,方方法法是是把把那那些缺少的边添上。些缺少的边添上。定定义义7.1.2 设设GV,E是是一一个个具具有有n个个结结点点的的简简单单图图。以以V为为结结点点集集，以以从从完完全全图图Kn中中删删去去G的的所所有有边边后后得得到到的的图图（或或由由G中中所所有有结结点点和和所所有有能能使使G成成为为完完全全图图的的添添加加边边组组成成的的图图）称为称为G的补图，的补图，记为记为 。例如，零图和完全图互为补图。例如，零图和完全图互为补图。图图 7.1.6给出了一个图给出了一个图G和和G的补图的补图 。【例例7.1.4】（拉拉姆姆齐齐问问题题）试试证证在在任任何何一一个个有有个个人人的的组组里里，存存在在个个人人互互相认识，相认识，或者存在个人互相不认识。或者存在个人互相不认识。我我们们用用个个结结点点来来代代表表人人，并并用用邻邻接接性性来来代代表表认认识识关关系系。这这样样一一来来，该该例例就就是是要要证证明明：任任意意一一个个有有个个结结点点的的图图G中中，或或者者有有个个互互相相邻邻接接的的点点，或或者者有有个个互互相相不不邻邻接接的的点点。即即，对对任任何何一一个个有有个个结结点点的的图图G，G或或 中中含含有一个三角形（即有一个三角形（即K3）。）。证证明明:设设GV,E，|V|6，v是是G中中一一结结点点。因因为为v 与与G的的其其余余个个结结点点或或者者在在 中中邻邻接接，或或者者在在G中中邻邻接接。故故不不失失一一般般性性可可假假定定，有有个个结结点点v1，v2，v3在在G中与中与v邻接。邻接。如如果果这这个个结结点点中中有有两两个个结结点点（如如v1，v2）邻邻接接，则则它它们们与与v3就就是是G中中一一个个三三角角形形的的个个顶顶点点。如如果果这这3个个结结点点中中任任意意两两个个在在G中中均均不不邻邻接接，则则v1，v2，v3就是就是 中一个三角形的个顶点。中一个三角形的个顶点。7.1.2 图的结点的度数及其计算图的结点的度数及其计算 我我们们常常常常需需要要关关心心图图中中有有多多少少条条边边与与某某一一结结点点关关联联，这这就就引引出出了了图图的的一一个重要概念个重要概念结点的度数。结点的度数。定定义义7.1.3 图图中中结结点点v 所所关关联联的的边边数数（有有自自回回路路时时计计算算两两次次）称称为为结结点点v 的度数，的度数，记为记为deg（v）。）。如如图图7.1.3中中的的deg（v1）2，deg（v2）3，deg（v3）5。定定理理 7.1.1 图图GV,E中中结结点点度度数数的的总总和和等等于于边边数数的的两两倍倍，即即 证证明明:因因为为每每条条边边都都与与两两个个结结点点关关联联，所所以以加加上上一一条条边边就就使使得得各各结结点点度度数数的的和和增增加加 2，由由此此结结论成立。论成立。推论推论:图图G中度数为奇数的结点必为偶数个。中度数为奇数的结点必为偶数个。证证明明:设设V1和和V2分分别别是是G中中奇数度数和偶数度数的结点集。奇数度数和偶数度数的结点集。由定理由定理7.1.1知知 由于由于 是偶数之和，是偶数之和，必为偶数，必为偶数，而而2|E|也也为为偶偶数数，故故 是是偶偶数数。由由此此|V1|必为偶数。必为偶数。定定义义7.1.4 在在有有向向图图中中,射射入入结结点点v的的边边 数数 称称 为为 结结 点点 v 的的 入入 度度，记记 为为 ;由由结结点点v射射出出的的边边数数称称为为结结点点v 的的出出度度，记记为为 。结结点点v的的入入度度与与出出度之和就是结点度之和就是结点v的度数。的度数。如如图图7.1.4中中 1，2。图图7.1.4 定定理理 7.1.2 在在任任何何有有向向图图GV,E中，中，有有 7.1.3 子图和图的同构子图和图的同构 1.子图子图 在在研研究究和和描描述述图图的的性性质质时时，子子图图的的概概念占有重要地位。念占有重要地位。定义定义7.1.5 设有图设有图GV,E和图和图 G V,E 。1)若若VV，EE，则则称称G是是G的子图。的子图。2)若若G是是G的的子子图图，且且EE，则则称称G是是G的真子图。的真子图。3)若若VV，EE，则则称称G是是G的的生成子图。生成子图。图图 7.1.7给给出出了了图图G以以及及它它的的真真子子图图G1和生成子图和生成子图G2。图图 7.1.7 图图G以及其真子图以及其真子图G 1和生成子图和生成子图G2 2.图的同构图的同构 从从图图的的定定义义可可以以看看出出，图图的的最最本本质质的的内内容容是是结结点点与与结结点点的的邻邻接接关关系系。例例如如例例7.1.1也也可可以以用用图图7.1.8中中几几种种不不同同形形状状的的图图形形表表示示。它它们们与与图图7.1.1一一样样，都都同同样样表表示示例例7.1.1中中个个队队之之间间的的比比赛赛情情况况。从从这这个个意意义义上上讲讲，我我们们说说它它们们是是同同一一个个图图，并并称称图图7.1.1与与图图7.1.8的的(a)和和(b)是同构的。是同构的。图图 7.1.8 同构的图同构的图 图图 7.1.9 图图 7.1.1 定义定义7.1.6 设有图设有图 GV,E和图和图 G V,E。如果存在双射如果存在双射：VV，使得使得 e（u，v）E iff e（(u)，(v)）E，且（且（u，v）与（）与（(u)，(v)）有相同的重数，）有相同的重数，则称则称G与与G同构。同构。记记作作G G。【例例7.1.5】考考察察图图7.1.9中中的的两两个个图图GV,E和和 G V,E。显显然然，定定义义：VV，（vi）v i，可可以以验验证证是是满满足足定定义义7.1.6的双射，的双射，所以所以G G。对对于于同同构构，形形象象地地说说，若若图图的的结结点点可可以以任任意意挪挪动动位位置置，而而边边是是完完全全弹弹性性的的，只只要要在在不不拉拉断断的的条条件件下下，这这个个图图可可以以变变形形为为另另一一个个图图，那那么么这这两两个个图图是是同同构构的的。故故同同构构的的两两个个图图从从外外形形上上看看可可能不一样，能不一样，但它们的拓扑结构是一样的。但它们的拓扑结构是一样的。小小结结:本本结结介介绍绍了了图图的的基基本本概概念念、图图的的结结点点的的度度数数及及其其性性质质以以及及子子图图、生生成成子子图图与与图图的同构等概念。的同构等概念。重重点点：图图的的结结点点的的度度数数及及其其性性质质以以及及生生成成子图的概念。子图的概念。作业：作业：P279（1），（），（2）
展开阅读全文