
离散数学笔记(12)——图论的基本概念
图论
图的基本概念
无向图的概念
设 A,B 是两个非空集合,记:
A×B={⟨a,b⟩|a∈A∧b∈B}A&B={(a,b)|a∈A∧b∈B}
定义 1:一个无向图 G 定义为一个二元组 ⟨V,E⟩,记作 G=⟨V,E⟩,其中:
- V 是一个非空集合,称为 G 的顶点集,它的元素称为顶点。
- E⊆V&V,称为 G 的边集,其元素称为边,V&V 中的元素可以在 E 中出现不止一次。
定义 2:没有任何边的图称为空图,只有一个点的图称为平凡图。
定义 3:图中顶点的个数称为图的阶,若 |V(G)|=n,则称 G 为 n 阶图;连接两个相同顶点的边的条数称为边的重数,这些边称为平行边或多重边。
邻接点:与一边关联的两个结点。
邻接边:关联同一个点的两条边。
环:只关联一个结点的边。
简单图:没有环以及没有重数大于 1 的边的图。
孤立点:不与任何点邻接的点。
以下记 |V(G)|=n,|E(G)|=m。
无向图结点 v 的度
G 是无向图,v∈V(G),结点 v 所关联边数,称之为结点 v 的度,记作 d(v),环对度贡献为 2。
奇点:度为奇数的点。
偶点:度为偶数的点。
无向图的结点度序列
令 G=⟨V,E⟩ 是无向图,V={v1,v2,⋯,vn},则称 (d(v1),d(v2),⋯,d(vn)) 为图 G 的结点度序列。
图的最大度和最小度
最大度:Δ(G)=max{d(v)|v∈G}
最小度:δ(G)=min{d(v)|v∈G}
相关定理
定理 1:每个无向图所有结点度总和等于边数的 2 倍,即:
∑v∈Vd(v)=2|E|
定理 2:每个无向图中,奇数度的结点必为偶数个。
k-正则图
一个无向简单图 G 中,如果 Δ(G)=δ(G)=k,则称 G 为 k-正则图。
完全图
G 是个简单图,如果每对不同结点之间,都有边相连,则称 G 是个无向完全图。如果 G 有 n 个结点,记为 Kn。
定理:完全图 Kn 有边数 n(n–1)2。
补图
定义 1:设 G 是简单图,H 是一个以 V(G) 为顶点集的图,且两个顶点在 H 中邻接当且仅当它们则在 G 中不邻接,则称 H 是 G 的补图,记作 H=¯G。
定义 2:由 G 的所有结点和为使 G 称为完全图,所需要添加的那些边组成的图,称之为 G 的补图。
图的同构
设 G=⟨V,E⟩ 和 G′=⟨V′,E′⟩ 是图,如果存在双射 f:V→V′ 且任何 e=(vi,vj)∈E,有 e′=(f(vi),f(vj))∈E′,并且边 e 与 e′ 的重数相同。
则称 G 与 G′ 同构,记作 G∽=G′。
两个图同构的必要条件:
- 结点个数相等。
- 边数相等。
- 度数相同的结点数相等。
- 对应的结点的度数相等。
子图
定义 1:称图 H 为图 G 的子图,如果 V(H)⊆V(G),E(H)⊆E(G),且 H 中边的重数不能超过 G 中对应边的重数。
定义 2:设 G=⟨V,E⟩,一个满足 H=⟨V,E1⟩,E1⊆E 的子图称为 G 的生成子图。
定义 3:设 V′ 是图 G 的顶点集 V 的一个非空子集,以 V′ 作为顶点集,以两端点均在 V′ 的边的全体为边集的子图,称为由 V′ 导出的 G 的子图,记为 G[V′],称其为 G 的导出子图。
定义 4:设 E′ 是图 G 的边集 E 的一个非空子集,以 E′ 为边集,以 E′ 中边的全体端点为顶点集组成的子图称为由 E′ 导出的子图,记为 G[E′]。
注:G、空图均为 G 的子图,而且是非空子图,称为平凡子图。其中,G 为 G 的点导出子图。
路与回路
路(walk)
给定图 G=⟨V,E⟩,设 v0,v1,⋯,vk∈V,e1,e2,⋯,ek∈E,其中 ei 是关联 vi–1 和 vi 的边,则称结点和边的交叉序列 v0e1v1⋯ekvk 是连接 v0 和 vk 的路。
v0 是此路的起点,vk 是此路的终点。路中含有的边数 k 称之为路的长度。
如果 G 是个简单图,则路可以只用结点序列表示。
回路
如果一条路的起点和终点是同一个结点,则称此路是一个回路。
迹(chain)和闭迹
如果一条路中,所有边都不同,则称此路为迹。
如果一条回路中,所有边都不同,则称此回路为闭迹。
通路(path)和圈(cycle)
如果一条路中,所有结点都不同,则称此路为通路。
如果一条回路中,除起点和终点外,其余结点都不同,则称此回路为圈。
No Comments