图论

定义:图是一个由非空节点集合V(G)和一个边集合E(G)⊆V&V(或V×V)构成的多重集合,简记为G=<V, E>.

基本定义

有/无向

无向图:E=V&V.

有向图:E=V×V.

特殊图

n阶图：有n个顶点的图.

有限图：顶点有限的图.

零图：没有边的图.

平凡图：1阶零图(即只有一个顶点，且没有边的图).

空图：顶点集和边集都为空的图.

标定图: 顶点或边带标记.

非标定图: 顶点或边不带标记.

基图(底图) : 有向图去掉边的方向后得到的无向图.

简单图:无环, 无平行边.

k-正则图: 无向简单图且每一个节点的度数都为K.

n阶完全图: n个节点的简单图,且每个节点的度数为最大值(无向: n-1, 有向2*(n-1)), 有n(n-1)/2的边.

竞赛图: 基图为完全图的有向图.

轮图: 图中含有一个圈,圈中含有一个点,该点与圈中其他所有点关联.

r部图: 把图分为r部分, 仅各部分之间的顶点相关连, 各部分内部顶点不相互关连.

相邻与关联

邻接(相邻):点对点,边连边.

邻接到:指向.

邻接于:被指向.

关联:点与边.

关联次数:无向图关联次数皆为1,有向图关联次数起始点与边为正终止点与边为负.

环:单个点自我相连.

平行边:位于相同两点之间,若为有向图则仅同向平行,不同向不平行.

邻域

邻域:与该点相邻的点的集合(无向图).

闭邻域:邻域U该点本身(无向图).

关联集:与该点关联的边的集合(无向图).

后继元集:该点邻接到的点的集合(有向图).

前/先驱元集:该点邻接于的点的集合(有向图).

邻域:前驱元集和后继元集的并集(有向图).

闭邻域:邻域U该点本身(有向图).

度

该点与边的关联次数的和.

出度:该点与其出边的关联次数,为正.

入度:该点与其入边的关联次数,为负.

图族

子图

子图: V′⊆V且E′⊆E.

生成子图: G′⊆G 且V′=V.

真子图: V′⊂V 或E′⊂E.

顶点导出子图: V′⊆V 且V′≠∅, 以V ′为顶点集, 以G中两端点都在V ′中的边为边集的G的子图.

边导处子图: E′⊆E且E ′≠∅, 以E′为边集, 以E ′中边关联的所有顶点为顶点集的G的子图.

补图

补图: 顶点相同,边集关于完全图构成补集.

相对补图: 边集关于某图构成补集, 顶点不一定相同(相对补集不包含不与任何边关联的孤立顶点).

自补图: 其补图与自身同构.

鸽巢原理

若A是n+1元集, B是n元集, 则不存在从A到B的单射.

推广

如果要把n个元素分配到m个集合中, 必有至少一个集合容纳至少|n/m|个元素.

握手定理

定理一: 无向图结点度数的总和等于边数的两倍.

定理二: 有向图的出度=入度=边数.

推论:在任何图中,度数为奇数的结点必定是偶数个.

拉姆齐定理

对于所有的N顶图，包含k个顶点的完全图或l个顶点的独立集。具有这样性质的最小自然数N就称为一个拉姆齐数，记作R(k,l)

R(3,3)=6

度数列

定义:每一个顶点对应的度组成的序列,简记为d.

可图化

定义:存在图使得度数列成立.

可图化充要条件: 所有度数之和为偶数.

可简单图化

定义:存在图使得度数列成立.

Havel定理(充要条件)

把度数列按照从大到小的顺序排列,删除第一个数(假设该数为x),后续x个数减一所得新度数列与原度数列是否可简单图化性质一致,若减出负数则不可简单图化(PS:每一次操作后所得新度数列需要重新排序,且删去度数为零的节点).

Erdös定理(充要条件)

设非负整数列d=(d~1~,d~2~,…,d~n~)满足: n-1>=d~1~>=d~2~>=…>=d~n~>=0,则d可简单图化 等价于

