1.理解图的基本概念,了解几类特殊的图。
2.理解路径与回路及有关概念(基本路径、简单路径、基本回路、简单回路),了解连通图的概念(强连通、单向连通、弱连通、强分图、单向分图、弱分图)。
3.掌握求赋权图短路径的Dijkstra算法。
4.掌握欧拉路径、欧拉回路、欧拉图的判别法,理解哈密尔顿路径、哈密尔顿回路、 哈密尔顿图的概念,了解其性质和邻近算法。
5.掌握图的矩阵表示(邻接矩阵、可达性矩阵)。
6.了解二部图的概念,知道求大匹配的方法。
7.了解平面图的概念,会进行平面图(或非平图)的判别,了解Kuratowski定理、对偶图、五色问题。
8.理解无向树、生成树的概念,掌握用Kruskal算法求小生成树。
9.了解有向树及有关概念,理解二元树的概念和性质,知道搜索树、决策树。