7图论1(部编)课件

图的基本概念7.1

图的矩阵表示7.3欧拉图与哈密顿图7.4

目录第七章图论树7.5

图的连通性7.2

图的基本概念一

多重图与带权图三

图中结点的度数二

7.1图的基本概念第一节图的基本概念7.1图的基本概念

图论起源于1736年欧拉(Enler)的第一篇图论论文,解决了“哥尼斯堡的七桥问题”.

陆地岛屿岛屿陆地哥尼斯堡七桥问题如何不重复地走完七桥后回到起点？

。。。。ABCD7.1图的基本概念图论起源7.1图的基本概念

当时人们热衷于这样的游戏：设想从任一个地方出发通过每座桥一次且仅一次后回到原地,这是否可能?但多次实践都发现不行。

1727年欧拉的朋友向欧拉提出了这个问题是否有解？1736年欧拉用图论的方法解决了这个问题，写了第一篇图论的论文，成为图论的创始人。后来称此问题为哥尼斯堡七桥问题。图论起源7.1图的基本概念

图论在理论上和应用上都得到很大的发展,特别是在近30多年来由于计算机的广泛应用而又得到飞跃的发展。在计算机科学、运筹学、化学、物理和社会科学等方面都取得了不少成果，对计算机学科中的操作系统研究、编译技术、人工智能和计算机网络等方面都有广泛的应用。图论是一个应用十分广泛而又极其有趣的数学分支。物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹。本章主要介绍图论的一些基本知识、图论中常用的初等方法。图论在抽象理论和具体编程之间为同学们架设一座桥梁。为了让大家知道图论主要讲些什么，我们先举几个例子。图论概述7.1图的基本概念

【引例1】

考虑一张航线地图，图中用点表示城市，当两个城市间有直达航班时，就用一条线将相应的点连接起来。这种航线地图的一部分如下图所示．长春北京成都武汉上海7.1图的基本概念图论引例

【引例２】

我们把图7—1看成是一个公路网，网V1,V2,…,V10是一些城镇,每条线旁边的数字代表这一段公路的长度。现在问要从V1把货物运到V10走哪条路最近？

这个问题通常叫做最短路径问题。这是一个有很大现实意义的问题,它不仅出现在各种运输问题中,而且在电路设计等问题中也有用。

因为这种问题研究的是从V1到V10的所有路径中,哪一条路最短?因此它是一个极大极小问题,即极值问题,而它又和一个“图”密切联系着,因此这种问题就叫做图论中的极值问题。图7-17.1图的基本概念

这类问题称为图的连通性问题。图7-1

【引例３】还是把图7—1看成公路网,V1,V2,…,V10看成公路网的站点,若这个公路网目前被敌方占领。请分析一下,能否仅破坏其公路网的一个站点或者至少破坏敌人哪几个站点，就可摧毁敌方整个运输线。

如果公路网,任意两个站点之间互相可达,这样的图称作连通图。一旦删去一些(或一个)点以及和它们关联的边时,这张图就不再成为一张完整的连通图了。军事指挥中这类问题就很多。7.1图的基本概念图论引例

※【例3】

飞行大队有若干个来自各地的驾驶员,专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员。由于种种原因,例如相互配合的问题，有些驾驶员，不能在同一架飞机上飞行，问如何搭配驾驶员才能使出航的飞机最多？图7-2

为简单起见,假设有10个驾驶员,图7-2中的V1,…，V10就代表这10个驾驶员。如果两个人可以同机飞行,就在代表他们两个之间连一条线;两个人不能同机飞行,就不连。7.1图的基本概念图论引例

上面问题就成为:如何找一个包含最多线的匹配?这个问题叫做图的最大匹配问题。请大家试试看，能不能从图7—2中找出一个包含4条线的匹配，再试试能不能找到包含5条线的匹配。像上述例子那样,将实际生活中的事物分析转化为图论问题的实例还很多,这里就不多介绍了。

画了这个图后,就可以研究搭配飞行员的问题了。图7—2中画的3条粗线就代表了一种搭配方案。由于一个飞行员不能同时派往两架飞机。因此任何两条粗线不能有公共的端点,把一个图中没有公共端点的一组线叫做一个“匹配”.

假设有一群人和一组工作，这群人中的某些人能够做这组工作中的某些工作。例如，有3个人A、B和C，3件工作D、E和F.假设A只能做工作D，B能做工作E和F，C能做工作D和E。则这种情形可用下图表示，其中，在人和这个人能够做的工作之间画有线段。ACFDBE7.1图的基本概念

