PDF《图的基本概念》

1 图的基本概念 何英华 hyh@tju.

edu.cn 集合论与图论07 ? 图论〔Graph Theory〕是数学的一个分 支.它以图为研究对象.图论中的图是由 若干给定的点及连接两点的线所构成的图 形,这种图形通常用来描述某些事物之间 的某种特定关系,用点代表事物,用连接 两点的线表示相应两个事物间具有这种关 系. 七桥问题 ? 1736年,欧拉提出"七桥问题",图论诞生 问题是要从这四块陆地中任何一块开 始,通过每一座桥正好一次,再回到 起点. A D cd a b f C g B e 周游世界问题 ? 1859年,数学家哈密顿将正十二面体的每个顶点比作一个 城市,连接两个顶点之间的边看作城市之间的交通线,提 出周游世界问题:能否从某个城市出发沿交通线经过每个 城市一次并且仅一次,最后回到出发点? 四色猜想 ? 1852年,毕业于伦敦大学的弗南西斯・格思里 (Francis Guthrie)来到一家科研单位搞地图着色工作 时,发现了一种有趣的现象:"看来,每幅地图都可 以用四种颜色着色,使得有共同边界的国家着上不 同的颜色." 即"将平面任意地细分为不相重迭的区 域,每一个区域总可以用1,2,3,4这四个数字之 一来标记,而不会使相邻的两个区域得到相同的数 字." ? 每个地图可以导出一个图,其中国家都是 点,当相应的两个国家相邻时这两个点用 一条线来连接.所以四色猜想是图论中的 一个问题.

2 目录 ? 无向图与有向图 ? 顶点度数与握手定理 ? 简单图、完全图、正则图 ? 子图、补图 ? 图的同构 有序积、无序积、多重集 ? 有序积: A*B={ |x∈A∧y∈B} 有序对: ≠ ? 无序积: A&B={ (x,y) |x∈A∧y∈B} 无序对: (x,y)=(y,x) ? 多重集: {a,a,a,b,b,c}≠{a,b,c} 重复度: a的重复度为3, b的为2, c的为1 无向图 ? 无向图G=: (1) V≠?, 顶点,结点;

(2) 多重集E?V&V, 边. ? 例: G=,V={a,b,c,d,e}, E={(a,a),(a,b),(a,b),(b,c),(c,d),(b,d)}. a b c d e u v (u,v) V(G)=V, E(G)=E 有向图 ? 有向图D=: (1) V≠?, 顶点,结点;

(2) 多重集E?V*V, 边?例: D=,V={a,b,c,d,e}, E={ ,,

,,

,,

(d,b) }. a b c d e u(起点) v(终点) V(D)=V, E(D)=E n阶图,零图,平凡图,空图 ? 有限图: 顶点集和边集都是有限集 ? n阶图: |V(G)|=n ? 零图: E=?,n阶零图 ? 平凡图: 1阶零图 ? 空图: V=E=? 标定图,非标定图,基图 ? 标定图: 顶点或边带标记 ? 非标定图: 顶点或边不带标记 ? 基图: 有向图去掉边的方向后得到的无向图 a b c d

3 ek 关联,相邻 ? 关联: 点与边 C 端点, C 孤立点:无边关联的顶点;

C 环:若一条边所关联的两个顶点重合;

C 边与顶点的关联次数: 1:若vi ≠ vj,则称ek与vi(或vj)的关联次数为1;

2:若vi = vj,则称ek与vi(或vj)的关联次数为2;

0:若vl 不是ek的端点,则称ek与vl 的关联次数为0;

vi vj 关联,相邻 ? 相邻: 点与点:若存在一条边e以vi,vj为端点,即e=(vi,vj),则称vi与vj彼此相邻,简称相邻的. 边与边:若边ek与el至少有一个公共端点,则称ek 与el是彼此相邻的,简称相邻的. 关联,相邻 ? 有向图的关联与相邻 C 始点:vi是ek的始点;

