第八章图与网络分析 引论哥尼斯堡七桥问题 A D C B 简捷表示事物之间的 本质联系,归纳事物 之间的一般规律 D OR3 B
OR3 1 第八章 图与网络分析 引论 哥尼斯堡七桥问题 A B D C A B C D 简捷表示事物之间的 本质联系，归纳事物 之间的一般规律
引论图的用处 豢A、B、C、D、E 某公司的 五支球队进行循环赛 组织机构设置图 A 总公司分公司厂或 办事处 C OR3
OR3 2 引论 图的用处 A、B、C、D、E 某公司的 五支球队进行循环赛 组织机构设置图 A B C D E 总公司 分公司 工厂或 办事处
8.1图的基本概念 蜂图是由点和线构成的 点的集合V表示,V=W 不带箭头的连线叫做边(edge),边的集 合记为E={e},一条边可以用两点 [vv]表示,e=[v,] 壽带箭头的连线叫做弧(arc),弧的集合记为 A,A={ak},条弧也是用两点表示, ak=[v,v]弧有方向:v为始点,为终 OR3
OR3 3 8.1 图的基本概念 图是由点和线构成的。 点的集合V表示，V={vi} 不带箭头的连线叫做边(edge)，边的集 合记为E= { ej } ，一条边可以用两点 [ vi,vj ]表示,ej= [ vi,vj ]. 带箭头的连线叫做弧(arc),弧的集合记为 A，A= { ak },一条弧也是用两点表示， ak= [ vi,vj ],弧有方向：vi为始点，vj为终 点
图的基本概念(续) 由点和边组成的图叫做无向图,记为G=(V,E) 由点和弧组成的图叫做有向图,记为D=(V,A) 秦例1 e1 V1 e2 V3 a8 810 e3 e4 a4 a6 as a11 V6 a2 a7 V2 a5 V4 e7 无向图:点集、边集 有向图:点集、弧集 OR3
OR3 4 图的基本概念(续) 由点和边组成的图叫做无向图，记为G=（V，E） 由点和弧组成的图叫做有向图，记为D=（V，A） 例1. v1 v2 v3 v4 v1 v2 v3 v4 v5 v6 v7 e1 e2 e3 e4 e5 e6 e7 a1 a2 a8 a4 a3 a5 a6 a9 a7 a10 a11 无向图：点集、边集 有向图：点集、弧集
图的基本概念(续) 以点u为端点的边的条数,叫做点u的次 为1的点叫做悬挂点;次为0的点叫做 孤立点;次为奇数则称奇点;次为偶数 则称偶点。 癱点弧交替序列称为链;闭合的链称为圈 癱首尾相接的链称为路;闭合的路称回路 任意两点之间都有边相连,称为连通图 OR3
OR3 5 图的基本概念(续) 以点u为端点的边的条数，叫做点u的次 次为1的点叫做悬挂点；次为0的点叫做 孤立点；次为奇数则称奇点；次为偶数 则称偶点。 点弧交替序列称为链；闭合的链称为圈 首尾相接的链称为路；闭合的路称回路 任意两点之间都有边相连，称为连通图