图论及其应用
2017-11-09 15:45:17 0 举报AI智能生成
中山大学图论及其应用思维导图
作者其他创作
大纲/内容
树
概念
树：连通的无圈图
森林：无圈的图（不一定连通）
定理2.1：在一棵树中，任意两个顶点均由唯一的路连接
定理2.2：若G是树，则ε=υ-1
推论2.2：每棵非平凡树至少有两个1度顶点
割边和键
割边：使得ω(G-e)>ω(G)的边e
定理2.3：e是G的割边当且仅当e不包含在G的一个圈中
定理2.4：一个连通图是树当且仅当它的每条边都是割边
推论2.4.1：每个连通图都包含生成树
推论2.4.2：若G连通，则ε≥υ-1
生成树T：G的生成子图同时又是树
定理2.5：设T是图G的生成树，并且e是G的不在T中的一条边，则T+e包含唯一的圈
对V的子集S和S'，用[S,S^']表示一个端点在S中，另一个端点在S'中的所有边的集合
边割：删去边割图连通分支会变多
极小边割（键）：再删少一条都不能使连通分支变多
补图：若H是G的子图，G中H的补图是指子图G-E(H)，记为H ̅(G)
余树：生成树的补
定理2.6：设T是连通图G的生成树，e是T的任一边，则
1、余树不包含G的键
2、T ̅+e包含G的唯一的键
1、余树不包含G的键
2、T ̅+e包含G的唯一的键
割点
概念：割点v是指删去该点会使得图G的连通分支变多
定理2.7：设v是树G的顶点，则v是G的割点当且仅当d(v)＞1
推论2.7：每个非平凡的无环连通图，至少有两个不是割点的顶点
Cayley公式
边收缩：G的边e称为被收缩，是指把它删去并使它的两个端点重合，这样得到的图记为G·e
若T是树，则T·e也是树
用τ(G)记G的生成树的棵数
定理2.8：若e是G的连杆，则τ(G)=τ(G-e)+τ(G∙e)。
定理2.9：τ(K_n )=n^(n-2)
连线问题（求最小生成树）
Kruskal算法：每次选权值最小的且不会与已选边构成圈的边
Prim算法：选定起始点，选择离该点最近的点，然后后面就找与那些已选的点最近的点
Euler环游和Hamilton圈
Euler环游
Euler迹：经过图G的每条边的迹称为G的Euler迹
半Euler图：一个图包含Euler迹，但不包含Euler环游
Euler环游：经过图G的每条边恰好一次的闭迹
Euler图：一个图包含Euler环游
定理4.1：一个非空连通图是Euler图当且仅当它没有奇点
中国邮递员问题
求Euler图的Euler环游的算法
Fleury算法
定理4.2：若G是Euler图，则G中任一用Fleury算法作出的迹都是G的Euler环游
求一般赋权图的最优环游算法
Hamilton图
Hamilton路：经过图G中所有顶点一次且仅一次的路径
半Hamilton图：具有Hamilton路但不含Hamilton圈的图
Hamilton圈：经过图G中所有顶点一次且仅一次的圈
Hamilton图：具有Hamilton圈的图
定理4.3：若G是Hamilton图，则对于V的每个非空真子集S，均有ω(G-S)≤|S|
推论4.3：设无向图G=(V,E)是半Hamilton图，那么对于任意∅≠S⊂V，均有ω(G-S)≤|S|+1
定理4.4：设G是υ(υ≥3)阶无向简单图，若对于G中任意不相邻的顶点u和v均有d(u)+d(v)≥υ，则G中存在Hamilton圈。
引理4.5：设G是简单图，u和v是G中不相邻的顶点，且适合d(u)+d(v)≥υ，则G是Hamilton图当且仅当G+(u,v)是Hamilton图。
闭包c(G)：反复连接G中度之和不小于v的不相邻的顶点对，知道没有这样的顶点对为止
引理4.6：c(G)是唯一确定的
定理4.7：一个简单图是Hamilton图当且仅当它的闭包是Hamilton图
推论4.7：设G是v≥3的简单图。若c(G)是完全图，则G是Hamilton图
对集（匹配）
对集
对集：M是边集的子集，M中任意俩元素均不相邻
M中一条边的两个端点称为在M下是配对的。若对集M的某条边与顶点v关联，则称M饱和v，并称v是M饱和的，否则称v是M非饱和的
完美对集：G的每个顶点都属于该对集里
最大对集：边数最多的那个对集；完美对集都是最大对集
M-交错路：G的M-交错路是指其边在E\M和M中交错出现的路
M-可扩路：是指其起点和终点都是M非饱和顶点的M-交错路
定理6.1：G的对集M是最大对集当且仅当G不包含M-可扩路
偶图的对集和覆盖
N_G (S)：即图G中S的邻点，S为顶点的子集
定理6.2：设G为具有二分类(X,Y)的偶图，则G包含饱和X的每个顶点的对集当且仅当|N(S)|≥|S|,对所有S⊆X成立。
推论6.2：若G是k正则偶图（k＞0），则G有完美对集
覆盖：图G的一个覆盖是指V的一个子集K，使得G的每条边都至少有一个端点在K中
最小覆盖：G没有覆盖K'，使得|K' |<|K|
引理6.3：设M是对集，K是覆盖，适合|M|=|K|。则M是最大对集，且K是最小覆盖
完美对集
奇（偶）分支：奇（偶）数个顶点的分支称为奇（偶）分支
o(G)表示G的奇分支个数
定理6.4（Tutte）：图G有完美对集当且仅当o(G-S)≤|S|,对所有S⊂V成立
推论6.4：每个没有割边的3正则图都有完美对集
人员分派问题
匈牙利算法
最优分派问题
独立集和团
独立集
点
独立集：设S是V的一个子集，若S中任意两个顶点在G中均不相邻，则S是G的一个独立集
最大独立集：G不包含适合|S' |>|S|的独立集S'
覆盖：V的子集K，使得G的每条边都至少有一个端点属于K
独立数：G的最大独立集的顶点数称为G的独立数，记为α(G)
覆盖数：G的最小覆盖的顶点数称为G的覆盖数，记为β(G)
定理8.1：设S⊆V，则S是G的独立集当且仅当V\S是G的覆盖。
推论8.1：α+β=υ
边
边覆盖：G的一个边覆盖是指E的一个子集L，使得G的每个顶点都是L中某条边的端点
边独立集：即对集
边覆盖并不总是存在，G有边覆盖当且仅当δ＞0
边独立数和边覆盖数：最大对集的边数称为边独立数，记作α′G;
最小边覆盖的边数称为边覆盖数，记作β′(G)
对集的补集不一定是边覆盖，边覆盖的补集也不一定是对集
定理8.2(Gallai)：若δ>0,则α'+β'=υ
定理8.3：在δ>0的偶图G中，最大独立集的顶点数等于最小边覆盖的边数。
团：顶点集C被称为无向图 G 的团，如果C是顶点集V的子集(C⊆V)，而且任意两个C中的顶点都有边连接
Turan定理
定理8.8：若简单图G不包含K_(m+1)，则G度弱于某个完全m部图H。并且，若G具有与H相同的度序列，则G≅H
设T_(m,n)表示有n个顶点的完全m部图，它的各个部分在大小上尽可能地相等
定理8.9：若G是简单图，并且不包含K_(m+1)，则ε(G)≤ε(T_(m,ν))。此外，仅当G≅T_(m,ν)时，有ε(G)=ε(T_(m,ν))
平面图
平面和平面图
平面图：如果一个图能画在平面上使得它的边仅在端点相交，则称这个图为可嵌入平面的，或称为平面图
Jordan曲线：是指一条连续的自身不相交的，起点和终点相重合的曲线
设J是平面上的一条Jordan曲线，平面的剩下部分被分成两个不相交的开集，称为J的内部和外部，分别记为int J和ext J，并且用Int J和Ext J表示它们的闭包
Int J∩Ext J=J
Jordan曲线定理：连接int J的点和ext J的点的任何连线，必在某点和J相交
定理10.1：K_5 和K_3,3是非平面图
定理10.2：图G可嵌入平面当且仅当它可嵌入球面。
定理10.3：若图G是平面图，则G的任何子图都是平面图
定理10.4：若图G是非平面图，则G的任何母图也都是非平面图。
对偶图
面：平面图G把平面划分成若干连通的区域：这些区域的闭包称为G的面
用F(G)和ϕ(G)表示平图G中面的集合和面的个数
每个平图恰有一个无界的面，称为外部面
用b(f)表示平图G中面f的周界
面f的度：dG(f)是指和f关联的边的条数(即b(f)中边的条数，其中割边被计算两次)
定理10.5：设v是平面图G的顶点，则存在G的一个平面嵌入，使得v在这个嵌入的外部面上
对偶图：对于平面图G，定义另一个图G*：对于G的每个面f，都有G*的顶点f*与之对应，对于G的每条边e，都有G*的边e*与之对应；G*中顶点f* 和g* 由边e* 连接，当且仅当G中与顶点f* 和g* 对应的面f和g被边e分隔。图G*称为G的对偶图
若e是平图G的环，则e* 是G*的割边，反之亦然
当G是连通图，则G**≅G
同构的图的不同平面嵌入的对偶图可能不同构
υ(G* )=ϕ(G)
ε(G* )=ε(G)
d_(G* ) (f* )=d_G (f) 对所有f∈F(G)成立
ε(G* )=ε(G)
d_(G* ) (f* )=d_G (f) 对所有f∈F(G)成立
定理10.6：若G是平图，则图面的度之和=边数的两倍
Euler公式
定理10.7：若G是连通平图，则υ-ε+ϕ=2
推论10.7.1：给定的连通平面图的所有平面嵌入有相同的面数
推论10.7.2：若G是υ≥3的简单平面图，则ε≤3υ-6
推论10.7.3：若G是简单平面图，则δ≤5
推论10.7.4：K_5 是非平面图
平面图的判定
片：设G_1=(V_1,E_1 )是图G=(V,E)的子图。图G的相关于G_1的一个片是：
1、或者 一条边(u,v)∈E，其中(u,v)∉E_1 但u,v∈V_1；
2、或者G-G_1的一个连通分支加上该连通分支与G_1相关联的边
1、或者 一条边(u,v)∈E，其中(u,v)∉E_1 但u,v∈V_1；
2、或者G-G_1的一个连通分支加上该连通分支与G_1相关联的边
接触点
桥
设C是图G的一个圈
C上的两座桥B1和B2被称为不相容的(B1≠B2)是说：当它们被放入C的同一个面中时，它们至少有一条边交错
两个图被称为是同态的是说：通过在这两个图中加入和压缩2度点，可以使这两个图同构
一个图是非平面图当且仅当它的同态图也是非平面图
剖分图
定理10.8 (Kuratowski定理)：一个图G是平面图当且仅当G中不包含同态于K_5或K_3,3的子图
平面图判定算法
G允许的：设H*是G的子图H的平面嵌入。如果存在G的一个平面嵌入G*，使得H*⊆G*，那么H就称为是G允许的
算法
平面图着色
地图：连通无割边平面图的平面嵌入及其所有面称为平面地图或地图。
面着色：对地图G的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对G的一种正常面着色
若能用k种颜色给G进行正常面着色，就称G是k面可着色的。
若G是k面可着色的，但不是(k−1)面可着色的，就称G的面色数为k，记作χ∗(G)=k。
定理10.10：地图G是k面可着色的当且仅当它的对偶图G*是k可着色的
定理10.11：每个平面图都是5顶点可着色的
定理10.12：下面3个断言是等价的
(i) 每个平面图都是4顶点可着色的
(ii) 每个平面嵌入都是4面可着色的
(iii) 每个简单2边连通3正则平面图都是3边可着色的
(i) 每个平面图都是4顶点可着色的
(ii) 每个平面嵌入都是4面可着色的
(iii) 每个简单2边连通3正则平面图都是3边可着色的
图和子图
图和简单图
图：G
顶点集：V(G)
顶点数v = |V(G)|
顶点数v = |V(G)|
边集：E(G)
边数：ε=|E(G)|
边数：ε=|E(G)|
连杆：不是环的边
图的同构
同构的定义
偶图：顶点集可以分为两个子集，任意一条边的两个端点分别在两个子集中
完全偶图：X中的每个顶点都与Y中的每个顶点相连。K_(m,n)
子图
生成子图：点集与母图相等，边集不等
导出子图：点集为母图的子集，边集为包含点集里的所有边
顶点的度
度：顶点v连接的边的数目，记做d(v)
最大度：∆(G)
最小度：δ(G)
有向图
入度：v作为边的终点的次数
出度：v作为边的起点的次数
度数为偶数（奇数）的点称为偶点（奇点）
定理1.1握手定理：一个图的顶点的度数之和=边数的两倍
推论1.1：任何图中奇度数顶点的个数是偶数
度序列
度序列可图化
定理1.2：一个度序列可图化当且仅当该度序列的和是偶数
关联矩阵和邻接矩阵
关联矩阵M(G)：点与边的关联次数；行为点列为边
每列之和为2：每条边关联两个顶点
每行元素之和为该顶点的度数
所有元素之和为边数两倍
邻接矩阵：每个点之间的关系
无向图的邻接矩阵是对称的
有向图的邻接矩阵中的值为该两点间边的权值
通路与回路及图的连通性
通路与回路
途径W：从v0到vk的一条途径
回路（闭途径）：途径W的起点=终点
迹：在途径W中，若边互相不同称为迹
闭迹：迹W中起点=终点
路（径）：在迹W中，点也互相不通，则称W为路
圈：路的起点=终点
奇圈：长度为奇数
偶圈：长度为偶数
图的连通性
称u,v是连通的，是指u,v之间存在通路
连通图：G中任意两个顶点都是连通的
连通分支ω(G)
定理1.3：一个无向图G是偶图当且仅当G中无长度为奇数的圈（奇圈）
最短路径问题
Dijkstra算法：以某个点为起点，不停地找与它最短的，然后将最短的边连着的点加入到起点集里再找与起点集里最短的
Floyd算法：三重循环，每次把某个点当做途经点
连通度
连通度
顶点割
（点）连通度：G所具有的k顶点割中最小的k，记做κ(G)
所有非平凡图都是1连通的
κ(G)≥k，则称图G是k连通的
完全图没有顶点割
边割
边连通度：G的所有k边割中最小的k，记做κ' (G)
G平凡或不连通：κ' (G)=0
G具有割边：κ' (G)=1
κ' (G)≥k则称G是k边连通
所有非平凡的连通图都是1边连通
定理3.1： κ≤κ'≤δ。（点连通度≤边连通度≤图的最小度）
块
概念：没有割点的连通图
内部不相交的路：G中一族路称为内部不相交的，如果G中没有这样的顶点，它是这族路中一条以上的路的内部顶点
定理3.2：一个υ≥3的图G是2-连通的，当且仅当G的任意两个顶点至少被两条内部不相交的路所连
推论3.2.1：若G是2连通图，则G的任意两个顶点都位于同一个圈上
推论3.2.2：若G是υ≥3的块，则G的任意两条边都位于同一个圈上。
边的剖分：边e称为被剖分，是指删去它，并换上一条连接它的两个端点而长为2的路，该路的内部顶点是一个新顶点
Menger定理
定理3.3：设u和v是图G中的两个不相邻的顶点。分割u和v的最小顶点数目等于u到v的内部不相交的路径的最大数目。
有向图
强连通有向图
有向途径
有向迹：途径中边不重复出现
有向路：有向迹中顶点不重复出现
有向圈：有向路的起点=终点
可达：两点间存在有向路径
连通
弱连通：图D的基图为连通图（不考虑方向）
单向连通：若D中任意两个顶点要么u→v，要么v→u
强连通：对任意两个顶点互相可达
定理5.1：如果有向图D包含一条长为l的有向(u,v)途径，那么D包含一条长至多为l的有向(u,v)路
定理5.2：有向图D是强连通的当且仅当D包含一个闭的生成途径(经过所有顶点的闭途径)
无向简单图G的定向图：给G的每一条边加上一个方向所得到的有向图D称为G的定向图
定理5.3：一个非平凡的连通图G有强连通的定向图当且仅当G不含割边
竞赛图
有向Hamilton路：经过有向图中每一个顶点的路
有向Hamilton圈：该圈经过有向图每一个顶点
竞赛图：给无向完全图K_υ的每条边加一个方向的定向图称为竞赛图
定理5.4：每一个竞赛图包含一条Hamilton路
定理5.5：一个非平凡的竞赛图T是Hamilton图当且仅当T是强联通的
边着色
边色数
正常k边着色：无环图G的一个k边着色C是指k种颜色1,2,⋯,k对于G的各边的一个分配。若没有相邻的两条边有着相同的颜色，则称着色是正常的。
k边可着色：若G有正常的k边着色，则称G是k边可着色的。 若G是k边可着色的，则对于每个l>k，G亦是l边可着色的。
边色数：无环图G的边色数χ' (G)是指G为k边可着色的那些最小的k值。若χ' (G)=k，则称G是k边色的。
显然：在正常着色中，χ'≥Δ
引理7.1：设G为不是奇圈的连通图，则G有一个2边着色，它的两种颜色在度至少为2的每个顶点上都表现。
着色的改进：给定G的k边着色C后，我们用c(v)表示在v上表现的不同颜色的数目，显然恒有c(v)≤d(v) 。当另一个着色比这个着色用的颜色多就叫着色的改进
引理7.2：设C=(E_1,E_2,⋯,E_k)是G的一个最优k边着色。若存在G中的一个顶点u和颜色i及j，使得i不在u上表现，而j在u上至少表现两次，则G[E_i∪E_j]中包含u的那个分支是奇圈。
定理7.3：若G是偶图，则χ'=Δ。
Vizing定理
定理7.4：若G是简单图，则χ'=Δ或χ'=Δ+1
顶点着色
色数
k顶点着色：G的一个k顶点着色是指k种颜色1,2,⋯,k对于G的各顶点的一个分配
着色正常：任意两个相邻顶点都分配到不同的颜色
把正常k顶点着色简称为k着色，把k顶点可着色简称为k可着色
色数：G的色数χ(G)是指G为k可着色的数k的最小值
若χ(G)=k，则称G是k色的
临界图：一个图G称为临界的，是说：对G的每个真子图H有χ(H)<χ(G)
k临界图是指k色的临界图。每个k色图有k临界子图
定理9.1：若G是k临界图，则δ≥k-1
推论9.1.1：每个k色图至少有k个度不小于k-1的顶点
推论9.1.2：对任意图G，有χ≤Δ+1
定理9.2：临界图的顶点割不是团
推论9.2：每个临界图都是块
定理9.3：设G是k临界图且有2顶点割{u,v}，则
1、 G=G_1∪G_2，这里G_i 是i型(i=1,2)的{u,v}分支，并且
2、G_1+uv和G_2∙uv都是k临界图(这里G_2∙uv表示G_2的u和v重合而得到的图)
1、 G=G_1∪G_2，这里G_i 是i型(i=1,2)的{u,v}分支，并且
2、G_1+uv和G_2∙uv都是k临界图(这里G_2∙uv表示G_2的u和v重合而得到的图)
Brooks定理
定理9.4：若G是连通的简单图，并且它既不是奇圈，又不是完全图，则χ≤Δ
网络
流
网络：一个网络N是指一个具有两个特定顶点子集X和Y的有向图D(称为N的基础有向图)，以及一个在D的弧集A上定义的非负整数数值函数c
称函数c是N的容量函数，它在弧a上的值称为a的容量
称X中的顶点是N的发点，Y中的顶点是N的收点
既不是发点又不是收点的顶点称为中间点；所有中间点的集合记为I
流：网络N中的流是指定义在A上的一个整数值函数f，使得0≤f(a)≤c(a), 对所有a∈A成立以及 f^- (v)=f^+ (v), 对所有v∈I成立
零流：每个网络至少有一个流，即对任何a∈A，由f(a)=0
合成流量：若S是网络N的顶点子集，而f是N中的流
f流出S的合成流量：f^+ (S)-f^- (S)
f流入S的合成流量：f^- (S)-f^+ (S)
流的值：对于任何流f，流出X的合成流量等于流进Y的合成流量。这个共同的量称为f的值。用val f表示
val f=f^+ (X)-f^- (X)
割
定义：设N是具有单一发点x和单一收点y的网络。N中的割是指形如(S,S ̅)的弧集，这里x∈S,而y∈S ̅
容量：指它的各条弧的容量之和。我们用cap K表示K的容量。于是cap K=∑_(a∈K)▒〖c(a)〗
引理11.1：对于N中的任一流f和任一割(S,S ̅)均有val f=f^+ (S)-f^- (S)
最小割：N中的割K称为最小割，是说：N中不存在割K'使得cap K^'<cap K
定理11.2：对于N中的任一流f和任一割K=(S,S ̅)，均有val f≤cap K
推论11.2：设f是流而K是割，适合val f=cap K。则f是最大流而K是最小割
最大流最小割定理
定义内容见书
f可增路：从发点x到收点y的f非饱和路
定理11.3：N中的流f是最大流当且仅当N不包含f可增路
定理11.4：在任何网络中，最大流的值等于最小割的容量
标号法求最大流最小割
0 条评论
下一页
