图论基础PPT学习教案_第1页
图论基础PPT学习教案_第2页
图论基础PPT学习教案_第3页
图论基础PPT学习教案_第4页
图论基础PPT学习教案_第5页
已阅读5页，还剩17页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、会计学1 图论基础图论基础 G(V,E),V=a,b,.,E(x,y)|x,yV,xy 第2页/共22页第1页/共22页 2 n 2 Polya定理告诉我们如何计算无标号图的个数定理告诉我们如何计算无标号图的个数 如何判断两个图是否如何判断两个图是否“同构同构”依然是图论的最基依然是图论的最基 本挑战之一本挑战之一 第3页/共22页第2页/共22页 第4页/共22页第3页/共22页 G(V,E),V=a,b,.,E|x,yV,xy 第5页/共22页第4页/共22页 存在一条路存在一条路 n连通分量连通分量 1.连通子图连通子图 2.不被真包含在任何其他连通子图不被真包含在任何其他连通子图 中中

2、 第6页/共22页第5页/共22页 第7页/共22页第6页/共22页 第8页/共22页第7页/共22页 距离至少为距离至少为3。 n桥可以看成是捷桥可以看成是捷 径的一个特例径的一个特例 第9页/共22页第8页/共22页 (2)不被真包含在不被真包含在 任何其他满足任何其他满足 性质性质(1)的子图的子图 中中 (B,C,D, ,) 第10页/共22页第9页/共22页 n从某一点开始，从某一点开始， 对图的节点的对图的节点的 一种一种“遍历遍历” 方式方式 第11页/共22页第10页/共22页 nUCSB, UCLA, STAN BFS从概念上对图中的节点进行从概念上对图中的节点进行 了一个了

3、一个“分层分层”，所涉及到的边，所涉及到的边 “自然形成了自然形成了”一个二部图一个二部图 第12页/共22页第11页/共22页 n万维网上的网页之间的链接关系万维网上的网页之间的链接关系 n论文之间的引用关系论文之间的引用关系 n 第13页/共22页第12页/共22页 0111 1001 1001 1110 1110 1001 0100 0011 0 0 1 1 相邻节点列表相邻节点列表 1：2,3,4 2：1,4 3：1,4 4：1,2,3 边序列边序列 1,2 1,3 1,4 2,4 3,4 第14页/共22页第13页/共22页 nCuttlefish，一个简单易用工具的一个简单易用工具的 例子例子 第15页/共22页第14页/共22页 度优先搜索结果度优先搜索结果 下次课前交的：上网搜索，找到下次课前交的：上网搜索，找到3 个不同类型的网络图及其简单说个不同类型的网络图及其简单说 明；第明；第2章章练习练习2.1 第16页/共22页第15页/共22页 第17页/共22页第16页/共22页 第18页/共22页第17页/共22页 第19页/共22页第18页/共22页

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论