20211018第十四章复习

第十四章 图的基本概念

图

A，B 为任意两个集合，称{{a，b}|a 属于 A 合取 b 属于 B}为 A 与 B 的无序积，记作 A&B。将无序积中的无序对{a，b}记为（a，b），因而 A&B=B&A

一个无向图 G 是一个有序的二元组<V,E>,其中
（1）V 是一个非空有穷集，称作顶点集，其元素称作顶点或结点。
（2）E 是无序积 V&V 的有穷多重子集，称作边集，其元素乘坐无向边，简称为边。
一个有向图 D 是一个有序的二元组<V,E>,其中
（1）V 是一个非空有穷集，称作顶点集，其元素称作顶点或结点。
（2）E 是笛卡尔积 VxV 的有穷多重子集，称作边集，其元素乘坐有向边，简称为边。

相关概念：
1.V（G）表示 G 的顶点集，E（G）表示 G 的边集，加绝对值就代表顶点/边的数量（V 是顶点，E 是边）
2.顶点数称作图的阶，n 个顶点的图称作 n 阶图
3.一条边也没有的图称作零图。n 阶零图记作 N_n。一阶零图 N_1 称作平凡图，平凡图只有一个顶点，没有边。
4.图的定义中规定顶点集 V 为非空集，但是在运算中可能产生顶点集为空集的运算结果，规定顶点集为空集的图为空图，记作空集的符号
5.当用图形表示图时，如果给每一个顶点和每一条边指定一个符号（字母或数字），则称这样的图为标定图，否则称作非标定图。
6.有向图的各条有向边改成无向边后得到的无向图称作有向图的基图。
7.设 G=<V,E>为无向图，e_k=（v_i,v_j）属于 E，称 v_i,v_j 为 e_k 的端点，e_k 与 v_i(v_j) 关联。若 v_i 不等于 v_j，则称 e_k 与 vi（vj）的关联次数为 1；若 vi=vj，则称 e_k 与 v_i 的关联次数为 2，并称 e_k 为环。如果顶点 vi 不与边 ek 关联，则称 ek 与 vi 的关联次数为 0。（边与点关联）
若两个顶点 vi 与 vj 之间有一条鞭链接，则称这两个定点相邻，若两条边至少有一个公共断电，则称这两条边相邻。
8.设 D=<V,E>为有向图，ek=<vi,vj>属于 E，称 vi，vj 为 ek 的端点，vi 为 ek 的始点，vj 为 ek 的重点，并称 ek 与 vi（vj）关联。若 vi=vj，则称 ek 为 D 中的环。
若两个顶点之间有一条有向边，则称这两个顶点相邻。若两条边中一条边的终点是另一条边的始点，则称这两条边相邻。
图中没有边关联的顶点称作孤立点。
9.
设无向图 G=<V,E>,任取 v 属于 V，
称 N_G(V)={u|u 属于 V 合取 (u,v) 属于 E 合取 u 不等于 v}为 v 的邻域（与 v 相邻不包含 v 的所有点的集合）。
称 N(上一横杠）_G(v)=N_G(v)U{v}为 v 的闭邻域（与 v 相邻包含 v 的所有点的集合）。
称 I_G(v)={e|e 属于 E 合取 e 与 v 相关联}为 v 的关联集（链接 v 的所有边的集合）。
设有向图 D=<V,E>，任取 v 属于 V，
称所有 v 指向的点为后继元集
称所有指向 v 的点为先驱元集
称先驱元集与后继元集的并集为邻域，加上 v 本身为闭邻域

无向图中，如果关联一对顶点的无向边多于 1 条，则称这些边为平行边，平行边的条数称作重数。
在有向图中，如果关联一堆顶点的有向边多于 1 条，并且他们方向相同，则称这些边为平行边。
含平行边的图称作多重图，即不含平行边也不含环的图称作简单图。

设 G=<V,E>为无向图，则称 v 作为边的断电的次数为 v 的度数，简称度。记作 d_G(v)，不混淆记作 d(v)。
若为有向图，v 作为边的始点的次数为 v 的出度，d^+(v)，作为终点的次数为入度，d^-(v)。v 的度数为入度 + 出度。出 + 入 -
最大度与最小度
度数为 1 的顶点为悬挂顶点，与它关联的边称作悬挂边。奇度顶点和偶度顶点。

握手定理：
在任何无向图中，所有顶点的度数之和等于边数的两倍
在任何有向图中，所有顶点的度数之和等于边数的两倍；所有顶点的入度之和等于出度之和等于边数

度数列就是所有点度数的排列 d(v1),d(v2)…d(vn)。对于给定的非负整数列 d，若存在 n 阶无向图 G 满足度数列 d，就说 d 是可图化的，若所得到的图是简单图，则称 d 是可简单图化的。
有向图还有出度列和入度列

非负整数列 d 是可图化的，当且仅当求和 d 是偶数。

两个无向图，若存在双射函数 f：v1->v2，使得（1）任取 vi，vj 属于 V1，（vi,vj) 属于 E1 当且仅当（f（vi），f（vj））属于 E2，（2）（vi,vj）与（f（vi）f（vj））重数相同。则称两图同构。

