资源描述：
《图与网络模型及方法.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、图与网络模型及方法图与子图图的连通与割集树与支撑树最小树最短有向路最大流最小费用流最大对集图与网络无向图的基本概念网络的基本概念关联矩阵和邻接矩阵关联矩阵邻接矩阵主要结论子图绪论图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷n2n+2CH的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈绪论近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应
2、用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学，生物遗传学、心理学、经济学、社会学等学科中。绪论图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题这个图是连通的，且每个点都与偶数线相关联绪论图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的问题涉
3、及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。图------由若干个点和连接这些点的连线所组成的图形vi——图中的点，称为顶点（代表具体事物，研究对象。ei——图中的连线，称为边（对象之间的联系）m(G)=
4、E
5、——G的边数，简记为mn(G)=
6、V
7、——G的顶点数，简记为n一.图的概念记V={vi}——点的集合，E={ei}——边的集合G={V，E}G——一个图m=6,n=5图的基本概念有向图无向图——边e=(vi,vj)有方向vi为始点，vj为
8、终点——边e=(vi,vj)无方向，此时(vi,vj)=(vj,vi)e4=(v3，v4）=(v4，v3）e4=(v3，v4)≠(v4，v3）e5=(v3，v4）=(v4，v3）此时(vi,vj)≠(vj,vi)e5=(v4，v3)≠(v3，v4)图有向图无向图二.常用名词：1、端点和关联边：2、相邻点和相邻边：3、多重边与环：4、多重图和简单图：无环也无多重边的图称为简单图。含有多重边的图称为多重图；5、次：6、悬挂点和悬挂边：次为1的点称为悬挂点，与悬挂点相联的边称为悬挂边。7、孤立点：8、奇点与偶点：，G的边数m=6性质1：在图G=(V,E)中，
9、所有点的次之和是边数m的两倍。证明：由于每条边均与两个顶点关联，因此在计算顶点的次时每条边都计算了两遍，所以顶点次数的总和等于边数的二倍。三.次（度）的性质性质2：在任何图G=(V,E)中，奇点的个数为偶数证明：设V1，V2分别是图G中奇点和偶点的集合，则V1∪V2=V,V1∩V2=Φ,有性质1，，因为V2是偶点的集合，d(vi)(i∈V2)均为偶数，所以只有偶数个奇数相加才能得到偶数，所以V1中的点，即奇点的个数为偶数。四.链、路、连通图1.链：对于无向图G=(V，E)，若图G中有一个点与边的交替序列μ={vi0,ei1,vi1,ei2,,vik-
10、1,eik,vik}，且eit=(vit-1,vit)(t=1,2,…,k),则称该交替序列μ为连结vi0和vik的一条链。简单链：μ中只有重复的点而无重复边者为简单链。初等链：μ中没有重复的点和重复边者为初等链。圈：无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个点 时，称此链为圈。圈中只有重复点而无重复边者为简单圈，既（除起点、终点重复外）无重复点也无重复边者为初等圈不是链初等链简单链（简单圈）（初等圈）2路：在有向图D=(V，A)中，若有从vi0到vik不考虑方向的链，且各边方向一致，则称之为从vi0到vik的一条路。对于有向图可
11、以类似于无向图定义链和圈，初等链、圈，简单链、圈．此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同3连通图：一个图中任意两点间至少有一条链(或路)相连的图。连通图非连通图五．网络在实际问题中，往往只用图来描述所研究对象之间的关系还不够，与图联系在—起的，通常还有与点或边有关的某些数量指标，通常称之为“权”，权可以代表如距离、费用、通过能力(容量)等等。这种带有某种数量指标的图称为网络(赋权图)。如公路交通图：vi表示城市,ei表示公路w(ei)表示公路ei的长度如w(e2)=50表示城市v2
12、与城市v3之间的距离是50千米六.完全图、偶图1．完全图：一个简单图，若任意两个顶点之间均有一