1.d~1~+d~2~+…+d~n~=0(mod 2).

2.对r=1,2,…,n-1有d~1~+d~2~+…+d~r~ <= r(r-1)+min{r,d~r+1~}+ min{r,d~r+2~}+…+min{r,d~n~}(检查n-1个不等式).

图的结构

同构

将图一中的所有节点V~1~一一置换为图二中的节点V~2~后得到的图与图二相等则这两个图同构, 即置换后的E~1~=E~2~.

同构的充要条件:

1. 两个图的结点和边分别存在一一对应，且保持关联关系.

同构的必要条件:

1. 边数相同, 顶点数相同. 度数相同的结点数目相等, 即度数列相同(不计度数的顺序).

图的运算

|运算|解释|
| :--- | ---- |
|G-E′|删除E′|
|G-V′|删除V′|
|G\e|边e的收缩, 表示从G中删除e后，将e的两个端点用一个新的顶点代替|
|G+(u, v)|加新边|
|G~1~∪G~2~|以E~1~∪E~2~为边集, 以E~1~∪E~2~中边关联的结点组成的集合为结点集|
|G~1~∩G~2~|以E~1~∩E~2~为边集, 以E~1~∩E~2~中边关联的结点组成的集合为结点集|
|G~1~-G~2~|以E~1~-E~2~为边集, 以E~1~-E~2~中边关联的结点组成的集合为结点集|
|G~1~⊕G~2~|以E~1~⊕E~2~为边集, 以E~1~⊕E~2~中边关联的结点组成的集合为结点集|
|G~1~+G~2~|G~1~与G~2~不相交,G~1~+G~2~ = <V,E>,其中V= V~1~∪V~2~,E= E~1~∪E~2~∪{(u, v)|u∈V~1~∧v∈V~2~}​|
|G~1~× G~2~|V= V~1~×V~2~,E={(<u~i~, u~j~>, <v~k~, v~s~>)|<u~i~, u~j~>, <v~k~, v~s~>∈V~1~×V~2~ ∧(u~i~=v~k~∧u~j~与v~s~相邻)∨(u~j~=v~s~∧u~i~与v~k~相邻)}|
|k-立方体|Q~1~=K~2~, Q~2~=K~2~×Q~1~, …, Q~k~=K~2~×Q~k-1~|

ps:G~1~和G~2~皆为无孤立结点的图.

基本定义

通路: 顶点和边的交替序列.

回路: 始点和终点重合的通路.

空集不是回路.

简单通路: 通路中所有边互异.

简单回路: 始点和终点重合的简单通路.

初级通路(路径): 通路中所有边互异，所有的顶点互异.

初级回路(圈): 始点和终点重合的初级通路. 长度(边数)为奇数的圈称为奇圈，长度为偶数的圈为偶圈.

复杂通路: 通路中有边重复.

复杂回路: 始点和终点重合的复杂通路.

周长: 最长圈的长度,记作c(G).

围长: 最短圈的长度,记作g(G).

点割集: 破坏图的连通性的极小的点集合.

边割集: 破坏图的连通性的极小的边集合.

扇形割集: 所有边都与某一点关联的边割集.

无向图的连通性

连通: 两个顶点之间有通路.

连通关系: 等价关系.

连通分支: 关于连通关系的等价类的导出子图.

图是连通的: 该图是平凡图或任意两结点都是连通的.

有向图的连通性

u可达v: u到v有一条有向路径.

u到v的距离: u到v长度最短的路径长度.

若u不可达v, 规定d<u, v>=∞
d<u, v> ≠d<v, u>
d<u, v>+d<v, w> ≥d<u, w>

图的直径: 图中最长的路径

连通的分类

弱连通: 有向图的基图是连通的.

单向连通: 任何一对顶点至少单向可达.

强连通: 任何一对结点，两者之间是互相可达的.

连通判别方法