图是一个包含有限的点（称之为结点）和连接一对顶点的线段（称之为边）。

用图形表示一组对象，其中有些对象是有联系的，有些也是没有联系的．同一个图形也可以表示不同的含义。例如，引例２中的图，即可以表示从V1把货物运到V10走哪条路最近的问题，又可以表示公路网的运输线摧毁的最少站点问题．对于这种图形，我们感兴趣的只是有多少个点和哪些结点之间有线连接，至于连线的长短曲直和结点的位置却无关紧要，只要求每一条线都起始于一个点，而终止于另一个点。7.1图的基本概念7.1图的基本概念

图论研究的对象是图。什么是图？一个图一般用图形表示。它可以由两部分组成：一部分是一些点，我们称其为结点，如下图中的v1,v2,v3,v4诸点；另一部分是连接这些点的线，我们称其为边，如下图中的e1,e2,e3,e4,e5,e6,e7。

v4v2v3e1e3e2e4e5e6e7v1

图G是由非空结点集合V={v1,v2,…,vn}以及边集合E={e1,e2,…,en}所组成，其中每条边可用一个结点对表示之，这样的一个图G可表示为G=＜V，E＞观察下图7.1图的基本概念

【定义1

】

一个无向图G是一个二元组<V,E>，即G=<V,E>，其中

(1)V是有限的非空集合，称为顶点集,其元素称为结点或顶点．(2)E是以结点的无序对为元素的集合，称为边集,其元素称为无向边，简称为边．每条边可用一个无序结点对表示。即表示为一、图的基本概念

图的表示：用图形表示无向图时，常用小圆圈或实心点表示结点，用顶点之间的连线表示无向边.7.1图的基本概念

【例1】设，其中，

,

则G可用图表示为：7.1图的基本概念

【定义2】

一个有向图是一个有序的二元组<V,E>,记作D，

其中(1)V≠

，称为顶点集，其元素称为结点或顶点。(2)E称为边集，（它是笛卡儿积V×V的子集）,其元素称为有向边，简称为边。

用图形表示无(有)向图时，常用小圆圈或实心点表示结点，用顶点之间的连线表示无向边，用有方向的边表示有向边。每条边可用一个有序结点对表示。即表示为7.1图的基本概念

【例如】有四个程序：v1,v2,

v3,v4，它们间有一些调用关系：v1能调用v2，v2能调用v3，v2能调用v4，将此事实用图的方法表示之。v1v2v3v4e1e3e2有向图：图中所有的边均为有向边

【解】图中的结点集为

这个图可用D=<V,E>表示.

图中的边集为

7.1图的基本概念

注意到无向图与有向图集合表示的异同了吗？

【例2】画出下列图形。

(1)

G=<V,E>,其中V={v1,v2,v3,v4,v5},

E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),

(v1,v5),(v2,v5),(v4,v5)}。

(2)D

=<V,E>,其中V={a,b,c,d},

E={<a,a>,<a,b>,<a,d>,<d,a>,<b,c>,<c,b>,<c,d>}。7.1图的基本概念

【例3】

画出下列图形。（1）

G=<V,E>,其中V={v1,v2,v3,v4,v5},

E={(v1,v1),(v1,v2),(v2,v3),

(v2,v3),

(v1,v5),(v2,v5),(v4,v5)}.【解】（1）：作图如下e6e1v1v2v3v4v5e2e3e4e5e77.1图的基本概念【例3】

画出下列图形。(2)D=<V,E>,其中V={a,c,b,d},E={<a,a>,<a,b>,<a,d>,<d,a>,<b,c>,<c,b>,<c,d>}。adcbe1e2e3e4e5e6e7【解】（2）作图如下：7.1图的基本概念与图有关的概念和规定

设G=<V,E>为一有向图或无向图。(1)V、E分别表示G的顶点集、边集，|V|、|E|分别表示G的顶点数、边数。若|V|=n，则称G为n阶图。

(2)若|V|、|E|均为有限数，则称G为有限图。

(3)在图G中，若E=

，则称G为零图（即只有点没有边的图称为零图）．只有一个点的图称为平凡图。(b)零图(a)图7.1图的基本概念