C 终点: vj是ek的始点;

C 邻接到:vi邻接到vj;

C 邻接于:vj邻接于vi;

vi vj ek 目录 ? 无向图与有向图 ? 顶点度数与握手定理 ? 简单图、完全图、正则图 ? 子图、补图 ? 图的同构 顶点的度数 ? 度dG(v): v作为边的端点的次数之和 ? 出度dD +(v): v作为边的起点的次数之和 ? 入度dD -(v): v作为边的终点的次数之和 ? 度dD(v) = dD +(v) + dD -(v)

0 3

3 4 0,0 1,2 (d+,d-) 2,1 2,2

4 最大(出/入)度,最小(出/入)度?最大度: Δ(G) = max{ dG(v) | v∈V(G) } ? 最小度: δ(G) = min{ dG(v) | v∈V(G) } ? 最大出度: Δ+(D) = max{ dD +(v) | v∈V(D) } ? 最小出度: δ+(D) = min{ dD +(v) | v∈V(D) } ? 最大入度: Δ-(D) = max{ dD -(v) | v∈V(D) } ? 最小入度: δ-(D) = min{ dD -(v) | v∈V(D) } ? 简记为 Δ, δ, Δ+, δ+, Δ-, δ- 悬挂顶点(边)、奇(偶)度顶点 ? 称度数为1的顶点为悬挂顶点,与它关联的边为悬挂 边.度为奇数(偶数)的顶点称为奇度(偶度)顶点. ? 在下图中,(1)的d(v1)=4,= 4,δ= 1,v4是悬挂顶点,e7 是悬挂边.(2)的d+(a)=4,d-(a)=1,d(a)=5,=5,δ=3, +=4,δ+=0,-=3,δ-=1. 握手定理 ? 定理1:设G=是无向图, V={v1,v2,…,vn}, |E|=m, 则d(v1)+d(v2)+…+d(vn)=2m. ? 定理2:设D=是有向图, V={v1,v2,…,vn}, |E|=m, 则d+(v1)+d+(v2)+…+d+(vn) = d-(v1)+d-(v2) +…+d-(vn) = m. ? 推论:任何图中,奇数度顶点的个数是偶数. 度数列 ? 设G=为一个n阶无向,V={v1,v2,…,vn},称d(v1),d(v2),…,d(vn)为G的度数列,对于顶点标定 的无向图,它的度数列是唯一的. ? 设D=为一个n阶有向图,V={v1,v2,…,vn}, 称d(v1),d(v2),…,d(vn)为D的度数列,另外称 d+(v1),d+(v2),…,d+(vn)与d-(v1),d-(v2),…,d-(vn)分别 为D的出度列和入度列. 例题1 ? 在下图中, (1)按顶点的标定顺序,度数列为 4,4,2,1,3.在(2)中,按字母顺序,度数列,出度 列,入度列分别为5,3,3,3;

4,0,2,1;

1,3,1,2. 例题2 1)以下两组数能够称无向图的度序列吗?为什么? ① 2,3,4,5,6,7 ② 1,2,2,3,4 2)已知图中有11条边,有1个4度顶点,4个3度顶 点,其余顶点的度数均小于等于2,问G中至少有 几个顶点? 3)已知5阶有向图D的顶点集V={v1,v2, v3,v4,v5},它 的度数列和出度列分别为3,3,2,3,3和1,2,1,2,1, 试求D的入度列.

