1、转化转化 Euler1736年年 图论中讨论的图 问题：是否能从四块陆地中问题：是否能从四块陆地中的任一块开始，通过每座桥的任一块开始，通过每座桥恰好一次再回到起点？恰好一次再回到起点？是否能从任意一个顶点开始，通过每条边恰好一次再回到起点？包含两个要素：对象（陆包含两个要素：对象（陆地）及对象间的二元关系地）及对象间的二元关系（是否有桥连接）（是否有桥连接）Leonhard Euler(公元1707-1783年)1707年出生在瑞士的巴塞尔城，13岁就进巴塞尔大学读书，师从著名的数学家约翰.伯努利。他从19岁开始发表论文，直到76岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线
2、，多面体的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了886本书籍和论文，其中分析、代数、数论占40%，几何占18%，物理和力学占28%，天文学占11%，弹道学、航海学、建筑学等占3%。 1733年，年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长，直到1766年，重回彼得堡，没有多久，完全失明欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的研究。问题二：四色问题问题二：四色问题 四色问题是世界近代三
3、大数学四色问题是世界近代三大数学难题之一。难题之一。 四色问题的内容是：任何一四色问题的内容是：任何一张地图只用四种颜色就能使具有张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。共同边界的国家着上不同的颜色。 它的提出来自英国。它的提出来自英国。1852年，年，毕业于伦敦大学的弗南西斯毕业于伦敦大学的弗南西斯格思格思里发现了一种有趣的现象：里发现了一种有趣的现象：“看看来，每幅地图都可以用四种颜色来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都着色，使得有共同边界的国家都被着上不同的颜色。被着上不同的颜色。”这个现象这个现象能不能从数学上加以严格证明呢？能不能从数学上加以严格
4、证明呢？ 进入进入20世纪以来，科学家们对四色猜想的证明基本上世纪以来，科学家们对四色猜想的证明基本上是按照是按照的想法在进行。后来美国数学家的想法在进行。后来美国数学家于于1939年证明了年证明了22国以下的地图都可以用四色着色。国以下的地图都可以用四色着色。1950年，有人从年，有人从22国推进到国推进到35国。国。1960年，有人又证明了年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了国以下的地图可以只用四种颜色着色；随后又推进到了50国。国。 1976年年6月，美国伊利诺大学月，美国伊利诺大学与与在两台不在两台不同的电子计算机上，用了同的电子计算机上，用了1200个
5、小时，作了个小时，作了100亿判断，亿判断，终于完成了四色定理的证明，轰动了世界。终于完成了四色定理的证明，轰动了世界。 然而，真正数学上的严格证明仍然没有得到！数学然而，真正数学上的严格证明仍然没有得到！数学家仍为此努力，并由此产生了多个不同的图论分支。家仍为此努力，并由此产生了多个不同的图论分支。问题二：四色问题问题二：四色问题问题三：问题三：Hamilton问题问题 Hamilton问题源于问题源于1856年，英国数学家年，英国数学家Hamilton设计了一个名为设计了一个名为周游世界的游戏：他用一个正十二面体的二十个端点表示世界上的二周游世界的游戏：他用一个正十二面体的二十个端点表示世
6、界上的二十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体十座大城市（见图），提出的问题是要求游戏者找一条沿着十二面体的棱通过每个端点恰好一次的行走路线。反映到图论上就是判断一个的棱通过每个端点恰好一次的行走路线。反映到图论上就是判断一个给定的图是否存在一条含所有顶点的回路。给定的图是否存在一条含所有顶点的回路。Hamilton至今尚无有效方法來解決！至今尚无有效方法來解決！一直往前走一直往前走碰壁就回碰壁就回头头換条路找換条路找沿途要沿途要记录记录下走过的下走过的路线路线2e1v2v3v4v5v1e3e4e5e6e7e8e9e。第第i年初年初1234购置费（万元）购置费（万元）2.
7、52.62.83.1使用年限使用年限1234每年的维修与运行费（万元）每年的维修与运行费（万元）11.524某工厂的某台机器可连续工作某工厂的某台机器可连续工作4年，决策者每年年初都年，决策者每年年初都要决定机器是否需要更新。若购置新的，就要支付一定要决定机器是否需要更新。若购置新的，就要支付一定的购置费用；若继续使用，则要支付一定的维修与运行的购置费用；若继续使用，则要支付一定的维修与运行费用，而且随着机器使用年限的增加费用逐年增多。计费用，而且随着机器使用年限的增加费用逐年增多。计划期（划期（4 年）中每年年初的购置价格及各个年限内维修年）中每年年初的购置价格及各个年限内维修与运行费用由下
8、表给出，试制订今后与运行费用由下表给出，试制订今后4年的机器更新计年的机器更新计划，使总的支付费用最少。划，使总的支付费用最少。解：把该问题看成一个最短路问题。设解：把该问题看成一个最短路问题。设 v1 和和 v5 分别分别表示计划期的始点和终点（表示计划期的始点和终点（x5 可理解为第可理解为第4年年末）。年年末）。图中各边图中各边 (vi , vj) 表示在第表示在第 i 年初购进的机器使用到第年初购进的机器使用到第 j 年初（即第年初（即第 j 1 年底），边旁的数字由表中的数据得年底），边旁的数字由表中的数据得到。到。 又如果已知不同役龄机器年末的处理价格又如果已知不同役龄机器年末的处
9、理价格如下表所示，那末在这计划期内机器的最优更如下表所示，那末在这计划期内机器的最优更新计划又会怎样？新计划又会怎样？年度年度第第1年末年末第第2年末年末第第3年末年末第第4年末年末机器处理价（万元）机器处理价（万元）2.01.61.31.1 关于第二问，类似于第一问，可转化为求下图中从 v1 到 v5 的最短路问题。 按照最短路算法可得最短路 v1, v2, v3, v5，即计划期内机器更新最优计划为第 1 年、第 3 年初各购进一台新机器，4 年总的支付费用为 6.8万元。 1.图的定义图的定义图G(graph)主要由主要由2部分组成部分组成:(1)节点集合节点集合V, 其中的元素称为其中
10、的元素称为节点.(2)边集合边集合E, 其中的元素称为其中的元素称为边.通常将图通常将图G记为记为G = (V, E).CADB1b2b3b4b5b6b7b2e1v2v3v4v5v1e3e4e5e6e7e8e9e(a)节点又可以称为点、顶点或结点节点又可以称为点、顶点或结点,常用一个实心点或常用一个实心点或空心点表示空心点表示,但在实际应用中还可以用诸如方形、圆形、但在实际应用中还可以用诸如方形、圆形、菱形等符号菱形等符号.(b)边及其的表示边及其的表示.无向边? b3 = AB = BA =A, B(可重). 有向边(弧)?.,),(32328vvvve几点说明几点说明:所有边都是无向边的图
11、称为无向图；所有边都是无向边的图称为无向图；所有边都是有向边的图称为有向图所有边都是有向边的图称为有向图.CADB1b2b3b4b5b6b7b2e1v2v3v4v5v1e3e4e5e6e7e8e9e(c)图的拓扑不变性质图的拓扑不变性质. 需要注意的是需要注意的是,我们讨论我们讨论的图不但与节点位置无关的图不但与节点位置无关,而且与边的形状和而且与边的形状和长短也无关长短也无关.有有n个节点的图称为个节点的图称为n阶图阶图,有有n个节点个节点m条边的图条边的图称为称为(n, m)图图. 在图在图G = (V, E)中中, 称称V = 的图为空图的图为空图, 记为记为. 几点说明几点说明:5N1
12、N若若 V 但但E = 的图称为的图称为零图, n阶零图可记阶零图可记为为Nn.仅一个节点的零图称为平凡图仅一个节点的零图称为平凡图.euveuvuve定义：设定义：设G = (V, E)是图是图, 对于任意对于任意u, v V,若从若从节点节点u到节点到节点v有边有边, 则称则称u邻接到v或称或称u和和v是邻是邻接的接的.2.邻接邻接无向图无向图?有向图有向图?12341e2e3e4e5e(无向图的两条边邻接是指它们有公共端点无向图的两条边邻接是指它们有公共端点.)(平面图的面相邻平面图的面相邻?)3.关联关联定义：定义： 设设G = (V, E)是图是图, e E, e的两个端点分的两个端
13、点分别为别为u和和v, 则称边则称边e与节点与节点u以及边以及边e与节点与节点v是关是关联的联的.图的任意一条边都关联两个节点图的任意一条边都关联两个节点. 关联相同两个关联相同两个节点的边称为吊环节点的边称为吊环,可简称环可简称环.关联的起点相同与关联的起点相同与终点也相同的边称为多重边或平行边终点也相同的边称为多重边或平行边,其边数称其边数称为边的重数为边的重数.4.简单图简单图(1)简单图简单图定义：定义： 设设G = (V, E)是图是图, 若若G中既无吊环又无中既无吊环又无多重边多重边,则称则称G是是简单图.彼得森彼得森(Petersen, 18311910)图图, 是一种妖怪图是一
14、种妖怪图.妖怪图妖怪图?Petersen图称为图称为单星妖怪单星妖怪.下面的图称为下面的图称为双星双星妖怪妖怪.(2)完全无向图完全无向图Def 设设G = (V, E)是是n阶简单无向图阶简单无向图, 若若G中任中任意节点都与其余意节点都与其余n - 1个节点邻接个节点邻接, 则称则称G为为n阶阶完全无向图，记为，记为Kn.K5: .2) 1(| )(|nnKEn将将n阶完全无向图阶完全无向图Kn的边任意加一个方向所得到的的边任意加一个方向所得到的有向图称为有向图称为n阶阶竞赛图.设设G = (V, E)是是n阶简单有向图阶简单有向图, 若若G中任意节点都与中任意节点都与其余其余n - 1个
15、节点邻接个节点邻接, 则称则称G为为n阶阶完全有向图。(3)补图补图Def 设设G = (V, E)是是n阶简单无向图阶简单无向图,由由G的所有的所有节点以及由能使节点以及由能使G成为成为Kn需要添加的边构成的需要添加的边构成的图称为图称为G的的补图,记为记为(u和和v在在G中不邻接中不邻接 u和和v在在 中邻接中邻接).GGGG“七桥七桥”中从一个地方出发的桥的数目就是对中从一个地方出发的桥的数目就是对应节点的度数应节点的度数.边与节点的边与节点的关联次数关联次数?Def 设设G = (V, E)是无向图是无向图, v V,称与节点称与节点v关联的所有边的关联次数之和为节点关联的所有边的关联
16、次数之和为节点v的的度数(degree),记为记为deg(v).一个环算一个环算2度度?. 3)deg(, 5)deg(, 2)deg(321vvv1v2v3v2e1e3e4e5eDef 设设G = (V, E)是有向图是有向图, v V, 称以称以v为为起点起点的边的数目为节点的的边的数目为节点的出度(out-degree),记为记为deg+(v),以以v为终点的边的数目为节点的为终点的边的数目为节点的入度(in-degree),记为记为deg-(v), 称称deg+(v) + deg-(v)为节点为节点v的的度数,记为记为deg (v). 一个环算一个环算2度度?1v2v3v4v图论第一定
17、理图论第一定理,常称为常称为“握手握手(?)定理定理”.Theorem 6-1 在任何在任何(n, m)图图G = (V, E)中中, 其所其所有节点度数之和等于边数有节点度数之和等于边数m的的2倍倍,即即Corollary 在任意图在任意图G = (V, E)中中, 度数为奇数的度数为奇数的节点个数必为偶数节点个数必为偶数.Proof .2)deg(mvVv. )deg()deg()deg(2)deg()deg(奇数偶数vvVvvvvm由定理及其推论很容易知道由定理及其推论很容易知道,在任何一次聚会上在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次所有人握手次数之和必为偶数并且握了
18、奇数次手的人数必为偶数手的人数必为偶数.(环的解释环的解释?)Theorem 6-2 在任意有向图中在任意有向图中,所有节点的出度所有节点的出度之和等于入度之和之和等于入度之和.在任意图中在任意图中, 度数为度数为0的节点称为的节点称为孤立点。度数。度数为为1的节点称为的节点称为悬挂点。例例6-1 6-1 证明证明: 对于任意对于任意n(n 2)个人的组里个人的组里,必有必有两个人有相同个数的朋友两个人有相同个数的朋友.Proof 将组里的每个人看作节点将组里的每个人看作节点,两个人是朋两个人是朋友当且仅当对应的节点邻接友当且仅当对应的节点邻接,于是得到一个于是得到一个n阶简单无向图阶简单无向
19、图G,进而进而G中每节点的度数可能中每节点的度数可能为为0, 1, 2, , n - 1中一个中一个. 当当G中无孤立点时中无孤立点时,于是每节点的度数可能为于是每节点的度数可能为1, 2, , n - 1. 由于共有由于共有n个节点个节点,于是必有两节点于是必有两节点度数相同度数相同.当当G中有孤立点时中有孤立点时,这时每节点的度数只可能这时每节点的度数只可能为为0, 1, 2, , n - 2. 同样由于共同样由于共n有个节点有个节点,因此因此必有两节点度数相同必有两节点度数相同.若一个若一个Simple无向图无向图G的每节点度数均为的每节点度数均为k, 则则称称G为为k-正则图(k-re
20、gular graph). 例例6-2 设无向图设无向图G是一个是一个3-正则正则(n, m)图图, 且且2n 3 = m, 求求n和和m各是多少各是多少? Hint 根据握手定理有根据握手定理有:.23mn .32mn9, 6mnDef 最大度、最小度；最小出度、最小入度最大度、最小度；最小出度、最小入度任意图任意图G = (V, E):有向图有向图G = (V, E):),deg(max)(vGVv).deg(min)(vGVv),(degmax)(vGVv),(degmax)(vGVv),(degmin)(vGVv).(degmin)(vGVv对于无向图对于无向图G = (V, E),
21、V = v1, v2, , vn,称称deg(v1), deg(v2), , deg(vn)为的为的度数序列. 对于对于有向图有向图, 还可以定义其出度序列和入度序列还可以定义其出度序列和入度序列.例例6-36-3 是否存在一个无向图是否存在一个无向图G, 其度数序列分别其度数序列分别为为(1)7, 5, 4, 2, 2, 1.(2)4, 4, 3, 3, 2, 2. (1)由于序列由于序列7, 5, 4, 2, 2, 1中中, 奇数个数为奇数奇数个数为奇数, 根据握根据握手定理的推论知手定理的推论知, 不可能存在一个图其度数序列为不可能存在一个图其度数序列为7, 5, 4, 2, 2, 1.
22、(2)因为序列因为序列4, 4, 3, 3, 2, 2中中, 奇数个数为偶数奇数个数为偶数, 可以得到可以得到一个无向图一个无向图,其度数序列为其度数序列为4, 4, 3, 3, 2, 2.1.子图子图可以通过一个图的子图去考察原图的有关性可以通过一个图的子图去考察原图的有关性质以及原图的局部结构质以及原图的局部结构.Def 设设G = (V, E)和和H = (W, F)是图是图, 若若W V且且F E, 则称则称H = (W, F)是是G = (V, E)的的子图. 若若H = (W, F)是是G = (V, E)的子图且的子图且W = V, 则则称称H = (W, F)是是G = (V,
23、 E)的的生成子图.AeBABABABe1v2v3v例例子图子图子图子图1v1v1v1v1v2v2v2v2v2v3v3v3v3v3v) 1 ()2()3()4()5()6()7()8()9(1v1v1v1v2v2v2v2v2v3v3v3v3v3v)10()11()12()13()14(1v常见的常见的4种产生种产生G = (V, E)的子图的方式如下的子图的方式如下:(1)GW 设设W V,则以则以W为节点集合为节点集合,以两端以两端点均属于点均属于W的所有边为边集合构成的子图的所有边为边集合构成的子图,称为称为由W导出的子图(induced subgraph by W),记为记为GW.1v2
24、v3v4v5v?,321vvvG?,321vvvG (2)G W 设设W V, 导出子图导出子图GV W记为记为G W,是在是在G中去掉所有中去掉所有W中的节点中的节点,同时也要同时也要去掉与去掉与W中节点关联的所有边中节点关联的所有边. 通常将通常将G v记为记为G - v.(3)GF 设设F E, 则以则以F为边集合为边集合,以以F中边中边的所有端点为节点集合构成的子图的所有端点为节点集合构成的子图,称为称为由F导出的子图(induced subgraph by F),记为记为GF. (4)G F 设设F E,则从则从G中去掉中去掉F中的所有边中的所有边得到的生成子图记为得到的生成子图记为
25、G F.1v2v3v4v5vabcdefg?,cbaG?,cbaG 简单图简单图G = (V, E)的补图的补图G + U: (与子图无关与子图无关).EKGn.uvGuvG).,(),(vuGvuG2. *图的运算图的运算图的运算就是通过一定的操作图的运算就是通过一定的操作,产生产生“新新”的的图图. 前面的子图的产生实际上就是图的运算前面的子图的产生实际上就是图的运算,但但它们都是在一个图中进行讨论的它们都是在一个图中进行讨论的. 也便于用代也便于用代数方法讨论图数方法讨论图.Def (1).,(),(222111EVGEVG.21GG (2)(3)(4)思考 图的每种运算的性质有哪些图的
26、每种运算的性质有哪些? 它与集合它与集合的并、交、差、的并、交、差、(补补)及环和及环和(对称差对称差)运算的性运算的性质有什么不同质有什么不同?.21GG .,),(12121VVEEEEVGG).()(122121GGGGGG3.图同构图同构由于图的拓扑性质由于图的拓扑性质, 有可能两个表面上看起来不同有可能两个表面上看起来不同的图本质上是同一个图的图本质上是同一个图, 这就是图同构的问题这就是图同构的问题.Def 设设G1=(V1,E1)和和G2=(V2,E2)是无向图，若存是无向图，若存在一个双射在一个双射 :V1V2使得对于任意使得对于任意u,v V1，(u,v)E1当且仅当且当且仅
27、当且 (u) (v) E2且边的重数相且边的重数相同，则称同，则称G1与与G2同构，记为同构，记为G1 G2.直观理解直观理解: G1 G2是指其中一个图仅经过下列两是指其中一个图仅经过下列两种变换可以变为另一个图种变换可以变为另一个图:(a)挪动节点的位置；挪动节点的位置；(b)伸缩边的长短伸缩边的长短.无向图无向图:1G2G2G1G有向图有向图:对于两个有向图同构的判断对于两个有向图同构的判断, 特别要特别要注意边的方向的一致性注意边的方向的一致性. 思考 给出至少给出至少4个两个图同构的必要条件个两个图同构的必要条件.1G2G3GUlam猜想猜想?Simple graphs:,.,211
28、nvvvV ,.,212nwwwV ,1G2GniwGvGii,.,2 , 1,2121GG 在图在图G = (V, E)中中, 经常考虑从一个节点出发经常考虑从一个节点出发,沿着一些边连续移动到另一个节点的问题沿着一些边连续移动到另一个节点的问题,这这就是路的概念就是路的概念.1.路路(walk, way)Def 对于任意图对于任意图G = (V, E)中，称中，称G中节点与中节点与边交替出现的序列为一条路。边交替出现的序列为一条路。.:122110lliiivevevvevevL路的起点路的起点;终点终点; 路的长度路的长度; 平凡路平凡路.需要注意的是需要注意的是,有向图中的路须按边的方
29、向走有向图中的路须按边的方向走,有向图中的路可称为有向路有向图中的路可称为有向路.1v1v2v2v3v3v4v1e1e2e2e3e3e4e4e5e5e6e7e143322233vevevevev3321171vevevev有两种特殊的路有两种特殊的路: 一种是节点不重复的路一种是节点不重复的路, 称为称为路径. 一种是边不重复的路一种是边不重复的路, 称为称为轨迹.显然显然, 路径是轨迹路径是轨迹, 但轨迹不一定是路径但轨迹不一定是路径. 说明 由于图论应用的广泛性由于图论应用的广泛性, 很多概念存在很多概念存在意义上的差别意义上的差别. 之所以选择之所以选择“路径路径”, 它有捷它有捷径之意
30、；径之意；“轨迹轨迹”强调边不重复强调边不重复, 它是它是(可能可能多次多次)走过后留下的痕迹走过后留下的痕迹. 在在n阶图阶图G = (V, E)中中, 若存在从节点若存在从节点v0到到vl一条一条路路(v0 vl), 则存在一条从则存在一条从v0到到vl一条长度一条长度 n - 1的的路径路径.Def 在图在图G=(V,E),称节点称节点u到到v的边数最少的长的边数最少的长度为度为u到到v的距离，记为的距离，记为d(u, v)。d(u, v): u到到v边数最少的路径长度边数最少的路径长度.称称maxd(u,v)为图为图G的的直径直径，记为，记为diam(G).2.回路回路Def 起点与终
31、点相同的起点与终点相同的(长度长度 1)路称为路称为回路回路.边不重复的回路称为边不重复的回路称为简单回路简单回路（闭迹（闭迹).除起点重复一次外除起点重复一次外, 别的节点均不重复的简单回别的节点均不重复的简单回路称为路称为圈或环圈或环,显然显然,圈圈简单回路简单回路, 但反过来不成立但反过来不成立.有有n个节点的圈称为个节点的圈称为n阶圈阶圈,记为记为Cn. 在在n - 1阶圈阶圈Cn-1的内部放置一个节点的内部放置一个节点, 并使之与并使之与Cn-1的每个节点邻接的每个节点邻接, 这样得到的图称为这样得到的图称为n阶轮图阶轮图, 记为记为Wn.5W在在n阶图阶图G = (V, E)中中,
32、 若存在从节点若存在从节点v0到到v0一条一条简简单单回路回路, 则存在一条从则存在一条从v0到到v0一条长度一条长度 n 的的圈圈.0v采用采用“最长路径法最长路径法”技巧技巧.Theorem 在无向图在无向图G = (V, E)中中,若任意若任意v V有有deg(v) 2,则则G中存在圈中存在圈 .Proof 不妨设不妨设G是简单图是简单图. 在在G中选取一条最长的路径中选取一条最长的路径L: v0v1vl. 0v1v2vivlv图的基本性质之一是其连通性图的基本性质之一是其连通性,它与图中从节它与图中从节点到节点的路密切相关点到节点的路密切相关. 为了讨论方便为了讨论方便,先给先给出出D
33、ef 在任何图在任何图G = (V, E)中中,若从节点若从节点u到到v存存在一条路在一条路,则称则称u可达可达v (accessible). 由于节点由于节点v到到v总存在一条长度为总存在一条长度为0的路的路, 因此因此任意节点任意节点v可达可达v自身自身.先讨论无向图的连通性先讨论无向图的连通性.1.无向图的连通性无向图的连通性Def 6-17 设设G = (V, E)是无向图是无向图, 对于对于G中任意中任意两个节点两个节点u和和v均可达均可达, 则称则称G是是连通图.)(a)(bDef 设设G = (V, E)是无向图是无向图, G中极大的连通子中极大的连通子图称为图称为G的的连通分支
34、(connected component), 图图G的连通分支数记为的连通分支数记为w(G).由定义知由定义知,图图G的连通分支满足的连通分支满足3 个条件个条件: (1)连连通分支是通分支是G的子图；的子图；(2)该子图本身是连通图；该子图本身是连通图；(3)在该子图中再添加原图的任意边或节点都不在该子图中再添加原图的任意边或节点都不连通连通.Theorem 设设G = (V, E)是无向图是无向图, 则则G是连通图是连通图当且仅当当且仅当w(G) = 1. G是非连通图当且仅当w(G) 2.例例6-5 G不连通不连通 连通连通.Hint u, v:(1) u, v在在G中不邻接中不邻接.(
35、2) u, v在在G中邻接中邻接:Gwuv第一种方法:根据定义证明!例例6-6 设设G = (V, E)是是n阶简单无向图阶简单无向图, 若若对对于任意的于任意的G中不相邻的节点中不相邻的节点u和和v有有deg(u) + deg(v) n - 1, 则则G是连通图是连通图.Hint (反证反证)Theorem 6-7 去掉简单回路上的去掉简单回路上的一条一条边或度为边或度为1的节点的节点, 图的连通性不变图的连通性不变.uv., 1)deg(1 nu1)deg(2 nvnnn21第二种方法:反证法!2.无向连通图的点连通度与边连通度无向连通图的点连通度与边连通度对于无向连通图对于无向连通图,其
36、连通的程度是不同的其连通的程度是不同的,有些很有些很“脆弱脆弱”,有的则相反有的则相反.(1)点割集与点连通度点割集与点连通度(G).Def 设设G = (V, E)是是连通连通无向图无向图, W V, (i) G W不连通或是不连通或是1阶图阶图; (ii)删除删除W的任意真子集均的任意真子集均连通连通, 则称则称W为为G的点割集的点割集.“割”是分割、分离、分开的意思, 恰使得G不连通或是1阶图所要去掉的节点集合称为的点割集. 若点割集W = v,则称v为的割点或关节点.点割集点割集: a, b; c, d. (G) = 2. 边割集边割集: e1, e2, e3. (G) = 3.abc
37、d1e2e3e割点割点: A; B. (G) = 1. 割边割边: e. (G) = 1.eABDef根据定义根据定义,一个连通无向图的点连通度是使得一个连通无向图的点连通度是使得G不连通或为不连通或为1阶图所要删去的最少的节点个数阶图所要删去的最少的节点个数. 于是于是,1阶图的点连通度为阶图的点连通度为0,而完全无向图而完全无向图Kn的的点连通度为点连通度为n - 1.|min|)(的点割集是GWWG 点连通度为点连通度为2的图的图G称为称为2-连通或连通或重连通图. 确定一个无向图是否重连通具有重要的意义确定一个无向图是否重连通具有重要的意义. 假假定无向图的节点表示电话交换站定无向图的
38、节点表示电话交换站,边表示电话线边表示电话线,则在点连通度为则在点连通度为2的通讯网络系统中的通讯网络系统中,一个站发一个站发生故障系统仍可正常工作生故障系统仍可正常工作.(2)边割集与边连通度边割集与边连通度(G).Def 设设G = (V, E)是连通无向图且是连通无向图且F E, 若从若从G中删除中删除F的所有边所得到的子图不连通或是平凡的所有边所得到的子图不连通或是平凡图图,而删除而删除F的任意真子集都连通的任意真子集都连通,则称则称F为为G的的边割集.恰使得恰使得G不连通或是平凡图所要去掉的边的集合不连通或是平凡图所要去掉的边的集合称为称为G的边割集的边割集. 若边割集若边割集F =
39、 e,则称则称e为的割为的割边或桥边或桥.Def根据定义根据定义, 一个连通无向图一个连通无向图G的边连通度是使的边连通度是使得得G不连通或为平凡图所要删去的最少的边的不连通或为平凡图所要删去的最少的边的数目数目. H. Whitney在在1932年给出的关于点连通度、年给出的关于点连通度、边连通度及最小度之间的联系的一个结论边连通度及最小度之间的联系的一个结论.Theorem 6-8 设设G = (V, E)是连通是连通无向图无向图,则则.|min|)(的边割集是GFFG ).()()(GGGProof (1)由于将任意一个节点所关联的边全由于将任意一个节点所关联的边全去掉后都不连通去掉后都
40、不连通,所以有所以有 (2)设设F是是G的恰具有的恰具有 条边的边割集条边的边割集. 考虑删考虑删除除F中中 条边条边.删除后不连通删除后不连通, 显然显然若删除后连通若删除后连通, 则存在桥则存在桥uv = u, v. 再删除再删除u或或v, 即得知结论成立即得知结论成立.).()(GG?)()(GG1)(G).(1)()(GGG)(Guv3.有向图的连通性有向图的连通性(1)强连通图强连通图Def 设设G = (V, E)是有向图是有向图, u, v V均均相互相互可达可达, 则称则称G为强连通图为强连通图.(2)单向连通图单向连通图Def 设设G = (V, E)是有向图是有向图,对于任
41、意对于任意u, v V,从从u可达可达v或者或者从从v可达可达u,则称则称G为为单向连通图.(3)弱连通图弱连通图Def 设设G = (V, E)是有向图是有向图,若不考虑边的方向若不考虑边的方向是一个无向连通图是一个无向连通图,则称有向图则称有向图G为弱连通图，为弱连通图，简称有向图连通简称有向图连通.强强连通图连通图 单向单向连通图连通图 弱弱连通图连通图.但反过来均不成立但反过来均不成立!)(a)(b)(cTheorem6-9 设设G = (V, E)是是n阶阶(n2)有向图有向图, 则则G强连通当且仅当强连通当且仅当G中存在一条回路中存在一条回路, 它通它通过所有节点过所有节点. De
42、f 设设G = (V, E)是有向图是有向图, G的极大的强连通的极大的强连通子图称为子图称为G的的强连通分支. (i)子图子图;(ii)强连通强连通;(iii)极大极大.Theorem 6-10 设设G = (V, E)是有向图是有向图,则则G的任的任意节点都位于且仅位于的一个强连通分支中意节点都位于且仅位于的一个强连通分支中.Hint 任意节点任意节点v本身强连通本身强连通.123456;3 , 2 , 1 G.6;5;4GGGDef 设设G = (V, E)是有向图是有向图, G的极大的单向连的极大的单向连通子图称为通子图称为G的的单向连通分支.无向连通图的节点可以位于不同的单向连通无向
43、连通图的节点可以位于不同的单向连通分支中分支中. Def 设设G = (V, E)是有向图是有向图, G的极大的弱连通的极大的弱连通子图称为子图称为G的的弱连通分支.将一个图画出来是最直观的表示图的方式将一个图画出来是最直观的表示图的方式. 为为了便于使用计算机存储和处理图了便于使用计算机存储和处理图,更为了借助更为了借助于完善的矩阵理论于完善的矩阵理论(线性代数知识之一线性代数知识之一!)研究研究图的有关性质图的有关性质,有必要学习图的矩阵表示有必要学习图的矩阵表示.本节简单介绍图的常见的本节简单介绍图的常见的3种矩阵表示及一些种矩阵表示及一些简单结论简单结论, 不涉及更多的有关图的矩阵方面
44、的不涉及更多的有关图的矩阵方面的知识知识.1.图的邻接图的邻接(adjacency)矩阵矩阵第一种图的矩阵表示第一种图的矩阵表示邻接矩阵邻接矩阵,它表示的是它表示的是图中任意两个节点间的邻接关系图中任意两个节点间的邻接关系.Def 6-29 G = (V, E), 对节点编号对节点编号V = v1, v2, , vn.其中其中aij是是vi邻接到邻接到vj的边数的边数, i, j = 1, 2, , n.nnnnnnaaaaaaaaaGA.)(2112221112111v1v2v2v3v3v4v4v1G2G,0110110110020120)(1GA.0100010110000020)(2GA
45、显然显然, 无向图的邻接矩阵是对称矩阵无向图的邻接矩阵是对称矩阵.一个图与其邻接矩阵是一一对应的一个图与其邻接矩阵是一一对应的.从一个图从一个图G的邻接矩阵的邻接矩阵A(G)容易得出每个节容易得出每个节点的度数点的度数. 以有向图为例以有向图为例, A(G)中第中第i行元素行元素之和为第个之和为第个i节点的出度节点的出度vi, i = 1, 2, , n, 第第j列元素之和为第个列元素之和为第个j节点的入度节点的入度, j = 1, 2, , n.从图的邻接矩阵可以得出从节点从图的邻接矩阵可以得出从节点vi到到vj长度为长度为l(l 1)的路的数目的路的数目.Theorem 6-12 设设A是
46、图是图G的邻接矩阵的邻接矩阵, 则则Al中中(i, j)位置元素为从节点位置元素为从节点vi到到vj长度为长度为l(l 1)的路的路的数目的数目.Proof 对对l归纳归纳. l = 1, 显然显然.Al = Al-1A:.)1(2)1(21)1(11)1()(njlinjlijlinkkjliklijaaaaaaaaajviv1v2vnv例例6-71v2v3v4v5v,0010110000010101000001010A.001011000001010100000101000101100000101010000010102A0202000101200000010120000,40000020
47、200020202020002023A00404400000404040000040404A2.图的可达图的可达(accessible)矩阵矩阵第二种图的矩阵表示第二种图的矩阵表示可达矩阵可达矩阵,它表示的是它表示的是图中任意两个节点间的可达关系图中任意两个节点间的可达关系.Def G = (V, E), 对节点编号对节点编号V = v1, v2, , vn.其中其中pij= 1, 若若vi可达可达vj, 否则否则pij= 0, i, j = 1, 2, , n.nnnnnnpppppppppGP.)(211222111211例例6-7(continue)1v2v3v4v5v111111111
48、1111111111111111P容易由图的邻接矩阵得出其可达矩阵容易由图的邻接矩阵得出其可达矩阵,一个非一个非常有效的算法是常有效的算法是Warshall算法算法. 根据我们的可根据我们的可达矩阵的定义知达矩阵的定义知, 中所有主对角线上的元素全中所有主对角线上的元素全为为1, 这是由于任意节点可达自身所致这是由于任意节点可达自身所致.更容易从图的可达矩阵得出图的连通性质更容易从图的可达矩阵得出图的连通性质.3.图的关联图的关联(incidence)矩阵矩阵第三种图的矩阵表示第三种图的矩阵表示关联矩阵关联矩阵,它表示的是它表示的是图中节点与边之间的关联关系图中节点与边之间的关联关系.(1)无
49、向图无向图Def 无向图无向图G = (V, E), 对节点编号对节点编号V = v1, v2, , vn, 对边编号对边编号E = e1, e2, , em.其中其中mij是是vi与与ej的关联次数的关联次数, i, j.,)(mnijmGM1v1v2v2v3v3v4v4v1G2G,110001011000110010021e1e2e2e3e3e4e4e5e5e.11000101100011101001(2)有向图有向图Def 无自环无自环(loop)有向图有向图G = (V, E), 对节点对节点编号编号V = v1, v2, , vn, 对边编号对边编号E = e1, e2, , em:
50、例子例子?图与其关联矩阵是一一对应的图与其关联矩阵是一一对应的.,)(mnijmGM., 0, 1, 1不关联与的终点是的起点是jijijiijevevevm精品课件精品课件！精品课件精品课件！图还有其他矩阵表示图还有其他矩阵表示,如距离矩阵、圈矩阵以如距离矩阵、圈矩阵以及割集矩阵等及割集矩阵等,参考有关文献参考有关文献. 前面已经谈到前面已经谈到,有了这些图的矩阵表示有了这些图的矩阵表示,可以用线性代数中的可以用线性代数中的知识知识,特别是矩阵理论对图做更深入的研究特别是矩阵理论对图做更深入的研究,由由于篇幅所限于篇幅所限,本书不涉及这些内容的进一步讨本书不涉及这些内容的进一步讨论论,可参见
