第一章图
教学安排的说明
章节题目：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算
学时分配：共2课时
本章教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），会进行图的运算，会用图论的方法描述一些简单的实际问题．
其它：由于离散数学中已介绍过相关内容，本章以复习为主
课 堂 教 学 方 案
课程名称：§1.1图的概念；§1.2子图；§1.3顶点的度；§1.4道路与连通性；§1.5图的运算
授课时数：2学时
授课类型：理论课
教学方法与手段：讲授法
教学目的与要求：会正确表述关于图的一些基本概念（如图、连通图、道路、圈），
会进行图的运算，会用图论的方法描述一些简单的实际问题．
教学重点、难点：
（1） 理解图、简单图、子图以及图的同构等概念，并能够用图表示简单
的现实问题；
（2） 掌握途径、链和道路的概念及其区别；
（3） 理解图的连通性概念；
（4） 掌握图的四种运算。
教学内容：
第一章 图
§1.1图的概念
引例
例1.下面是五城市之间的航线图，若两城市间有航线，则连线，否则不连如图1.1（a ）：由图中可知，北京与广州间没有航线，而大连到上海间有航线
北京 大连 上海 广州 昆明 9 6 4 8 10 （a ） （b ）
图1.1
例2.数4，6，8，10，9五个数，若有公因子则连线，，否则不连，如上图1.1(b) 通常人们认为，过去我们所学的微积分是属于连续数学，而本章所要讨论的图论是离散数学的重要分支．
首先要注意，我们这里所讨论的图论中的“图”，并不是以前学过的通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统．也就是说，几何图形是表述物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系．因此在图论中，顶点之间的距离、弯曲、以及顶点间的位置关系都是无关紧要的，即图的概念是抽象化的,它是数学中经常采用的抽象直观思维方法的典型代表．
下面给出图作为代数结构的一个定义。
图的定义:一个图是一个三元组〈)(G V ，)(G E ，G ϕ〉，其中)(G V 是一个非空的点
集合，)(G E 是有限的边集合，G ϕ是从边集合E 到点集合V 中的有序偶或无序偶的
映射。
例3 图G =〈)(G V ，)(G E ，G ϕ〉，其中)(G V =},,,{d c b a ，)(G E =},,,,,{654321e e e e e e ，
),()(1b a e G =ϕ，),()(2c a e G =ϕ，),()(3d b e G =ϕ，),()(4c b e G =ϕ，),()(5c d e G =ϕ，),()(6d a e G =ϕ。
图1.2
由于在不引起混乱的情况下，图的边可以用有序偶或无序偶直接表示。因此，图也
可以简单的表示为：
,
G V E
=
,其中，V是非空点集，E是连接点的边集。
若边i e与点无序偶
)
,
(
k
j
v
v
相关联，则称该边为无向边（Undirected Edge）。若边i e与
点有序偶
>
<
k
j
v
v,
相关联，则称该边为有向边（Directed Edge），其中j
v
称为i e的
起点（Initial Vertex），k v称为i e的终点（Terminal Vertex）。
定义：每一条边都是无向边的图称为无向图（Undirected Graph），每一条边都是有向边的图称为有向图（Directed Graph），本课主要介绍无向图
（无向图的定义）图的定义;一个图（Graph）G定义为一个偶对()
,V E
，记作
()
,
G V E
=
。其中：
1）V是一个集合，其中的元素称为顶点
2）E是无序积V V
⨯中的一个子集合，其元素称为边，
我们分别用
()
V G
和
()
E G
表示的G顶点集合与边的集合。如果
()
V G
和
()
E G
都是
有限集合，则称为G有限图。本书只研究有限图。
以下从边和顶点及其关系对图的有关基本概念加以介绍：
从“点”的角度考虑，
有限图中顶点的个数称作图的阶
没有任何边的图称为空图,记作φ,
只有一个顶点的图叫做平凡图.
在一个图中，不与任何点相邻接的点，称为孤立点（Isolated Vertex）。
关联于同一点的一条边称为自闭途径或环（Loop）。如图1.3中的1e与2e，1e与4e 是邻接边，5
e是环。
一个有p 个顶点和q 条边的图称为(),p q 图,一个(),p q 图,若它的p 个顶点标以不同的名称,则称为标定的,否则称为非标定的..
图1-3
二分划：图G 顶点集合()V G 分成两个不相交且并为()V G 的两个子集1V 和2V ,记为()12,V V
二部图：若G 有二分划()12,V V ，且G 的每一条边的一个端点在1V 中，另一个端点
在2V 中，则称G 为二部图，记作()12,;G V V E =。
完全二部图：若()12,;G V V E =，12,,V m V n ==且1V 中每一个点与和2V 中每一个点
都邻接，则称G 为完全二部图，记作：,m n K
完全图:任意两个点间都有边相连的简单图称为完全图（Complete Graph ）。n 个点的无向完全图记为n K 。显然n 个点的无向完全图n K 的边数为2
n C 。图1-4分别给出了1个点、2个点、3个点、4个点和5个点的无向完全图。
15K K -的图示
图1-4
