第14讲 图的有关概念, 节点的度数 主要内容: 1.图的有关概念. 2.节点的度数. 3.子图与图的同构.

Chapter 7 图论 图论的创始人是瑞士数学家L. Euler，他于1736年首次建立“图”模型解决了Köningsberg七桥问题. 图论的应用领域非常广泛，它已经渗透到诸如语言学、逻辑学、物理学、化学、电信工程、信息论、控制论、经济管理等各个领域，特别是在计算机科学中的数据结构、计算机网络、计算机软件、算法理论、操作系统、分布式系统、编译程序以及数据挖掘等方面都扮演着重要角色.

7.1 图的基本概念 哥尼斯堡(Köningsberg)七桥问题: 7.1 图的基本概念 哥尼斯堡(Köningsberg)七桥问题: 问题是: 是否可从某一个地方出发，经过七座桥，每座桥只经过一次，然后又回到原出发点.

e8: v3可调用v2; e1: v2可调用v1; e4: v5可调用v5自身. 程序调用的图论模型: e8: v3可调用v2; e1: v2可调用v1; e4: v5可调用v5自身. 单行道; 好感?

1.图的定义 由前面的2个例子可以得出 Definition 图G(graph)主要由2部分组成: (1)节点集合V, 其中的元素称为节点(vertex 或node). (2)边集合E, 其中的元素称为边(edge). 通常将图G记为G = (V, E). 几点说明:

(a)节点又可以称为点、顶点或结点,常用一个实心点或空心点表示,但在实际应用中还可以用诸如方形、圆形、菱形等符号,为了方便可以在这些符号的旁边或内部写上表意名称. (计算机学科中常称节点.) (b)边及其的表示. 无向边? b3 = AB = BA ={A, B}(可重). 有向边(弧)? 所有边都是无向边的图称为无向图(graph, undirected graph),所有边都是有向边的图称为有向图(digraph, directed graph).

(c)图的拓扑不变性质. 需要注意的是,我们讨论的图不但与节点位置无关,而且与边的形状和长短也无关. 有n个节点的图称为n阶(order)图,有n个节点m条边的图称为(n, m)图. 在图G = (V, E)中, 称V = 的图为空图(empty graph), 记为, 若 V  但E = 的图称为零图(discrete graph), n阶零图可记为Nn,仅一个节点的零图称为平凡图(trivial graph).

2.邻接 Def 设G = (V, E)是图, 对于任意u, v  V,若从节点u到节点v有边, 则称u邻接到(adjacent to) v或称u和v是邻接的(adjacent). 无向图? 有向图? (无向图的两条边邻接是指它们有公共端点.)

3.关联 Def 设G = (V, E)是图, e  E, e的两个端点分别为u和v, 则称边e与节点u以及边e与节点v是关联的(incident). 显然,图的任意一条边都关联两个节点. 关联相同两个节点的边称为吊环,可简称环(loop) .关联的起点相同与终点也相同的边称为多重边(multiple edges)或平行边,其边数称为边的重数(multiplicity). 例子见书Figure 7-4(a)(b).

4.简单图 (1)简单图 Def 设G = (V, E)是图, 若G中既无吊环又无多重边,则称G是简单图(simple graph). 简单图的例子? 彼得森(Petersen, 1831~1910)图, 它是一个有着特殊性质的简单图, 后面会多次出现.

(2)完全无向图 Def 设G = (V, E)是n阶简单无向图, 若G中任意节点都与其余n - 1个节点邻接, 则称G为n阶完全无向图(complete graph), 记为Kn. K5: 将n阶完全无向图Kn的边任意加一个方向所得到的有向图称为n阶竞赛图.

(3)补图 Def 设G = (V, E)是n阶简单无向图,由G的所有节点以及由能使G成为Kn需要添加的边构成的图称为G的补图,记为 (u和v在G中不邻接 u和v在 中邻接)

7.2 节点的度数 边与节点的关联次数? Def 设G = (V, E)是无向图, v  V,称与节点v关联的所有边的关联次数之和为节点v的度数(degree),记为deg(v). 一个环算2度?

Def 设G = (V, E)是有向图, v  V, 称以v为起点的边的数目为节点的出度(out-degree),记为deg+(v),以v为终点的边的数目为节点的入度(in-degree),记为deg-(v), 称deg+(v) + deg-(v)为节点v的度数,记为deg (v). 一个环算2度?

下面的定理是L. Euler在1736年证明的图论中的第一定理,常称为“握手(?)定理”. Theorem 在任何(n, m)图G = (V, E)中, 其所有节点度数之和等于边数m的2倍,即 Corollary 在任意图G = (V, E)中, 度数为奇数的节点个数必为偶数. Proof