【定义3】设G=<V,E>为无（有）向图，e=(u,v)(或e=<u,v>)是图的一条边，则称点u,v为边e的端点，边e关联于点u和v，也称点u或v关联于边e。

无边关联的顶点称为孤立点。若一条边所关联的两个顶点重合，则称此边为环。

若边e=(u,v)且u=v，则称边e与点u的关联次数为2；

若边e=(u,v)且uv，则称边e与点u的关联次数为1；

若边点u，v不是边e的端点，则称边e与点u的关联次数为0；与同一条边e关联和两个结点u和v称为是相邻的若e=<u,v>为有向边，则称点u邻接到v，v邻接于u．7.1图的基本概念

【解】

边e2与点v1，v2的关联次数均为1，边e1与点v2的关联次数为2。边e1与V4的关联次数为０.v1v2v3v4v5e1e2e3e4e5e6【例4】指出下图中，各边与点关联的次数。v5是孤立点，e1是环.7.1图的基本概念

【解】下图中，e2=<v1，v2>，点v1是边e2的始点，点v2是e2的终点，点v1邻接到v2，点v2邻接于点v１，边e1与边e2相邻.

【例5】观察下图：指出边与边的邻接，边与点的邻接，点与点的邻接。7.1图的基本概念

【定义４】

设G=<V,E>为一无（有）向图，点ｕ∈V,所有与点ｕ

关联的边的条数，称为点ｕ的度数，简称为度，记作d(ｕ).

设D=<V,E>为一有向图，

ｕ∈V,以点ｕ为起点的边的条数,称为点ｕ的出度,记作d+(ｕ);以点ｕ为终点的边的条数,称为ｕ的入度，记作d-(ｕ);称d+(ｕ)+d-(ｕ)为点ｕ的度数，记作d(ｕ).

称度数为1的顶点为悬挂点,它所对应的边为悬挂边.二、

图中结点的度数

【注意】图中每一条边对应的度数为２.约定：每个环在其对应结点上的度数增加２7.1图的基本概念

【例6】

在下图(1)中，指出各点的度数:

d(v1)=4,d(v2)=4,

d(v3)=3,d(v4)=1,d(v5)=0。在图(2)中，指出各点的度、出度和入度.

d+(v1)=2，d-(v1)=1，d(v1)=3,

d+(v2)=1，d-(v2)=3，d(v2)=4，……v1v2v3v4v5e1e2e3e4e5e6v1v2v3v4v5e1e2e3e4e5e6e7e8(2)(1)7.1图的基本概念

【定义5】在图G中,令△(G)=max{d(v)|v∈V}，

(G)=min{d(v)|v∈V

},△(G)和

(G)分别称为G的最大度和最小度。分别简记作7.1图的基本概念在图（２）中，最大度△=4,最小度

=2，最大出度△+=3,最大入度△-=3，最小出度

+=1,最小入度

-=0.(2)

【解】在图(1)中,最大度△=4,最小度

=0,

【例7】在图(1)中,最大度△和最小度

是多少？在图(2)中,最大度、最小度与最大出度、最大入度及最小出度？7.1图的基本概念

【解】(1)d(b)＝6,△＝6,

＝2.

【实训】求下列图中指定结点的度。(1)d(b),△,.abcd(1)(2)(2)d+(v3)=3,d-(v3)=2,△=5,=3,△+=3,

+=1,△-=2,

-=2。(2)d+(v3),d-(v3),△,,△+,

+,

△-,

-.

7.1图的基本概念

【定理1】（握手定理）

设G=<V,E>为无向图或有向图，V={v1,v2,…,vn},|E|=m(m为边数),则

【证明】图G中每条边（包括环）均提供2个端点，故在计算各顶点度数的和时，每条边均提供2度，m条边共提供2m度。因此在一个图中，节点度数的总和等于边数的2倍。=2m（即每个顶点度数之和等于边数的2倍）

【推论】

任何图(无向或有向)中，度为奇数的顶点个数为偶数。【例如】设图G为下列情况：(1)16条边，每个顶点都是2度；(2)21条边，3个4度顶点，其余均为３度顶点；试求每个图有几个节点？【解答】利用握手定理，设图Ｇ有x个顶点，则（1）２x=16*2,x=16.（2）21*2=12+3*x,x=10.握手定理的应用7.1图的基本概念7.1图的基本概念

设V={v1,v2,…,vn}为图的顶点集,称(d(v1),d(v2),…，d(vn))为G的度数序列.

