高教_离散数学耿素云+屈婉玲图论部分

几点说明： 图之间的同构关系具有自反性、对称性和传递性. 能找到多条同构的必要条件，但它们全不是充分条件： ① 边数相同，顶点数相同 ② 度数列相同 ③ 对应顶点的关联集及邻域的元素个数相同，等等 若破坏必要条件，则两图不同构 判断两个图同构是个难题
试画出 4 阶 3 条边的所有非同构的无向简单图（答案为 3 个）
第十四章 图的基本概念
本章的主要内容 图及相关的诸多概念 通路与回路 图的连通性 图的矩阵表示
预备知识 多重集合——元素可以重复出现的集合 无序集——AB={(x,y) | xAyB}
第一节 图
一、无向图与有向图的定义 1． 无向图的定义 定义 14.1 无向图 G = <V,E>, 其中 （1）V 为顶点集，元素称为顶点 （2）E 为 VV 的多重集，其元素称为无向边，简称边 设 V = {v2, v2, …,v5}, E = {(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)} 则 G = <V,E>为一无向图，用图 1 表示 G
六、正则图 定义 14.7 n 阶 k 正则图——==k 的无向简单图
简单性质：边数 m nk （由握手定理得） 2
Kn 是 n1 正则图，彼得松图（见书上图 14.3（1）所示， 记住它）
七、子图 定义 14.8 G=<V,E>, G=<V,E> （1）GG —— G为 G 的子图，G 为 G的母图 （2）若 GG 且 V=V，则称 G为 G 的生成子图 （3）若 VV 或 EE，称 G为 G 的真子图 （4）V（VV 且 V）的导出子图，记作 G[V] （5）E（EE 且 E）的导出子图，记作 G[E]
第二节 通路与回路
一、通路与回路的定义 定义 14.11 给定图 G=<V,E>（无向或有向的），G 中顶点与边的交 替序列 = v0e1v1e2…elvl，vi1, vi 是 ei 的端点. （1）通路与回路：为通路；若 v0=vl，为回路，l 为回路长度. （2）简单通路与回路：所有边各异，为简单通路，又若 v0=vl， 为简单回路 （3）初级通路（路径）与初级回路（圈）：中所有顶点各异，则称 为初级通路（路径），又若除 v0=vl，所有的顶点各不相同且 所有的边各异，则称为初级回路（圈） （4）复杂通路与回路：有边重复出现
2. 图论基本定理——握手定理
定理 14.1 设 G=<V,E>为任意无向图，V={v1,v2,…,vn}, |E|=m, 则
n
d (vi ) 2m
i 1
证 G 中每条边（包括环）均有两个端点，所以在计算 G 中各顶
点度数之和时，每条边均提供 2 度，当然 m 条边共提供 2m
度.
定理 14.2 设 D=<V,E>为任意有向图，V={v1,v2,…,vn}, |E|=m, 则
例 画出 K4 的所有非同构的生成子图 图6
八、补图 定义 14.9 设 G=<V,E>为 n 阶无向简单图，以 V 为 顶点集，以所有使 G 成为完全图 Kn 的添加边组成 的集合为边集的图，称为 G 的补图，记作 G . 若 G G , 则称 G 是自补图. 相对于 K4, 求图 6 中所有图的补图，并指出哪些是 自补图. 问：互为自补图的个图的边数有何关系？
图7 图 7 中，{v1,v4}，{v6}是点割集，v6 是割点. {v2,v5}是点割集吗？
② 边割集与割边 定义 14.17 G=<V,E>, EE E是边割集——p(GE)>p(G)且有极小性 e 是割边（桥）——{e}为边割集 在图 7 中，{e1,e2}，{e1,e3,e5,e6}，{e8}等是边割集，e8 是桥， {e7,e9,e5,e6}是边割集吗？ 几点说明： Kn 中无点割集 Nn 中既无点割集，也无边割集，其中 Nn 为 n 阶零图 若 G 连通，E为边割集，则 p(GE)=2 若 G 连通，V为点割集，则 p(GV)2
（1）
（2）
（3）
（4）
图3
图 3 中，（1）与（2）不同构（度数列不同），（3）与（4）也不同构.
（1）
（2）
图4
图 4 中（1）与（2）的度数列相同，它们同构吗？为什么？
五、完全图与竞赛图
1．定义 14.6
（1）n (n1) 阶无向完全图——每个顶点与其余顶点均相邻的无
向简单图.
简单性质：边数 m n(n 1) , n 1
图1
2. 有向图的定义 定义 14.2 有向图 D=<V,E>, 只需注意 E 是 VV 的多重子集 图 2 表示的是一个有向图，试写出它的 V 和 E
图2 注意：图的数学定义与图形表示，在同构（待叙）的意义下是一一对应的
3． 关于无向图和有向图诸多定义或表示 （1）图 ① 可用 G 泛指图（无向的或有向的） ② V(G), E(G), V(D), E(D) ③ n 阶图 （2）有限图 （3）n 阶零图与平凡图 （4）空图—— （5）用 ek 表示无向边或有向边 （6）顶点与边的关联关系 ① 关联、关联次数 ②环 ③ 孤立点 （7）顶点之间的相邻与邻接关系
2
（2）n (n1)阶有向完全图——每对顶点之间均有两条方向相反的
有向边的有向简单图.
简单性质： m n(n 1), 2(n 1), n 1
（3）n (n1) 阶竞赛图——基图为 Kn 的有向简单图.
简单性质：边数 m n(n 1) , n 1
2
图 5 中，（1）为 K5，（2）为 3 阶有向完全图，（3）为 4 阶竞赛图. 图5
四、图的同构 定义 14.5 设 G1=<V1,E1>, G2=<V2,E2>为两个无向图（两个 有向图），若存在双射函数 f：V1V2, 对于 vi,vjV1, (vi,vj)E1 （<v i,v j>E1）当且仅当(f(vi),f (v j))E2（<f (v i),f(v j)>E2），并 且, (vi,vj)（<vi,vj>）与 (f(vi),f(vj))（<f(vi),f(vj)>）的重数相同， 则称 G1 与 G2 是同构的，记作 G1G2.
（8）邻域与关联集 ① vV(G) (G 为无向图)
v的邻域 N (v) {u | u V (G) (u, v) E(G) u v} v的闭邻域 N (v) N (v) {v}
v 的关联集 I (v) {e | e E(G) e与v关联}
② vV(D) (D 为有向图)
v的后继元集 D (v) {u | u V (D) v, u E(D) u v}
三、顶点的度数及握手定理 1． 顶点的度数（度） 定义 14.4 及衍生的概念 （1）设 G=<V,E>为无向图, vV, d(v)——v 的度数, 简称度 （2）设 D=<V,E>为有向图, vV, d+(v)——v 的出度 d(v)——v 的入度 d(v)——v 的度或度数 （3）(G), (G) （4）+(D), +(D), (D), (D), (D), (D) （5）奇顶点度与偶度顶点
（3）点连通度与边连通度 ① 点连通度 定义 14.18 G 为连通非完全图 点连通度— (G) = min{|V |V 为点割集} 规定 (Kn) = n1 若 G 非连通，(G) = 0 若 (G)k，则称 G 为 k-连通图 易知，图 7 中图，=1，它只能是 1-连通图 ② 边连通度 定义 14.19 设 G 为连通图 边连通度——(G) = min{|E|E为边割集} 若 G 非连通，则(G) = 0 若(G)r，则称 G 是 r 边-连通图 易知，图 7 中图，=1，它只能是 1 边-连通图
第三节 图的连通性
一、无向图的连通性与连通度 1． 无向图的连通性 （1）顶点之间的连通关系：G=<V,E>为无向图 ① 若 vi 与 vj 之间有通路，则 vivj ② 是 V 上的等价关系 R={<u,v>| u,v V 且 uv} （2）G 的连通性与连通分支 ① 若u,vV，uv，则称 G 连通 ② V/R={V1,V2,…,Vk}，称 G[V1], G[V2], …,G[Vk]为连通分 支，其个数 p(G)=k（k1）；k=1，G 连通
n
n
n
d (vi ) 2m, 且
d (vi ) d (vi ) m
i 1
i 1
i 1
本定理的证明类似于定理 14.1
推论 任何图（无向的或有向的）中，奇度顶点的个数是偶数.
证 设 G=<V,E>为任意图，令
V1={v | vVd(v)为奇数} V2={v | vVd(v)为偶数} 则 V1V2=V, V1V2=，由握手定理可知
（3）短程线与距离 ① u 与 v 之间的短程线：uv，u 与 v 之间长度最短的通路 ② u 与 v 之间的距离：d(u,v)——短程线的长度 ③ d(u,v)的性质： d(u,v)0, u≁v 时 d(u,v)= d(u,v)=d(v,u) d(u,v)+d(v,w)d(u,w)
2. 无向图的连通度 （1）删除顶点及删除边 ① Gv ——从 G 中将 v 及关联的边去掉 ② GV——从 G 中删除 V中所有的顶点 ③ Ge ——将 e 从 G 中去掉 ④ GE——删除 E中所有边 （2）点割集与边割集 ① 点割集与割点 定义 14.16 G=<V,E>, VV V为点割集——p(GV)>p(G)且有极小性 v 为割点——{v}为点割集
几点说明 表示法 ① 定义表示法 ② 只用边表示法 ③ 只用顶点表示法（在简单图中） ④ 混合表示法 环（长为 1 的圈）的长度为 1，两条平行边构成的圈长度为 2，无向简单图中，圈长3，有向简单图中圈的长度2.