强连通: 图中存在至少包含每个结点一次的回路(充要条件).

单向连通: 图中存在经过每个顶点至少一次的路(充要条件).

连通子图分类

强分图: 具有强连通性质的极大子图.

单向分图: 具有单向连通性质的极大子图.

弱分图: 具有弱连通性质的极大子图.

短程线: 两个顶点之间最短的通路, 短线程的长度记作d(u, v).

两点之间不连通时,d(u, v)=无穷.

直径: 图中最长的通路.

独立路径: 两条除起点和终点外无其他公共顶点的路径.

边不交路径: 两条无公共边(但可能有公共顶点)的路径.

二分图: 顶点集可分为两个内部顶点互不相连的子集.

点连通度: 为了破坏连通性,至少需要删除的顶点的个数, 破坏图的连通性的最小的点集合, 即最小的点割集.

边连通度: 为了破坏连通性,至少需要删除的边的条数, 破坏图的连通性的最小的边集合, 即最小的边割集.

K-连通图: 删除K点后仍然连通或破坏图的连通性的最小的点数, 即K <= 点连通度.

K-边连通图: 删除K边后仍然连通或破坏图的连通性的最小的边数, 即K <= 边连通度.

块: 极大无割点连通子图.

通路和回路

通路和回路的表示方法

简单图可用顶点序列表示,非简单图可用边序列表示或则两者混合的混合表示法.

通路和回路的存在性

定理1

在n阶图G中, 如果从顶点vi 到顶点v~j~ (v~i~ ≠ v~j~)存在通路, 则从v~i~ 到v~j~ 存在长度小于等于n-1的通路.

推论1

在n阶图G中, 若从顶点vi 到 v~j~(v~i~≠v~j~)存在通路, 则从v~i~ 到v~j~ 存在长度小于等于n−1的路径.

定理2

在一个n阶图G中, 若存在vi 到自身的回路, 则一定存在长度小于等于n的回路.

推论1

在一个n阶图G中, 若存在vi 到自身的简单回路, 则一定存在vi 到自身的长度小于等于n的初级回路(圈).

PS: 若G 为无向图, 且vi 到自身存在回路, 则不一定存在vi 到自身的长度小于等于n的圈.

扩大路径法

通路始点和终点向两端扩展得到最大路径.

连通性

短程线的性质

1. u=v时,d(u, v)=0.

2. d(u, v)+d(v, w) ≥d(u, w).

3. d(u, v)=d(v, u).

直径的性质

二分图的充分必要条件

充分必要条件: 一个无向图是二分图当且仅当图中无奇圈.

补

设G为n阶无向图, 若G是连通图, 则G的边数m≥n-1.

Whitney定理

点连通度 <= 边连通度 <= 最小度

引理1

减去边割集后的图的连通分支数 = 图的连通分支数 + 1

点割集无此性质.

引理2

由最小边割集割去后产生的两个连通分支必定有两点不相连.

PS:原图必须为非完全图.

推论

K-连通图一定是K-边连通图.

λ=δ的充分条件

G是n(n≥6)阶连通简单无向图. 下列三个皆为λ(G)=δ(G)的充分条件
1. δ(G)≥ [n/2].
2. d(G)≤2.
3. 任意一对不相邻顶点u, v都有d(u)+d(v)≥n-1.

2-连通的充分必要条件

若G为n(n≥3)阶无向简单连通图且G中任意两个顶点共圈, 则G是2-连通图.

2-边连通的充分必要条件

若G为n(n≥3)阶无向图且G中任意两个顶点共简单回路, 则G是2-边连通图.

k-(边)连通的充分必要条件

1. 若G为n(n≥3)阶无向图且G中任意两个顶点之间有k条以上独立路径, 则G是k-连通图.
2. 若G为n(n≥3)阶无向图且G中任意两个顶点之间有k条以上边不交路径, G是k-边连通图.

割点的充分必要条件