由定理及其推论很容易知道,在任何一次聚会上,所有人握手次数之和必为偶数并且握了奇数次手的人数必为偶数.(环的解释?) 在任意有向图中,显然有 Theorem 在任意有向图中,所有节点的出度之和等于入度之和. 在任意图中, 度数为0的节点称为孤立点(isolated vertex), 度数为1的节点称为悬挂点(pendant vertex).

例7-1(P200) 证明: 对于任意n(n  2)个人的组里,必有两个人有相同个数的朋友. Proof 将组里的每个人看作节点,两个人是朋友当且仅当对应的节点邻接,于是得到一个阶简单无向图G,进而G中每节点的度数可能为0, 1, 2, …, n - 1中一个. 当G中无孤立点时,于是每节点的度数可能为1, 2, …, n - 1. 由于共有n个节点,于是必有两节点度数相同. 当G中有孤立点时,这时每节点的度数只可能为0, 1, 2, …, n - 2. 同样由于共n有个节点,因此必有两节点度数相同.

若一个无向图G的每节点度数均为k, 则称G为k-正则图(k-regular graph). 例子? 例7-2(P200) 设无向图G是一个3-正则(n, m)图, 且2n – 3 = m, 求n和m各是多少? Hint 根据握手定理有, 3n = 2m.

Def 7-9 任意图G = (V, E): 有向图G = (V, E): 例子?

对于无向图G = (V, E), V = {v1, v2, …, vn},称deg(v1), deg(v2), …, deg(vn)为的度数序列. 对于有向图, 还可以定义其出度序列和入度序列. (1)7, 5, 4, 2, 2, 1. (2)4, 4, 3, 3, 2, 2.

Solution (1)由于序列7, 5, 4, 2, 2, 1中, 奇数个数为奇数, 根据握手定理的推论知, 不可能存在一个图其度数序列为7, 5, 4, 2, 2, 1. (2)因为序列4, 4, 3, 3, 2, 2中, 奇数个数为偶数, 可以得到一个无向图(见图7-11),其度数序列为4, 4, 3, 3, 2, 2.

7.3 子图、图的运算和图同构 1.子图 可以通过一个图的子图去考察原图的有关性质以及原图的局部结构. 7.3 子图、图的运算和图同构 1.子图 可以通过一个图的子图去考察原图的有关性质以及原图的局部结构. Def 设G = (V, E)和H = (W, F)是图, 若W  V且F  E, 则称H = (W, F)是G = (V, E)的子图(subgraph). 若H = (W, F)是G = (V, E)的子图且W = V, 则称H = (W, F)是G = (V, E)的生成子图(spanning subgraph).

例7-4(一个图的子图较多) 常见的4种产生G = (V, E)的子图的方式如下: (1)G[W] 设W  V,则以W为节点集合,以两端点均属于W的所有边为边集合构成的子图,称为由W导出的子图(induced subgraph by W),记为G[W].

(2)G – W 设W  V, 导出子图G[V – W]记为G – W,是在G中去掉所有W中的节点,同时也要去掉与W中节点关联的所有边 (2)G – W 设W  V, 导出子图G[V – W]记为G – W,是在G中去掉所有W中的节点,同时也要去掉与W中节点关联的所有边. 通常将G – {v}记为G - v. (3)G[F] 设F  E, 则以F为边集合,以F中边的所有端点为节点集合构成的子图,称为由F导出的子图(induced subgraph by F),记为G[F].

(4)G – F 设F  E,则从G中去掉F中的所有边得到的生成子图记为G – F.

简单图G = (V, E)的补图 G + U: (与子图无关)

2.图的运算 图的运算就是通过一定的操作,产生“新”的图. 前面的子图的产生实际上就是图的运算,但它们都是在一个图中进行讨论的. 也便于用代数方法讨论图. 在有些问题的讨论中,还会出现两个图之间的一些运算. 我们在此仅给出定义,请参见有关文献. Def (1)

(2) (3) (4) 思考 图的每种运算的性质有哪些? 它与集合的并、交、差、(补)及环和(对称差)运算的性质有什么不同?

3.图同构 由于图的拓扑性质, 有可能两个表面上看起来不同的图本质上是同一个图, 这就是图同构的问题. Def(见书) 直观理解: G1  G2是指其中一个图仅经过下列两种变换可以变为另一个图: (a)挪动节点的位置； (b)伸缩边的长短.

无向图: 不同构的例子P204 5.

有向图:对于两个有向图同构的判断, 特别要注意边的方向的一致性. 思考 给出至少4个两个图同构的必要条件.

Ulam猜想?