第三章图与网络分析系统工程南京农业大学工学院 陈青春制作
南京农业大学工学院 陈青春 制作 系 统 工 程 第三章 图与网络分析
主要内容第三章图与网络分析图的基本概念s1一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树s2有向图s3图的矩阵表示S4最短路问题2s1图的基本概念
2 主要内容 §1 图的基本概念 §1 图的基本概念 第三章 图与网络分析 一、图、连通图、赋权图 二、一笔画问题 三、中国邮路问题 四、子图和树 §2 有向图 §4 最短路问题 §3 图的矩阵表示
S1图的基本概念s1图的基本概念一、图、连通图、赋权图二、一笔画问题三、中国邮路问题四、子图和树3、图、连通图、赋权图
3 §1 图的基本概念 一、图、连通图、赋权图 §1 图的基本概念 一、图、连通图、赋权图 二、一笔画问题 三、中国邮路问题 四、子图和树
概述S1图的基本概念概述生产实际中的许多问题虽然多属于不同领域，但其中相当一部分问题都可以(1）由来用图与网络的形式进行描述不仅本身具有重要的理论意义，更重要的是作为其它学科的公共基础而被广（2）意义泛应用物理学、控制论、信息论、交通运输、经济管理、计算机科学等（3）应用项目管理、通信线路的架设、输油管道的铺设、公路或铁路交通网络的合理（4）用例布局等4兰德公司简介
4 §1 图的基本概念 概述 兰德公司简介 概述 （1）由来 生产实际中的许多问题虽然多属于不同领域，但其中相当一部分问题都可以 用图与网络的形式进行描述 （2）意义 不仅本身具有重要的理论意义，更重要的是作为其它学科的公共基础而被广 泛应用 （3）应用 物理学、控制论、信息论、交通运输、经济管理、计算机科学等 （4）用例 项目管理、通信线路的架设、输油管道的铺设、公路或铁路交通网络的合理 布局等
S1图的基本概念图、连通图、赋权图1图一、图、连通图、赋权图1.图与以前在数学中学的几何图形不完全相同欧拉将此问题归结为一个“哥尼斯堡七桥问题：笔画问题，并证明了是不可能的，因为图中的每个点都与奇数条边相关联，不可能将这个图不重复地一笔画成，这是古典图论中一个著名问题38esete2eCDere3esBB图论中的图示意图5图论中的图与几何图形的区别
5 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图论中的图与几何图形的区别 一、图、连通图、赋权图 1. 图 与以前在数学中学的几何图形不完全相同 哥尼斯堡七桥问题： A B C D 示意图 图论中的图 B C D e1 e2 e6 e5 e7 e3 e4 A 欧拉将此问题归结为一个 “一 笔画”问题，并证明了是不可 能的，因为图中的每个点都与 奇数条边相关联，不可能将这 个图不重复地一笔画成，这是 古典图论中一个著名问题
S1图的基本概念图、连通图、赋权图1图图论中的图与几何图形的区别几何图形：强调几何要素（如长度、角度、面积、形状等）的准确性（如桥的准确位置、长度、岛的面积大小）图论中的图：不关注几何要素的准确性，强调点的数量及点之间关系的准确性（如有几个岛、岛之间是否有桥、岛与岸之间是否有桥以及有几座桥）Aese2eie6BCDere3esB6两个图在图论中完全相同图的基本概念
6 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图的基本概念 图论中的图与几何图形的区别 几何图形： 强调几何要素（如长度、角度、面积、形状等）的 准确性（如桥的准确位置、长度、岛的面积大小 ） 两个图在图论中完全相同 图论中的图： 不关注几何要素的准确性，强调点的数量及点之间 关系的准确性（如有几个岛、岛之间是否有桥、岛与岸之间是否有桥 以及有几座桥） B C D e1 e2 e6 e5 e7 e3 e4 A A B C D
S81图的基本概念图、连通图、赋权图1图图的基本概念定义3-1：（图）对于点集V（非空）和边集E，如果任一边eEE对应于两个点u，VEV，则点集V和边集E的和集称为通常用点表示具体的或抽象的事物，而用边图，记作G=(V，E)。表示事物之间的某种联系，顶点：点集V中的点称为图的点。端点：边e对应的两个点u、v称为边eesDe6的端点，边e记作[u，v或[v，u]。关联边：边[u，v称为端点u、v的关联边。ea相邻点：有公共边的两个端点称为相邻e2B点。（与端点无异，多余）ei相邻边：有公共点的边称为相邻边。环：若边e的两个端点为同一点，则边e称为环7图的基本概念（续）
7 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图的基本概念（续） 图的基本概念 顶点： 定义3-1： A D B C e2 e1 e3 e4 e5 端点： e6 关联边： 相邻点： 相邻边： 环： 通常用点表示具体的或抽象的事物，而用边 表示事物之间的某种联系
81图的基本概念图、连通图、赋权图1图图的基本概念（续）多重边：若两个点之间多于一条边，则这些边称为多重边。多重图：含有多重边的图称为多重图。简单图：无环无多重边的图称为简单图。esA图的阶：图中顶点的个数称为图的阶。顶点的度：以>为端点的边的条数称为点！ea的度，记作deg(v)或d(v)enBC偶点：ei度为偶数的点称为偶点。规定环计算两次奇点：度为奇数的点称为奇点。8图的基本概念（续）
8 §1 图的基本概念 一、图、连通图、赋权图 1. 图 图的基本概念（续） 图的基本概念（续） 多重图： 多重边： A D B C e2 e1 e3 e4 e5 e6 简单图： 图的阶： 顶点的度： 偶点： 奇点： 含有多重边的图称为多重图。 无环无多重边的图称为简单图。 图中顶点的个数称为图的阶。 以v为端点的边的条数称为点v 的度，记作 deg(v)或d(v) 度为偶数的点称为偶点。 度为奇数的点称为奇点。 规定环计算两次
S1图的基本概念图、连通图、赋权图1图图的基本概念（续）孤立点：度为零的点称为孤立点。E悬挂点：度为1的点称为悬挂点。eesDA悬挂边：与悬挂点关联的边称为悬挂边Fes所谓连通图，即图中任意两点都能通过一系e2B列顺序相连边通达，这一系列顺序相连的边C称为链。e192.连通图
9 §1 图的基本概念 一、图、连通图、赋权图 1. 图 2. 连通图 图的基本概念（续） 悬挂点： 孤立点： A D B C e2 e1 e3 e4 e5 e6 悬挂边： 度为1的点称为悬挂点。 与悬挂点关联的边称为悬挂边。 E F 度为零的点称为孤立点。 所谓连通图，即图中任意两点都能通过一系 列顺序相连边通达，这一系列顺序相连的边 称为链
S1图的基本概念一、图、连通图、赋权图2联通图2.连通图定义3-3（链、圈）：设u={v，e,，v,，e,，Vi, e,, v.为图G的一个点边交替序列（下标不一定是递增的顺序），若其中的每条边均满足e,=[v,，v」，则称这个序列μ为从点v,到v即各边顺序相连的一条链；若vi=v，则称μ为一个圈。以下概念也适用于圈V2V6简单链：所有边不重复的链车（即各边互不重复）。初等链：所有点不重复的简单链（即点边均不重复）。V3V5连通图：若图中任意两点之间至少存在一条链，则图称为连通图，否VV4则称为不连通图。10在不致引起混淆的情况下，可将链u简记为u=enen,e或u=i,n，"。3.赋权图
10 §1 图的基本概念 一、图、连通图、赋权图 2.联通 图 3. 赋权图 2. 连通图 定义3-3（链、圈）： 简单链：所有边不重复的链（即各边互不重复）。 v1 v2 v3 v4 v5 v6 v7 即各边顺序相连 以下概念也适用于圈 初等链：所有点不重复的简单链 （即点边均不重复）。 连通图：若图中任意两点之间至少存在 一条链，则图称为连通图，否 则称为不连通图