第七章 图的基本概念.ppt

1、第七章：图论的基本概念，图论的起源可以追溯到18世纪。数学家欧拉在1736年发表了第一篇关于图论的论文，解决了著名的哥尼斯堡七桥问题。然而，直到20世纪中后期，特别是随着计算机科学技术的发展，图论的理论研究和应用研究才得到广泛的关注，图论作为数学的一个重要分支，真正确立了自己的地位。图论内容丰富，是一门交叉的、应用广泛的学科。计算机科学、网络理论、信息论、运筹学、语言学、物理学、化学等。都被用作解决理论和实践问题的工具。离散数学研究的图形是不同于几何图形和机械图形的另一种数学结构。它不关心图中顶点的位置、边的长度和形状，只关心顶点和边之间的连接关系。目录7.1无向图和有向图7.2路径、电路和图

2、的连通性7.3表示7.4最短路径问题和关键路径的图的矩阵7.1无向图和有向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7.2无向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7.1无向图7无向图7.1无向图7无向图7无向图7无向图7无向图7无无向图，元素可以重复出现的集合是多集的，例如：G=，V=V1，V2，V3，V4，V5，E=(V1，V2)，(V2，V2)，()(2)E是笛卡儿积的一个多重子集，它的元素称为有向边，简称为边。有时用V (d)和E (d)分别表示图D的顶点集和边集。例如：D=，V=v

