数模-图论及其算法

《数模-图论及其算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论及其算法南京理工大学理学院肖伟一、背景问题——哥尼斯堡（KÖnigsberg）七桥问题哥尼斯堡有一条河，河中有一个岛，共建七座桥联系被河隔开的四块陆地（如图）。城里人希望做一次散步，从一点出发，经过每座桥一次仅一次，再回到原出发点。1736年Euler否定了该问题。ACDACBDB二、图的定义一个图G是一个三重元素组，V(G)是图的顶点集合，E(G)是图的边的集合，G是从边集E到顶点偶对集合上的函数。顶点集通常用v表示，边集通常用e表示。如图所示。abcde1e2

2、e3e4e5图1图2v1v2v3e1e2e3e4三、各种图的定义如果图的边e所对应的顶点偶对是有序的，则称是e有向边，否则为无向边。对有向边e=，顶点a称为边e的始点，b是终点，他们统称为边e的端点。顶点a、b称为邻接的，e称为是关联结点a、b的。不与任何顶点邻接的顶点称为孤立点。全由孤立点构成的图称为零图。如果一条边的始点和终点相同，则称此边为环（自回路）。如果两个结点之间有多余一条边，则将他们称为平行边。两结点之间边的条数称为边的重数，没有边时，重数为0。1.如果图中每一条

3、边都是无向边，则称为无向图，如图1。2.如果图中每一条边都是有向边，则称为有向图，如图2。3.含有平行边的图称为多重图。非多重图称为线图。无环的线图称为简单图。4.如果图G中每条边e都指定了一个数相对应，记为W(e)，则称此图为赋权图。四、图的基本概念1.结点的度在有向图中，以顶点v为始点的边的数目称为结点v的引出次数（出度），记为deg+(v)=d+(v)；以顶点v为终点的边的数目称为结点v的引入次数（入度），记为deg-(v)=d-(v)；结点v的引出次数和引入次数之和称为结点v的次数（度数）

4、，记作deg(v)=d(v)；在无向图中，结点v的次数就是与结点v相关联的边的条数，记作deg(v)=d(v)；对于孤立点v，显然deg(v)=0。n个结点和m条边的图称为(n,m)图。定理1设G是一个(n,m)无向图，其结点集V={v1,v2,…,vn}，则说明：如果为无向图，则结论为定理2任何图的奇次结点有偶数个。2.正则图的定义：图中所有结点的度数均相同；对每个结点度数为k的图，称为k-正则图。3.图的同构：给定两个图G1=和G2=，如果存在从V1到V2的一一映射

5、，使对任意a,bV1，边(a,b)E1，当且仅当((a)，(b))E2，并且(a,b)和((a),(b))有相同的重数。说明：如果两个图同构，则应有如下结论：1）定点数同；2）边数同；3）度数相同的结点数相同。问题：到现在为止，还没有可行的办法判定两个图同构？4.图的运算：给定两个图G1=和G2=，定义：1）G1与G2的并G3=为V3=V1V2，E3=E1E2，记为G3=G1G2；2）G1与G2的交G3=为V3=V1V

6、2，E3=E1E2，记为G3=G1G2；3）G1与G2的差G3=为E3=E1-E2，V3=(V1-V2){E3中相关联的点}记为G3=G1-G2；4）G1与G2的环和G3=G1G2，G3=(G1G2)-(G1G2)；5）删除边的运算；6）删除图的顶点的运算（删除顶点及其相关联的边）。图3abcG1bacdG2e2e1e3e1e5e4abcG1删去边e2e3e1abe1G1删去结点cabdce1e3e5e2e4G1G2bace1G1G2bcade2e4e3e5G1G2

7、bcaG1-G25.子图：给定两个图G1=和G2=。1）如果V2V1且E2E1，则称G2是G1的子图。如果G2G1，则G2是G1的真子图。2）如果G1=G2且E2E1，则称G2为G1的生成子图。3)由图的一些边E0E与其所有相关联的结点组成的图，称为由边集E0导出的子图。4）由图G=中的一些顶点集V0V和E中的两端点都在V0中的边所组成的子图称为由顶点集V0导出的子图。6.完全图：如果图中任意两结点之间都存在唯一的一条（有向）边，则称此图为完全图。

8、注意：如果是无向图，则任意两结点之间只有唯一一条边；如果是有向图，则任意两结点之间存在方向相反的不同两条边。7.补图：给定线图A=，设

9、V

10、=n，定义图A的补图，其中E0是V生成的完全图的边删除E所得。8.一个无向图，如果同构于它的补，则该图称为自补图。9.图的支配集：对于图G的一个顶点子集，如果G中不在该顶点集中的结点至少与该集中某结点相邻，则称该顶点集为图G的支配集。尤其，如果支配集的任何真子集都不是图G的支配集，则称该集为最小支配集。10.图的独立集：对于图G的一个