若无向连通图G中存在与v不同的顶点u和w, 使得从顶点u到w 的路径都要经过v, 则v是割点.

桥的充分必要条件

若无向连通图G中的任何圈都不过边e则边e是桥.

割点, 桥的充分必要条件

若无向连通图G中V(G)划分成V1和V2且V1中任意顶点到V2中任意顶点的路径都要经过v(e),则v(e)是割点(桥).

块的充分必要条件

若G是n(n≥3)阶无向简单连通图且满足以下条件其中之一.

1. G中任意2顶点共圈.
2. G中任意1顶点与任意1边共圈.
3. G中任意2边共圈.
4. G中任意2顶点与任意1边, 有路径连接这2顶点并经过这1边.
5. G中任意3顶点, 有路径连接其中2顶点并经过第3点.
6. G中任意3顶点, 有路径连接其中2顶点并不经过第3点.

则G是块.

以上6条件皆为充分必要条件.

未名定理

定理1

G是n(n≥6)阶简单无向连通图, λ(G)<δ(G), 则存在G^^以G为生成子图, G^^ 由完全图K~n1~和K~n-n1~, 以及它们之间的λ(G)条边组成, λ(G)+2 ≤ n1 ≤ [n/2] .

[n/2]为向下取整运算.

推论1

δ(G)≤δ(G^*^)≤n1-1≤ [n/2]-1.

推论2

G^^中有不相邻顶点u和v, 使得dG^^(u)+dG^*^(v)≤n-2.

推论3

d(G)≥d(G^*^)≥3.

定理2

G是n阶简单连通无向非完全图, 则 2δ(G) - n + 2 ≤ κ(G) .

定理4

n阶简单连通图的κ, λ, δ之间关系有且仅有3种可能.

1. κ = λ = δ = n-1 (完全图)
2. 1 ≤ 2δ-n+2 ≤ κ ≤ λ = δ ≤ n-2 (δ ≥ [n/2]时)
3. 0 ≤ κ ≤ λ ≤ δ < [n/2] (δ < [n/2]时)

总结

1. 2-连通图: κ≥2, 或连通无割点
2. 2-边连通图: λ≥2, 或连通无桥
3. K2是块, 但不是2-(边)连通图
4. 2-连通图 ⊂ 2-边连通图 ⊂ 块
5. n≥3, 2-连通图<=>块

欧拉图

基本定义

欧拉通路: 通过所有边一次且仅一次行遍所有顶点的简单通路.

欧拉回路: 通过所有边一次且仅一次行遍所有顶点的简单回路.

半欧拉图: 有欧拉通路无欧拉回路的图.

欧拉图: 有欧拉回路的图.

上述定义对无向图和有向图都适用.
规定平凡图为欧拉图.
环不影响图的欧拉性.

无向欧拉图的充分必要条件

1. 图中所有顶点都是偶数度.
2. 该图是若干个边不交的圈的并.

无向半欧拉图的充分必要条件

1. 图中恰有2个奇度顶点.

有向欧拉图的充分必要条件

1. 图中所有顶点的入度与出度相等.
2. 该图是若干个边不交的有向圈的并.

有向半欧拉图的充分必要条件

1. 图中恰有2个奇度顶点入度与出度不相等, 其中1个入度比出度大1, 另1个出度比入度大1.

欧拉图算法

Fleury算法

图中任意选择一个顶点, 从该点开始不重复边的行遍全图, 除非仅有桥为下一步的行走路径, 否则不选择桥, 最后所得路径即为欧拉回路.

逐步插入回路算法

从一条回路开始, 每次任取一条目前回路中的点, 将其替换为一条简单回路, 以此寻找到一条欧拉回路.

哈密顿图

基本定义

哈密顿通路: 通过所有顶点一次且仅一次的简单通路.

哈密顿回路: 通过所有顶点一次且仅一次的简单回路.

半哈密顿图: 有哈密顿通路无哈密顿回路的图.

哈密顿图: 有哈密顿回路的图.