【例11】

在下图中指出各图的度数序列：【解】图①中的度数序列为（4,4,3,1,0).图②中的度数序列为（3,4,3,4,2).7.1图的基本概念

【定理2】（握手定理）

设D=<V,E>为任意有向图，V={v1,v2,…,vn},|E|=m,则

【证明】D中每条边（包括环）均关联两个顶点，即1个出度和1个入度，m条边则提供m个出度，m个入度，共2m度。故在计算各顶点度数的和时，每条边均提供2度，

定理表明：任何有向图中，各顶点的出度之和等于各顶点的入度之和，且都等于边数．7.1图的基本概念

※【例12】

①(3,3,2,3),(5,2,3,1,4)能成为图的度数序列吗？为什么？②已知图G中有10条边,4个3度顶点,其余顶点的度数均不大于2,问G中至少有多少个顶点?为什么？

【解】①由于这两个序列中,奇数个数均为奇数,由握手定理的推论知,它们都不能成为图的度数序列。②图中边数m=10,由握手定理可知,G中各顶点度数之和为20，4个3度顶点占去12度，还剩8度,若其余全是2度顶点,还需要4个顶点来占用这8度，所以G至少有8个顶点。7.1图的基本概念考察下列各图的度序列、出度序列及入度序列.

【答案】(1)度序列：2,6,3,3.(2)度序列：4,3,5,4.出度序列：1,2,3,2.入度序列：3,1,2,2.abcd（1）（2）7.1图的基本概念

【例4】

证明在

个人的集体中，总有两个人在此团体中恰有相同数量的朋友．【解】

以结点代表人，两人如果是朋友，则在代表他们的结点间连上一条边，这样可得无向简单图G．每个人的朋友数即是图中代表他的结点的度数，于是问题转化为：n阶无向简单图G必有两个结点的度数相同．7.1图的基本概念e1v1v2v3v4v5e2e3e4e5e6

【定义6】(1)在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。例如，在上图中e4

与e5

是平行边.三、

多重图与带权图7.1图的基本概念v1v2v3v4v5e1e2e3e4e5e6e7e8

【定义6】(2)在有向图中，关联一对顶点且方向相同的有向边如果多于1条，则称这些边为平行边。

例如，在上图中e3与e4是平行边,e7与e8不是平行边（因为e7与e8方向不同）.7.1图的基本概念

【思考】

n阶无向完全图Kn的边数？

【定义7】(1)设G为n阶无向简单图，若任何两个结点之间恰有一条边相连（若G中每个顶点均与其余的n-1个顶点相邻），则称G为n阶无向完全图，简称n阶完全图，记作Kn(n≥1)。常见的完全图如下：K6

【答案】m=n(n-1)/2.7.1图的基本概念。a。be。d。c。

含平行边的图称为多重图．

既不含平行边,也不含环的图称为简单图.简单图多重图7.1图的基本概念常见的完全图【思考】n阶有向完全图的边数.

【定义7】（2）

设D为n阶有向简单图，若D中每个结点都邻接到其余的n-1个结点，又邻接于其余的n-1个结点，则称D为n阶有向完全图。【答案】n(n-1).7.1图的基本概念

【定义8】

设G=<V,E>,G′=<V′,E′>为两个图(同时为无向图或有向图)，若V′

V且E′

E，则称G′为G的子图，G为G′的母图，记作G′

G。若G′G且G′≠G(V′

V或E′

E)，则称G′为G的真子图。

若G′G且点集V′=V，则称G′为G的生成子图。

若V1

V且V1≠,以V1为顶点集,以两端点均在V1中的边的全为边集的G的子图,称为点集V1导出的导出子图。若E1E且E1≠,以E1为边集,以E1中的边关联的结点的全体为结点集的G的子图,称为边集E1导出的导出子图.7.1图的基本概念abcdd1a1b1c1abcdd1b1母图G真子图V'V或E'E生成子图G'G且V'=V导出子图V'V或E'

Eabcdd1a1b1c1abcda1b17.1图的基本概念

【答案】图(2),(3)均是(1)的子图。

图(2)是顶点集

v1,v2的导出子图，图(2)也是边集

e4,e5的导出子图,图(3)是边集

e1,e3,e4的导出子图,

图（3）也是（1）的生成子图。v1v2v3v4v1v2v1v2v3v4e1e2e3e4e5e4e5e1e3e4(1)(2)(3)

