合图.
定义 若将图 G 的每一条边 e 都对应一个实数 w(e)，称 w(e)为边的权，
并称图 G 为赋权图.
求实
团结
创新
奉献
常用术语： （１）端点相同的边称为环． （２）若一对顶点之间有两条以上的边联结，则这些边称为重边． （３）有边联结的两个顶点称为相邻的顶点，有一个公共端点的边
称为相邻的边． （４）边和它的端点称为互相关联的． （５）既没有环也没有平行边的图，称为简单图． （６）任意两顶点都相邻的简单图，称为完备图，记为 Kn，其中 n
d (v4 ) 4
d (v4 ) 2 d (v4 ) 3 d (v4 ) 5
求实
团结
创新
奉献
握手定理：在无向图G=(V,E)中，所有顶点的度的总和等于 边数的两倍，即
d(v) 2m
vV (G)
推论：度数为奇数的顶点个数为偶数。
求实
团结
创新
奉献
例：证明在任意一次集会中和奇数个人握手的 人的个数为偶数个。
团结
创新
奉献
例2：设V ={v1,v2,v3,v4}，E ={v1v2 ,v1v2,v2v3 }， 则H = (V,E ）是一个图。
v1
v4
v2
v3
求实
团结
创新
奉献
定义 在图 G 中，与 V 中的有序偶(vi， vj)对应的边 e，称为图的有向
边（或弧），而与 V 中顶点的无序偶 vivj 相对应的边 e，称为图 的无向边.每一条边都是无向边 的图，叫无向图 ；每一条边都是 有向边的图，称为有向图；既有无向边又有有向边的图称为混
为顶点的数目．
顶点的次数
求实
团结
创新
奉献
定义 （１）在无向图中，与顶点 v 关联的边的数目（环算两次）
称为 v 的次数，记为 d(v)．
（２）在有向图中，从顶点 v 引出的边的数目称为 v 的出度，
记为 d+(v)，从顶点 v 引入的边的数目称为的入度，记为 d-(v)，
d(v)=d+(v)+d-(v)称为 v 的次数．
注：假设图为简单图
e1 e2 e3 e4 e5
1 0 0 0 1 v1
M= 1 1 0 1 0 v2
0 0
0 1
1 11 00来自1v3 v4对有向图Ｇ，其关联矩阵Ｍ＝ (mij ) ，其中：
1 mij 1
0
若vi
是e
的起点
j
若vi
是e
的终点
j
若vi与e j不关联
邻接矩阵
对无向图Ｇ，其邻接矩阵 A (aij ) ，其中：
哈密尔顿于1859年提出“周游世界”游戏，用图 论的术语，就是如何找出一个连通图中的生成圈，近 几十年来，由于计算机技术和科学的飞速发展，大大 地促进了图论研究和应用，图论的理论和方法已经渗 透到物理、化学、通讯科学、建筑学、生物遗传学、 心理学、经济学、社会学等学科中。
哥尼斯堡七桥(Königsberg Bridges)问题
例1：设V={v1, v2, v3, v4}，E={e1, e2, e3, e4, e5 }，满足 e1= v1v2， e2= v2v3， e3= v2v3， e4= v3v4， e5= v4v4， 则称G=（V，E）是一个图。
若用小圆点表示点 集中的点，连线表 示边，可用图形将 图表示出来。
求实
求实
团结
创新
奉献
第六章 图论与网络模型
图论概述
求实
团结
创新
奉献
图论(Graph Theory)是运筹学中的一个重要分支， 主要研究具有某种二元关系的离散系统的组合结构 和性质。
如，通信系统、交通运输系统、信息网络系统、 生产工艺流程以及军事后勤保障系统等的问题常 用图论模型来描述。
一 图论的基本概念 二 最短路问题及其算法 三 最小生成树及算法 四 行遍性问题
在哥尼斯堡有七座桥 将普莱格尔河中的两个岛 及岛与河岸联结起来问题 是要从这四块陆地中的任 何一块开始通过每一座桥 正好一次，再回到起点。
欧拉(Euler)解决了这个问题！ 将问题用图表示 四快被分开的区域作为点 连结它们的桥作为边
求实
团结
创新
奉献
原来是一笔画问题！
求实
团结
创新
奉献
欧拉考察了一般一笔画的结构特点，给
求实
团结
创新
奉献
一、图的基本概念
求实
团结
创新
奉献
图论起源于18世纪。第一篇图论论文是瑞士数 学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。 1847 年 ， 克 希 霍 夫 为 了 给 出 电 网 络 方 程 而 引 进 了 “树”的概念。1857年，凯莱在计数烷的同分异构 物时，也发现了“树”。
求实
团结
创新
奉献
第 七位图 灵 奖 (1972年 ) 获 得 者 。
图的定义
定义：一个图G是指由点和边组成的图形。
求实
团结
创新
奉献
图中的小圆点称为顶点，简称“点”。 顶点之间的连线称为边。
图可用集合表示。
设V为所有顶点组成的集合，E为所有边组成的集合，G 表示图，则 G=（V，E）
求实
团结
创新
奉献
证明: 将集会中的人作为点，若两个人握手则
对应的点联边，则得简单图G。这样G中点v的
度对应于集会中与v握手的人的个数。于是，
问题转化为证明“任意图中度数为奇的点的个
数为偶数”，这正是推论的结论。
关联矩阵
求实
团结
创新
奉献
对无向图Ｇ，其关联矩阵Ｍ＝ (mij ) ，其中：
mij 10
若vi与e j相关联 若vi与e j不关联
出了一笔画的一个判定法则：
这个图是连通的，且每个点都与偶数线
相关联。
将这个判定法则应用于七桥问题，得到
了“不可能走通”的结果，不但彻底解决
了这个问题，而且开创了图论研究的先河。
Euler——伟大的数学家
ei cos i sin
ei 1 0
著名的欧拉公式，最完美的公式
求实
团结
创新
奉献
结构程序设计之父
求实
团结
创新
奉献
aij 10
若vi与v j相邻 若vi与v j不相邻
注：假设图为简单图
v1
0
A= 1
0 1
v2 v3 v4
1 0 1 v1
0 1 1 v2
1 1
0 1
1 0
v3 v4
对有向图Ｇ＝（Ｖ，Ｅ），其邻接矩阵 A (aij ) ，其中：
aij 10
若（vi，v j） E 若（vi，v j） E
求实
团结
创新
奉献
对有向赋权图Ｇ，其邻接矩阵 A (aij ) ，其中：
wij aij 0
若(vi , v j ) E,且wij为其权 若i j
若(vi , v j ) E
无向赋权图的邻接矩阵可类似定义．
v1
0
A= 2
7
v2 v3 v4