图论期末考试有哪些复习重点

图论教材

图论历年期末考题

首先，我们要明确很多图论的概念。比如联图(顶点数、边数)、积图(顶点数、边数)、完全偶图，连通分支（无向图）、块、强连通分支（有向图）、i因子、一因子分解、割点、割边、点连通度、边连通度、欧拉闭迹、一笔画、H图、邻接矩阵、最大匹配、完美匹配、闭包、可平面图等。

其次，我们还要搞清楚很多细节。例如，高为h的树究竟有h层还是h+1层；彼得森图是什么样的；没有割点的图为什么可以没有割边(例如K2)；有割点的图为什么不一定是非哈密尔顿图(因为可以不连通)；平凡图是偶图吗（是的）；极大外平面图的每个面为什么不全是三角形（因为外平面图内面是三角形外面是圈）；

接下来，我们还需要熟练计算很多大概率会考的计算题。比如，最短路算法；最小生成树算法；最优欧拉环游的计算；色多项式的计算；

之后，我们还要熟练应对各类应用题。比如，给出很多人擅长的领域问能否合理分配大概率要用霍尔定理；课程安排/答辩不发生冲突其实是点着色；最少安排多少天比赛(没有冲突字样的)常常是边着色。

最后，我们还要记住一些的定理来应对证明题。比如握手定理、简单图最大度<总点数、H图的判别定理(尤其是Dirac定理：n>=3的简单图若delta(G)>=n/2则G是H图)；平面图性质（欧拉公式：n-m+φ=2）及其推论(n-m+φ=k+1\m<=3n-6);

考试的时候还要带上手表哦

平时上课也应该好好听课呀