1 《计算机数学基础》离散数学辅导(5) 第5章图的基本概念(2001级用

1

《计算机数学基础》离散数学辅导(5)

??第5章图的基本概念(2001级用) 中央电大 冯 泰

本章重点：图的概念，握手定理，通路、回路以及图的矩阵表示.

一、重点内容

1. 图的基本概念 ?图是一个有序对，V是结点集，E是边集，当?V?,?E?有限时，称为有限图；否则称无限图.

?无向边, 与无序结点(v,u)相关联的边；有向边，与有序结点相关联的边.

?无向图，每条边都是无向边的图，记作G＝; 每条边都是有向边的图，记作D＝.

?混合图，既有有向边，也有无向边的图.

?平凡图，仅有一个结点的图；零图，边集为空集的图，即仅有结点的图. ?自回路(环)，关联于同一个结点的边.

?无向平行边，联结相同两个结点的多于1条的无向边；有向平行边，联结两个结点之间的多于1条且方向相同的有向边.

?简单图，不含平行边和自回路的图；多重图，含平行边的图.

?在无向图G＝中，与结点v(?V)关联的边数，即为结点度数deg(v)或d(v).；在

＋

有向图D＝中，以v(?V)为起点的边之条数为出度deg(v)；以v(?V)为终点的边之条

－

数为入度deg(v). 结点v的出度和入度之和为度数. 图G所有结点的度数组成的数组(deg(v1)，deg(v2)，…，deg(vn)，…)(有限个或可列个)，称为图G的度数序列.

?最大度数，?(G)＝max{d(v)?v?V}；最小度数，?(G)=min{d(v)?v?V}

?有n个结点的且每对结点都有边相连无向简单图，无向完全图Kn. 此时有

1n(n?1)；有n个结点的且每对结点之间都有两条方向相反的边相关连的有向简单图2为有向完全图，.此时有E?n(n?1) E??设G＝, V，E的子集V?,E?构成的图G?=是图G的子图；若G??G且G??G，(V??V或E??E)，G?是G的真子图.

?生成子图，设图G＝, 若E??E, 则图<.V,E?>是的生成子图. 即结点与原图G相同的子图，为生成子图.

?补图?G=，设G＝, 以V为结点集，以使G成为完全图所添加的边为边集E?的图，就是图G的补图G?,.，即是完全图, 其中E?E?＝?. ?图的同构，设G1=和G2=, 存在双射f：V1?V2，?(vi,vj)?E1, 当且仅当 (f(vi),f(vj))?E2，且(vi,vj)与 (f(vi),f(vj))的重数相同. 则G1≌G2.

同构充分条件：建立两个图的对应关系，这个关系是双射函数.

同构必要条件：①结点数相同；②边数相同；③度数相同的结点个数相同. ?握手定理 设G=，有

?deg(v)?2E,

v?V 2

?在图D＝中，

?v?Vdeg?(v)??v?Vdeg?(v)，

?degv?V?(v)??deg?(v)＝2?E?.

v?V握手定理推论：奇数度结点的个数为偶数个. 2 通路、回路、图的连通性

?通路与通路的长度，设图G＝，V＝{v0,v1,…,vn},E={e1,e2,…,em},结点与边的交替序列v0e1v1e2…vi－1eivi,为结点v0到结点vi的通路. v0,vi是通路的起点和终点. 通路中边的数目就是通路的长度.

?回路，起点和终点重合的通路.

?边不重复的通路(回路)称简单通路(回路)；结点不重复的通路(回路)，称初级通路(回路)；边有重复的通路(回路)，称复杂通路(回路).

?连通与连通图，无向图G中，结点u,v存在通路，则u,v是连通的，G中任意结点u,v都是连通的，G是连通图.

?连通分支P(G)，设G＝，V的连通等价类V1，V2，…,Vm,子图G(V1),G(V2),…,G(Vm)称为连通分支.

?点割集与割点，设无向图G＝，存在结点集V??V，使得P(G－V?)>P(G)，而任意V??V?，有P（G－V?）＝P(G)，V?称为图G的点割集. 若V?是单元集{v}，v叫做割点.

?边割集与割边，设无向图G＝，存在边集E??E，使得P(G－V?)>P(G)，而任意E??E?，有P（G－E?）＝P(G)，E?称为图G的边割集. 若E?是单元集{e}，e叫做割边(桥).

注意：点割集和边割集的两个条件.

?有向图的连通，有向图中，任意一对结点之间至少有一个结点可达另一结点是单侧连通；任何一对结点都相互可达是强连通；略去有向图D边的方向成为无向连通图是弱连通.

???单侧连通?必是???弱连通. 由定义可知：强连通?必是3. 图的矩阵表示

? (无向图)关联矩阵 设G=, V?n,E?m，关联矩阵 M(G)=mij①

??n?m,其中mij=vi与ej的关联次数(行为结点，列为边). 具有性质：

mm?mi?1nmmij?2(列元素之和为2)；② ?mij?deg(vi),若?mij?0,表明vi是孤立点;

j?1j?1③??mij?2m,即所有元素之和等于边数的2倍;④平行边的列的元素完全对应相同.

i?1j?1? (无向图)相邻矩阵 设G＝, V?n,E?m，相邻矩阵 A(G)=aijnij

i

j

??，其中a=v与v相关联的边的条数(行、列均为结点).具有性质:

mnj?1i?1 ① A(G)是对称矩阵；② ?aij(??aij)?deg(vi)；若?aj?1mij?0，表明vi是孤立点;

? (有向图)关联矩阵 设D＝, V?n,E?m，关联矩阵 M(D)=mij???1?，其中m??n?m?0ij????1vi为始点,vj为终点vi与vj不关联vi为终点，vj为始点(结点为行，边为列). 具有性质：

n3

m ①

?mi?1nmi?1j?1ij?0(列元素之和为 0〕； ② ?mij?deg(vi);

j?1nmi?1j?1 ③ ??(mij?1)????(mij??1)?m

? (有向图)邻接矩阵 设D=, V?n,E?m，邻接矩阵 A(D)=aijnij

i

j

nm??,其中a=邻接v与v的边的条数 (与A(G)类似)( 以行和列均为结点)

i?1j?1具有性质：??aij?m

? (有向图)可达矩阵 设D=，V?n,E?m，可达矩阵 P(D)=pij??，其中pnij?1???0vi可达vj 否则 P(D)?Bn?1(D)?E?A(D)?A2(D)?..?An?1(D)?E，E是单位矩阵. 二、实例

例5.1 设G＝(V,E)是一个无向图，V?{v1,v2,...,v8},

E?{(v1,v2),(v2,v3),(v3,v1),(v1,v5),(v5,v4),(v3,v4),(v7,v8)}

(1) G＝的?V?，?E?各是多少？ (2) 画出G的图解； (3) 指出与v3邻接的结点，以及与v3关联的边； (4) 指出与e1关联的结点； (5) 该图是否有孤立结点和孤立边？ (6) 求出各结点的度数； 解(1) G=中，有?V?=8个结点，?E?=7条边的图，故又称是8阶图. (2) 所给图G的一个图解，如图5－1. (3) 结点v1, v2, v4与v3邻接，v3关联 ? v2 的边为e1, e2, e3. e4 e1

(4)与边e1关联的结点为v2, v3. v1 ? e2 ? v3 ? v7 (5) 结点v6是孤立点；e5是孤立边. e7

(6) deg(v1)=3，deg(v2)=2，deg(v3)=3， ? v6 e5 deg(v4)=2＝deg(v5)，deg(v6)=0， e

deg(v7)=1=deg(v8).

3

例5.2 设图G是具有3个结点的完全图，试问

(1) G有多少个子图？ (2) G有多少个生成子图？

(3) 如果没有任何两个子图是同构的，则G的子图个数是多少？将它们构造出来.

3?解 (1) 因为只有1个结点的子图有????3个(平凡子图)；

?1??? v5 ? e6 ? v4 ? v8 图5－1

3?83?2个结点的子图有?个； 3个结点的子图有?个； ????2?6?3???2?8?2?????所以，G共有3＋6＋8＝17个子图.

(2) G的生成子图，含有G的所有结点，G有3条边，构成子图时，每条边有选中或不选中两种可能，所以G的生成子图的个数是23＝8个.