资源描述：
《图与网络模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、网络的挑战快乐的网络开始成功的一切建立网络是成功的一切图与网络模型瑞士数学家欧拉在1736年发表了一篇题为“依据几何位置的解决方法”的论文，有效地解决了哥尼哥尼斯堡“七桥问题”，这是有史以来的第一篇图论论文，欧拉被公认为图论的创始人。18世纪的哥尼斯堡城中流过一条河。河上游七座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样的游戏：一个游者怎样才能一次连续走过这七座桥而每座桥只走一次，回到原出发点。没有人想出这种走法，又无法说明走法不存在，这就是著名的“七桥”难题。欧拉将这个问题归结图论的问题。他用A,B,C,
2、D四点表示河的两岸和小岛，用两点间的连线表示桥。七桥问题变为：从A,B,C,D任意点出发，能否通过每条边一次且仅一次，再回到原点？欧拉证明了这样的走法不存在，并给出了这类问题的一般结论。1857年，英国数学家哈密顿发明了一种游戏，他用一个实心正12面体象征地球，正12面体的20个定点分别表示世界上20座名城，要求游戏者从任一城市出发，寻找一条可经由每个城市一次切仅一次再回到原出发点的路，这就是“环球旅行”问题。如图5-3所示。他与七桥问题不同，前者要在图中找一条经过每边且仅一次的路统称欧拉回路，而后者是要在图中找一条经过
3、每个点一次且仅一次的路，能成为哈密尔顿回路。哈密顿根据这个问题的特点，给出了一种解法如图5-4所示。在这一时间，还有许多诸如迷宫问题、博弈问题以及棋盘上马的行走路线之类的游戏难题，吸引了许多学者。这些看起来似乎无足轻重的游戏却引出了许多有实用意义的新问题，开辟了新学科。运筹学中的“中国邮路问题”：一个邮递员从邮局出发要走遍他所负责的每一条街道去送信，蚊蝇如何选怎适当的路线可是所走的总路程最短。这个问题就与欧拉回路有密切的关系。而著名的“货郎担问题”则是一个带权的哈密尔顿回路。而著名的“货郎担问题”则是一个带权的哈密尔顿回
4、路问题。图论的第一本专著是匈牙利数学家OKoing写的“有限图与无限图的理论”，发表于1936年。从1736年欧拉的第一篇论文到这本专著，前后经历了200年之久，总的来讲这一时期图论的发展是缓慢的。直到20世纪中期，电子计算机的发展以及离散数学问题具有越来越重要的地位，使得作为提供离散数学模型的图论得以迅速发展，成为运筹学中十分活跃的重要分支。目前图论被广泛地应用于管理科学、计算机科学、信息论、控制论、物理、化学、生物、心理学等各个领域，并取得了丰硕的成果。第一节图与网络的基本知识一、图与网络的基本概念1.图及其分类 自
5、然界和人类社会中，大量的实物以及事物之间的关系，常可以用图形来描述。例如，为了反映5个队参加的球类比赛请况，可以用点表示球队，用点间连线表示两个队已经比赛过，如图5-5所示。又例如工作分配问题，我们可以用点表示工人与需要完成的工作，点间连线表示每个人可以胜任那些工作，如图5-6所示。 这样的例子很多，物质结构、电路网络、城市规划、交通运输、物资调配等也都可以用点和线连接起来的图进行模拟。由上面的例子可以看出，这里所研究的图与平面几何中的图不同，这里只关心图中有多少个点，点与点之间又无连线，至于连线的方式是直线还是曲线，点
6、与点的相对位置如何，都是无关紧要的。总之，这里所讲的图是反映对象之间关系的一种工具。图的理论和方法，就是从形形色色的具体的图以及与他们相关的实际问题中，抽象出共同性的东西，找出其归律、性质、方法，在应用到解决实际问题中去定义1.一个图是由点集V={}和V中元素的无序对的一个集合E={}所构成的二元组，记为G=(V,E),V中元素叫做顶点，E中的元素叫做边。当V,E为有限集合时，G成为有限图，否则，成为无限图。本章只讨论有限图。例5.1在图5-7中：V={v1，v2，v3，v4，v5}E={e1，e2，e3，e4,e5}.
7、其中：e1=（v1，v2）e2=（v1，v2）e3=（v1,v3）e4=（v2，v3）e5=（v2，v3）e6=（v3,v4）两个点u，v属于V，如果边（u，v）属于E，则称u，v两点相邻。u，v成为边（u，v）的端点。两边ei,ej属于E，如果他们有一个公共端点u，则称ei,ej相邻。边ei,ej成为点u的关连边。用m（G）=
8、E
9、表示图G中的边数，用年（G）=
10、V
11、表示图G的定点个数。在不引起混淆情况下简记为m,n。对于任一条边（vi,vj）属于E，如果边（vi,vj）端点无序，则他是无向边，此时图G成为无向图。图5
12、-7时无向图。如果边（vi,vj）的端点有序，即他表示以vi为试点，vj为终点的有向边（或称弧），这时图G称为有向图。一条边的两个端点如果相同，称此边为环。如图5-7中的e1。两个点之间多余一条边的，称为多重边。如图5-7中的e4，e5。定义2不含环和多重边的图称为简单图，含有多重边的图成为多重图。以后我们讨论的图，