平凡图是哈密顿图.

无向哈密顿图的必要条件

1. ∀ V~1~⊆V, p(G-V~1~) ≤ |V~1~|.

无向半哈密顿图的必要条件

1. ∀ V~1~⊆V, p(G-V~1~) ≤ |V~1~|+1.

哈密顿通路存在的充分条件

1. ∀ u, v∈V(u和v不相邻), d(u)+d(v) ≥ n-1.

G是n(≥2)阶无向简单图.

无向哈密顿图的充分条件

若图为无向哈密顿图且u, v∈V(u和v不相邻), d(u)+d(v) ≥ n, 则该图加上边(u, v)仍然为哈密顿图.

1. ∀ u, v∈V(u和v不相邻), d(u)+d(v) ≥ n.
2. ∀ u∈V, d(u) ≥ n/2

G是n(≥3)阶无向简单图.

有向哈密顿图的充分条件

1. 强连通的竞赛图.
2. 该图含n阶强连通竞赛图.(该图为n阶有向图)

有向半哈密顿图的充分条件

1. n(≥2)阶竞赛图.
2. 该图含n阶强竞赛图.(该图为n阶有向图)

边不重的哈密顿回路

定义: 若该图的两条哈密顿回路的边集不相交则这两条回路为边不重的哈密顿回路.

定理11: 完全图K2k+1(k≥1)中同时有k条边不重的哈密顿回路, 且这k条边不重的哈密顿回路含K2k+1中所有边.

推论: 完全图K2k(k≥2)中同时有k-1条边不重的哈密顿回路, 并且删除这k-1条哈密顿回路上所有边后, 剩下的是k条彼此不相邻的边.

基本定义

无向树: 一个连通无回路的无向图.

有向树: 基图是树的有向图.

平凡树: 平凡图.

生成树: 生成子图为树.

生成树个数记为𝜏(G).

余树: 补为树.

根树: 平凡树或者有向树中有一个顶点的入度为0而其余顶点的入度均为1.

根子树: 根树的任一节点及其所有后代的导出子图.

家族树: 儿子, 父亲, 兄弟, 后代, 祖先.

有序树: 给相同层数的顶点标上次序的根树.

r叉树: 根树的每个分支点至多有r个儿子.

正则(regular)r叉树: r叉树的每个分支点恰好有r个儿子.
完全(complete)正则r叉树: 正则r叉树的每个树叶的高度均为树高.

左(右)子树: 2叉正则有序树的每个分支点的左右两个儿子导出的根子树.

森林: 每个连通分支都是树的无向图.

树叶: d(v)=1.

任一n阶非平凡无向树至少有两片树叶.

分枝点: d(v)≥2.

树枝: 生成子图与原图共有的边.

弦: 原图独有的边.

树根: 根树入度为0的顶点.

内点: 根树中除树根以外的分支点.

顶点的层数: 从树根到顶点的路径长度.

树高: 顶点的最大层数.

基本回路: 由生成树的子集与一条弦的并集生成的回路.

基本回路系统: 各个弦对应基本回路的集合.

圈秩𝜉(G): |E|-|V|+1.

基本割集: 由弦集的子集和一根树枝的并集组成的割集.

基本割集系统: 各个树枝对应基本割集的集合.

割集秩: 基本割集的个数.

环路: 图中圈或若干个边不重的圈的并.

空集是环路.
圈和简单回路都是环路, 但环路不一定是回路.

环和: 边集做对称差运算, 定点集做并运算.

Ω: 图的各边导处子图的的集合.

包含空集.

|Ω|=2^|E|^.

环路空间: 所有环路的集合.

断集: 原无向图的顶点集划分为两个子集, 断集中的边含于该图且该边两端分别连接两个子集中的顶点.

不要求极小性, 所以断集不一定是割集. 但割集一定是断集.

断集空间: 无向图中所有断集的导出子图和空集组成的集合.

根树的周游: 列出根树的所有顶点, 每个顶点恰好出现一次.

