网络的图网络矩阵及网络方程.ppt

:有条名叫Pregel的河流经哥尼斯堡(现加里宁格勒),河中有两个岛,把市区分成四块陆地(A,B,C,D),陆地间有七个桥相通。能否从任一陆地出发,走遍七桥而每桥只走一次?哥尼斯堡市区图图论趣话七桥问题的解决欧拉规则(a)连接奇数个桥的陆地只有一个或超过两个以上时,不能实现一笔画。(b)连接奇数个桥的陆地仅有两个时,则从两者中任一陆地出发,可以实现一笔画而停在另一陆地。(c)每块陆地都连接有偶数个桥时,则从任一陆地出发都能实现一笔画,而回到出发点。ABCD用点表示陆地,用线表示陆地间的桥,便抽象成图。问题变成该图能否实现一笔画?:把国土分成5块给儿子,规定各块之间都要有边界。儿子又提出在自己分到的领土上都要修一个王宫,并且各王宫之间都要有路直接相通而不能交叉。能否解决?用点表示王宫,用线表示王宫间的道路,便抽象成图。问题变成该图是否为平面图?:只须4种不同颜色,就能使平面地图上任何两个相邻的国家的颜色不同。图论问题:用点表示国家,用边表示国家直接相邻。证明只须4种颜色就可使所有相邻顶点具有不同颜色。。。1976年,,,。(1)电网络的分析与综合。(2)印刷电路与集成电路的布线和测试。(3)通讯网络。(4)在理论物理和统计力学的应用(杨振宁、李政道)。(5)在化学领域的应用(同分异构体)。(6)在心理学领域的应用(1936年,:拓扑心学)。(7)在经济学领域的应用(税率涨落、商品流通、供求关系)。(8)在计算机科学领域的应用(计算机网络)。图(graph):由“点”和“线”组成。“点”也称为节点或顶点(vertex),“线”也称为支路或边(edge)。图通常用符号G来表示。(a)电路只含二端元件,对应的图如图(b)所示。电桥电路及其图基本要求:掌握网络的图、子图、连通图、割集和树等概念。连通图:图中任何两个节点之间至少存在一条路径,则称为连通图;否则称为非连通图。子图:图的一部分称为子图。一个孤立的节点也是一个子图。两个子图含互感电路及其图123456④②③①有向图:图中的所有支路都指定了方向,则称为有向图;反之为无向图。回路:从图中某一节点出发,经过若干支路和节点(均只许经过一次)又回到出发节点所形成的闭合路径称为回路。割集:连通图的割集是一组支路集合,并且满足:(1)如果移去包含在此集合中的全部支路(保留支路的两个端点),则此图变成两个分离的部分。(2)如果留下该集合中的任一支路,则剩下的图仍是连通的。(a)(b)为割集,(c)(d)为非割集割集与非割集示例