考研复试 | 离散数学——第五章 图的基本概念
5.1 无向图及有向图
-
多重集 无序积 无向图，空图 有向图 n阶图，零图，平凡图 （无向图）端点，关联，孤立点，环，关联次数，相邻 （有向图）始点，终点，端点，关联，孤立点，环，邻接到，相邻 度数（度），入度，出度 悬挂顶点，悬挂边 最大度，最小度，最大（or最小）入度，最大（or最小）出度 握手定理 度数序列 平行边，重边，多重图，简单图 n阶无向完全图，n阶有向完全图 子图，母图，真子图，生成子图，导出子图 补图 同构，彼得森图
通路、回路和图的连通性
-
通路，起点，终点，长度，回路 简单通路，简单回路，初级通路，路径，初级回路，圈，复杂通路，复杂回路 图中通路和回路的性质 连通，可达 连通图，非连通图，连通分支，p(G) 弱连通图（连通图），单向连通图，强连通图 删除 点割集，割点，边割集（割集），割边（桥）
5.3 图的矩阵表示
-
无向图的关联矩阵 无向图的关联矩阵具有的性质 有向图的关联矩阵 有向图的邻接矩阵 长度为l的通路（或回路）数 有向图的可达矩阵 无向图的邻接矩阵和可达矩阵
最短路径，关键路径和着色
-
权，带权图 最短路径，距离 最短路径问题 dijkstra算法 项目网络图 关键路径，关键活动 点着色（着色），k-可着色的 着色问题 鸽巢原理
