总 结第八章 图论8.1 图的基本概念8.1.1 图定义8.1―1 一个图G 是一个三重组〈V (G ),E (G ),ΦG 〉,其中V (G )是一个非空的结点(或叫顶点)集合,E (G )是边的集合,ΦG 是从边集E 到结点偶对集合上的函数。
一个图可以用一个图形表示。
定义中的结点偶对可以是有序的,也可以是无序的。
若边e 所对应的偶对〈a ,b 〉是有序的,则称e 是有向边。
有向边简称弧,a 叫弧e 的始点,b 叫弧e 的终点,统称为e 的端点。
称e 是关联于结点a 和b 的,结点a 和结点b 是邻接的。
若边e 所对应的偶对(a ,b )是无序的,则称e 是无向边。
无向边简称棱,除无始点和终点的术语外,其它术语与有向边相同 每一条边都是有向边的图称为有向图。
每一条边都是无向边的图称为无向图。
有向图和无向图也可互相转化。
例如,把无向图中每一条边都看作两条方向不同的有向边,这时无向图就成为有向图。
又如,把有向图中每条有向边都看作无向边,就得到无向图。
这个无向图习惯上叫做该有向图的底图。
在图中,不与任何结点邻接的结点称为弧立结点。
全由孤立结点构成的图称为零图。
关联于同一结点的一条边称为自回路。
在有向图中,两结点间(包括结点自身间)若同始点和同终点的边多于一条,则这几条边称为平行边。
在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为平行边。
两结点a 、b 间互相平行的边的条数称为边［a ,b ］的重数。
仅有一条时重数为1,无边时重数为0。
定义8.1―2 含有平行边的图称为多重图。
非多重图称为线图。
无自回路的线图称为简单图。
仅有一个结点的简单图称为平凡图。
定义 8.1―3 赋权图G 是一个三重组〈V ,E ,g 〉或四重组〈V ,E ,f ,g 〉,其中V 是结点集合, E 是边的集合,f 是定义在V 上的函数,g 是定义在E 上的函数。
8.1.2 结点的次数定义 8.1―4 在有向图中,对于任何结点v ,以v 为始点的边的条数称为结点v 的引出次数(或出度),记为deg +(v );以v 为终点的边的条数称为结点v 的引入次数(或入度),记为deg -(v );结点v 的引出次数和引入次数之和称为结点v 的次数(或度数),记作deg (v )。
在无向图中,结点v 的次数是与结点v 相关联的边的条数,也记为deg (v )。
孤立结点的次数为零。
定理8.1―1 设G 是一个(n ,m )图,它的结点集合为V ={v 1,v 2,…,v n},则 定理8.1―2 在图中,次数为奇数的结点必为偶数个。
定义8.1―5 各结点的次数均相同的图称为正则图,各结点的次数均为k 时称为k ―正则图。
8.1.3 图的同构定义8.1.6 设G =〈V ,E 〉和G ′=〈V ′,E ′〉是两个图,若存在从V 到V ′的双射函数1deg()2n i i m υ==∑Φ,使对任意a 、b ∈V ,［a ,b ∈E 当且仅当［Φ(a ),Φ(b )］∈E ′,并且［a ,b ］和［Φ(a ),Φ(b )］有相同的重数,则称G 和G ′是同构的。
8.1.4 图的运算定义8.1―7 设图G 1=〈V 1,E 1〉和图G 2=〈V 2,E 2〉。
(1)G 1与G 2的并,定义为图G 3＝〈V 3,E 3〉,其中V 3=V 1∪V 2,E 3=E 1∪E 2,记为G 3=G 1∪G 2。
(2)G 1与G 2的交,定义为图G 3＝〈V 3,E 3〉,其中V 3=V 1∩V 2,E 3=E 1∩E 2,记为G 3=G 1∩G 2。
(3)G 1与G 2的差,定义为图G 3＝〈V 3,E 3〉,其中E 3=E 1-E 2,V 3=(V 1-V 2)∪{E 3中边所关联的顶点},记为G 3=G 1-G 2。
(4)G 1与G 2的环和,定义为图G 3＝〈V 3,E 3〉,G 3=(G 1∪G 2)-(G 1∩G 2),记为G 3=G 1G 2。
除以上4种运算外,还有以下两种操作:(1) 删去图G 的一条边e ;(2) 删去图G 的一个结点v 。
它的实际意义是删去结点v 和与v 关联的所有边。
8.1.5 子图与补图定义8.1―8 设G =〈V ,E 〉和G ′=〈V ′,E ′〉是两个图。
(1) 如果V ′⊆V 和E ′⊆E ,则称G ′是G 的子图。
如果V ′⊆V 和E ′⊆E ,则称G ′≠G 的真子图。
(注意:“G ′是图”已隐含着“E ′中的边仅关联V ′中的结点”的意义。
)(2) 如果V ′=V 和E ′⊆E ,则称G ′为G 的生成子图。
(3) 若子图G ′中没有孤立结点,G ′由E ′唯一确定,则称G ′为由边集E ′导出的子图。
(4)若在子图G ′中,对V ′中的任意二结点u 、v ,当［u ,v ］∈E 时有［u ,v ］∈E ′,则G ′由V ′唯一确定,此时称G ′为由结点集V ′导出的子图。
定义8.1―9在n 个结点的有向图G =〈V ,E 〉中,如果E =V ×V ,则称G 为有向完全图;在n 个结点的无向图G =〈V ,E 〉中,如果任何两个不同结点间都恰有一条边,则称G 为无向完全图,记为Kn 。
定义8.1―10 设线图G =〈V ,E 〉有n 个顶点,线图H =〈V ,E ′〉也有同样的顶点,而E ′是由n 个顶点的完全图的边删去E 所得,则图H 称为图G 的补图,记为 ,显然, 。
8.2 路径和回路8.2.1 基本概念定义8.2―1在有向图中,从顶点v 0到顶点vn 的一条路径是图的一个点边交替序列（v 0e 1v 1e 2v 2…envn ）,其中vi -1和vi 分别是边ei 的始点和终点,i =1,2,…,n 。
在序列中,如果同一条边不出现两次,则称此路径是简单路径,如果同一顶点不出现两次,则称此路径是基本路径(或叫链)。
如果路径的始点v 0和终点vn 相重合,即v 0=vn ,则此路径称为回路,没有相同边的回路称为简单回路,通过各顶点不超过一次的回路称为基本回路。
定义8.2―2 路径P 中所含边的条数称为路径P 的长度。
长度为0的路径定义为单独一个顶点。
(但注意习惯上不定义长度为0的回路。
)定理8.2―1 在一个具有n 个结点的简单图G =〈V ,E 〉中,如果从v 1到v 2有一条路径,则从v 1到v 2有一条长度不大于n -1的基本路径。
定理8.2―2 在一个具有n 个结点的简单图G =〈V ,E 〉中,如果经v 1有一条简单回路,则经v 1有一条长度不超过n 的基本回路。
定义8.2―3 在图G =〈V ,E 〉中,从结点vi 到v j 最短路径的长度叫从vi 到v j 的距离,记为H G =G G=d (vi ,v j)。
若从vi 到v j 不存在路径,则d (vi ,v j)=∞。
注意,在有向图中,d (vi ,v j)不一定等于d (v j,vi ),但一般地满足以下性质:(1) d (vi ,v j)≥0;(2) d (vi ,vi )=0;(3) d (vi ,v j)+d (v j,v k)≥d (vi ,v k)。
8.2.2 图的连通度定义8.2―4设G=〈V ,E〉是图,且vi 、v j ∈V 。
如果从vi 到v j 存在一条路径,则称v j 从vi 可达。
vi 自身认为从vi 可达。
定义8.2―5在无向图G 中,如果任两结点可达,则称图G 是连通的;如果G 的子图G ′是连通的,没有包含G ′的更大的子图G ″是连通的,则称G ′是G 的连通分图(简称分图)。
一个无向图或者是一个连通图,如图8.2―2(a )所示,或者是由若干个连通分图组成,如图8.2―2(b )所示。
图 8.2―2定理8.2―3 设G 是任一(n ,m )无向简单图,ω是其分图个数,则定义8.2―11在有向图中,如果在任两结点偶对中,至少从一个结点到另一个结点是可达的,则称图G 是单向连通的;如果在任两结点偶对中,两结点都互相可达,则称图G 是强连通的;如果它的底图是强连通的,则称图G 是弱连通的。
显然,强连通的也一定是单向连通和弱连通的,单向连通的一定是弱连通的,但其逆均不真。
在图8.2―3中,(a )是强连通的,(b )是单向连通的,(c )是弱连通的。
图 8.2―3定义8.2―12 在有向图G =〈V ,E 〉中,G ′是G 的子图,若G ′是强连通的(单向连通的,弱连通的),没有包含G ′的更大子图G ″是强连通的(单向连通的,弱连通的),则称G ′是G 的强分图(单向分图,弱分图)。
在图8.2―4中,强分图集合是:{〈{1,2,3},{e 1,e 2,e 3}〉,〈{4},φ〉,〈{5},φ〉,〈｛6｝,φ〉,〈｛7,8｝,{e 7,e 8}〉｝单向分图集合是:{〈{1,2,3,4,5},{e 1,e 2,e 3,e 4,e 5}〉,〈{6,5},{e 6}〉,〈｛7,8｝,{e 7,e 8}〉｝弱分图集合是:1()(1)2n m n n ωωω-≤≤--+{〈{1,2,3,4,5,6},{e1,e2,e3,e4,e5,e6}〉,〈｛7,8｝,{e7,e8}〉｝图8.2―48.2.3 赋权图中的最短路径设G=〈V,E,W〉是个赋权图,W是从E到正实数集合的函数,边［i,j］的权记为W(i,j),称为边的长度。
若i和j之间没有边,那么W(i,j)=∞。
路径P的长度定义为路径中边的长度之和,记为W(P)。
图G中从结点u到结点v的距离记为d(u,v),定义为min{W(P)|P为G中从u到v的路径}∞当从u到v不可达时本小节主要讨论在一个赋权的简单连通无向图G=〈V,E,W〉中,求一结点a(称为源点)到其它结点x的最短路径的长度,通常称它为单源问题。
下面介绍1959年迪克斯特拉(E.W.Dijkstra)提出的单源问题的算法,其要点如下:(1) 把V分成两个子集S和T。
初始时,S={a},T=V-S。
(2) 对T中每一元素t计算D(t),根据D(t)值找出T中距a最短的一结点x,写出a到x的最短路径的长度D(x)。
(3)置S为S∪{x},置T为T-{x},若T= ,则停止,否则再重复2。
8.2.4 欧拉路径和欧拉回路哥尼斯堡(Ko nig s berg,现加里宁格勒)位于普雷格尔(Prege l)河畔,河中有两岛。
城市的各部分由7座桥接通,如图8.2―8(a)所示。
古时城中居民热衷于一个问题:游人从任一地点出发,怎样才能做到穿过每座桥一次且仅一次后又返回原出发地。
1736年欧拉用图论方法解决了此问题,写了第一篇图论的论文,从而成为图论的创始人。
不难看出,如果用结点代表陆地,用边代表桥,哥尼斯堡七桥问题就等价在于图8.2―8(b)中找到这样一条路径,它穿程每条边一次且仅一次。
