34
定理1 在一个图中，所有顶点次的和等于边的两倍。 定理2 在任意一个图中，次为奇数的顶点必为偶数 个。 定义6：有向图中，以vi为始点的边数称为点vi的出 次，d+(vi); 以vi为终点的边数称为点vi的入次，d-(vi); 所有顶点的入次之和=所有顶点的出次之和；
35
3、子图 定义：设G=（V，E）和G1=（V1，E1）。
如果V1 V， E1 E则称G1为G的子图； 如果G1 =（ V1，E1 ）是G=（V，E）子图， 并且V1 = V，则称G1为G的生成子图；
36
v1 e1
e5 e3
e4
e7 v4
e8
v2
v3
e2
e6
v5
37
（a）
v1
v2
的子图
e1
e5 e3
v4
v5
38
（a）的生 v1 成子图
e5
v2
v3
e2
e6
v4
v5
e8
39
二、连通图
定义8:如果图中的某些点、边可以排列成点和边的交错序列 (v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,…,vn-1 , en ， vn ） ，ei=(vi-1,vi)，则称 此为一条链。 由两两相邻的点及其相关联边构成的点边序列。 初等链：链中无重复的点和边； 定义9：无向图中，如一条链中起点和终点重合，则称此链为 圈。 初等圈：圈中无重复的点和边； 有向图中，当链（圈）上的边方向相同时，为道路（回路）。
个城市，Pregei河把该城分成两部分，河中 有两个小岛，十八世纪时，河两边及小岛之 间共有七座桥，当时人们提出这样的问题： 有没有办法从某处（如A）出发，经过各桥 一次且仅一次最后回到原地呢？
5
A C
B
D
6
最后，数学家Euler在1736年巧妙地给出 了这个问题的答案，并因此奠定了图论的基 础，Euler把A、B、C、D四块陆地分别收缩 成四个顶点，把桥表示成连接对应顶点之间 的边，问题转化为从任意一点出发，能不能 经过各边一次且仅一次，最后返回该点。这 就是著名的Euler问题。
32
e1
v1
e2
e5
e6
v4 e4
e8
v2 e3
v3 e7
v6
v5
33
V= （ v1， v2，…... v6） E= （ e1， e2，…... e8） （e1）= （v1， v2） （e2）= （v1， v2） （e7）= （v3， v5） （e8）= （v4， v4） (e8)= (v4， v4),称为自回路(环)； v6是孤立点，v5为悬挂点，e7为悬挂边，顶点v3的次为 4，顶点v4的次为4。
7
A D
C
B
8
例：哈密顿（Hamilton）回路是十九世 纪英国数学家哈密顿提出，给出一个正 12面体图形，共有20个顶点表示20个城 市，要求从某个城市出发沿着棱线寻找 一条经过每个城市一次而且仅一次，最 后回到原处的周游世界线路（并不要求 经过每条边）。
9
10
11
12
13
14
15
29
环（自回路）：一条边的两个端点如果相同。 两个点之间多于一条边的，多重边。 定义2：不含环和多重边的图，简单图。
含有多重边的图，多重图。 有向图中的两点之间有不同方向的两条边，不是多重边。
简单图
30
定义3：每一对顶点间都有边相连的无向简单图，完全图。
有向完全图：指每一对顶点间有且仅有一条有向边的简单 图。
点击此处输入
相关文本内容
概述二
点击此处输入
相关文本内容
概述三
点击此处输入
相关文本内容
2
第二阶段是从十九世纪中叶到二十世纪 中叶，这时，图论问题大量出现，如 Hamilton问题，地图染色的四色问题以 及可平面性问题等，这时，也出现用图 解 决 实 际 问 题 ， 如 Cayley 把 树 应 用 于 化 学领域，Kirchhoff用树去研究电网络等.
3
第三阶段是二十世纪中叶以后，由生产管理、 军事、交通、运输、计算机网络等方面提出 实际问题，以及大型计算机使大规模问题的 求解成为可能，特别是以Ford和Fulkerson 建立的网络流理论，与线性规划、动态规划 等优化理论和方法相互渗透，促进了图论对 实际问题的应用。
4
例：哥尼斯堡七桥问题 哥尼斯堡（现名加里宁格勒）是欧洲一
定义4:图G=(V,E)的点集V可以分为2个非空子集X,Y，使得 E中每条边的两个端点必有一个端点属于X，另一个端点属 于Y，G为二部图（偶图），有时记为： G=(X,Y,E)
X
YV1V3V2V4312、顶点的次 定义5：以点v为端点的边的个数称为点v的次，记作d(v), 如次为零的点称为弧立点； 次为1的点称为悬挂点。悬挂点的边称为悬挂边。 次为奇数的点称为奇点，次为偶数的点称为偶点。 偶点：d(v)=偶数； 奇点：d(v)=奇数；
16
17
18
19
20
21
22
23
24
25
26
图的基本概念
图论是专门研究图的理论的一 门数学分支，主要研究点和线之间的 几何关系。
27
第一节 图与网络的基本知识
一、图与网络的基本概念
1、图及其分类 定义1：（图）一个图由点集V和V中的元素无序对的一个 集合，记为 G=（V，E） 其中：V= （ v1， v2，…... vm）是m个顶点集合；
第八章 图与网络分析
引言 图论是专门研究图的理论的一门数学分
支，属于离散数学范畴，与运筹学有交叉， 它有200多年历史，大体可划分为三个阶段： 第一阶段是从十八世纪中叶到十九世纪中叶， 处于萌芽阶段，多数问题围游戏而产生，最 有代表性的工作是所谓的Euler七桥问题，即 一笔画问题。
1
整体概述
概述一
E= （ e1， e2，…... en） 是n条边集合。 当V和E为有限集合时，G为有限图。 2个点u,v属于V，如果边(u,v)属于E， u,v相邻； u,v为边(u,v)的端点。
28
具有公共端点u的两条边，称为点u的关联边。
如果任一边(u,v)属于E且端点无序，无向边；图G为无向图。 如果任一边(u,v)属于E且端点有序，有向边；图G为有向图 m(G)= E ，表示图G的边数； n(G)= V ，表示图G的点数；
40
链、初等链、初等圈
道路、回路
Q 1v1e1v2e7v5e8v2e5v4 链
道路
Q 2v1e1v2e2v3e4v4 初等链 道路
Q 3v1e1v2e5v4e6v5e9v1 初等圈 回路