Q买非点藏为同课程运笑学 第三章图与网络分析 (Graph and Network Analysis) 3.1图的基本概念 3.2网络分析 20天津大学运筹学课程网站20211367mrrg
2007-6-26 第三章 图与网络分析 (Graph and Network Analysis) 3.1 图的基本概念 3.2 网络分析
运筹学 operations research 第三章图与网络分析 图论起源—哥尼斯堡七桥问题 A A D B B 问题:一个散步者能否从任一块陆地出发,走过七 座桥,且每座桥只走过一次,最后回到出发点? 结论:每个结点关联的边数均为偶数
http://www.tju.edu.cn 第三章 图与网络分析 A B C D A C B D 图论起源——哥尼斯堡七桥问题 结论：每个结点关联的边数均为偶数。 问题：一个散步者能否从任一块陆地出发，走过七 座桥，且每座桥只走过一次，最后回到出发点？
运筹学 operations research 第三章图与网络分析 3,1图的基本概念 1.图 由点和边组成,记作G=(V,B),其中 V=(v,, v 9●●0@● ,vn)为结点的集合, E=(e 1,℃2 ●●●●● ,e为边的集合。 点表示研究对象 边表示表示研究对象之间的特定关系
http://www.tju.edu.cn 第三章 图与网络分析 3.1 图的基本概念 由点和边组成，记作G=(V，E)，其中 V=(v 1，v 2 ，……，v n)为结点的集合， E=(e 1，e 2 ，……，e m) 为边的集合。 点表示研究对象 边表示表示研究对象之间的特定关系 1. 图
运筹学 operations research 第三章图与网络分析 42、图的分类 无向图,记作G=(V,E) 图 有向图的边 称为弧。 有向图,记作D=(V,A 例1:哥尼斯堡桥问题的图为一个无向图。 例2:五个球队的比赛情况,v1V2表示v胜v2
http://www.tju.edu.cn 第三章 图与网络分析 图 无向图，记作G=(V ，E) 有向图，记作D=(V ， A ) 例 1：哥尼斯堡桥问题的图为一个无向图。 有向图的边 称为 弧 。 例 2：五个球队的比赛情况， v 1 v 2 表示 v 1 胜 v 2 。 v1 v2 v3 v4 v5 2、图的分类
运筹学 operations research 第三章图与网络分析 43、链与路、圈与回路 无向图:链点边交错的序列圈起点=终点的链 有向图:路点弧交错的序列回路起点=终点的路 v2 V2
http://www.tju.edu.cn 第三章 图与网络分析 v1 v2 v3 v4 v5 3、链与路、圈与回路 链 点边交错的序列 圈 起点 =终点的链 路 点弧交错的序列 回路 起点 =终点的路 v1 v2 v3 v4 v5 无向图： 有向图：