18143453325 在线咨询 在线咨询
18143453325 在线咨询
所在位置: 首页 > 营销资讯 > 信息时代 > 图论(数据库)

图论(数据库)

时间:2022-11-24 06:30:01 | 来源:信息时代

时间:2022-11-24 06:30:01 来源:信息时代

    图论 : 数学中以图为研究对象的一个分支。图论中的图是由若干个点及一些连接两点的线构成的图形,其中点表示事物,连接两点的线表示对应的两个事物之间的某种关系。图论起源于著名的哥尼斯堡七桥问题: 18世纪中叶,普鲁士的哥尼斯堡有一条普雷哥尔河,河中有两个岛屿。在河的两岸与两个岛屿之间有七座桥,如图1所示。


图1 哥尼斯堡七桥



图2 七桥问题图表示


当时人们热衷于一个难题: 一个人怎样不重复地走完七桥,最后回到出发地点? 1736年,瑞士数学家Leonhard Euler发表论文,证明哥尼斯堡七桥问题无解,即一个人不可能不重复地走完七桥回到出发点。Euler研究的方法是,用4个点A、B、C、D分别表示两岸和两个岛屿,用两点之间的连线表示对应两块陆地之间的桥,如图2所示。由于这一开创性的工作,后人把Euler尊为图论的鼻祖,称1736年为图论的元年。19世纪中叶,在电网络和饱和碳氢化合物的研究中引入连通图、树等概念。1859年,William Rowan Hamilton给出 “周游世界”的游戏,把一个正12面体的20个顶点看作20座城市,要寻找一条沿着多面体的边走的旅行路线,恰好经过每一个顶点一次,最后回到出发点,见图3。这就是所谓的哈密顿回路。到了20世纪中期以后,由于科学技术的发展,特别是计算机科学技术的迅猛发展,图论在许多领域中得到广泛的应用,自身也得到空前地发展,成为一个十分活跃的研究领域。


图3 周游世界问题


1. 图的基本概念
图是由若干个点和一些连接两点的线构成的图形,在这里点的位置、线的长短及曲直都是无关紧要的,点称作顶点,线称作边。图有有向图与无向图之分。无向图不考虑边的方向,称作无向边,简称边;有向图的边要考虑方向,称作有向边,见图4和图5。


图4 无向图



图5 有向图


有关的形式定义:
(1)无向图:设V={v1,v2,…,vn},E={e1,e2,…,em},n≥1,m≥0,其中每一个vj表示一个顶点,ek=(vi,vj)表示连接vi和vj的一条边,vi和vj称作ek的端点。在这里,(vi,vj)=(vj,vi),称作无序对,即ek是没有方向的。我们称G=<V,E>为无向图,简称图,其中V是G的顶点集,E是边集。注意:ek的两个端点可以是相同的,此时称作环,如图4中的e1=(a,a)。允许两条和两条以上的边有两个相同的端点,此时称这些边为平行边,并称平行边的条数为重数。如图4中e2、e3,是两条平行边。既无平行边也无环的图称为简单图。有n个顶点的图称为n阶图。若n=1且E=∅, 即只有一个顶点没有边的图称为平凡图。若有一条边ek=(vi,vj),则称顶点vi与vj相邻,边ek与顶点vi和vj相关联。无边关联的顶点称为孤立点。称有共同端点的两条边(vi,vj)与(vj,vk)相邻。
(2)有向图:与无向图类似,只是每条边都是有方向的,用两个端点的有序对表示ek=<vi,vj>,其中vi是ek的始点,vj是ek的终点。在有向图中,只有当两条有向边有相同的始点和终点时才称为平行边,如图5中的e3和e4是平行边,而e6和e7不是平行边。
(3)顶点的度数:在无向图中,顶点v作为边的端点的总次数称作v的度数,记作d(v)。类似地,在有向图中,顶点v作为边的端点的总次数称作为v的度数,记作d(v)。又称v作为边的始点的总次数为v的出度,记作d+(v),v作为边的终点的总次数为v的入度,记作d-(v)。d+(v)+d-(v)=d(v)。注意:一个顶点作为环的端点要计算2次; 同样地,作为平行边的端点也要重复计算。无向图G中顶点度数的最大值和最小值分别称为G的最大度数和最小度数,分别记作Δ(G)和δ(G)。类似地,有向图D中顶点度数的最大值和最小值分别称为D的最大度数和最小度数,分别记作Δ(D)和δ(D); D中顶点出度的最大值和最小值分别称为D的最大出度和最小出度,分别记作Δ+(D)和δ+(D); D中顶点入度的最大值和最小值分别称为D的最大入度和最小入度,分别记作Δ-(D)和δ-(D)。在无向简单图G中,Δ(G)≤n-1(n为G的阶数)。例如,在图4所示的无向图G中,d(a)=5,d(c)=2,d(d)=0,Δ(G)=5,δ(G)=0。在图5所示的有向图D中,d(a)=5,d+(a)=3,d-(a)=2,Δ(D)=5,Δ+(D)=3,Δ-(D)=2,δ+(D)=1,δ-(D)=1。
2. 握手定理
在任何无向图和有向图中,所有顶点的度数之和等于边数的2倍,且奇度数顶点的个数为偶数。在有向图中,所有顶点的出度之和等于所有顶点的入度之和,且都等于边数。
3. 图的同构
设G1=<V1,E1>和G2=<V2,E2>为两个无向图,若存在双射函数f:V1→V2(见函数)使得∀vi, vj∈V1,(vi,vj)∈E1当且仅当(f(vi),f(vj))∈E2,且当是平行边时(vi,vj)与(f(vi),f(vj))的重数相同,则称G1与G2同构,记做G1=G2。类似可定义有向图之间的同构。例如,图6所示的两个图同构。