中序行遍: LDR.

前序行遍: DLR.

后序行遍: LRD.

通讯编码: 在通讯工作中，常用二进制数字0, 1组成的符号串(简称二元码)来表示数字、字母和汉字等.

不等长编码: 出现频率不同的码字用不同长度的编码.

可能出现码字互为前缀.

前缀码: 码字互相不为前缀的不等长编码.

前缀码与二叉树对应, 边代表0或1, 树叶对应一个前缀码.

最佳前缀码: 给定信号出现频率, 平均码字长度最短的前缀码.

平均码字长度: 码字长度乘以频率再求和(加权和).

带权二叉树: 每个树叶都指定实数权.

带权二叉树的权: 各片树叶的层数乘以它对应的实数权相加的和.

最优二叉树: 权最小的一个二叉树.

不唯一.

无向树的充分必要条件

1. 图中任二顶点之间存在唯一路径.
2. 图中无圈且|E|=|V|-1.
3. 图连通且|E|=|V|-1.
4. 图连通且每条边均为桥.
5. 图无圈, 但在任二不同顶点之间增加新边, 所得图含唯一的一个圈.

生成树的存在性定理

定理: 无向图具有生成树当且仅当该图是连通的.

推论:

1. 若 |E| ≥ |V|-1, 则具有生成树.
2. 余树边数为 |E|-|V|+1.
3. 余树和原图中的圈的边集有交集.

生成树算法

破圈法

删去图中圈的任意一条边, 直到图中无圈为止.

定理补充

1. 非平凡树至少有2个树叶.

2. 生成树和一条弦的并集中包含一圈, 圈中只有一条边为弦其余皆为树枝, 且不同弦对应的圈不同.

3. 任意一条数枝都对应一个原图的割集, 该割集仅由该树枝与弦组成, 且不同树枝对应的割集不同.

基本割集算法

算法一

任意选择一树枝, 生成树除去该树枝后变为两新生成树, 基本割集由这两个新树的对应顶点相连的弦和树枝组成.

生成树个数算法

算法一

𝜏(G) = 𝜏(G-e) + 𝜏(G\e)

e为任意非环边. 𝜏(G\e): G中含e的生成树个数

算法二

𝜏(K~n~) = n^n-2^

n ≥ 2, K~n~为n阶标定完全图.

构造长度为n-2的序列

方法:

Step1

选最小树叶, 与其在同一树枝上的一点为l~1~.

Step2

选最小树叶(不包含已选树叶), 与其在同一树枝上的点为l~2~.

Step

...

Step n-2

选最小树叶(不包含已选树叶), 与其在同一树枝上的点为l~n-2~.

Step n-1

(l~1~, l~2~ ... l~n-2~)即为序列.

构造K~n~的一颗生成树

方法

Step1

计算n-2的生成序列.

Step2

选择最小顶点(不包含n-2序列), 将该点与n-2序列中一点相连, 从n-2序列中删除相连的点, 加上该点.

Step

...

Step n-1

重复以上步骤n-1遍, 所连图即为K~n~的一颗生成树.

未名定理

定理1

无向连通图中的任意一棵子树所对应的弦都含于该子树所对应的所有基本回路环和运算的集合.

定理2

无向连通图中任意两个回路做环和运算得到的集合仍然为图中环路.

推论1

无向连通图中任意两个环路做环和运算得到的集合任然为图中环路.

定理3

无向连通图中的任意回路都为该图的任意一颗生成树的基本回路或者若干个基本回路的环和.

推论1

|E|-|V|+1 ≤ |C~回路~| ≤ 2^|E|-|V|+1^-1

|E|-|V|+1为弦数, 空集不是回路.

|C~环路~| = 2^|E|-|V|+1^

空集是环路.

定理4

无向连通图的环路空间是Ω的|E|-|V|+1维的子空间.

|E|-|V|+1维即环路空间中任何一个环路, 均是基于包含|E|-|V|+1个基本回路的基本回路系统中的元素推导(环和运算)而来.

