第七章图论.doc

第7章 图论图论是建立和处理离散型数学模型的重要数学工具，它已发展成具有广泛应用的一个数学分支。图论的发展已有200多年的历史，它最早起源于一些数学游戏的难题研究。1736年瑞士数学家欧拉（L.Eluer）发表了关于解决哥尼斯堡七桥问题的一篇文章，标志着图论的正式诞生。从19世纪中叶到20世纪中叶，图论问题大量出现，如汉密尔顿图问题、四色猜想等。这些问题的出现进一步促进了图论的发展。1847年，克希霍夫（Kirchhoff）用图论分析电网络，这是图论最早应用于工程科学的一个例子。随着计算机科学的迅猛发展，在现实生活中的许多问题，如交通网络问题，运输的优化问题，社会学中某类关系的研究，都可以用图论进行研究和处理。图论在计算机领域中，诸如算法、语言、数据库、网络理论、数据结构、操作系统、人工智能等方面都有重大贡献。本章主要介绍图论的基本概念、基本性质和一些典型应用。7.1 图的基本概念7.1.1图的基本概念1.图的定义图在现实生活中随处可见，如交通运输图、旅游图、流程图等。此处我们只考虑由点和线所组成的图。这种图能够描述现实世界的很多事情。例如，用点表示球队，两队之间的连线代表二者之间进行比赛，这样，各支球队的比赛情况就可以用一个图清楚地表示出来。 到底什么是图呢？可用一句话概括：图是用点和线来刻划离散事物集合中的每对事物间以某种方式相联系的数学模型。因为上述描述太过于抽象，难于理解，因此下面给出图作为代数结构的一个定义。定义7.1.1 一个图（Graph）是一个三元组，其中是一个非空的节点集合，是有限的边集合，是从边集合到点集合中的有序偶或无序偶的映射。例7.1.1 图=，其中=，=，。一个图可以用图形表示出来。例7.1.1的图可表示为图7-1()或()。由于在不引起混乱的情况下，图的边可以用有序偶或无序偶直接表示。因此，图也可以简单的表示为：其中，是非空节点集， 是连接节点的边集。图7-1 若边与节点无序偶相关联，则称该边为无向边（Undirected Edge）。若边与节点有序偶相关联，则称该边为有向边（Directed Edge），其中称为的起点（Initial Vertex），称为的终点（Terminal Vertex）。定义7.1.2 每一条边都是无向边的图称为无向图（Undirected Graph），例如图7-2()。每一条边都是有向边的图称为有向图（Directed Graph），例如图7-2()。如果在图中，一些边是有向边，一些边是无向边，则称之为混合图（Mixed Graph）。例如图7-2()。图7-2 这些图可分别表示为：G=，其中，其中，其中，今后我们只讨论有向图和无向图。2. 图G的节点与边之间的关系及图的分类定义7.1.3 在一个图中，若两个节点由一条有向边或一条无向边关联，则这两个节点称为邻接点(Adjacent Vertice)。在一个图中，不与任何节点相邻接的节点，称为孤立节点（Isolated Vertex）。如图7-2()中的节点。仅由孤立节点组成的图称为零图（Null Graph），仅由一个孤立节点构成的图称为平凡图。由定义知，平凡图一定是零图。关联于同一节点的两条边称为邻接边（Adjacent Edges）。关联于同一节点的一条边称为自回路或环（Loop）。环的方向是没有意义的，它既可作为有向边，也可作为无向边。如图7-3中的与，与是邻接边，是环。图7-3在一个图形中，有时一对节点间常常不止一条边，在图7-3中，节点与节点之间有两条边与。把连接于同一对节点间的多条边称为平行边（Multiple Edges）。定义7.1.4 含有平行边的任何一个图，称为多重图（Multigraph）。不含有平行边和环的图称为简单图（Simple Graph）。图7-4 多重图示例例如，在图7-4中节点和之间有两条平行边，节点和之间有三条平行边，节点上有两条平行边，这两条平行边都是环。图7-4不是简单图，而是多重图。又如，在图7-4()中节点v和v之间有两条平行边。v和v之间的两条边，因为方向不同，所以不是平行边。图7-4()不是简单图，而是多重图。定义7.1.5 任意两个节点间都有边相连的简单图称为完全图（Complete Graph）。个节点的无向完全图记为。定理7.1.1 个节点的无向完全图的边数为。证明 因为在无向完全图中，任意两个节点之间都有边相连，所以个节点中任取两个点的组合数为，故无向完全图的边数为。如果在中，对每条边任意确定一个方向，就称该图为个节点的有向完全图。显然，有向完全图的边数也是。例7.1.2 图7-5分别给出了1个节点、2个节点、3个节点、4个节点和5个节点的无向完全图。图7-5 的图示例7.1.3 图7-6()是简单图，并且是完全图。图7-6()是多重图，因为节点与之间有平行边，因而不是完全图。图7-6定义7.1.6 给每条边都赋予权的图称为带权图或加权图（Weighted Graph），记为，其中为各边权的集合。带权图在实际生活中有着广泛的应用，例如在城市交通运输图中，可以赋予每条边以公里数、耗油量、运货量等，与此类似，在表示输油管系统的图中，每条边所指定的权表示单位时间内流经输油管断面的石油数量。如图7-7是带权图。图7-7 带权图示例需要注意，带权图中各边的权数可以是正数、负数或零。7.1.2 补图与子图给定任意一个含有个节点的图，我们总可以把它补成一个具有同样节点的完全图，方法是把那些没有联上的边添加上去。定义7.1.7 给定一个图，由中所有节点和所有能使成为完全图的添加边组成的图，称为图相对于完全图的补图（Complement），或简称为的补图，记作。如图7-8中()和()互为补图。图7-8 例7.1.4 证明：在任意6个人的集会上，总会有3个人相互认识或者有3个人互相不认识（假设认识是相互的）。证明 这是发表在1958年美国数学月刊上的一个数学问题。把参加某会议的人视为节点，若两人认识，则两人之间画一连线，这样得到一图。设是的补图，这样问题就转化为证明或中至少有一个三角形。考虑完全图，顶点与其余的5个节点有5条边相连，这5条边一定有其中的3条边落在或中。不妨设这3条边落在中，且这3条边就是，（如图7-9所示）。考虑节点，若在中无线相连，则互相不认识，命题得证；若在中至少有一条线相连，例如，则就相互认识。因此，总会有3个人相互认识或者有3个人相互不认识。图7-9下面为了给出子图的概念，首先介绍图的两种操作。删边：删去图的某一条边，但仍保留边的端点。删点：删去图的某一节点以及与该节点所关联的所有的边。例如，图7-10()删去边和后所得的图为图7-10()。图7-10()删去节点后所得的图为图7-10()。定义7.1.8 设和是两个图。（1）若，则称是的子图（Subgraph），是的母图。（2）若是的子图，且或，则称是的真子图。（3）若且，则称是的生成子图或支撑子图（Spanning Subgraph）。（4）若是的子图，且中没有孤立节点，则称为图的由边集导出的子图（Derived Subgraph）。（5）设，在图中删去中所有节点后所得的图称为图的由节点集导出的子图。例如，图7-10 ()、()、()都是图7-10()的子图，也是真子图。图7-10 ()、()是图7-10()的生成子图。图7-10()和图7-10()互为补图。图7-10()是图7-10()的由边集导出的子图，图7-10()是图7-10()的由边集导出的子图。图7-10()是图7-10()的由节点集导出的子图。图7-10 子图实际上就是从原来的图中适当地去掉一些节点和边所形成的新图，它的节点和边必须含在原来的图中，以反映图的局部。定义7.1.9 设是图的子图，并且给定另外一个图，如果，且由两部分节点组成：（1）中的边所关联的节点，（2）在中而不在中的孤立节点。则称是子图相对于图的补图。例如，在图7-11中，图7-11()是图7-11()关于图7-11()的补图。图7-11 7.1.3 节点的度数研究图的性质就必须研究节点与边的关联关系。为此，我们引入节点的度的概念。定义7.1.10 在有向图中，射入节点的边数，称为节点的入度(In-degree)，记作；由节点射出的边数，称为节点的出度(Out-degree)，记作。节点的入度与出度之和称为节点的度数（degree），记作或。在无向图中，以节点为端点的边的条数称为节点的度数，记作或。若有环，规定该节点的度数因环而增加2。此外，我们记，分别称为图的最大度和最小度。例如在图7-4()中，=3，=9，。在图7-4()中，=3，。孤立节点的度数为0。下面的定理是欧拉在1936年给出的，称为握手定理，它是图论中的基本定理。定理7.1.2 每个图中，节点度数的总和等于边数的两倍。=证明 因为每条边必关联两个节点，而一条边给予关联的每个节点的度数为1。因此，在一个图中，节点度数的总和等于边数的两倍。对于有向图，我们还可以说得更精确一点，即若是有向图，则定理7.1.3 在任何图中，度数为奇数的节点必定是偶数个。证明 设和分别是图中奇数度节点和偶数度节点的集合，则由定理7.1.2有，+=由于是偶数之和，必为偶数，而是偶数，所以是偶数，而为奇数度节点的集合，故，为奇数，但奇数个奇数之和只能为奇数，故是偶数。例7.1.5 （1）已知图中有11 条边，1 个4 度节点，4 个3 度节点，其余节点的度数均不大于2，问中至少有几个节点？（2）数列1,3,3,4,5,6,6 能否是一个无向简单图的度数列?解 （1）由握手定理，中的各节点度数之和为22，1 个4 度节点，4 个3 度节点共占去16 度，还剩6 度；若其余节点全是2 度点，还需要3 个节点，所以至少有1+4+3=8 个节点。（2）如果存在这样一个无向简单图，那将它的一个6 度节点去掉，得到的简单无向图的度数列为0，2，2，3，4，5； 再将这一图的5 度节点去掉得到的简单图具有度数列0，1，1，2，3。但这一图有3 个奇数度节点，这与定理7.1.3相矛盾。例7.1.6 在一场足球比赛中，传递过奇数个球的队员人数必定为偶数个。解 把参加球赛的队员抽象为节点，两个互相传球的队员用边相连，这样得到的图就是球赛中传递球的简单的数学模型，由定理7.1.3即知结论正确。7.1.4 图的同构在图论中我们只关心节点间是否有连线，而不关心节点的位置和连线的形状。因此，对于给定的图而言，如果将图的各节点安排在不同的位置上，并且用不同形状的弧线或直线表示各边，则可以得到各种不同图形。所以，同一个图的图形表示并不唯一。由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。例如，在图7-12中，和()两个图的图形不同，但它们的结构完全相同，是同一个图。图7-12为了描述看起来不同，而其结构完全相同的图，引入了图的同构的概念。定义7.1.11 设和是两个图，如果存在着双射使得（或）当且仅当（或），则称与是同构的，记作。通过定义可以看出，对于同构的图与来说，存在着一一对应，将中的节点对应到中的节点，将中的边对应到中的边，且保持着关联关系，即边关联着节点和，当且仅当对应到中的边也关联着，对应到中的节点。在有向图的情况下，这种对应关系不但应该保持节点间的邻接关系，而且还应保持边的方向。例7.1.7 如图7-13所示，映射，在无向简单图和之间建立了一个同构。图7-13 同构图示例与群、格、布尔代数一样，图的同构也具有自反性、对称性和传递性。因此，图的同构关系是等价关系。利用这个等价关系可以把图分解成等价类，使得同类中的图相互同构，而不同类中的图互不同构。从抽象的观点来看，相互同构的图可视为同一个图，这样，我们就可以在图的同构类中选一个图来代表它们。由于图本质上与节点和边的标记无关，因此，选出的这个图常常略去节点和边的标记，这个图就称为无标记图。如图7-14所示的()、()、()、()四个图形均相互同构，它们属于同一个同构的等价类。而图7-14()就是该类的一个无标记图。图7-14例7.1.8 设是简单无向图，且，试画出的所有可能形式（不同构的图）。解 由握手定理可知，所画的简单无向图各节点度数之和为23=6。最大度数小于或等于3。于是所求的简单无向图的度数列应满足的条件是：将6分成5个非负整数，每个整数均大于或等于0且小于或等于3，并且奇数个数为偶数。将这样的整数列排列出来，只有下列四种情况：3，1，1，1，02，2，2，0，02，1，1，1，12，2，1，1，0将每种度数列所有非同构的图都画出来即得到所要求的全部非同构的图，如图7-15所示。图7-15 （5,3）图的全部非同构图由图同构的定义，可以得到两图和同构的几个必要条件：（1）节点数目相等；（2）边数相等；（3）度数相同的节点数目相等。需要指出的是，上述的三个条件不是两个图同构的充分条件，例如图7-16中的两个图满足上述的三个条件，但这两个图并不同构。这是因为，图7-16中的应与图7-16中的对应，因为度数都是3 。但图7-16()中的与两个度数为1的节点和邻接，而图7-16()中的仅与一个度数为1 的节点邻接。图7-16同理，图7-17中的两个图也不同构。图7-17 寻找一种简单而有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。习题7.11设无向图， ，E=， ，。 (1)画出的图形；(2)求的各节点的度数，并验证握手定理；(3) 是否是简单图？2写出图7-18相对于完全图的补图。 图7-18 图7-193证明图7-19中两个图是同构的。4下面各图有几个节点？（1）16条边，每个节点度均为2。 （2）21条边，3个度为4的节点，其余都是度为3的节点。 5给定有向图如图7-20所示，求各节点的入度、出度和度。 6是否可画一无向简单图使各节点的度与下面所给的序列一致，如可能，画出一个符合条件的图；如不可能，请说明理由。 图7-20（1）（2，2，2，2，2，2） （2）（1，2，3，4，5，5） （3）（1，2，3，4，5，6） （4）（2，2，3，4，5，6）7证明在任何有向完全图中，所有节点的入度的平方和等于所有节点的出度的平方和。7.2 路与图的连通性在无向图（或有向图）的研究中，常常考虑从一个节点出发，沿着一些边连续移动而到达另一个指定节点，这种依次由节点和边组成的序列，便形成了路的概念。在图的研究中，路与回路是两个重要的概念，而图是否具有连通性则是图的一个基本特征。7.2.1 路与回路定义7.2.1 给定图，设，边，其中，是关联于节点，的边，交替序列称为连接到的路(Walk)。和分别称为路的起点(Initial Vertex)和终点(Terminal Vertex)，路中边的数目称为该路的长度。当=时，称其为回路(Circuit)。由于无向简单图中不存在重复边与自回路，每条边可以由节点对唯一表示，所以在无向简单图中一条路由它的节点序列，确定，所以简单图的路，可表示为。如图7-1表示的简单图中，路可写成。在有向图中，节点数大于1的一条路也可由边序列来表示。在上述的定义的路与回路中，节点和边不受限制，即节点和边都可以重复出现。下面我们讨论路与回路中节点和边受限的情况。定义7.2.2 在一条路中，若出现的所有的边互不相同，则称其为简单路或迹(Trail)；若出现的节点互不相同，则称其为基本路或通路(Path)。由定义可知，基本路一定是简单路，但反之不一定成立。定义7.2.3 在一条回路中，若出现的所有的边互不相同，则称其为简单回路(Simple Circuit)；若简单回路中除=外，其余节点均不相同，则称其为基本回路或初级回路或圈(Cycle)。长度为奇数的圈称为奇圈；长度为偶数的圈称为偶圈。例如在图7-21中，是起点为，终点为，长度为4的一条路。是简单路但不是基本路。既是通路又是简单路。是圈。图7-21利用路的概念可以解决很多问题，下面是一道智力游戏题。例7.2.1 “摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河。另外，不能让狼和羊、羊和菜单独留下。问怎样安排摆渡过程？ 解 河左岸允许出现的情况有以下10种情况：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一直线，得到图7-22图7-22这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路。容易看出，只有两条简单路符合要求，即：（1）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；（2）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空。对于简单路（1）的安排为：人带羊过河；人回来；带狼过河；放下狼再将羊带回；人再带菜过河；人回来；带羊过河。对于简单路（2）的安排为：人带羊过河；人回来；带菜过河；放下菜再将羊带回；人再带狼过河；人回来；带羊过河。上述的两种方案都是去4次、回3次，且不会再有比这更少次数的渡河办法了。定理7.2.1 在一个图中，若从节点到存在一条路，则必有一条从到的基本路。证明 如果从节点到的路已经是基本路，则结论成立。否则，在到的路中至少有一个节点（如）重复出现，于是经过有一条回路，删去回路上的所有的边，如果得到的到的路上仍有节点重复出现，则继续此法，直到到的路上没有重复的节点为止，此时所得即为基本路。定理7.2.2 在一个具有个节点的图中，则（1）任何基本路的长度均不大于。（2）任何基本回路的长度均不大于。证明 由于在一个具有个节点的图中，任何基本路中最多有个节点，任何基本回路中最多有个节点，所以任何基本路的长度均不大于，任何基本回路的长度均不大于。7.2.2 图的连通性下面讨论图的连通性及相关性质。定义7.2.4 在无向图中，节点和之间若存在一条路，则称节点和节点是连通的(Connected )。如果认为节点与其自身也是连通的，则中两节点之间的连通关系是一个等价关系，在此等价关系下， 节点集合可以形成一些等价类，不妨设等价类为，使得节点和是连通的，当且仅当它们属于同一个。我们把子图，称为图的连通分支(Connected Component )，我们把图的连通分支数记作。定义7.2.5 若图只有一个连通分支，则称图是连通图(Connected Graph)；否则，称图是非连通图或分离图(Disconnected Graph)。例7.2.2 如图7-23所示，图7-23()是一个连通图，图7-23()是一个具有3个连通分支的非连通图。图7-23 连通图和非连通图示例 每一个连通分支中任何两个节点是连通的，而位于不同连通分支中的任何两个节点是不连通的。即每一个连通分支都是原图的最大的连通子图。对于图的连通性，常常由于删除了图中的节点和边而影响了图的连通性。例如，在连通图7-24中，删除边，则由图变成了图()，而图()不再是连通图。图7-24定义7.2.6 若无向图为连通图，若有点集，使图删除了的所有节点后，所得到的子图是非连通图，而删除了的任何真子集后所得到的子图仍是连通图，则称是的一个点割集（Vertex Cutset）。若某一个节点构成一个点割集，则称该节点为割点（Cut Vertex）。如图7-25，e都是点割集，节点和节点都是割点。虽然删除节点和图成为不连通的，但因是，的真子集，所以，不是点割集。图7-25若图不是完全图，我们定义是的点割集为的点连通度(Vertex Connectivity)（或连通度）。连通度是为了产生一个非连通图需要删去的点的最少数目。于是一个不连通图的连通度为0，存在割点的连通图的连通度为1。完全图中，删去任何m个()点后仍是连通图，但是删去了个点后产生了一个平凡图，故定义k(Kp)= 。定义7.2.7 若无向图=V，E为连通图，若有边集，使图删除了的所有边后，所得到的子图是非连通图，而删除了的任何真子集后所得到的子图仍是连通图，则称是的一个边割集(Edge Cutest)。若某一条边构成一个边割集，则称该边为割边(Cut Edge)或桥(Bridge)。如图7-25中， (，)，(，)，(，)为边割集， (，)为割边。的割边也就是的一条边使。与点的连通度相似，我们定义非平凡图的边连通度(Edge Connectivity)为：是的边割集，边连通度是为了产生一个不连通图需要删去的边的最少数目。对平凡图规定=0，此外，一个不连通图也有=0。点连通度和边连通度反映了图的连通程度，和的值越大，说明图的连通性越好。定理7.2.3 一个无向连通图中的节点是割点的充分必要条件是存在节点和，使得连接和的每条路都经过。证明 充分性：如果连通图中存在节点和，使得连接和的每条路都经过，则在子图中和必不可达，故是割点。必要性：如果是割点，则中至少有两个连通分支和，任取，因为连通，故在中必有连接和的路，但和在中不可达，因此路必通过，即和之间的任意路必经过。定理7.2.4 一个无向连通图中的边是割边的充分必要条件是存在节点和，使得连接和的每条路都经过。证明留给读者。定理7.2.5 无向连通图中的边是割边的充分必要条件是不包含在图的任何基本回路中。证明 是连通图的割边当且仅当和在的不同连通分支中，而后者等价于在中不存在到的路，从而等价于不包含在图的任何基本回路中。于是定理得证。定理7.2.6 对于任意的无向图，有。证明 若不连通，则=0，故上式成立。若连通，（1）证明如果是平凡图，则，若是非平凡图，则因为每一个节点的所有关联边必含有一个边割集，故。（2）再证1)设，即有一割边，显然这时，上式成立。2)设，则必可删去某条边，使不连通，而删去其中条边，它仍是连通的，且有一条桥。对条边中的每一条边都选取一个不同于，的端点，把这些端点删去则必至少删去条边。若这样产生的图是不连通的，则；若这样产生的图是连通的，则仍是桥，此时再删去或，就必产生一个不连通图，故。由（1）和（2）得。如图7-26是无向连通图，点连通度，边连通度，最小度，此图满足。图7-26 示例对于有向图而言，两个节点的连通是有方向的，因此其连通性比无向图要复杂得多。定义7.2.8 在有向图中，从节点到之间有一条路，称从可达。可达性是有向图节点集上的二元关系，它具有自反性和传递性，但一般说来不具有对称性，因为如果从到有一条路，不一定必有从到的一条路，因此可达性不是等价关系。定义7.2.9 在简单有向图中，若任何两个节点间是相互可达的，则称是强连通图(Strongly Connected Graph)；若任何两个节点之间至少从一个节点到另一个节点是可达的，则称是单向连通图或单侧连通图(Unilaterally Connected Graph)；若在图中略去边的方向，将它看成无向图后，图是连通的，则称该图是弱连通图(Weakly Connected Graph)。例如，在图7-27中，图7-27是强连通图、单向(侧)连通图和弱连通图。图7-27()是单向(侧)连通图和弱连通图，但不是强连通图。图7-27()是弱连通图，但不是单向(侧)连通图，也不是强连通图。图7-27 强连通、单向连通和弱连通图示例由定义可知，强连通图一定是单向连通的，单向连通图一定是弱连通的，但反之不然。定理7.2.7 一个有向图是强连通的，当且仅当中有一个回路，它至少包含每个节点一次。证明 充分性：如果中有一个回路，它至少包含每个节点一次，则中任两个节点都是相互可达的，故是强连通图。必要性：如果是强连通图，则任何两个节点都是相互可达的，故必可作一回路经过图中所有各点。若不然，则必有一回路不包含某一节点，并且与回路上的各节点就不是相互可达的，与强连通条件矛盾。定义7.2.10 在简单有向图中，具有强连通性质的最大子图，称为强分图；具有单侧连通性质的最大子图，称为单侧分图；具有弱连通性质的最大子图，称为弱分图。例如在图7-28中，由，导出的子图是强分图，导出的子图也是强分图。由，导出的子图是单侧分图，也是弱分图。在图7-28 ()中，导出的子图是强分图，和，导出的子图是单侧分图， 导出了弱分图。 图7-28定理7.2.8 简单有向图中的每一个节点位于且只位于一个强分图中。证明 设，是中所有与相互可达的节点集合，由导出的子图是的一个强分图，且包含节点。如果节点位于两个不同的强分图和中，则中每个节点与相互可达，与中每个节点也相互可达，于是中任一节点与中任一节点相互可达，这与和是强分图矛盾。所以，中的每个节点只位于一个强分图中。定义7.2.11 在图中，节点到节点的最短路的长度称为到的距离，记作。如果到没有路，则=。它满足下列性质：。注意：当与相互可达时，不一定等于。习题7.21分析图7-29，求（1）从到的所有的基本路。 （2）从到的所有的简单路。（3）从到的距离。 （4），。 图7-292给定有向图如图7-30所示，求（1） 从到的所有基本路和简单路。 （2）所有基本回路和简单回路。 图7-303找出图7-31中的点割集、边割集、割点、割边。图7-314分别指出图7-32中的三个图分别属于哪种类型（强连通，单侧连通，弱连通）。图7-325求图7-33中的有向图的强分图、单侧分图和弱分图。图7-336证明一个有向图是单侧连通的，当且仅当它有一条经过每一个节点的路。 7.3图的矩阵表示前面讨论了图的图形表示方法以及相关的性质，在节点与边数不太多的情况下，这种表示方法有一定的优越性，它比较直观明了，但当图的节点和边数较多时，就无法使用图形表示法。由于矩阵在计算机中易于储存和处理，所以可以利用矩阵将图表示在计算机中，而且还可以利用矩阵中的一些运算来刻划图的一些性质，研究图论中的一些问题。本节主要考虑3种矩阵，即邻接矩阵、可达性矩阵和完全关联矩阵。邻接矩阵反映的是节点与节点之间的关系，可达性矩阵反映的是图的连通情况，完全关联矩阵反映的是节点与边之间的关系。7.3.1 邻接矩阵定义7.3.1 设是一个简单图，阶方阵称为的邻接矩阵(Adjacency Matrix )。其中，例7.3.1 如图7-34所示的图，其邻接矩阵为图7-34邻接矩阵中的元素非0即1，称这种0-1矩阵为布尔矩阵。通过例题我们容易发现，简单无向图的邻接矩阵是对称矩阵；但是当给定的图是有向图时，邻接矩阵不一定是对称的。例7.3.2 如图7-35()所示的有向图， 其邻接矩阵为图7-35 邻接矩阵与节点在图中的标定次序有关。例如图7-35()的邻接矩阵是，若将图7-35()中的节点和的标定次序调换，得到图7-35()，图7-35()的邻接矩阵是。= 考察和发现，先将的第一行与第二行对调，再将第一列与第二列对调可得到。称与是置换等价的。 一般地说，把阶方阵的某些行对调，再把相应的列做同样的对调，得到一个新的阶方阵，则称与是置换等价的。可以证明置换等价是阶布尔方阵集合上的等价关系。 虽然，对于同一个图，由于节点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去节点标定次序的任意性，取任意一个邻接矩阵表示该图。 对有向图来说，邻接矩阵的第行1的个数是节点的出度， 第列1的个数是节点的入度。零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。通过图的邻接矩阵可以得到图的很多重要性质。定理7.3.1 设是具有个节点的图， 其邻接矩阵为， 则 2，)中的项元素等于从节点到节点的长度等于的路的总数。 证明对用数学归纳法。 当1时， 由的定义， 定理显然成立。 假设当时定理成立， 则当1时， 故根据邻接矩阵定义是连接和的长度为1的路的数目,是连接和的长度为的路数目，故上式右边的每一项表示由经过条边到，再由经过1条边到的总长度为+1的路的数目 。对所有求和，即得是所有从到的长度等于+1的路的总数，故命题对+1成立。 例7.3.3 如图7-36所示，为简单有向图，写出的邻接矩阵，算出，且确定到有多少条长度为3的路? 到有多少条长度为2的路? 到自身长度为3和长度为4的回路各多少条?解 邻接矩阵及，如下： 图7-36 =2，所以到长度为3的路有2条，它们分别是：和。=1，所以到长度为2的路有1条：。=0，到自身无长度为3的回路。 =4，到自身有4条长度为4的回路，它们分别是：、和。7.3.2 可达性矩阵在许多实际问题中，常常要判断有向图的一个节点到另一个节点是否存在路的问题。对于有向图中的任何两个节点之间的可达性，也可用矩阵表示。定义7.3.2 设是一个简单有向图，阶方阵=称为的可达性矩阵(Reachability Matrix )，其中可达性矩阵表明，图中的任何两个节点之间是否存在路及任何节点是否存在回路。由于任何两个节点之间如果有一条路，则必有一条长度不超过的基本回路，所以由的邻接矩阵可得到可达性矩阵。方法是：令= ，再把中的非零元素改为1，而零元不变，得到的矩阵即为可达性矩阵。例7.3.4 设有向图的邻接矩阵为=，求的可达性矩阵。解 根据矩阵的乘法运算得 根据矩阵的加法运算得于是由此可知，图中任何的两个节点都是相互可达的，因而图是强连通图。上述计算可达性矩阵的步骤还是比较复杂的，因为可达性矩阵是一个布尔矩阵，我们在求可达性矩阵时，只关心两个节点间是否存在路，而不管路的长度及路的数目，所以我们可将矩阵，A，分别改为布尔矩阵，则可达性矩阵可表示为P=，其中表示在布尔运算下的次方。下面仍以例7.3.4为例来说明这种求可达性矩阵的方法。根据布尔矩阵的布尔积、布尔和运算得= 于是由于求可达性矩阵的上述过程与求传递闭包关系矩阵的过程相同，所以也可以利用Warshall算法计算可达性矩阵。上述可达性矩阵的概念，也可以推广到无向图中，只要将无向图中的每条无向边看成是具有相反方向的两条边，这样一个无向图就可看成一个有向图。无向图也可以用矩阵描述一个节点到另一个节点是否有路。在无向图中，如果两个节点之间有路，则称这两个节点是连通的，所以把描述一个节点到另一个节点是否有路的矩阵叫连通矩阵。无向图的连通矩阵是对称矩阵。 7.3.3 完全关联矩阵定义7.3.3 设是一个无向图，则矩阵称为的完全关联矩阵(Complete Incidence Matrix)，其中例7.3.5 给定无向图，如图7-37所示，写出其完全关联矩阵。解 图7-37 设是无向图，的完全关联矩阵有以下的性质： （1）每列元素之和均为2。这说明每条边关联两个节点。 （2）每行元素之和是对应节点的度数。 （3）所有元素之和是图各节点度数的和，也是边数的2倍。 （4）两列相同，则对应的两个边是平行边。（5）某行元素全为零，则对应节点为孤立节点。（6）同一个图当节点或边的编序不同时，其对应的仅有行序和列序的差别。下面给出有向图的完全关联矩阵。定义7.3.4 设是一个有向图，则矩阵称为的完全关联矩阵，其中1 在中是的起点 mij= -1 在中是的终点 0 若与不关联例7.3.6 给定有向图，如图7-38所示，写出其完全关联矩阵。解 图7-38 设是有向图，的完全关联矩阵有以下的性质： （1）每列有一个1和一个-1，这说明每条有向边有一个起点和一个终点。 （2）每行1的个数是对应节点的出度，-1的个数是对应节点的入度。 （3）所有元素之和是0，这说明所有节点出度的和等于所有节点入度的和。 （4）两列相同，则对应的两边是平行边。习题7.31 图7-39给出了一个有向图，试求（1）邻接矩阵。（2），并找出从到长度为1、2、3、4的路各有几条？（3）可达性矩阵。 图7-392设为图的邻接矩阵，的主对角线元素之和为600，问上有多少个三角形 ？3给定图7-40，写出完全关联矩阵。图7-404根据简单有向图的邻接矩阵，如何确定它是否有有向回路？ 7.4 欧拉图与汉密尔顿图7.4.1 欧拉图欧拉图是一类非常重要的图，之所以如此，不仅是因为欧拉是图论的创始人，更重要的是欧拉图具有对边的“遍历性”。1736年瑞士数学家欧拉发表了图论的第一篇著名的论文“哥尼斯堡七桥问题”（下称七桥问题）。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，河中有两个小岛，城的各部分用七座桥连接，如图7-41所示。每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每座桥恰好一次，在走遍七桥后又返回到出发点”的问题。这个问题看起来简单，但是谁也解决不了。最终，欧拉解决了这个问题，第一次论证了这个问题是不可解的。图7-41 欧拉把哥尼斯堡七桥表示成了图7-42所示的图，其中，用各节点表示各块陆地，用边表示桥。显然每座桥只穿行一次的问题等价于在图7-42中，从图中的某一点出发，找到一条路，通过每条边一次而且仅一次，最后又回到了出发点。这也就是所谓的一笔画问题。图7-42 图7-41的等价图为了解决上述的问题，我们先介绍欧拉图的相关概念。定义7.4.1 给定无孤立节点的图，若存在一条路，经过途中每条边一次而且仅一次，则该条路称为欧拉路(Euler Path)；若存在一条回路，经过图中每条边一次而且仅一次，称该条路为欧拉回路(Euler Circuit )。具有欧拉回路的图称为欧拉图(Eulerian Graph)。下面给出判定一个图是否有欧拉路或欧拉回路的理论依据。定理7.4.1 无向图具有一条欧拉路的充分必要条件是是连通的且有零个或两个奇数度节点。证明 必要性：设具有一条欧拉路，下证是连通的且有零个或两个奇度节点。设中有一条欧拉路：，该路经过的每一条边。因为中无孤立节点，所以该路经过的所有节点，即的所有节点都在该路上。故中任意两个节点连通，从而是连通图。设是图的任意节点，若不是的端点，每当沿经过一次都经过该节点关联的两条边，为该节点的度数增加2。由于的每一条边都在该路上，且不重复，所以的度数必为偶数。对于端点，当时，则和的度数也为偶数，即中无奇度节点；当时，则和的度数均为奇数，即中有两个奇度节点。 充分性：设是连通的且有零个或两个奇度节点，下证具有一条欧拉路。 设是连通图，有零个或两个奇度节点，用下述方法构造一条欧拉路： （1）若中有两个奇度节点，则从其中的一个开始构造一条简单路。 从出发经关联边进入，若是偶数度节点，则必可以由经关联边进入。如此下去，每边只取一次。由于是连通图，必可到达另一个奇度节点，从而得到一条简单路：。若中无奇数度节点，则从任意节点出发，用上述方法必可回到节点，得到一条简单回路：。 （2）若经过的所有边，则就是欧拉路。（3）否则，在中删除，得子图，则中的每一个节点的度数为偶数。因为是连通图，故和至少有一个节点重合，在中由出发重复（1），得到简单回路。（4）若与组合在一起恰是，则得到了欧拉路，否则，重复（3）可得到简单回路。以此类推直到得到一条经过中所有边的欧拉路。 推论 7.4.1 无向图具有一条欧拉回路，当且仅当是连通的并且所有节点度数全为偶数。 定理7.4.1不仅给出了欧拉路的判定方法，而且也给出了构造欧拉路的方法。例7.4.1 图如图7-43所示，构造其欧拉回路。解 在中找出一基本回路：，从中删去的各条边后得到；在中再找出一个基本回路：，再从中删去的各条边后得到；在中再找出一个基本回路：。若从中删去的各边后得到零图，则基本回路、即图7-43为所求。与有公共节点，与有公共节点或，（当然与也有公共节点，不予考虑了）这样便可得到一个欧拉回路：。有了欧拉路和欧拉回路的判别准则，因此七桥问题便有了确切的否定答案。因为从图7-42中可以看到，图中的4个节点都是奇数度节点，所以七桥问题无解。例7.4.2 图7-44()是一幢房子的平面图形， 前门进入一个客厅， 由客厅通向4个房间。 如果要求每扇门只能进出一次， 现在你由前门进去， 能否通过所有的门走遍所有的房间和客厅， 然后从后门走出。 图7-44解 将4个房间和一个客厅及前门外和后门外作为节点， 若两节点有边相连就表示该两节点所表示的位置有一扇门相通。 由此得图7-44()。 由于图中有4个节点是奇度节点， 因此本题无解。 与七桥问题类似的还有一笔画的判定问题，要判定一个图是否可以一笔画出，有两种情况：一是从图中某一节点出发，经过图的每一边一次且仅一次到达另一个节点。另一种是从图的某个节点出发，经过图的每一边一次且仅一次又回到该节点。上述的两种情况由欧拉路和欧拉回路的判定准则知有两种情况可以一笔画出： （1） 如果图中所有节点是偶数度节点， 则可以任选一点作为始点一笔画完；（2） 如果图中只有两个奇数度节点， 则可以选择其中一个奇数度节点作为始点也可一笔画完。 例7.4.3 判断如图7-45所示的3个图形是否可以一笔画出。图7-45 解 图7-45()中，各节点的度数都是偶数，所以从任一节点出发，一笔画可以回到原来的出发点。图7-45()中，有两个奇数度节点，故可以选择其中一个奇数度节点作为始点也可一笔画完。图7-45()中，有4个奇数度节点，因此不可以一笔画出。例7.4.4 试问个节点的完全图中有多少回路？有没有欧拉路或欧拉回路？解 在中，3条边可以组成一个回路，有个；4条边也可以组成一个回路，有个；以此类推，条边可以构成的回路有个，故中回路总数为+=当为奇数时，每个节点的度数都是偶数，有欧拉回路；当为偶数时，只有在=2时有欧拉路。欧拉路和欧拉回路的概念，也可以推广到有向图中去。定义7.4.2 给定有向图，通过图中每边一次而且仅一次的一条单向路（回路），称作单向欧拉路（回路）。定理7.4.2 有向图具有一条单向欧拉回路，当且仅当是连通的，且每个节点入度等于出度。一个有向图具有一条单向欧拉路，当且仅当是连通的，且除了两个节点外，每个节点的入度等于出度，但这两个节点中，一个节点的入度比出度大1，另一个节点的出度比入度大1。这个定理的证明，可以看作是无向图的欧拉路的推广，因为对于有向图的任一个节点来说，如果入度等于出度，则该节点的总度数为偶数，如果入度与出度之差为1，则其总度数为奇数，因此，定理7.4.2与定理7.4.1的证明类似。7.4.2 汉密尔顿图1859年，英国数学家汉密尔顿（Hamilton）提出一个问题，他用一个正十二面体的20个顶点代表20个大城市，要求沿着棱，从一个城市出发，经过每个城市仅一次，最后又回到出发点。这就是当时风靡一时的周游世界游戏，解决这个问题就是在如7-46所示的图中寻找一条经过图中每个节点恰好一次的回路。与欧拉图不同，汉密尔顿图是遍历图中的每个节点， 一条汉密尔顿回路不会在两个节点间走两次以上，因此没有必要在有向图中讨论。定义7.4.3 给定无向图，通过图中每个节点一次而且仅一次的路称为汉密尔顿路(Hamilton Path)。经过图中每个节点一次而且仅一次的回路称为汉密尔顿回路(Hamilton Circuit)。具有汉密尔顿回路的图称为汉密尔顿图(Hamilton Graph)。汉密尔顿图和欧拉图相比，虽然考虑的都是遍历问题，但是侧重点不同。欧拉图遍历的是边，而汉密尔顿图遍历的是节点。另外两者的判定困难程度也不一样，前面我们已经给出了判定欧拉图的充分必要条件，但对于汉密尔顿图的判定，至今还没有找出判定的充要条件，只能给出若干必要条 图7-46 汉密尔顿图示例件或充分条件。下面我们先给出一个图是汉密尔顿图的必要条件。定理7.4.3 设图是汉密尔顿图，