《图论初步》课程教学资源（PPT课件讲稿）图论初步

图论基本术语 米有向图和无向图 无向图e=a,b} 有向图e=<a,b>={a,b}b,a

 有向图和无向图  无向图 e={a,b}  有向图 e=<a,b>={{a,b},{b,a}} 图论基本术语

图论基本术语 度(入度、出度) 路径 米生成树

 度（入度、出度）  路径  生成树  割 图论基本术语

度 入度通常指有向图中某点作为图中边的终点的次数 之和 *出度通常指有向图中某点作为图中边的起点的次数 之和 无向图是有向图的特例 无向图的度

 入度通常指有向图中某点作为图中边的终点的次数 之和  出度通常指有向图中某点作为图中边的起点的次数 之和  无向图是有向图的特例  无向图的度 度

度的一些定理 *定理1:无向图中所有顶点的度之和等于边数的2倍, 有向图中入度和等于出度和 定理2:任意一个无向图一定有偶数个奇点 定理3:无论无向图还是有向图 E=(dv+…+dn)2

 定理1：无向图中所有顶点的度之和等于边数的2倍， 有向图中入度和等于出度和  定理2：任意一个无向图一定有偶数个奇点  定理3：无论无向图还是有向图 E=(d[v1]+...+d[vn])/2 度的一些定理

图的分类 *G=(v,E) 米简单图 米完全图 米二分图 平面图

 G=(V,E)  简单图  完全图  二分图  平面图 图的分类