第八拿国的基本概心 需是有根生金然去原问题较需模 菂围态基方法、二聋法早善 但蒙务论尙然启 图论的力法 返回首页 2021/1/21
2021/1/21 1 第八章 图的基本概念 图是一类相当广泛的实际问题的数学模 型，有着极其丰富的内容，是数据结构 等课程的先修内容.学习时应掌握好图论 的基本概念、基本方法、基本算法；善 于把实际问题抽象为图论的问题，然后 用图论的方法解决问题. 返回首页
第一节图的概念 ●本节介绍图的一些最常用的概念主要有 无向图有向图边顶点(或结点点弧或有 向边顶点集边集n阶图有 关联 2生字补菌图的局构人度出 度度孤立点等 主要定理:握手定理 返回本章首页 2021/1/21
2021/1/21 2 第一节 图的概念 ⚫ 本节介绍图的一些最常用的概念,主要有: 无向图,有向图,边,顶点(或结点,点),弧(或有 向边),顶点集,边集,n阶图,有限图,关联, 多重图,简单图,完全图,二分图(或偶图), 完全二分图,母图,子图,支撑子图(或生成 子图),导出子图,补图,图的同构,入度,出 度,度,孤立点等. 主要定理:握手定理. 返回本章首页
第二节路与回路(1) ●本节介绍图中有关路的基本概念,同时 作为路在权图中的应用,我们给出求权 图最短路的迪克斯特拉算法. 1基本概念有:路,路的起点,路的终点,路的 长度开路闭路简单路,回路,基本路圈, 连通连通分支连通图两点问的距离可 达强连通图单向连通图,弱连通图权图 权迪克斯特拉算法等 3 返回本章首页 2021/1/21
2021/1/21 3 第二节 路与回路(1) ⚫ 本节介绍图中有关路的基本概念，同时 作为路在权图中的应用，我们给出求权 图最短路的迪克斯特拉算法. 1.基本概念有:路,路的起点,路的终点,路的 长度,开路,闭路,简单路,回路,基本路,圈, 连通,连通分支,连通图,两点间的距离,可 达,强连通图,单向连通图,弱连通图,权图, 权,迪克斯特拉算法等； 返回本章首页
第二节路与回路(2) 2主要结论:设G=NE是图,且V=n若 存在结点u到v的路,则必存在u釥的长 度不超过n-1的路 3算法迪克斯特拉( Dijkstra)算法迪克斯 特拉算法是图论中最基本的算法应很好 地掌握 返回本章首页 2021/1/21
2021/1/21 4 第二节 路与回路(2) 2.主要结论: 设G=(V,E)是图，且|V|=n,若 存在结点u到v的路，则必存在u到v的长 度不超过n-1的路. 3.算法:迪克斯特拉(Dijkstra)算法,迪克斯 特拉算法是图论中最基本的算法,应很好 地掌握. 返回本章首页
第三节矩阵与图 ●本节主要考虑三种矩阵,即邻接矩阵 可达矩阵与关联矩阵邻接矩阵反映的是 顶点与顶点之间的关系;可达矩阵反映 了图的联通情况;关联矩阵反映的是顶 点与边(弧)的关系分有向图与无向 图来讨论 5 返回本章首页 2021/1/21
2021/1/21 5 第三节 矩阵与图 ⚫ 本节主要考虑三种矩阵，即邻接矩阵， 可达矩阵与关联矩阵.邻接矩阵反映的是 顶点与顶点之间的关系；可达矩阵反映 了图的联通情况；关联矩阵反映的是顶 点与边（弧）的关系. 分有向图与无向 图来讨论. 返回本章首页