Question

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

Answer 1

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

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

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

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

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