离散数学Ⅰ（图论）期末复习第一篇
写这个时的感想第五章 图的基本概念5.1 有向图和无向图5.2 通路、回路和图的连通性5.3 图的矩阵表示5.4 最短路径、关键路径和着色
写这个时的感想
第一篇博客！！！ 小激动！ 深刻怀疑这些题目是要考的（判断与应用）； 唉，还有一些定理、结论性的东西（证明类）； 到时候再写罢……
基于老师的ppt和清华大学出版社的《离散数学（第五版）》
第五章 图的基本概念
5.1 有向图和无向图
握手定理
求边，求点。给一个度数列，判断其能不能构成一个图
子图
哪些是边导出子图，哪些是点导出子图这是不是点导出子图，这是不是边导出子图请画出某图的： 生成子图（包含所有的顶点、边不一定有） 子图（相比生成子图，点也不一定全有） 点导出子图 边导出子图
同构
这几幅图同构吗，为什么 如果同构，记得要写出点、边的一一对应关系。 如果不同构，要写出原因
记得图的数学表达（等考完前几场试我再补充）
补图 请画出某图的补图
5.2 通路、回路和图的连通性
通路与回路
存在通路吗？写出来 简单通路（所有边都不一样、点无所谓） 复杂通路（有重复边出现） 初级通路（所有边都不一样，所有点都不一样）存在回路吗？写出来 （如上） 连通
有多少个连通分支？这个点集是不是点割集？这个边集是不是边割集？ 有向图当中
弱连通吗？ 看基图连不连通就好了强连通吗？ 当且仅当图中存在经过每一个顶点至少一次的回路单向连通吗？ 当且仅当图中存在经过每一个顶点至少一次的通路
5.3 图的矩阵表示
无向图的关联矩阵
怎么写 行是边，列是点，m
ij是顶点v
i和边e
j的关联次数。 关联次数有三种取值： 0（v
i与e
j不关联） 1（v
i与e
j关联一次） 2（v
i与e
j关联两次，也就是e
j是以v
i为顶点的环！）性质 每一列恰好有两个1：每条边关联两个顶点 每一列恰好有一个2：环关联的两个顶点重合 第i行的元素之和：即v
i的度数 所有元素之和：边数的二倍（握手定理） v
i是孤立点时：当且仅当第i行全部为0 e
j和e
k是平行边时：第j列和第k列相同 （没有环的） 有向图的关联矩阵
怎么写 行是边，列是点 但是！m
ij的取值和之前无向图的不太一样 1 ：v
i是e
j的始点 0 ：v
i与e
j不关联 -1：v
i是e
j的终点性质 每一列恰好有一个+1和一个-1； 每行中 +1 的个数：对应的点的 出度 每行中 -1 的个数：对应的点的 入度 有向图的邻接矩阵 （可以有环了！）
怎么写 每行每列都代表了点。 m
ij的取值：v
i邻接到v
j的边的条数性质 第i行的元素之和：v
i的出度 第j列的元素之和：v
j的入度 所有的元素之和 = 边数 噢还有一个很重要的定理： A
l中的元素a
ij是v
i到v
j长度为l的通路数 A
l中所有元素和是有向图中长度为l的通路（包括回路）的总数 其中对角线上的元素和是图中长度为l的回路总数 就……先不在这里证明了 有向图的可达矩阵
怎么写 若v
i可达v
j，元素p
ij=1；反之，元素p
ij=0性质 对角线上元素都是1
类似的，无向图也可以有邻接矩阵和可达矩阵！ 即每一条无向边都可以看作一对方向相反的有向边 显然，无向图的邻接矩阵和可达矩阵都是对称的
5.4 最短路径、关键路径和着色
Dijkstra算法
项目网络图
着色