图6 两个同构的图


4.完全图
任意两个顶点之间都有一条边的无向简单图。n阶完全图记为Kn。K3,K4与K5如图7所示。设D为n阶有向简单图,若D中任何两个不同的顶点之间均有两条方向相反的边,则称D为有向完全图。


图7 无向完全图


5.正则图
每个顶点度数都为k的无向简单图称为k正则图。
6.子图
设G=<V, E>, G′=<V′,E′>, 若V′V, E′E,则称G′为G的子图, 记为G′G。又当G′G, 且V′⊂V或E′⊂E时, 称G′为G的真子图。 又若V′=V时,称G′为G的生成子图。
7.补图
设G=〈V,E〉为无向简单图, 令={(u, v)|u,v∈V,u≠v且(u,v)∉E},称=〈V,〉为G的补图。例如,图8中的两个图互为补图。


图8 补图


8.通路与回路
在无向图中,设Γ=v0e1v1e2…etvt是顶点与边的交替序列且vi-1与vi是ei的端点(1≤i≤t),称Г为v0到vt的通路。Г中的边数称为Г的长度。若v0=vt则称Г为回路。除首尾两点外,所有边都不相同的通路称为简单通路,所有边都不相同的回路称为简单回路。所有顶点和所有边都不相同的通路称为初级通路或路径。所有顶点和所有边都不相同的回路称为初级回路或圈。有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路。
9. 图的连通性
若无向图G中任何两个顶点之间均有通路,则称G是连通图,否则称G是非连通图。设G′是G的连通子图,如果在G′中再任意添加G中另外一个顶点或另外一条边,所得到的图就成为非连通的,则称G′是G的极大连通子图。G的极大连通子图称为G的连通分支。连通图只有一个连通分支,非连通图的连通分支数大于等于2。
在有向图D中,去掉所有有向边的箭头(即,把有向边改成无向边)所得到的无向图称作有向图的基图。若D的基图是连通的,则称D是弱连通的;若D中任意两个顶点之间至少有一个顶点到另一个顶点有通路,则称D是单向连通的; 若D中任何两个顶点相互之间都有通路,则称D是强连通的。
10.二部图
设G=〈V,E〉为无向图,若能将V分成V1和V2,使得V=V1∪V2,V1∩V2=∅, 而且G的每条边的一个端点属于V1,另一个端点属于V2,则称G为二部图。又若,简单二部图G中V1中每个顶点均与V2中所有顶点相邻,则称G为完全二部图,记为Kr,s,其中r和s分别为V1和V2中的顶点数。例如,图9是K2,3和K3,3