【例7】

在下三图中,指出各图之间的关系。7.1图的基本概念图(5)，(6)均是(4)的子图。

图（5）也是边集

e1,e3的导出子图。(6)是边子集

e1的导出子图。v1v2v3v1v2v2e1e3e4e3e1(4)(5)(6)e2v3v1e1图(5)是图（4）生成子图

※【例７】

在上图中,【注意】每个图都是本身的子图。7.1图的基本概念图(1)是图(2)的补图。

(1)

（2)

Ｇ

【定义８】设G=<V,E>为n阶无向简单图，则以V为顶点集，以使G成为ｎ阶完全图而添加的边为边集的图，称为G的补图，记作.如下图所示：7.1图的基本概念(1)abdce1e2e3e4e5e6cbde3e4e5(2)(3)母图同时也是(1)的生成子图子图、真子图V={b,c,d}E={e3,e4,e5}子图、真子图生成子图E={e2,e3,e4,e5}cabde3e4e5e2※【例８】判断下列各图的母子关系。7.1图的基本概念

【定义12】

设G1=<V1,E1>,G2=<V2,E2>为两个无(有)向图，若存在双射函数f:V1→V2,对于任意的e1=(u,v)e2=(f(v),f(v))

，并且边e1与e2重数相同，则称G1与G2是同构的，记作G1≌G2

。

也就是说:两个图G1=<V1,E1>,G2=<V2,E2>,如果它们的结点间存在一一对应关系（双射），而且这种对应关系也反映在表示边的结点对中,(如果是有向边则对应的结点对还保持相同的顺序),则称此两图是同构的。7.1图的基本概念

【解】(1)是(2)的补图,当然(2)也是(1)的补图,就是说,(1),(2)互为补图.同样,(3),(4)互为补图.

(1)(2)(3)(4)【例９】在下图中,哪两个图互为补图？

