离散数学(软件)课程第14章

第十四章 图的基本概念

14.1 图

?无向图与有向图

?握手定理

?几个特殊的图

?顶点和边的关联与相邻

?图的度数列 ?图的同构

?邻域和关联集 ?简单图与多重图 ?顶点的度数

?完全图与正则图 ?子图 ?补图

1

1、无向图与有向图

多重集合：元素可以重复出现的集合。

无序积：A?B={(x,y) | x?A?y?B} 。 无向图 G =, 其中

(1) V??为顶点集，元素称为顶点. (2) E为V?V的多重子集，其元素 称为无向边，简称边.

例 如图，V={v1, v2, …,v5},

E={(v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5)}

2

有向图 D=, 其中

(1) V同无向图的顶点集, 元素也称为顶点. (2) E是笛卡尔积V?V的多重子集， 其元素称为有向边，简称边.

如右图，试写出它的V和E。

注意：图的数学定义与图形表示，在同构的意义下是一一对应的。

3

一般地，用小圆圈（或实心点）表示顶点，用顶点间的连线表示无向边，用有方向的连线表示有向边。如

u(u, v)vu(起点)v(终点)例1 设D=，V={a, b, c, d, e}，E={, , , , , , }，画图。

4

2、几个特殊的图

? 通常用G表示无向图,

D表示有向图, 也常用G泛指

无向图和有向图, 用ek表示无向边或有向边.

? V(G), E(G) —表示图G的顶点集, 边集.

? |V(G)|, |E(G)| —表示图G的顶点数集（阶）和边数.

n 阶图：n个顶点的图

有限图：V, E都是有穷集合的图

零图：E=? 平凡图：1 阶零图 空图：V=? 基图：用无向边代替D的所有有向边所得到的无向图称作D的基图。

5