G 为 n 阶五项简单图，若 G 中每个顶点均与其余的 n-1 个顶点相邻，则称 G 为 n 阶无向完全图，简称 n 阶完全图 K_n
D 为 n 阶有向简单图，若 D 中每个顶点都临接到其余的 n-1 个顶点，则称 D 为 n 阶有向完全图
D 为 n 阶有向简单图，若 D 的基图为 n 阶无向完全图 k_n，则称 D 为 n 阶竞赛图

G 为 n 阶无向简单图，若每个顶点度数相同，G 为 k- 正则图，彼得松图是 3- 正则图

G 和 G‘为两个图，若 V’包含于 V 且 E‘包含于 E，则称 G’为 G 的子图，G 为 G‘的母图，记作 G’包含于 G。若是真包含，就是真母图，若 v‘=v，则称 G’为 G 的生成子图

选出 G 中的一些便 V1（不嫩全选），以 V1 为顶点，两个端点都在 V1 中的边为 E1，以 E1 为边的图为 G 的 V1 导出的子图，记作 G[V1]。
选出一些边 E1（不能全选），以 E1 中的边与 E1 包含的点构成的图，叫做 G 的 E1 导出子图，记作 G[E1]

删掉五项简单图的所有边，加上所有之前没有的边，生成的图就是补图，如果补图和原本的图同构，就是自补图

无向图中：
删除边 e：G-e
删除点 v：G-v
收缩：G\e，e=（u,v) 删除这条边，用 w 代替边的两个端点，w 关联除 e 之外 u，v 关联的所有边。
新加边：GU(u,v) 在 u，v 之间加一条鞭，可能产生换和平行边

通路与回路

F 少一横，点和边的交替序列叫通路，始点和终点，如果始点终点相等就是回路，如果所有边不同就是简单通路，同理简单回路。
所有顶点都不同（除始点和终点可能相同），所有边不同就叫初级通路或路径，如果始点和终点相同就是初级回路或圈。长度为奇数叫奇圈
简单无向图中，圈的长度至少为 3.
有边重复出现，就叫复杂通路、复杂回路。
初级通路必是简单通路。

u 到 v 有同路，则存在长度小于等于 n-1 的通路（初级通路）。
u 有回路，则一定存在到自身长度小于等于 n 的回路
u 有简单回路，则一定存在 v 到自身长度小于等于 n 的初级回路。
圈顶点相同就是同构的，但是两个圈标记序列不同，就说他们在定义意义下不同。

图的连通性

无向图

无向图 uv 之间存在通路，就说 uv 联通，记作 u~v
若无向图 G 是平凡图或 G 中任何两个顶点都是联通的，则称 G 为联通图，否则称 G 为非连通图。

连通分支数就是一个图包括多少个联通图。

uv 之间长度最短的通路是 uv 之间的短程线，段呈现的长度称为 uv 之间的距离。记作 d(u,v)，不联通时为无穷。u 和自己距离为 0
d（u，v）满足三角不等式

无向图，存在 V‘真包含于 V，p（G-V’）>p(G)，且对于任意 V‘’真包含与 V‘，都有 p（G-V’‘）=P（G），则称 V’是 G 的点割集，若 V‘={v}，则称 v 为割点。
同理边割集，或简称割集，e 称作割边或桥。

G 为无向连通图且不失完全图，则称最少的点割集长度为点连通度（也叫连通度）k，非负整数，称 G 为 k- 联通图
G 是无向连通图，最少的边割集的长度称作边连通度λ，称 G 为λ边 - 连通图

有向图

有向图，若 vi->vj，则称最短的通路为短程线，长度为 vi 到 vj 的距离。
基图是联通图则称 D 为若连通图，简称为连通图。
任取 vi，vj，vi->vj 或 vj->vi 至少成立一个，就成为单向连通图
若都成立，就是强连通图

无向图 G 若能划分为 V1，V2，使得每条边顶点一个属于 V1，一个属于 V2，那么 G 为二部图，或二分图、呕吐。
若 V1 每一个顶点均与 V2 中所有顶点相邻，则称为完全二部图。
n 阶 0 图是二部图。

n 阶无向图是二部图当且仅当 G 中无奇圈。

图的矩阵表示关联矩阵记录关联次数

关联矩阵，每一列是一条边，无向图就是每一列和为 2.
关联矩阵有向图（无环）每一列和为 0，一个 +1 表示始点，一个 -1 表示终点
邻接矩阵，ij 的值表示从 i 到 j 的边的条数。其 n 次幂就是长度为 d 的通路/回路数量
可达矩阵，i 能到 j 就是 1，否则就是 0.

图的运算

V1 交 V2=空集，就是不交的
E1 交 E2=空集，就是边不交的，或边不重的
并图：V1UV2，E1UE2
差图：E1-E2
交图：E1 交 E2
环和：G1 圆圈 +G2