1、第七章 图与网络优化第 1节 图的基本概念第 2节 树第 3节 最短路问题第 4节 网络最大流问题第 5节 最小费用最大流问题第 6节 中国邮递员问题例：哥尼斯堡七桥问题问题：一个散步者能否走过七座桥，且每座桥只走过一次，最后回到出发点。能否从某一点开始一笔画出这个图形，最后回到原点，而不重复。AB C D例：有甲、乙、丙、丁、戊五个球队，各队之间比赛情况如表：第 1节 图的基本概念v1v2 v3v4v5点：球队；连线：两个球队之间比赛过，如甲胜乙，用v1 v2表示。点：研究对象（陆地、路口、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、路口之间道路、两国边界、两球队比赛及结果）。对
2、称关系：桥、道路、边界；用不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。图：点及边（或弧）组成。无向图：由点及边构成 ，记为 G=(V,E)， 式中 V,E分别是 G的点集合和边集合。边 vi， vj有向图：由点及弧构成，记为 D=(V,A)， 式中 V,A分别是 G的点集合和弧集合。弧 ( vi， vj）图 G中点集 V的顶点个数，记为 P (G) ， 边数记为 q(G),简记 P， q。一、图的定义若边 e=u， v E，称 u， v是 e的端点，也称 u， v是相邻的。称 e是点 u（ 及点 v） 的关联边。若两条边有一个公共的端点，则称这两条边相邻 。
3、点 点，相邻二、图论中常用术语1、相邻与关联vi vjevi， vj相邻 e 与 vi， vj关联vi e1e1 与 e2相邻vjvk e2边 边，相邻点 边2、简单图与多重图某条边两个端点相同，称这条边为环。若两点之间有多于一条的边，称这些边为多重边。无环、无多重边的图称为简单图。多重图：无环、但允许有多重边。v1e1 e2e3v2 v3e5e4v43、次与悬挂点、孤立点图 G中以点 v为端点的边的数目，称为 v在 G中的次，记为 d（ v）。v1e1 e2e3v2 v3e5e4v4d(v1)=2 , d(v2)=3 , d(v3)=4 , d(v4)=1次为 1的点为悬挂点，悬挂点的关联边称为悬挂边，次为零的点称为孤立点。定理 1 图 G=（ V， E） 中，所有点的次之和为边数的两倍， 即4、奇点与偶点次为奇数的点称为奇点，否则称为偶点。定理 2 任一图中奇点的个数为偶数。