定理5

连通图中每个割集至少包含该图的每棵生成树的一个树枝.

定理6

无向连通图中的任意一棵子树所对应的基本割集系统对应的树枝的并集都含于该子树所对应的所有基本割集对称差运算的集合.

定理7

断集做对称差运算仍然是断集.

定理8

无向连通图中任一断集为任一树的基本割集或若干个基本割集的对称差.

定理9

断集空间是Ω的|V|-1维的子空间.

断集空间中元素均可由|V|-1个线性无关的基本割集通过对称差运算得到.

定理10

设正则r(≥2)叉树 T 有 i 个分支点和 t个树叶, ri = i+t-1 即 (r-1)i=t-1.

Huffman算法

Step1

选取最小的两片树叶作为树叶.

Step2

将这两片树叶相加, 作为下一次循环的新实数权, 这两个权就不再加入下一轮运算.

Step3

重复前两个步骤, 直到只剩下一个权.

问题

1. 序列???
2. 定理4, 5???
3. 断集空间???

基本定义

无向图的关联矩阵: 顶点为行, 边为列, 顶点与边关联为一, 不相关为零.

无向图的基本关联矩阵: 无向图的关联矩阵删去任意一个顶点.

有向图的关联矩阵: 顶点为行, 边为列, 顶点与入边关联为负一, 顶点与出边关联为正一, 不相关为零.

无向图相邻矩阵: |V|×|V|的矩阵, 每一个元素值为该行对应的顶点是否与该列对应的顶点相邻, 是为1, 否为0.

有向图邻接矩阵: |V|×|V|的矩阵, 每一个元素值为该行对应的顶点到该列对应的顶点的边数之和.

连通矩阵: |V|×|V|的矩阵, 每一个元素值为该行对应的顶点是否连通该列对应的顶点, 是为1, 否为0.

可达矩阵: |V|×|V|的矩阵, 每一个元素值为该行对应的顶点是否可达该列对应的顶点, 是为1, 否为0.

u可达v: u到v有一条有向路径.

生成树算法

无向图的基本关联矩阵法

任取一无向基本关联矩阵的n-1列构成方阵, 若该行列式的值不等于零, 则该方阵对应的子图为生成树.

无向图的关联矩阵的性质

1. 行和为2.
2. 列和为该点度.
3. 每行所有1对应的边构成断集.
4. 若图有k(k>1)个连通分支, 矩阵为伪对角阵.
5. 若连通图有n个顶点则关联矩阵的秩为n-1, 基本关联的矩阵的秩为n-1.
6. 若图有p个连通分支, 则基本关联的矩阵的秩为n-1.
7. 平行边对应的列相同.
8. 不能表示自环.

有向图的关联矩阵的性质

1. m~1j~+m~2j~+...+m~nj~=0 (j = 1, 2, 3...)
2. 每行 1 项的个数即位该点出度, 每行 -1 项的个数即位该点入度.
3. 握手定理: m~11~+m~21~+...+m~n1~+...+m~1m~+m~2m~+...+m~nm~=0
4. 平行边对应的列相同.
5. 不能表示自环.

无向图相邻矩阵的性质

1. 矩阵对称.
2. 每行(列)和为顶点度.

有向图邻接矩阵的性质

1. 行和为出度.
2. 列和为入度.
3. 主对角线元素为各顶点环的个数.

相邻矩阵与通路数

1. a^(r)^ _ij: 从v~i~到v~j~的长度为r的通路总数.

2. a^(r)^ _ii: 含v~i~的长度为r回路总数.

3. a^(2)^ _ii=d(v~i~).

4. 若无向图连通, 则距离d(vi, vj)=min{r|a^{(r)}~{ij} \neq 0}.

a^(r)^ _ij: v~ik~×v~kh~...×v~dj~(r个元素相乘).
B~r~=A+A^2^+…+A^r^.

邻接矩阵与通路数

