文档介绍：第十四章图的基本概念
第四部分图论
图
设A,B为任意的两个集合,称{{a,b}|a∈A∧b∈B}为A与B的无序积,记作A&B 。
为方便起见,将无序积中的无序对{a,b}记为(a,b),并且允许a=b 。需要指出的是,无论a,b是否相等,均有(a,b)
=(b,a),因而A&B=B&A 。
元素可以重复出现的集合称为多重集合或者多重集,某元素重复出现的次数称为该元素的重复度。例如,在多重集合{a,a,b,b,b,c,d}中,a,b,c,d的重复度分别为2,3,1,1 。
一个无向图是一个有序的二元组<V,E>,记作G,其中
(1)V≠称为顶点集,其元素称为顶点或结点。
(2)E称为边集,它是无序积V&V的多重子集,其元素称为无向边,简称边。
一个有向图是一个有序的二元组<V,E>,记作D,其中
(1)V同无向图。
(2)E为边集,它是笛卡儿积V×V的多重子集,其元素称为有向边,简称边。
上面给出了无向图和有向图的集合定义,但人们总是用图形来表示它们,即用小圆圈(或实心点)表示顶点,用顶点之间的连线表示无向边,用有方向的连线表示有向边。
给定无向图G=<V,E>,其中,
V={v1,v2,v3,v4,v5},
E={(v1,v1),(v1,v2),(v2,v3),
(v2,v3),(v2,v5),(v1,v5),(v4,v5)}.
(2) 给定有向图D=<V,E>,其中,
V={a,b,c,d},
E={<a,a>,<a,b>,<a,b>,<a,d>,<c,d>,
<d,c>,<c,b>}.
画出G与D的图形。
解: (1),(2)分别给出了无向图G和有向图D的图形。
。
在图的定义中,用G表示无向图,D表示有向图,但有时用G泛指图(无向的或有向的),可是D只能表示有向图。另外为方便起见,有时用V(G),E(G)分别表示G的顶点集和边集,若|V(G)|=n,则称G为n阶图,对有向图可做类似规定。
若|V(G)|与|E(G)|均为有限数,则称G为有限图,本课件中只讨论有限图。
在图G中,若边集E(G)=,则称G为零图,此时,又若 G为n阶图,则称G为n阶零图,记作Nn,特别地,称N1为平凡图。
在图的定义中规定顶点集V为非空集,但在图的运算中可能产生顶点集为空集的运算结果,为此规定定点集为空集的图为空图,并将空图记为。