图的模型和算法初步.ppt

好算法还是坏算法 算法无效 算法的时间复杂性分析 什么是算法 时间复杂度 量级比较 有效算法 返 回 一个算法就是解决某一特定问题的方法，是一系列确定步骤，它必须在有限的时间内终止。 表述一个算法一般有两种方式 （1） 步骤描述； （2） 框图。 什么是算法 例：求两个正整数m和n的最大公因子的Euclid算法 什么是算法 输入：正整数m, n。 输出：m和n的最大 公因子。 1） 求余数 m除以n，令r为所得的余数 (0?rn)。 2) 判断r是否为0。若r=0，则算法终止；否则，转3)。 3) 互换。 置m?n,n?r,返回第一步 返 回 用行列式的定义求一个20阶行列式的值，即使是每秒1000万次的计算机也要花大约15万年的时间。 算法无效 好算法还是坏算法 如何才能简便地判断一个算法的有效性呢？在什么情况下一个问题找不到有效算法来求出正确解？ 返 回 ? * 下一页 上一页 主 页 图的表示与算法初步 参考书： 1.傅鹂 龚劬 刘琼荪 何中市 《数学实验》科学出版社 2.张绍民 李淑华 《数据结构教程C语言版》中国电力出版社 3.龚劬 《图论与网络最优化算法》 龚劬 重庆大学出版社 主讲：龚 劬 制作：龚 劬 主要内容 图的模型 算法初步 图的矩阵表示方法 结束 图的模型 一个时间安排问题 图论的起源——七桥问题 人、狼、羊、菜渡河问题 图论的起源：七桥问题 a c b d a c b d 图论的起源：七桥问题 graph 以四块陆地a,b,c,d为4个点(称为顶点),当且仅当两块陆地之间有一座桥时,就在对应的两点之间连一条线(称为边), 得到图G. 一般用大写字母G,H表示无向图。 一种表示工具——图 顶点 边 d c a b 三要素：顶点集V；边集E；关联函数? G=(V,E,?) 如 ?(e1)={a,b}， e2 e3 e1 e4 e5 无向图 ? e与顶点u, v相关联 ? u与v相邻 ? 两边相邻 ? 重边 c a b d 一种表示工具——图 你能给出一些可用无向图描述的实际例子吗？ ? 无向图 ? 任何两个以上的人组成的人群中，至少有两个人，他们的朋友数一样多。 ? 在一次象棋比赛中，若每名选手与其余选手都比赛过，人数是n，求总盘数。 ? 设S=（x1，,x2，…，xn）是平面上的点集，其中任意两点间的距离至少是1，证明：距离正好是1的点对数最多为3n。 ? 在n个运动队间安排了一项竞赛，已赛n+1局，试证：存在一个队，它至少参加过3局比赛。 一种表示工具——图 一些特殊的图 一种表示工具——图 １) 既没有环也没有重边的图，称为简单图． ２) 任意两顶点都相邻的简单图,称为完全图. 记为Kv 一种表示工具——图 ３) 若 ， ，且X 中任意两顶点不 相邻，Y 中任意两顶点不相邻，则称为二部图或 偶图；若X中每一顶点皆与Y 中一切顶点相邻,称为 完全二部图或完全偶图,记为 (m=|X|,n=|Y|)． 二部图 你能给出一些可用二部图描述的实际例子吗？ 有向图： V1 V2 V3 V5 V4 你能给出一个可用有向图描述的实际例子吗？ 一种表示工具——图 ? 加权图 这些数字可以代表距离，费用，可靠性或其他的相关参数。 1 2 3 4 5 8 6 9 1 5 7 10 3 一种表示工具——图 返 回 一种表示工具——图 返 回 定义 若图 的每一条边e 都赋以 一个实数w(e)，称w(e)为边e的权，G 连同边上的权 称为赋权图. 定义 设 和 是两个图. 1) 若 ,称 是 的一个子图,记 2) 若 ， ，则称 是 的生成子图. 路径与连通 返 回 定义 1) 无向图G的一条通路是指 一个有限非空序列 ，它的项交替 地为顶点和边，