返 回 下一页

一、图的概念


二、顶点的度数,握手定理


三、子图,补图


四、图的同构

重点: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) 画出 个顶点, 条边的所有非同构的有向简单图。

  解:只有如下 个图:

  

返 回 下一页