《第讲图的有关概念节点的度数》由会员分享，可在线阅读，更多相关《第讲图的有关概念节点的度数（32页珍藏版）》请在金锄头文库上搜索。
1、第14讲 图的有关概念, 节点的度数n主要内容:n1.图的有关概念.n2.节点的度数.n3.子图与图的同构.Chapter 7 图论n图论的创始人是瑞士数学家L. Euler，他于1736 年首次建立“图”模型解决了Kningsberg七桥问 题. n图论的应用领域非常广泛，它已经渗透到诸如语 言学、逻辑学、物理学、化学、电信工程、信息 论、控制论、经济管理等各个领域，特别是在计 算机科学中的数据结构、计算机网络、计算 机软件、算法理论、操作系统、分布式系 统、编译程序以及数据挖掘等方面都扮演着 重要角色. 7.1 图的基本概念n哥尼斯堡(Kningsberg)七桥问题: n问题是: 是否可从
2、某一个地方出发，经过七座桥，每座桥 只经过一次，然后又回到原出发点. n程序调用的图论模型:ne8: v3可调用v2; e1: v2可调用v1; e4: v5可调用v5 自身. 单行道; 好感?n1.图的定义n由前面的2个例子可以得出nDefinition 图G(graph)主要由2部分组成:n(1)节点集合V, 其中的元素称为节点(vertex 或node).n(2)边集合E, 其中的元素称为边(edge).n通常将图G记为G = (V, E).n几点说明:n(a)节点又可以称为点、顶点或结点,常用一 个实心点或空心点表示,但在实际应用中还 可以用诸如方形、圆形、菱形等符号,为了 方便可以在
3、这些符号的旁边或内部写上表 意名称. (计算机学科中常称节点.)n(b)边及其的表示. 无向边? b3 = AB = BA =A, B(可重). 有向边(弧)?n所有边都是无向边的图称为无向图(graph, undirected graph),所有边都是有向边的图称 为有向图(digraph, directed graph).n(c)图的拓扑不变性质. 需要注意的是,我们讨 论的图不但与节点位置无关,而且与边的形 状和长短也无关.n有n个节点的图称为n阶(order)图,有n个节点 m条边的图称为(n, m)图. n在图G = (V, E)中, 称V = 的图为空图 (empty graph)
4、, 记为, 若 V 但E = 的图 称为零图(discrete graph), n阶零图可记为Nn, 仅一个节点的零图称为平凡图(trivial graph).n2.邻接nDef 设G = (V, E)是图, 对于任意u, v V,若从 节点u到节点v有边, 则称u邻接到(adjacent to) v或称u和v是邻接的(adjacent).n无向图?n有向图?n(无向图的两条边邻接是指它们有公共端点.)n3.关联nDef 设G = (V, E)是图, e E, e的两个端点分 别为u和v, 则称边e与节点u以及边e与节点v 是关联的(incident).n显然,图的任意一条边都关联两个节点.
5、关联 相同两个节点的边称为吊环,可简称环(loop) .关联的起点相同与终点也相同的边称为多 重边(multiple edges)或平行边,其边数称为边 的重数(multiplicity).n例子见书Figure 7-4(a)(b).n4.简单图n(1)简单图nDef 设G = (V, E)是图, 若G中既无吊环又无 多重边,则称G是简单图(simple graph).n简单图的例子?n彼得森(Petersen, 18311910)图, 它是一个有 着特殊性质的简单图, 后面会多次出现. n(2)完全无向图nDef 设G = (V, E)是n阶简单无向图, 若G中 任意节点都与其余n - 1个
6、节点邻接, 则称G 为n阶完全无向图(complete graph), 记为Kn.nK5:n n将n阶完全无向图Kn的边任意加一个方向所 得到的有向图称为n阶竞赛图.n(3)补图nDef 设G = (V, E)是n阶简单无向图,由G的所 有节点以及由能使G成为Kn需要添加的边构 成的图称为G的补图,记为n(u和v在G中不邻接 u和v在 中邻接)7.2 节点的度数n边与节点的关联次数?nDef 设G = (V, E)是无向图, v V,称与节点v 关联的所有边的关联次数之和为节点v的度 数(degree),记为deg(v).n一个环算2度?nDef 设G = (V, E)是有向图, v V, 称
7、以v为起 点的边的数目为节点的出度(out-degree),记 为deg+(v),以v为终点的边的数目为节点的入 度(in-degree),记为deg-(v), 称deg+(v) + deg-(v) 为节点v的度数,记为deg (v). n一个环算2度?n下面的定理是L. Euler在1736年证明的图论 中的第一定理,常称为“握手(?)定理”.nTheorem 在任何(n, m)图G = (V, E)中, 其所 有节点度数之和等于边数m的2倍,即nCorollary 在任意图G = (V, E)中, 度数为奇数 的节点个数必为偶数.nProof n由定理及其推论很容易知道,在任何一次聚 会上
8、,所有人握手次数之和必为偶数并且握 了奇数次手的人数必为偶数.(环的解释?)n在任意有向图中,显然有nTheorem 在任意有向图中,所有节点的出度 之和等于入度之和.n在任意图中, 度数为0的节点称为孤立点 (isolated vertex), 度数为1的节点称为悬挂点 (pendant vertex).n例7-1(P200) 证明: 对于任意n(n 2)个人的 组里,必有两个人有相同个数的朋友.nProof 将组里的每个人看作节点,两个人是朋 友当且仅当对应的节点邻接,于是得到一个 阶简单无向图G,进而G中每节点的度数可能 为0, 1, 2, , n - 1中一个. n当G中无孤立点时,于
9、是每节点的度数可能 为1, 2, , n - 1. 由于共有n个节点,于是必有 两节点度数相同.n当G中有孤立点时,这时每节点的度数只可 能为0, 1, 2, , n - 2. 同样由于共n有个节点, 因此必有两节点度数相同.n若一个无向图G的每节点度数均为k, 则称G 为k-正则图(k-regular graph). n例子?n例7-2(P200) 设无向图G是一个3-正则(n, m) 图, 且2n 3 = m, 求n和m各是多少? nHint 根据握手定理有, 3n = 2m.nDef 7-9n任意图G = (V, E):n有向图G = (V, E):n例子?n对于无向图G = (V, E
10、), V = v1, v2, , vn,称 deg(v1), deg(v2), , deg(vn)为的度数序列. 对 于有向图, 还可以定义其出度序列和入度序 列.n例7-3 是否存在一个无向图G, 其度数序列分 别为n(1)7, 5, 4, 2, 2, 1.n(2)4, 4, 3, 3, 2, 2.nSolution (1)由于序列7, 5, 4, 2, 2, 1中, 奇数个 数为奇数, 根据握手定理的推论知, 不可能 存在一个图其度数序列为7, 5, 4, 2, 2, 1.n(2)因为序列4, 4, 3, 3, 2, 2中, 奇数个数为偶 数, 可以得到一个无向图(见图7-11),其度数
11、序列为4, 4, 3, 3, 2, 2.7.3 子图、图的运算和图同构n1.子图n可以通过一个图的子图去考察原图的有关 性质以及原图的局部结构.nDef 设G = (V, E)和H = (W, F)是图, 若W V 且F E, 则称H = (W, F)是G = (V, E)的子图 (subgraph). n若H = (W, F)是G = (V, E)的子图且W = V, 则 称H = (W, F)是G = (V, E)的生成子图 (spanning subgraph).n例7-4(一个图的子图较多)n常见的4种产生G = (V, E)的子图的方式如下:n(1)GW 设W V,则以W为节点集合,
12、以两 端点均属于W的所有边为边集合构成的子图 ,称为由W导出的子图(induced subgraph by W),记为GW.n(2)G W 设W V, 导出子图GV W记为 G W,是在G中去掉所有W中的节点,同时也 要去掉与W中节点关联的所有边. 通常将G v记为G - v.n(3)GF 设F E, 则以F为边集合,以F中边 的所有端点为节点集合构成的子图,称为由F 导出的子图(induced subgraph by F),记为 GF. n(4)G F 设F E,则从G中去掉F中的所有 边得到的生成子图记为G F.n简单图G = (V, E)的补图nG + U: (与子图无关)n2.图的运算
13、n图的运算就是通过一定的操作,产生“新”的 图. 前面的子图的产生实际上就是图的运算, 但它们都是在一个图中进行讨论的. 也便于 用代数方法讨论图.n在有些问题的讨论中,还会出现两个图之间 的一些运算. 我们在此仅给出定义,请参见有 关文献.nDef n(1)n(2)n(3)n(4)n思考 图的每种运算的性质有哪些? 它与集 合的并、交、差、(补)及环和(对称差)运算 的性质有什么不同?n3.图同构n由于图的拓扑性质, 有可能两个表面上看起 来不同的图本质上是同一个图, 这就是图同 构的问题.nDef(见书)n直观理解: G1 G2是指其中一个图仅经过下 列两种变换可以变为另一个图:n(a)挪动节点的位置；n(b)伸缩边的长短.n无向图:n不同构的例子P204 5.n有向图:对于两个有向图同构的判断, 特别要 注意边的方向的一致性. n思考 给出至少4个两个图同构的必要条件.nUlam猜想?
