图论(数据库)

时间：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={v₁,v₂,…,v_n},E={e₁,e₂,…,e_m},n≥1,m≥0,其中每一个v_j表示一个顶点,e_k＝(v_i,v_j)表示连接v_i和v_j的一条边,v_i和v_j称作e_k的端点。在这里,(v_i,v_j)＝(v_j,v_i),称作无序对,即e_k是没有方向的。我们称G=<V,E>为无向图,简称图,其中V是G的顶点集,E是边集。注意:e_k的两个端点可以是相同的,此时称作环,如图4中的e₁＝(a,a)。允许两条和两条以上的边有两个相同的端点,此时称这些边为平行边,并称平行边的条数为重数。如图4中e₂、e₃,是两条平行边。既无平行边也无环的图称为简单图。有n个顶点的图称为n阶图。若n=1且E=∅, 即只有一个顶点没有边的图称为平凡图。若有一条边e_k＝(v_i,v_j),则称顶点v_i与v_j相邻,边e_k与顶点v_i和v_j相关联。无边关联的顶点称为孤立点。称有共同端点的两条边(v_i,v_j)与(v_j,v_k)相邻。
(2)有向图:与无向图类似,只是每条边都是有方向的,用两个端点的有序对表示e_k＝<v_i,v_j>,其中v_i是e_k的始点,v_j是e_k的终点。在有向图中,只有当两条有向边有相同的始点和终点时才称为平行边,如图5中的e₃和e₄是平行边,而e₆和e₇不是平行边。
(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. 图的同构
设G₁＝<V₁,E₁>和G₂＝<V₂,E₂>为两个无向图,若存在双射函数f:V₁→V₂(见函数)使得∀v_i, v_j∈V₁,(v_i,v_j)∈E₁当且仅当(f(v_i),f(v_j))∈E₂,且当是平行边时(v_i,v_j)与(f(v_i),f(v_j))的重数相同,则称G₁与G₂同构,记做G₁＝G₂。类似可定义有向图之间的同构。例如,图6所示的两个图同构。

图6 两个同构的图

4.完全图
任意两个顶点之间都有一条边的无向简单图。n阶完全图记为K_n。K₃,K₄与K₅如图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.通路与回路
在无向图中,设Γ=v₀e₁v₁e₂…e_tv_t是顶点与边的交替序列且v_i-1与v_i是e_i的端点(1≤i≤t),称Г为v₀到v_t的通路。Г中的边数称为Г的长度。若v₀＝v_t则称Г为回路。除首尾两点外,所有边都不相同的通路称为简单通路,所有边都不相同的回路称为简单回路。所有顶点和所有边都不相同的通路称为初级通路或路径。所有顶点和所有边都不相同的回路称为初级回路或圈。有边重复出现的通路称为复杂通路,有边重复出现的回路称为复杂回路。
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分成V₁和V₂,使得V=V₁∪V₂,V₁∩V₂＝∅, 而且G的每条边的一个端点属于V₁,另一个端点属于V₂,则称G为二部图。又若,简单二部图G中V₁中每个顶点均与V₂中所有顶点相邻,则称G为完全二部图,记为K_r,s,其中r和s分别为V₁和V₂中的顶点数。例如,图9是K_2,3和K_3,3。

图9 完全二部图

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

图10 欧拉图

图11 平面图

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

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

图12 无向图G

16.有向图的关联矩阵
设无环有向图D=〈V,E〉,V={v₁,v₂,…,v_n},E={e₁,e₂,…,e_n}。令

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

图13 无环有向图D

17.无向图的相邻矩阵
设无向简单图G=<V,E>,其中V={v₁,v₂,…,v_n},令a_ii＝0,

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

图14 无向简单图G

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

图15 有向图D

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

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