第八章图的基本概念W 蠶塞态楼县法丢撵法 但题 图论的尙蕙,然后 用图论的万法解问题 返回首页 2021/2/20
2021/2/20 1 第八章 图的基本概念 图是一类相当广泛的实际问题的数学模 型，有着极其丰富的内容，是数据结构 等课程的先修内容.学习时应掌握好图论 的基本概念、基本方法、基本算法；善 于把实际问题抽象为图论的问题，然后 用图论的方法解决问题. 返回首页
第一节图的概念 本节介绍图的一些最常用的概念,主要有: 无向图有向图边顶点或结点点)弧或有 向迈)点集迈集n阶图有酿图关 多美图)单雳全二倒或偶) 全二 支撑子图吗生成 子图)是出子补图图的同构入度出 度度孤立点等 主要定理:握手定理. 返回本章首页 2021/2/20
2021/2/20 2 第一节 图的概念 ⚫ 本节介绍图的一些最常用的概念,主要有: 无向图,有向图,边,顶点(或结点,点),弧(或有 向边),顶点集,边集,n阶图,有限图,关联, 多重图,简单图,完全图,二分图(或偶图), 完全二分图,母图,子图,支撑子图(或生成 子图),导出子图,补图,图的同构,入度,出 度,度,孤立点等. 主要定理:握手定理. 返回本章首页
第二节路与回路(1) 本节介绍图中有关路的基本概念,同时 作为路在权图中的应用,我们给出求权 图最短路的迪克斯特拉算法. 1.基本概念有:路路的起点,路的终点路的 长度开路闭路简单路,回路,基本路,圈, 连通连通分支连通图两点间的距离可 达强连通图单向连通图弱连通图权图, 权迪克斯特拉算法等 3 返回本章首页 2021/2/20
2021/2/20 3 第二节 路与回路(1) ⚫ 本节介绍图中有关路的基本概念，同时 作为路在权图中的应用，我们给出求权 图最短路的迪克斯特拉算法. 1.基本概念有:路,路的起点,路的终点,路的 长度,开路,闭路,简单路,回路,基本路,圈, 连通,连通分支,连通图,两点间的距离,可 达,强连通图,单向连通图,弱连通图,权图, 权,迪克斯特拉算法等； 返回本章首页
第二节路与回路(2) 2主要结论:设G=(E是图,且=n,若 存在结点u到∨的路,则必存在u到的长 度不超过n-1的路 3算法迪克斯特拉( Dijkstra)算法迪克斯 特拉算法是图论中最基本的算法应很好 地掌握. 返回本章首页 2021/2/20
2021/2/20 4 第二节 路与回路(2) 2.主要结论: 设G=(V,E)是图，且|V|=n,若 存在结点u到v的路，则必存在u到v的长 度不超过n-1的路. 3.算法:迪克斯特拉(Dijkstra)算法,迪克斯 特拉算法是图论中最基本的算法,应很好 地掌握. 返回本章首页
第三节矩阵与图 ●本节主要考虑三种矩阵,即邻接妾矩阵 可达矩阵与关联矩阵邻接矩阵反映的是 顶点与顶点之间的关系;可达矩阵反映 了图的联通情况;关联矩阵反映的是顶 点与边(弧)的关系分有向图与无向 图来讨论 5 返回本章首页 2021/2/20
2021/2/20 5 第三节 矩阵与图 ⚫ 本节主要考虑三种矩阵，即邻接矩阵， 可达矩阵与关联矩阵.邻接矩阵反映的是 顶点与顶点之间的关系；可达矩阵反映 了图的联通情况；关联矩阵反映的是顶 点与边（弧）的关系. 分有向图与无向 图来讨论. 返回本章首页
第四节关系与图 ●在讨论集合的二元关系时,我们就给出 了关系的图形表示,即关系图这里用图 仑的方法给出关系图的严格定义 关系中的很多性质可以在关系图上反映 出来,可以通过图来研究关系也可以通 过关系来研究图 6 返回本章首页 2021/2/20
2021/2/20 6 第四节 关系与图 ⚫ 在讨论集合的二元关系时，我们就给出 了关系的图形表示，即关系图.这里用图 论的方法给出关系图的严格定义. ⚫ 关系中的很多性质可以在关系图上反映 出来 ,可以通过图来研究关系,也可以通 过关系来研究图. 返回本章首页
第五节欧拉图(1) ●欧拉图是一类非常著名的图,之所以如 此,不仅是因为欧拉是图论的创始人 更主要是欧拉图具有对边(弧)的“遍 历性 1概念有:欧拉路,欧拉图半欧拉路,半欧拉 图割边等 7 返回本章首页 2021/2/20
2021/2/20 7 第五节 欧拉图(1) ⚫ 欧拉图是一类非常著名的图，之所以如 此，不仅是因为欧拉是图论的创始人， 更主要是欧拉图具有对边（弧）的“遍 历性”. 1.概念有:欧拉路,欧拉图,半欧拉路,半欧拉 图,割边等； 返回本章首页
第五节欧拉图(2) 2结论有(1)无向连通图G是欧拉图的充要 条件是G中每个顶点的度均为偶数 (2)设G是无向连通图,则G是半欧拉图 的充要条件是G恰含有两个奇数度点 3.算法:在欧拉图中找欧拉路的 Fleury算法 8 返回本章首页 2021/2/20
2021/2/20 8 第五节 欧拉图(2) 2.结论有:(1)无向连通图G是欧拉图的充要 条件是G中每个顶点的度均为偶数； (2)设G是无向连通图，则G是半欧拉图 的充要条件是G恰含有两个奇数度点. 3.算法:在欧拉图中找欧拉路的Fleury算法. 返回本章首页
第六节哈密尔顿图(1) 哈密尔顿图是_类实际肖景很强的 模型与欧拉图不同,哈密尔顿图感兴趣 的是遍历图中的诸质点 1主要概念啥家尔顿胫半啥尔顿图哈 密尔顿回路哈密尔顿图图的闭包 2主要结论哈密顿图的判定,至令也还 有令人满薏地结果下面的、些哈密顿图 的结果都只是充分条件或必要条件,而 菲充要条件 9 返回本章首页 2021/2/20
2021/2/20 9 第六节 哈密尔顿图(1) ⚫ 哈密尔顿图是一类实际背景很强的图论 模型,与欧拉图不同，哈密尔顿图感兴趣 的是遍历图中的诸顶点. 1.主要概念:哈密尔顿路,半哈密尔顿图,哈 密尔顿回路,哈密尔顿图,图的闭包； 2.主要结论:哈密顿图的判定，至今也还没 有令人满意地结果.下面的一些哈密顿图 的结果都只是充分条件或必要条件，而 非充要条件. 返回本章首页
第六节哈密尔顿图(2) 子集看W 顿图,则对V的任 其中GS 美示在G中删除S中的点以及少S为端点 的边后所构成的图;WG)表示G的 连通分支数 (2设G=E是n阶无向简单凰,若对G中 任意不相邻的顶点u都有d)+d 2n-1则G存在哈密尔顿路,因此G是半 哈密尔顿图; 3)设G是n阶简单图,则是哈密尔顿图当 且仅当其閉包是哈密尔顿图 返回本章首页 2021/2/20
2021/2/20 10 第六节 哈密尔顿图(2) (1)设G=(V,E)是哈密尔顿图，则对V的任 意非空子集S均有W(G-S) ≦|S|,其中G-S 表示在G中删除S中的点以及以S为端点 的边后所构成的图；W(G-S)表示G-S的 连通分支数; (2)设G=(V,E)是n阶无向简单图，若对G中 任意不相邻的顶点u,v都有d(u)+d(v) ≧n-1,则G存在哈密尔顿路，因此G是半 哈密尔顿图； (3)设G是n阶简单图，则是哈密尔顿图当 且仅当其闭包是哈密尔顿图. 返回本章首页