美文网首页离散数学笔记
离散数学第五版:第五章知识点概要

离散数学第五版:第五章知识点概要

作者: 燃烧的铁蛋 | 来源:发表于2018-04-24 18:58 被阅读0次

           第五章主要是讲图的基本概念,其中大部分内容都是考研的时候接触过的。

           第一节为无向图与有向图,又和以前一样,堆了若干概念定义,主要有多重集,无序积,顶点集,边集,n阶图,零图,平凡图,端点,孤立点,关联次数等等,无甚大用。

           第二节为通路、回路和图的连通性,主要也是讲了图的一些概念,何为连通,何为可达等等。这一节有三个可能有用的概念,一个为弱连通图,指的是对应的无向图可以连通;一个是单向连通图,指的是任意两个节点之间至少有一个方向可以连通;另一个是双向连通图,它指任意两点任意方向都能连通的图。

           第三节为图的矩阵表示,讲了无向图有向图的关联矩阵,有向图的邻接矩阵,和有向图的可达矩阵。至于可达矩阵,说的就是两个点之间是不是存在指定方向的路径,存在的话矩阵内该元素为1,否则为0。另外关于有向图的邻接矩阵还有一个比较重要的定理,即邻接矩阵的次方形式表示两点间为次方数长度的路径数。

           第四节为最短路径、关键路径和着色,应用型比较强,主要讲的内容如题所示。

    相关文章

      网友评论

        本文标题:离散数学第五版:第五章知识点概要

        本文链接:https://www.haomeiwen.com/subject/nqtslftx.html