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

图论初步 柏钧文

图论初步 柏钧文

图论简介 米图论是数学的一个分支 以图为研究对象 米点代表事物 米边代表关系

 图论是数学的一个分支  以图为研究对象  点代表事物  边代表关系 图论简介

图论起源

图论起源

七桥问题 *哥尼斯堡的七座桥 D F B 米欧拉(1736) G C 米一笔画

 哥尼斯堡的七座桥  欧拉（1736）  一笔画 七桥问题

图论基本术语 *图G=(v,E) 米V代表点集 E代表边集

 图 G=(V,E)  V代表点集  E代表边集 图论基本术语

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

 有向图和无向图  无向图 e={a,b}  有向图 e=={{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)  简单图  完全图  二分图  平面图 图的分类