5 例题 ? 例3:设n阶m条边的无向图G中,m=n+1, 证明G中存在顶点v,d(v) ≥3. 例题 ? 例4:证明空间不存在有奇数个面且每个面 有奇数条棱的多面体. 例题 ? 例5:设G为9阶无向图,G的每个顶点的度 数不是5就是6.证明G中至少有5个6度顶 点或者至少6个5度顶点. 目录 ? 无向图与有向图 ? 顶点度数与握手定理 ? 简单图、完全图、正则图 ? 子图、补图 ? 图的同构 多重图与简单图 ? 在无向图中,关联一对顶点的无向边如果多于1 条,则称这些边为平行边,平行边的条数称为重 数. ? 在有向图中,关联一对顶点的有向边如果多于1 条,并且这些边的始点和终点相同(也就是它们的 方向相同),则称这些边为平行边. ? 含平行边的图称为多重图,既不含平行边也不含 环的图称为简单图. 例题 ? 下图(1)中e5与e6是平行边, (2)中e2与e3是平行 边,e6与e7不是平行边.两个图都不是简单图. ? n阶简单无向图满足0≤Δ≤n-1.

6 完全图 K1 K2 K3 K4 K5 ? n阶无向完全图记做Kn(n≥1) 中每个顶点均与其 余的n-1个顶点相邻. ? Kn的边数为n(n-1)/2. ? n阶有向完全图D中每个顶点都邻接到其余的n-1 个顶点,并邻接于其余的n-1个顶点. ? n阶有向完全图的边数为n(n-1). 有向完全图 正则图 定义 设G=是无向简单图.若顶点的度数均为k,则称 G为k-正则图. 库拉图斯基图K3,3 库拉图斯基图K5 彼得松图 ? n阶零图是0-正则图,n阶无向完全图是(n-1)-正则图.n阶k-正则图的边数m=kn/2,因而当k为奇数时,n必为偶数. 圈C1 C2 C3 C4 C5 轮W1 W2 W3 W4 W5 超立方体 Q0 Q1 Q2 Q3 Q4

7 目录 ? 无向图与有向图 ? 顶点度数与握手定理 ? 简单图、完全图、正则图 ? 子图、补图 ? 图的同构 子图 ? 设G=,G'=为两个图(同为无 向图或同为有向图),若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中的 全体边为边集E1的G的子图称为V1导出的导 出子图,记作G[V1]. 设E1?E且E1≠φ,以E1中的边关联的顶点的全体为顶点集V1的G 的子图称为E1导出的导出子图,记作 G[E1]. 例题 ? 在下图中,设G为(1)中图所表示,取V1={a,b,c}, 则V1的导出子图G[V1]为(2)中图所示.取E1={e1, e3},则E1的导出子图G[E1]为(3)中图所示. 补图 ? 设G=,以V为顶点集,以所有使G成为完 全图Kn的添加边组成的集合为边集的图,称为G 的补图,记做 G 目录 ? 无向图与有向图 ? 顶点度数与握手定理 ? 简单图、完全图、正则图 ? 子图、补图 ? 图的同构

8 图同构 ? 图同构: 设无向(有向)图G1=, G2=, 若存在双射 f:V1→V2, 满足?u∈V1,?v∈V1, (u,v)∈E1 ? (f(u),f(v))∈E2 ( ∈E1 ? ∈E2 ) 则称G1与G2同构, 记作G1?G2 图之间的同构关系 ? 图之间的同构关系是等价关系.这个等价关系的 每一个等价类中的图,在同构的意义之下都可以 看成一个图,这样就可以说,在图同构的意义 下,图的数学定义与图形表示是一一对应的. 判断两个图是否同构 ? 到目前为止,人们还没有找到判断两个图是否同构的好的 算法,还只能根据定义看是否能找到满足条件的双射函 数. ? 两个图同构的必要条件:若G1?G2,则它们的阶数相同, 边数相同,度数列相同. ? 不要将两个图同构的必要条件当成充分条件.破坏这些必 要条件的任何一个,两个图就不会同构,但以上列出的条 件都满足,两个图也不一定同构. 例题 例题 例 画出4阶3条边的所有非同构的无向简单 图.

9 例题 例 画出3阶2条边的所有非同构的有向简单 图. 例 画出以1,1,1,2,2,3为度数列的3个 非同构的无向简单图.