图9 完全二部图


11. 欧拉图
图(无向图或有向图)中经过每条边一次且仅一次的回路称作欧拉回路。有欧拉回路的图称为欧拉图。无向图为欧拉图当且仅当它是连通的且没有奇度数顶点。有向图为欧拉图当且仅当它是强连通的且每个顶点的入度等于出度。例如,图10所示的图为一个欧拉图,cbahgfedbhfdc为一条欧拉回路。
不难看出,在哥尼斯堡七桥问题中“不重复地走完七桥回到出发点的路线”应该是图2中的一条欧拉回路,而这个图的4个顶点的度数都是奇数,因此不存在欧拉回路,所以哥尼斯堡七桥问题无解。


图10 欧拉图



图11 平面图


12. 哈密顿图
图G(无向图或有向图)中恰好经过每个顶点一次的回路称作哈密顿回路。有哈密顿回路的图称为哈密顿图。到目前为止,还没有找到判别一个图是否是哈密顿图的好方法,哈密顿图的判别问题是NP完全的(见计算复杂性理论)。哈密顿的周游世界问题就是要在图3中找一条哈密顿回路。这个图是哈密顿图,其中ABCDEFGHIJKLMNO PQRSTA为一条哈密顿回路。
13. 平面图
能够画在平面上使得除在顶点处外没有边相交的无向图称为平面图。例如,图11所示的图为一个平面图。
14. 图的矩阵表示
图的一种表示方法。
15.无向图的关联矩阵
设无向图G=<V,E>,其中V={v1,v2,…,vn},E={e1,e2,…,en}。令

则称[mij]n×m为G的关联矩阵。例如,图12所示无向图G的关联矩阵为



图12 无向图G


16.有向图的关联矩阵
设无环有向图D=〈V,E〉,V={v1,v2,…,vn},E={e1,e2,…,en}。令

则称[mij]n×m为D的关联矩阵。例如,图13所示有向图D的关联矩阵为



图13 无环有向图D


17.无向图的相邻矩阵
设无向简单图G=<V,E>,其中V={v1,v2,…,vn},令aii=0,

则称[aij]n×m为G的相邻矩阵。例如,图14所示的无向图的相邻矩阵为



图14 无向简单图G


无向图相邻矩阵的性质:
(1)A(G)是对称的。
(2)第i行元素之和为顶点vi的度数。
(3)A(G)中所有元素之和等于边数的2倍。
18.有向图的邻接矩阵
设有向图D=〈V,E〉,V={v1,v2,…,vn},令aij为从顶点vi到vj的有向边的条数(i,j=1,2,…,n),则称[aij]n×n为D的邻接矩阵。例如,图15所示有向图D的邻接矩阵为



图15 有向图D


有向图邻接矩阵的性质:
(1)第i行元素之和为顶点vi的出度,第j列元素之和为顶点vj的入度。
(2)A(D)中所有元素之和为图中的边数,亦即图中长度为1的通路数,其中对角线元素之和为图中长度为1的回路数(即环数)。
(3)A(D)的k次幂Ak(D)中的元素aijk(i≠j)为vi到vj长度为k的通路数,而aijk为vi到自身长度为k的回路数,Ak(D)中的所有元素之和为D中长度为k的通路总数,其中Ak(D)的对角线元素之和为D中长度为k的回路数。
19.有向图的可达矩阵
设有向图D=〈V,E〉,V={v1,v2,…,vn},令pij=1,当i≠j时,

则称P(D)=[pij]n×n为D的可达矩阵。图15所示有向图的可达矩阵为

74
73
25
news

版权所有© 亿企邦 1997-2022 保留一切法律许可权利。

为了最佳展示效果,本站不支持IE9及以下版本的浏览器,建议您使用谷歌Chrome浏览器。 点击下载Chrome浏览器
关闭