图论及其应用
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包含唯一的圈
边割:删去边割图连通分支会变多
极小边割(键):再删少一条都不能使连通分支变多
补图:若H是G的子图,G中H的补图是指子图G-E(H),记为H ̅(G)
余树:生成树的补
定理2.6:设T是连通图G的生成树,e是T的任一边,则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.4:设G是υ(υ≥3)阶无向简单图,若对于G中任意不相邻的顶点u和v均有d(u)+d(v)≥υ,则G中存在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是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:每个没有割边的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.3:在δ>0的偶图G中,最大独立集的顶点数等于最小边覆盖的边数。
团:顶点集C被称为无向图 G 的团,如果C是顶点集V的子集(C⊆V),而且任意两个C中的顶点都有边连接
Turan定理
定理8.8:若简单图G不包含K_(m+1),则G度弱于某个完全m部图H。并且,若G具有与H相同的度序列,则G≅H
平面图
平面和平面图
平面图:如果一个图能画在平面上使得它的边仅在端点相交,则称这个图为可嵌入平面的,或称为平面图
Jordan曲线:是指一条连续的自身不相交的,起点和终点相重合的曲线
设J是平面上的一条Jordan曲线,平面的剩下部分被分成两个不相交的开集,称为J的内部和外部,分别记为int J和ext J,并且用Int J和Ext J表示它们的闭包
Int J∩Ext J=J
Jordan曲线定理:连接int J的点和ext J的点的任何连线,必在某点和J相交
定理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)成立
定理10.6:若G是平图,则图面的度之和=边数的两倍
Euler公式
定理10.7:若G是连通平图,则υ-ε+ϕ=2
推论10.7.1:给定的连通平面图的所有平面嵌入有相同的面数
推论10.7.2:若G是υ≥3的简单平面图,则ε≤3υ-6
推论10.7.3:若G是简单平面图,则span lang=EN-US style='font-size:14.0pt;font-family:\"Cambria Math\
推论10.7.4:K_5 是非平面图
平面图的判定
接触点
桥
设C是图G的一个圈
C上的两座桥B1和B2被称为不相容的(B1≠B2)是说:当它们被放入C的同一个面中时,它们至少有一条边交错
两个图被称为是同态的是说:通过在这两个图中加入和压缩2度点,可以使这两个图同构
一个图是非平面图当且仅当它的同态图也是非平面图
剖分图
平面图判定算法
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)\t每个平面图都是4顶点可着色的(ii)\t每个平面嵌入都是4面可着色的(iii)\t每个简单2边连通3正则平面图都是3边可着色的
图和子图
图和简单图
图:G
顶点集:V(G)顶点数v = |V(G)|
边集:E(G)边数:font face=\
连杆:不是环的边
图的同构
同构的定义
偶图:顶点集可以分为两个子集,任意一条边的两个端点分别在两个子集中
子图
生成子图:点集与母图相等,边集不等
导出子图:点集为母图的子集,边集为包含点集里的所有边
顶点的度
度:顶点v连接的边的数目,记做d(v)
最大度:∆(G)
最小度:δ(G)
有向图
入度:v作为边的终点的次数
出度:v作为边的起点的次数
度数为偶数(奇数)的点称为偶点(奇点)
定理1.1握手定理:一个图的顶点的度数之和=边数的两倍
推论1.1:任何图中奇度数顶点的个数是偶数
度序列
度序列可图化
定理1.2:一个度序列可图化当且仅当该度序列的和是偶数
关联矩阵和邻接矩阵
关联矩阵M(G):点与边的关联次数;行为点列为边
每列之和为2:每条边关联两个顶点
每行元素之和为该顶点的度数
所有元素之和为边数两倍
邻接矩阵:每个点之间的关系
无向图的邻接矩阵是对称的
有向图的邻接矩阵中的值为该两点间边的权值
通路与回路及图的连通性
通路与回路
途径W:从v0到vk的一条途径
回路(闭途径):途径W的起点=终点
迹:在途径W中,若边互相不同称为迹
闭迹:迹W中起点=终点
路(径):在迹W中,点也互相不通,则称W为路
圈:路的起点=终点
奇圈:长度为奇数
偶圈:长度为偶数
图的连通性
连通图: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.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边着色,则称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.3:若G是偶图,则χ'=Δ。
Vizing定理
定理7.4:若G是简单图,则χ'=Δ或χ'=Δ+1
顶点着色
色数
着色正常:任意两个相邻顶点都分配到不同的颜色
把正常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:每个临界图都是块
Brooks定理
定理9.4:若G是连通的简单图,并且它既不是奇圈,又不是完全图,则χ≤Δ
网络
流
网络:一个网络N是指一个具有两个特定顶点子集X和Y的有向图D(称为N的基础有向图),以及一个在D的弧集A上定义的非负整数数值函数c
称函数c是N的容量函数,它在弧a上的值称为a的容量
称X中的顶点是N的发点,Y中的顶点是N的收点
既不是发点又不是收点的顶点称为中间点;所有中间点的集合记为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)
割
容量:指它的各条弧的容量之和。我们用cap K表示K的容量。于是cap K=∑_(a∈K)▒〖c(a)〗
最小割:N中的割K称为最小割,是说:N中不存在割K'使得cap K^'<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 条评论
回复 删除
下一页