图论初步 柏钧文
图论初步 柏钧文
图论简介 米图论是数学的一个分支 以图为研究对象 米点代表事物 米边代表关系
图论是数学的一个分支 以图为研究对象 点代表事物 边代表关系 图论简介
图论起源
图论起源
七桥问题 *哥尼斯堡的七座桥 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) 简单图 完全图 二分图 平面图 图的分类
