有向图中两点之间有不同方向的两条边，不是多重边。
定义2：不含环和多重边的图是简单图，含有多重边的 图称为多重图。下图哪些是简单图，哪些是多重图？
(a)
(b)
(c)
(d)
a,b为简单图，c,d为多重图。
定义3: 每一对顶点间都有边相连的无向简单图称为完全 图。每一对顶点间有且仅有一条有向边的简单图称为有 向完全图。
A
C
D
B
此难题于1736年被瑞士数学家欧拉解决，他在 “依据几何位置的解题方法”论文中证明这样的 走法不存在。欧拉被公认为图论的创始人。
A
Cቤተ መጻሕፍቲ ባይዱ
D
B
A D
C
B
1857年，英国数学家Hamilton发明一种游戏，用一个实心 正12面体象征地球，其20个顶点分别表示世界的20个城市， 要求游戏者从某一城市出发寻找一条经由每个城市一次且仅 经一次再回到原出发点的路。此问题有解。
v4
1 aij 0
边(vi , v j ) E 其他
v1
称矩阵A为图G的邻接矩阵。当G为
v2
v3
无向图时，邻接矩阵为对称矩阵。
右图的邻接阵为： 0 1 1 1 1
0 0 0 1 0 A 0 1 0 0 1
0 0 1 0 1 0 0 0 0 0
四、欧拉回路与中国邮路问题
定义13：连通图中，若存在一条回路，经过每边一次且 仅一次，则称之为欧拉回路。具有欧拉回路的图称为欧 拉图（E图）。 定理3：无向连通图G是欧拉图，当且仅当G中无奇点。
定义7：图G=(V,E)，若E’是E的子集，V’是V的子集， 且E’中的边仅与V’中的顶点相关联，则称G’=(V’,E’)是 G的一个子图。若V’=V, 则G’称为G的生成子图。
例，下图(b)为(a)的子图，(c)为(a)的生成子图。
v1
v1
v1
v2 v5
v4 v2 v5
v2 v5
v4
v3
v3
v3
(a)
5.1 图与网络基本知识
一、图与网络的基本概念
企业A 企业B
企业C
企业D
企业E
工人 甲
乙 丙 丁 戊
工作
A B C D
图：反映对象之间关系的一种工具。
定义1：一个图是由点集V={vi}和边集E={ek}（所有边 的端点都属于V）所构成的二元组，记为G=(V,E)。vi 为顶点，ek为边，当V、E为有限集时G为有限图。
定理4：有向连通图G是欧拉图，当且仅当G的每个顶点 的出次等于入次。
中国邮路问题：邮递员从邮局出发，走遍该地区所有街 道再返回邮局，如何安排路线可以使所走总路程最短？
Euler回路：在图中找一条经过每边一次且仅一次的 路且回到原点。 Hamilton回路：在图中找一条经过每个点一次其仅 一次的路且回到原点。
图论第一本专著：《有限图与无限图的理论》，1936， 匈牙利数学家。
图论迅速发展时期：20世纪中期，电子计算机的发 展以及离散数学的发展，促使图论在管理科学、信 息论、控制论等各领域广泛应用。
第五章 图与网络分析
主要内容： 5.1 图与网络的基本知识 5.2 树 5.3 最短路问题 5.4 最大流问题
思考：哥尼斯堡七桥问题
哥尼斯堡（现名加里宁格勒）是欧洲一个城市， 有一条河把该城分成两部分，河中有两个小岛，十 八世纪时，河两边及小岛之间共有七座桥，当时人 们提出这样的问题：有没有办法从某处（如A）出 发，经过各桥一次且仅一次，最后回到原地呢？
定义8：无向图G中能够连接两点的点、边序列构成一 定条SvS112,==义链v{{4vv9的。11：,,一ee没11无,,条vv有向33,,链重ee图77,,；复vvG55,,点ee中64,,或一vv34重,}条e为7复,链v初5边,的e等4的,始v链4链点}为为和连初终接等点链是v。同1 e一e12e点v3vv3时42ee5e，64e7 v5 称为圈。没有重复点或重复边的圈为初等圈。 S1={v1,e1,v3,e7,v5,e6,v3,e7,v5,e4,v4,e2,v1}为一个圈； S2={v1,e1,v3,e7,v5,e4,v4,e2,v1}为一个初等圈。
24 8
aij
0wij
边(vi , v j ) E 其他
9 v2
3 v3
称矩阵A为网络G的权矩阵。
右图的权矩阵为： 0 9 2 4 7
9 0 3 4 0 A 2 3 0 8 5
4 4 8 0 6 7 0 5 6 0
三、图的矩阵表示
v5 定义12：图G=(V,E)的顶点的数量
为n，构造矩阵A=(aij)n×n，其中
(b)
(c)
权：点或边相关的某些数量指标，可代表距离、费用、 容量等。 网络：点或边带有某种数量指标的图。
v3
5 23
v1
2 4 v256
v5
v4
(a)
v3
v1
5 2
2
3
4 v256
v5
v4
(b)
(a),(b)是常见网络例子，(a)网络图常见于最短路问题， (b)网络图常见于管道运输网络。
二、连通图
e1
右图中d(v1)=4 (e1计算两次)
d(v3)=4
e2
v2
v4
v1 e4
e3
e6
v3
e5
v5 定理1：任何图中，顶点次数的总和等于边数的2倍。 定理2：任何图中，次为奇数的顶点必为偶数个。
定义6：有向图中以vi为始点的边数称为vi的出次，记为 d+(vi) ，以vi为终点的边数称为vi的入次，记为d-(vi) 。
有向图中边的方向相同时，链和圈分别称为道路和回路。 定义10：一个图中任意两点间至少有一条链，称为连通图。 任何非连通图都可以分为若干个连通子图(分图)。
三、图的矩阵表示
定义11：网络(赋权图)G=(V,E)上的
v5 6
边(vi,vj)有权wij，构造矩阵 A=(aij)n×n，其中
7
5
v4
4
v1
例：右图中
e1
V={v1,v2,v3,v4,v5}
v4
E={e1,e2,e3,e4,e5,e6} e1=(v1,v1),e2=(v1,v2),…
e2 v2
无向图：任意边都是无向边的图
v1 e4
e3
e6
v3
e5
有向图：任意边都是有向边的图
v5
环：边的两端点相同也称环，如e1;
多重边：两点间多于一条边，如e4,e5
定义4：图G的点集V可以分成两个非空子集X,Y,使得 E中每条边的两个端点必有一个属于X，另一个属于Y， 则G称为二部图。
以下哪些是二部图？
(a)
(b)
a,b图都是二部图。
定义5：以点v为端点的边数叫做点v的次。记为
deg(v),简记d(v)。
次为奇数的点称为奇点，次为偶数的点称为偶
点。次为0的点称为孤立点。