7.1图的基本概念如何判断两个图是否同构呢？答案：迄今为止还没有有效的算法。(没有找到两图同构的充要条件）根据定义，若两个图同构，则它们(1)结点数目相等，(2)边数相等，(3)度数相同的结点数目相同。但这仅仅是G1≌G2的必要条件。三

多重图与带权图7.1图的基本概念若图的每一边对应一个非负实数，这样的图叫带权图．该实数叫相应边的权．【注意】带权图中各边的权数可以是正数、负数或零．三

多重图与带权图

路与回路一

有向图的连通性三

无向图的连通性二

7.2图的连通性第二节图的连通性

图的连通性是图的最基本、是最重要的性质。如果我们将图设想成公路网或通讯网的话，这将有助于理解关于图的真实涵义.7.2图的连通性一、路与回路7.2图的连通性一、路与回路

在一条路中，若所有的边互不相同，则称其为简单路；

若所有结点互不相同（当然边也不相同），则称其为初级路（或基本路）．

（1）adcfe是长度为4的简单路.

（2）abedab是长度为5的路，但不是简单路.问：deca是不是图中的一条路？观察图中的路和简单路？7.2图的连通性

开始和结束是同一点的路称为回路.

若回路中出现的所有的边互不相同，则称其为简单回路；

若简单回路中除起点和终点相同外，其余结点均不相同，则称其为初级回路（或圈）．

（1）bcfeb是长度为4的简单回路.

（2）adcfba是长度为5的简单回路.【问题】aefbea是不是图中的一条回路？

（3）adcfea是长度为5的初级回路.7.2图的连通性7.2图的连通性

图(3)为v1到v1的长为6的简单回路.在有向图中,环和两条方向相反边构成的回路分别为长度为1和2的初级回路.图(3)为v0

到v5

(=v0)的长为5的初级回路.图(1)为v0

到v4的长为4的初级路.图(2)为v0到v8的长为8的简单路.【问题】提出下列各图中的初级路、简单路与初级回路.7.2图的连通性

【问题】考察下图中开始于结点1结束于结点3的路：1234P1:(1,2,3),P2:(1,4,3)P3:(1,2,4,3)P4:(1,2,4,1,2,3)P5:(1,2,4,1,4,3)P6:(1,1,2,3)

【答案】P5是简单路但不是初级路。P1,P2,P3是初级路,(当然也是简单路）.

指出上列六条路中，哪些是简单路，初级路？一条初级通路一定是简单通路,反之不然.7.2图的连通性

【问题】指出下列六条路中的回路，简单回路，初级回路？1234C1:(1,1),C2:(1,2,1)C3:(1,2,3,1)C4:(1,4,3,1)C5:(1,2,3,2,1)C6:(1,2,3,2,3,1)

【答案】C1,C2,C3,C4是初级回路,(当然也是简单回路),C5是简单回路但非初级回路,C6

是回路，但既非初级回路亦非简单回路.7.2图的连通性

【例1】（1）请判断下列4种路况,将左边的路与右边答案连线，并指明其长度.

v1v3e4

。。。。。v2v4v5e1e2e3e5e6e7

v1e1v2e6v5e4v4e7v2

v1e1v2e2v3e3v4e7v2e6v5e5v1

v1e5v5e6v2v1e1v2e7v4e4v5e5v1v1到v2的简单通路v1到v2的初级通路v1到v1的简单回路v1到v1的初级回路7.2图的连通性(e2),(e3,e4,e2),(e3,e5,e6,e10,e2),

路(e3,e5,e6,e7,e1)是从C到B的4个有向路.这4条有向路只有第一条，第四条是初级的.ABCDEFe1e2e3e4e5e6e7e9e8e10

C到c的回路：(e3,e4),(e3,e5,e6,e10),(e8),(e9)是4条有向回路;有向图G中,从B到其它任意点都没有有向路.

【例1】（2）在下图中,求C到B的通路和C到c的回路,要求各找出4个以上.C到B的通路有：7.2图的连通性

【例2

】“摆渡问题”：一个人带有一条狼、一头羊和一捆白菜，要从河的左岸渡到右岸去，河上仅有一条小船，而且只有人能划船，船上每次只能由人带一件东西过河．另外，不能让狼和羊、羊和菜单独留下．问怎样安排摆渡过程？

【解】将安全摆渡过河问题转化成图论问题，即可得到狼羊菜的安全摆渡模型．

注意这里的狼和菜是可以单独在一起的。河左岸允许出现的情况有以下10种情况（或状态）：人狼羊菜、人狼羊、人狼菜、人羊菜、人羊、狼菜、狼、菜、羊及空（各物品已安全渡河），我们把这10种状态视为10个点，若一种状态通过一次摆渡后变为另一种状态，则在两种状态（点）之间画一线段，得到下图.7.2图的连通性【例2】

这样摆渡问题就转化成在图中找出以“人狼羊菜”为起点，以“空”为终点的简单路．可看出，只有两条简单路符合要求，即：

（1）人狼羊菜、狼菜、人狼菜、菜、人羊菜、羊、人羊、空；

（2）人狼羊菜、狼菜、人狼菜、狼、人狼羊、羊、人羊、空．7.2图的连通性【例2】摆渡方案一人狼羊菜人狼菜人羊菜人羊人狼羊菜狼菜狼羊河右岸河左岸狼羊羊菜羊

对于简单路（1）的安排为：人带羊过河；人回来；带狼过河；放下狼再将羊带回；人再带菜过河；人回来；带羊过河．7.2图的连通性【定理1】在一个图中，若从U结点V到存在一条路，则必有一条从U到V的初级路．7.2图的连通性二、无向图的连通性v3

。。。。。v1e4v2v4v5e1e3e5e6e7v3

。。。。。v1v2v4v5e1e3e5e6连通图非连通图7.2图的连通性

【问题】判定下列图的连通性(下图是连通图还是非连通图)v1v2v3v5v4v1v2v3v4v5v6v1v2v3v4v5v6

图3则是非连通图，因为结点v1,v2,v3与结点v4,v5,v6间是不存在路.【答案】图1和图2均是连通图.图1图2图37.2图的连通性v3

。。。V1

v2v3

。。。。。v1e4v2v4v5e1e3e5e6e7图1v3

。。。。。v1v2v4v5e1e3图2图3

在无向图中,顶点之间的连通关系是等价关系,对于非连通图G，称相互连通部分中的结点构成的的子图,称为G的连通分支，连通分支数个数记为p(G).

例如:下列图的连通分支数分别为:1，3，3.若G中只有一个连通分支（即p(G)=1），则是连通图.7.2图的连通性

割点:

如果在图G中删去结点v(及与其相关联的所有边后),图G的分图数增加,则称结点v是G的割点.

图(1)是连通图,只有一个图.在去掉结点v6(及与v6相关联的边)后,图(1)就出现两个分图,成为图(2).