文档介绍：该【离散数学图论 】是由【海洋里徜徉知识】上传分享，文档一共【116】页，该文档可以免费在线阅读，需要了解更多关于【离散数学图论 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第七章 图论
§ 图基本概念
§ 路与回路
§ 图矩阵表示
§ 欧拉图和汉密尔顿图
§ 平面图
§ 对偶图与着色
§ 树与生成树
1
第1页
第1页
第七章 图论
教学目的及要求：
深刻理解和掌握图相关概念和表示。
教学内容：
图基本概念、路与回路、图矩阵表示、欧拉图与汉密尔顿图、平面图、对偶图与着色、树与生成树。
教学重点：
图、路、图矩阵表示、平面图、、 树与生成树。
教学难点：树与生成树。
2
第2页
第2页
图论
图论是近年来发展快速而又应用广泛一门新兴学科。
图论最早起源于一些数学游戏难题研究。如：哥尼斯堡七桥问题、迷宫问题等。
1847年，克希霍夫用图论分析电路网络，最早将图论应用于工程科学。
图论内容十分丰富, 它是一门应用性很强学科。计算机科学、网络理论、信息论、运筹学、语言学、物理、化学等都以图作为工具, 来处理实际问题和理论问题。
3
第3页
第3页
图论
现实世界中许多状态是由图形来描述, 我们用点表示事物, 用点之间是否有连线表示事物之间是否有某种关系, 于是点以及点之间若干条连线就构成了图。
当我们研究对象能够被抽象为离散元素集合和集合上二元关系时, 用关系图进行表示和处理是很以便。
图可分为有限图和无限图两类, 本书只研究有限图, 即顶点和边都是有限集合。
4
第4页
第4页
图基本概念
离散数学研究图是不同于几何图形、机械图形另一个数学结构,不关心图中顶点位置、边长短和形状, 只关心顶点与边联结关系。
以下图（a）和（b）
a
b
c
d
e1
e2
e6
e4
e3
e5
（a）
a
b
c
d
e1
e6
e2
e4
e3
e5
（b）
a
b
c
d
e1
e2
e6
e4
e3
e5
5
第5页
第5页
（1）定义: 一个图G是一个三元组<V(G),E(G), ΦG>, 其中V(G)为顶点集合, E(G)是边集合，ΦG是从边集E到结点偶对集合上函数。
讨论定义：
(a) V(G) ={V1，V2，…，Vn}为有限非空集合,
Vi称为结点,简称V是点集。
(b) E(G)={e1，…，em}为有限边集合,ei称为边，每个ei是连结V中某两个顶点,称E为边集。
(c) 可用e＝ <vi,vj>或e＝ (vi,vj)，来表示图边，这样可把图简化成：Ｇ＝<Ｖ，Ｅ>。
图基本概念
6
第6页
第6页
（2）每一条边都是无向边图称无向图。
每一条边都是有向边图称有向图。
b
c
d
a
b
c
d
a
假如图G中既有无向边, 又有有向边, 则称该图为混合图。本课程不讨论混合图。
图基本概念
7
第7页
第7页
例：对有向图可表示为：
Ｇ＝〈Ｖ，Ｅ〉，
其中Ｖ＝｛a、b、c、d｝
Ｅ＝｛<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>｝
则：Ｇ＝〈Ｖ，Ｅ〉= 〈 ｛a，b，c，d｝ ， ｛<a,b>,<b,a>,<b,d>,<d,a>,<d,d>,<c,c>｝ 〉
图基本概念
8
第8页
第8页
（3）在一个图中，若两个结点有一条有向边或者一条无向边关联,则这两个结点成为邻接点。
孤立结点：在一个图中不与任何结点相邻接结点，称为孤立结点。以下图中结点v5。
（4）零图：仅由孤立结点组成图称为零图。
v1
v2
v3
v4
v5
图基本概念
9
第9页
第9页
（5）平凡图：仅由一个孤立结点组成图称为平凡图。
邻接边：关联于同一结点两条边称为邻接边。
（6）自回路（环）：关联于同一结点一条边称为自回路。 以下图，中（c，c）是环
a
c
b
a
图基本概念
10
第10页
第10页