图的基本概念
无向图
图的定义： G = (V, E)
- V = {v₁, v₂, v₃, v₄, v₅}
- E = {e₁, e₂, e₃, e₄, e₅}
关联： e₁ 关联于结点 v₁, v₃
平行边： e₂, e₃
邻接结点： v₁ 和 v₃，v₁ 和 v₂
环： e₅
孤立点： v₅
结点 v₂ 的度数： d(v₂) = 3
悬挂结点： v₄
悬挂边： e₄
有向图
G = (V, E)
E = {(v₁,v₃), (v₁,v₂), (v₁,v₄), (v₂,v₁), (v₂,v₁)}
有向边 (v₁,v₂)： v₁ 为起点，v₂ 为终点
平行边： e₂, e₃
结点 v₁ 的出度： d⁺(v₁) = 3
结点 v₁ 的入度： d⁻(v₁) = 2
结点 v₁ 的度数： d(v) = d⁺(v₁) + d⁻(v₁) = 5
握手定理
- 图的所有结点的度数之和等于边数的两倍。
- 度数为奇数的结点的个数为偶数个。
- 在有向图中入度和等于出度和等于边数。
例题
1.无向图G中顶点数n与边数m相等，2度与3度结点各2个，其余结点均为悬挂结点（度为1），求图G的边数。
解：
2m = 2×2 + 3×2 + (n-4)×1
= 4 + 6 + m - 4
∴ m = 6
图G有 6 条边。
2.自然数序列 (3,3,2,2,1) 和 (4,2,2,1,1) 能作为图的结点的度数序列吗？
解：
① 序列 (3,3,2,2,1)
序列中含 3 个奇数结点，∴ 不能作为结点的度数序列。
② 序列 (4,2,2,1,1)
各度数之和 = 4+2+2+1+1 = 10，为偶数，并且可画出图。
∴ 可以作为结点的度数序列。
3.G 为 n 阶无向简单图，若 ∀v ∈ V，均有 d(v) = k，则称 G 为 k-正则图，k-正则图的边数为nk/2。
边数 = 总度数 / 2 = n·k / 2
概念说明：
- n 阶：结点数为 n
- 简单图：不含平行边、不含环
- k为每个结点的度数。
通路与回路、连通的概念
从结点 v₁ 到 v₄ 长度为 3 的通路：
v₁e₁v₂e₃v₅e₇v₄ → 点无重复，称为基本通路
从结点 v₁ 到 v₄ 长度为 4 的通路：
v₁e₂v₅e₃v₂e₄v₅e₇v₄ → 边无重复，称为简单通路
从结点 v₁ 到 v₄ 长度为 5 的通路：
v₁e₂v₅e₃v₂e₄v₅e₃v₂e₅v₄ → 边有重复
回路： v₁e₁v₂e₃v₅e₂v₁
类似地，回路也分为简单回路和基本回路。
非连通图与连通图： 若无向图G中任意两结点间都有一条通路，则称G是连通图；否则，称G是非连通图。
def： 设G = (V,E)是有向图，对G中任意两个结点u和v：
- 若从u到v存在通路，则称u到v是可达的，否则称u到v不可达。
- 若从u到v存在通路，且从v到u也存在通路，则称u和v是相互可达的。
规定一个结点到自己总是可达的。
def： 设 G = (V,E) 是有向图。
- 如果图G任意两个结点，至少从一个结点到另一个结点是可达的，则称G是单向连通的。
- 如果图G任意两个结点间是相互可达的，则称G是强连通的。
- 如果图G在略去有向边的方向后得到的无向图是连通的，则称G是弱连通的。
具有三种连通性中任何一种的有向图都称为有向连通图。
例题
求：
- G中 v₁ 到 v₄ 长度为 1,2,3,4 的通路各为几条？
- G中 v₁ 到 v₁ 长度为 1,2,3,4 的回路各为几条？
- G中长度为4的通路有多少条？其中长为4的回路有多少条？
- 写出G的可达矩阵。
- G是哪类连通图？
解：邻接矩阵
A中 aᵢⱼ：从 vᵢ 到 vⱼ 长度为1的通路数目 Aⁿ中 aᵢⱼ：从 vᵢ 到 vⱼ 长度为n的通路数目
① v₁ 到 v₄ 长度为 1,2,3,4 的通路分别为 0, 0, 2, 2 条。
② v₁ 到 v₁ 长度为 1,2,3,4 的回路分别为 1, 1, 3, 5 条。
③ 长度为4的通路：5+6+4+2+2+2+2+1+4+4+3+2+2+2+2+1 = 44条
长度为4的回路：5+2+3+1 = 11条
④ 可达矩阵：
其中 Pᵢⱼ = 1 表示 vᵢ → vⱼ 可达，Pᵢⱼ = 0 表示不可达。
⑤ G为强连通图。