1. a^(r)^ _ij: 从v~i~到v~j~的长度为r的通路总数.
2. a^(r)^ _ii: 含v~i~的长度为r回路总数.
3. b^(r)^ _ij:从v~i~到v~j~的长度小于r的通路总数
4. b^(r)^ _ii: 含v~i~的长度小于r回路总数.

a^(r)^ _ij: v~ik~×v~kh~...×v~dj~(r个元素相乘).
B~r~=A+A^2^+…+A^r^.

连通矩阵的性质

1. 主对角线元素都是1: ∀vi∈V, vi与vi连通.
2. 连通图: 所有元素都是1.
3. 伪对角阵: 对角块是连通分支的连通矩阵.

可达矩阵的性质

1. 主对角线元素都是1: 任一顶点都自己可达自己.
2. 强连通图: 所有元素都是1.
3. 伪对角阵: 对角块是连通分支的可达矩阵.

计算可达矩阵的方法

方法1

Step1

求B~n-1~, B~n-1~=A+A^2^+…A^n-1^.

Step2

再把B~n-1~中的非零元均改为一, 零元保持不变, 得到可达性矩阵.

方法2

Step1

把A^i^ (i=1, 2, …, n)中的非零元改为1, 零元保持不变, 得到布尔矩阵A^(i)^(i=1, 2, …, n-1).

Step2

求得可达矩阵P=A^(1)^∨A^(2)^∨…∨A^(n-1)^.

问题

1. 用邻接矩阵(相邻矩阵)求回路数时会不会重复???

基本定义

可平面图/平面图: 可以画在平面上, 使得边与边不在非顶点处相交的图.

可平面图是图的性质.

极大平面图: 在任意两个不相邻顶点之间加边就是非平面图.

极大平面图一定连通 .
极大平面图不含有割点和桥(|V| > 2).

平面嵌入(平面表示): 将图画在平面上使得边与边不在非顶点处相交.

平面嵌入是平面图的一种表示形式, 平面图的平面嵌入不唯一.

球面嵌入: 将图画在球面上使得边与边不在非顶点处相交.

曲面嵌入: 将图画在曲面上使得边与边不在非顶点处相交, 如环面嵌入.

约当曲线: 自身不相交的, 始点和终点重合的曲线.

同胚: 两图同构，或反复插入/消去2度顶点后同构.

面和次

面: 平面图的边将图所在平面划分为若干区域, 其中每个区域都称作面.

无限面(外部面): 面积无限的面.

有限面(内部面): 面积有限的面.

边界: 包围每个面的所有边组成的回路组(圈, 简单回路, 复杂回路或其并).

面的次数: 边界长度(回路长度).

悬挂边对其所插入的面的次的贡献是2, 对其他面的贡献是0.

约当定理

约当曲线将平面分为曲线内部和曲线外部两部分, 连接内部点和外部点的任何连续曲线必与约当曲线相交.

平面图的充要条件

1. 可平面嵌入等价于可球面嵌入.
2. 没有与K5同胚的子图，也没有与K3,3同胚的子图.
3. 没有可以边收缩到K5的子图，也没有可以边收缩到K3,3的子图.

推论1

球面嵌入和平面嵌入的图同构.

极大平面图的充要条件

每个面的次数都为3.

欧拉公式

连通平面图满足|V|-|E|+|R|=2

R是G的所有面的集合.

推论1

平面图满足|V|-|E|+|R|=1+|P|

P是G的所有连通分支的集合.

未名定理

定理1

所有面的次数和为边数的两倍.

定理2

极大平面图的最小度数大于等于3.

|V| > 3.

定理3

任何平面嵌入的内部面都可以在另一种平面嵌入下成为外部面.

定理4

连通平面图的最小次数为l, 则满足以下公式2 \times |E| \geq l \times |R|.

定理5

极大平面图: |E| = 3 \times |V| - 6.

定理6

简单平面图最小度数小于等于5.

问题