重点:1、有向图,无向图的定义,
2、图中顶点,边,关联与相邻,顶点度数等基本概念,
3、各顶点度数与边数的关系
及推论,
4、简单图,完全图,子图,补图的概念,
5、图的同构的定义。
图的基本概念
1、定义。
无序积
。
在无序积中,
。
无向图
,其中
为顶点(结点)集,
为边集,
,
中元素为无向边,简称边。
有向图
,其中
为顶点(结点)集,
为边集,
,
中元素为有向边,简称边。
有时,
泛指有向图或无向图。
2、图的表示法。
有向图,无向图的顶点都用小圆圈表示。
无向边
——连接顶点
的线段。
有向边
——以
为始点,以
为终点的有向线段。
例1、(1) 无向图
,
,
(2) 有向图
,
,
图形表示如下:
注:常用字母
表示边,如(1)中用
表示
,
表示
,…,(2)中也可用
表示有向边
,…。
3、相关概念。
(1)有限图——
都是有限集的图。
阶图——
的图。
零图——
的图。特别,若又有
,称平凡图。
(2)关联 (边与点关系)——设边
(或
),则称
与
(或
)关联。
无环
孤立点——无边关联的点。
环——一条边关联的两个顶点重合,称此边为环 (即两顶点重合的边)。
悬挂点——只有一条边与其关联的点,所对应的边叫悬挂边。
(3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。
多重图——含有平行边的图。
简单图——不含平行边和环的图。
如例1的(1)中,
与
关联的次数均为
,
与
关联的次数为
,边
都是相邻的,
为孤立点,
为悬挂点,
为悬挂边,
为环,
为平行边,重数
,
为多重图。
4、完全图
设
为
阶无向简单图,若
中每个顶点都与其余
个顶点相邻,则称
为
阶无向完全图,记作
。
若有向图
的任一对顶点
,既有有向边
,又有有向边
,则称
为有向完全图。
例如:
1、顶点的度数 (简称度)。
无向图
,
的度数记
,指与
相关联的边的条数。
有向图
,
的度数
,其中
称出度,指以
为始点的边的条数,
称入度,指以
为终点的边的条数。
最大度
最小度
对有向图相应地还有最大出,入度,最小出,入度,分别记为
,
,
,
。
如例1的(2)中,
,
设
为图
的顶点集,称
为
的度数序列。
2、握手定理。
定理1:设图
为无向图或有向图,
,
(
为边数),则
。
推论:任何图中,度为奇数的顶点个数为偶数。
定理2:设
为有向图,
,
,则
。
例2、(1)
,
能成为图的度数序列吗?为什么?
(2) 已知图
中有
条边,
个
度顶点,其余顶点的度数均小于
,问
中至少有多少个顶点?为什么?
解:(1) 由于两个序列中,奇数的个数均为奇数,由握手定理的推论知,不能构成图的度数序列。
(2) 因
,由握手定理知,
中各顶点度数之和为
,
个
度顶点占去
度,还剩
度,其余顶点的度可能为
,若全为
度顶点,则还需
个顶点,所以
至少有
个顶点。
1、子图定义:设
,
是两个图,若
,且
,则称
是
的子图,
是
的母图,记作
。
真子图——
且
(即
或
)。
生成子图——
且
。
导出子图——非空
,以
为顶点集,以两端均在
中的边的全体为边集的
的子图,称
的导出子图。
——非空
,以
为边集,以
中边关联的顶点的全体为顶点集的
的子图,称
的导出子图。
例3、
上图中,(1)-(6)都是(1)的子图,其中(2)-(6)为真子图,(1)-(5)为生成子图。
2、补图定义。
设
为无向完全图,
,
为无向简单图,其中
,
,则称
,
相对于
互为补图,记
,
。
如例3中,(1)为完全图
,(2),(3)互为补图,(4),(5)互为补图。
定义:设两个无向图
,
,若存在双射函数
,使得对于任意的
,当且仅当
,并且
与
重数相同,则称
与
同构,记作
。
例4、判断以下哪些图是同构。
上图中,
,
,
,
其中
,顶点间
,
,
,
,
。
,顶点间
,
,
,
,
,
。
但是(5),(6)不同构,因在(6)中存在
个彼此不相邻的顶点,而在(5)中找不到。
例5、(1) 画出
个顶点,
条边的所有非同构的无向简单图。
解:只有如下
个图:
(2) 画出
个顶点,
条边的所有非同构的有向简单图。
解:只有如下
个图: