资源描述：
《运筹学第06章图论概述》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、运筹学第六章图论概述本章重点图的基本概念常见的四个问题的求解方法图的含义图是一种模型如公路、铁路交通图，通讯网络图等图是对现实的抽象很多问题都可以用顶点和边来表示，一般顶点表示实体，边(顶点与顶点之间的连线)表示实体之间的关系，顶点和边的集合定义为图图论的提出(1)用图来描述事物及其联系，最早是由瑞士数学家欧拉(Euler)于1736年解决哥尼斯堡七桥问题时提出的如右图所示，哥尼斯堡地区被河流分为了四个区域，四个区域之间有七座桥相连，问是否有一条路线，可以经过所有的桥并且每座桥只经过一次？BACD图
2、论的提出(2)用图来表示这个问题用四个顶点表示四个地区用七条边表示七座桥要寻找这样的一条路线：经过所有的边并且每条边只经过一次该问题已经证明无解图的基本概念(1)图：顶点和边的集合点的集合用V表示，边的集合用E表示，则图可以表示为G=(V,E)如下图G=(V,E)其中，V={A,B,C,D}E={e1,e2,e3,e4,e5,e6,e7}E中，e1=(A,D),e2=(B,D),e3=(C,D)e4=(B,C),e5=(A,C),e6=(A,C),e7=(B,C)e2e1e3e4e5e6e7图的基本
3、概念(2)边都没有方向的图称为无向图，前面所讲的图就是无向图。无向图的边eij=(vi,vj)=(vj,vi)=eji当图中的边都有方向时，称为有向图。为了区别于无向图，有向图用G(V,A)表示在有向图中，有向边又称为弧，用aij=(vi,vj)表示，(vi,vj)≠(vj,vi)，弧的方向用箭头标识既有边又有弧的图称为混合图下图中从左向右依次为：无向图，有向图，混合图图的基本概念(3)集合V中元素的个数称为图G的顶点数，记作p(G)。前例中，p(G)=4集合E(或A)中元素的个数称为图G的边数，记
4、作q(G)。前例中，q(G)=7若e=(u,v)∈E(或a=(u,v)∈A)，则称u和v为e(或a)的端点，e(或a)称为顶点u和v的关联边，也称u,v与边e(或a)相关联。前例中，A,B是边e1的端点，e1是A,B的关联边若顶点u和v与同一条边相关联，则称u和v为相邻点若两条边ei和ej有同一个端点，则称ei和ej为相邻边图的基本概念(4)若一条边的两个端点是同一个顶点，则称该边为环若两个端点之间有多于一条边，则称为重边(书上称为多重边)，前例中，A,C之间和B,C之间都有两条边无环也无重边的图称
5、为简单图与顶点v相关联的边的数目，称为该顶点的“度”(书上称为次)，记为d(v)度数为奇数的顶点称为奇点，度数为偶数的顶点称为偶点在有向图中，由顶点指向外的弧的数目称为正度，记为d+，指向该顶点的弧的数目称为负度，记为d–度数为0的点称为孤立点，度数为1的点称为悬挂点图的基本概念(5)与悬挂点连接的边称为悬挂边若图中所有的点都是孤立点，则称为空图定理6.1所有顶点的度数之和，等于所有边数的两倍原因：每条边关联两个顶点，计算顶点的度数时，每条边计算了2次定理6.2图中奇点的个数总是偶数个原因：所有顶点
6、的度数之和是偶数，偶点的度数之和也是偶数，因此，奇点的度数之和必为偶数，因此，奇点的个数必是偶数个图的基本概念(6)点边交错序列v0,e1,v1,e2,v2,…,vn-1,en,vn称为链。其中v0称为路的起点，vn称为路的终点若v0≠vn，称为开链；反之，称为闭链(对于无向图而言，也称为回路)若链中所含的边均不相同，称为简单链若链中所含的顶点均不相同，称为初等链(对于无向图而言，也称为通路)除起点和终点外均不相同的闭链，称为圈(对于无向图而言，也称为初等回路)以上概念(除特别标注的外)对无向图和有
7、向图均适用图的基本概念(7)在有向图中，点边交错序列v0,e1,v1,e2,v2,…,vn-1,en,vn(其中ek=(vk-1,vk))称为路若v0≠vn，称为开路；反之，称为回路(注意和无向图的回路区分开来)若路中所含的边均不相同，称为简单路若路中所含的顶点均不相同，称为初等路除起点和终点外均不相同的回路，称为初等回路(注意和无向图的初等回路区分开来)本页概念都是针对有向图图的基本概念(8)若一个图(无向图或有向图)中任意两点之间至少有一条初等链连接，则称该图为连通图，否则称为不连通图在一个有向
8、图中，若任意两点u和v，u到v和v到u之间都至少有一条初等路连接，则称该图为强连通图，否则称为非强连通图图的基本概念(9)子图：设G1=(V1,E1)，G2=(V2,E2)，若V1V2，E1E2，则称G1是G2的子图注：生成子图时，可以只选顶点不选与该顶点相关联的边，但不能只选边不选与该边相关联的顶点如下图，右图是左图的子图图的基本概念(10)如下图，右图是左图的真子图真子图：若V1V2，E1E2，称G1是G2的真子图部分图：若V1=V2，E1E2，称G1是G2的部分