3、1，v2，v3，v4，v5，E=，G的图形是：E5，V5，v4，v3，v2，v1，E4，E3，E2，E1，E6，那么G被称为N阶图(3)。特别是，如果此时有V1，G就叫做平凡图。5阶图，零图，平凡图。定义7.3设ek(vi，vj)为无向图G中的边，称vi，vj为ek、ek和vi(或vj)的端点ek和vi(或vj)之间的关联次数，1，vi(vj)为ek、vivj的端点，2，vi(vj)为ek和vivj的端点，0，vi(vj)不是ek的端点，定义7.4设无向图G=，vi，vjV，ek，elE。(1 Vj彼此相邻，称为“相邻”。(2)如果ek和E1具有至少一个公共端点，则ek和E1彼此相邻，这被称为

4、“相邻”。对于像ekvi和vj这样的有向图，除了vi和vj是ek的端点之外，vi是ek vi的起点，VJ是ek的端点，并且vi与VJ相邻。E2、E1、E6、E7、E8、定义7.5设G为无向图，viV，vi为边的端点的次数之和称为vi的度数，简称为d(vi)。度数为1的顶点称为悬挂顶点，称为有向图vjV，vj是边起点的次数之和为vj的度数，记为D(VJ)；调用vj作为边的端点的次数之和是vj的穿透，记录为d-(VJ)；将vj作为边的端点的次数之和是vj的度数，称为d(vj)。显然d(vj)d (vj)d-(vj)。d(v1)3，d (v1)2，D-(V1)1；d(v2)3，d (v2)2，d-(

5、v2)1；d(v3)5，d (v3)2，d-(v3)3；d(v4)d(v4)d-(v4)0；d(v5)1，d (v5)0，d-(V5)1；其中v5是悬挂节点和悬挂边。例如，对于图g，记住(g) maxd (v) vv和(g) mind (v) vv，它们分别被称为g的最大度和最小度。如果DV、E和E是有向图，除了(D)、(D)外，还有最大出图度、最大入图度、最小出图度和最小入图度，它们分别定义为：定理7.1(握手定理)将图G设为无向图或有向图，Vv1，V2，VN，| E |=M(.V2，vn，Em，让Vv1，v2，vn是图G的顶点集，并调用(d(v1)，d(v2)，G (4，4，3，1)的度序

6、列为什么？不，通过握手定理很容易知道。(2)已知图G有10条边和4个3度的顶点，其他顶点的度数都小于或等于2。G中至少有多少个顶点？为什么？答：至少有8个顶点。定义7.6在无向图中，如果一对顶点有一条以上的无向边，这些边称为平行边。平行边的数量叫做多重性。在有向图中，如果有多个有向边与一对顶点相关联，并且它们的起点和终点相同，这些边简称为有向平行边。有平行边的图叫做多重图。它们既不包含平行边也不包含平行边。E3和e4是平行边，e7和e8不是平行边。定义7.7让G=是一个N阶无向简单图。如果G中的任何一个顶点与其他n-1个顶点相邻，G称为N阶无向图，表示为Kn。设D=是一个N阶有向简单图。如果任

7、何顶点u，vV(uv)都有两个有向边，则称它为d。图(1)显示K4，(2)显示K5，(3)显示三阶有向完全图，例如，(1)、(2)、(3)，定义7.8，让G=，G=是两个图。如果VV和EE，那么G是G的子图，G是G的G，G是G的生成子图，如果GG和v=v。让V1V，V1，把V1作为顶点集，把V1两端的所有边作为边集，称为V1导出子图。设E1 E，E1为边集，E1导出的g的子图与E1的所有相关顶点为顶点集，称为E1导出的子图。g是节点集v1、v2、v4、V5和V6的派生子图。，例如，(1)、(2)、(3)、(6)、(5)、(4)，定义7.9让G=是一个N阶的无向简单图，以V为顶点集，以及所有能使

8、G成为完全图Kn的加法。图(a)、图(b)、图(c)和图(d)所代表的数字实际上是相同的。，B，D，C，D，C，B，A，D，C，B，A，D，C，B，A，图(A)，图(B)，图(C)，图(D)，定义7.10让两个无向图G1=，G2=，如果有两个，那么G1和G2被认为是同构的，这被表示为G1G2。(1)(2)，并且顶点之间的对应关系是AV1、BV2、CV3、DV4、EV5。，(一)叫做彼得森图。(1)、(2)、(3)、(2)画出所有可能的具有3个顶点和2条边的非同构有向简单图。(1)，(2)，(3)，(4)，7.2路径，回路，图连通性，定义7.11给定的图G。让G中的顶点和边的交替序列为。要求vi

9、-1是ei的起点，vi是ei的终点。)，I1，2和1被称为从顶点v0到v1的路径。v0和v1分别称为该路径的起点和终点，中间边的数量称为长度。当v0vl时，该路径称为环路。如果其中的所有边E1、E2和E1彼此不同，则称为简单路径或轨迹。这个电路被称为简单电路或闭合轨迹。如果一条路径的所有顶点v0、v1、vl彼此不同(因此所有边彼此不同)，那么这条路径被称为初级电路或环路。如果除v0vl之外的所有边沿都不同，则该电路称为初级电路或环路。具有重复边的路径称为复杂路径。例如：v1、v0、v4、v2、v3、V5、v8、V6、V7、v1、v0、v4、v2、v3、v1、v0、v4、v2、v3、v1、v0、

10、v4，(3)从v0到v8长度为8的简单路径，(4)从v0到V8长度为8的简单路径。定理7.3在一个N阶图中，如果有一条从顶点vi到vj(vivj)的路径，则有一条长度小于或等于n-1的路径。在一个N阶图中，如果从顶点vi到vj (vivj)有一条路径，那么从vi到vj就有一条长度小于或等于n-1的主路径。定理7.4在一个N阶图中，如果从vi到它自己有一个长度小于或等于N的环，那么可以推断在一个N阶图中，如果从vi到它自己有一个简单的环，那么从vi到它自己就有一个长度小于或等于N的主环。定义7.12在无向图G中，如果从顶点vi到vj有一条路径(当然，从vj到vj也有一条路径)，那么vi和vj是连

11、通的。在有向图D中，如果从顶点vi到vj有一条路径，那么vi可以到达vj。它规定虚拟仪器总是能够到达它自己。捷径(无向图)，设vi和VJ为无向图g中的任意两点，则vi和vj之间的最短路径称为vi和vj之间的最短路径，其长度称为vi和vj之间的距离，记录为d(vi，vj)。设vi和vj是有向图d中的任意两点。如果vi能到达vj，则从vi到vj的最短路径称为vi到vj的最短路径，其长度称为vi到。如果VI不能到达vj，则规定d. d具有以下性质： (1) d 0。当vivj，等号成立。(2)它满足三角形不等式，即d，d，d。在无向图中，有对称性，即d(vi，vj)d(vj，vi)。连通图(无向图)

12、，定义否则，g称为非连通图。在无向图中，顶点之间的连通性是等价的。设G为无向图，r为G中顶点间的连通性。根据r，V(G)可分为k(k1)个等价类，表示为v1、v2和vk，由此导出的子图gv1、gv2和gvk称为G的连通分支。G2为非连通图，p(G2)为3。，G1，G2，例如，连通图(有向图)，定义7.14让D是有向图。如果通过省略D中每个有向边的方向而得到的无向图G是连通图，那么D被称为连通图或弱连通图。如果D中任意两个顶点中至少有一个可以到达另一个，那么D被称为单向连通图。如果D中的任意一对顶点是相互的。图b是单向连通图；图c是一个强连通图。图A，图B，图C，定义7.15让一个无向图G，如果

13、有一个顶点子集VV，让G删除在V中的顶点和它们相关的边)，得到的子图GV和G的连通分支满足p(G-V)p(G)，并且在删除V的任何合适的子集V之后，p(G-V)p(G)，如果有边集E的子集E，在G删除E之后(E中的所有边都从G中删除)， 所获得的子图和G的连通分支满足p(G-E)p(G)，但是在删除E的任何适当子集E之后，p(G-E)p(G)，则E是G的边割集。如果只有一个边割集，V5，E8，V6，V7，v1，v4，v2，v3，E1，E2，E3，E4，E5，E6，E7，e9。在本节中，概念：是无向图，有向图，N阶图，零图，平凡图度d-(vj)，握手定理及其推论，度序列，简单图，N阶无向图，完全图，子图，父图，生成子图等无向图的关联矩阵有向图的关联矩阵有向图的邻接矩阵无向图的可达矩阵，设无向图G，Vv1，V2，VN，EE1，E2，em，设mij为顶点vi与边ej之间的关联数，则(mij)nm为G的关联矩阵，表示为M (G)，mij， ej (