（含教学思路、课程设计方案等，字数不超过3000字） 教学进程 1、引入课题 采用ppt最新演示技术，使用海底世界为背景，吸引学生，介绍课程章节内容。 第七章共三小节，本节内容讲授第一小节，第一小节图的概念。 首先引入生活中的图，介绍地图及其包含的元素（重点是道路）；介绍电路图及其包含的元素，再介绍和我们专业相关的流程图及其包含的元素。 引入思考题：这些图都有什么共性？ 讲解：这些生活中的图都是由结点和连接边组成的，然后引入抽象的图的概念。 2、教学内容 7.1.1 图的定义 1.二元组 2.有向图和无向图 7.1.2 图中的基本术语 1.端点和邻接点 2.顶点的度、入度和出度 7.1.1 图的定义 1、二元组定义： G=(V,E) V：图的顶点集 E：图的关系集（边集） 图的边： ①(x,y):无向边 ②<x,y>:有向边（弧） 针对图G，顶点集和边集可分别记为V(G)和E(G) 讲解：首先要强调让同学们理解图的共性就是点和边的集合，然后引入数学概念，用V表示图的顶点集（结点），E表示图的关系集（边），这样，这个二元组就能表示定点和边组成的图。 2、相关概念 有向图：对于一个图G，若边集E(G)中为有向边，则称此图为有向图(directed graph)。 无向图：若边集E(G)中为无向边，则称此图为无向图(undirected graph) 讲解：使用图形G1举例讲解无向图的概念和数学表示；使用图形G2举例讲解有向图的概念和数学表示。（翻转课堂，学生讲解） 同时强调图是一种多对多的关系。 7.1.2 图中的基本术语 1、端点和邻接点 在一个无向图中，若存在一条边(vi,vj)，则称vi,vj为此边的两个端点，并称它们互为邻接点 。 讲解：以G1图为例讲解。 例如：在图G1中，存在一条边（0,2） 则端点0和端点2称为此边的两个端点 并称端点0和端点2互为邻接点。 端点0是端点2的邻接点，端点4,5也是端点2的邻接点 端点2是端点0的邻接点，端点1,3也是端点0的邻接点 引入思考题：思考：有三个端点的边吗？在无向图里是怎么处理的？（翻转课堂） 2、顶点的度、入度、出度 在一个无向图中，顶点v的度(degree)定义为以该顶点为一个端点的边的数目，记为D(v)。 有向图中顶点v的度有入度和出度之分，入度(indegree)是该顶点的入边的数目，记为ID(v)；出度(outdegree)是该顶点的出边的数目，记为OD(v)；顶点v的度等于它的入度和出度之和 D（V）=ID（V）+OD（V） 讲解：以图G1,G2为例进行讲解,详细讲解度是怎么计算的。（翻转课堂，学生讲解）无向图G1中，顶点0的度D(0)为4 有向图G2中，顶点C的入度ID(C)=2;出度OD(C)=2;顶点C的度D(C)=4  引入思考题，并作为作业布置：证明若一个图中有n个顶点和e条边，则该图中所有顶点的度同边数e满足下面关系：
3、完全图、稠密图、稀疏图 若无向图中的每两个顶点之间都存在着一条边，有向图中的每两个顶点之间都存在着方向相反的两条边，则称此图为完全图 。 当一个图接近完全图时，则称它为稠密图，相反地，当一个图含有较少的边数，即边数与顶点数接近时，则称它为稀疏图。 讲解：使用图解和举例说明完全图、稠密图和系数图的概念。 3、课堂总结 总结该节课的重点图的二元组定义，有向图和无向图，度，完全图。要求同学们多思考生活中的图都有哪些，怎样抽象成我们所学的图的表示。 4、布置作业 1.证明若一个图中有n个顶点和e条边，则该图中所有顶点的度同边数e满足下面关系： 2.联系实际，举一个身边的图的例子，分解元素，并把它抽象成二元组表示。 | 
