例7 画一维恩图用V表示,在英文字母中集合用元音字母.
解决方案:我们绘制一个矩形来表示通用集U, 这是组26个英文字母. 在这个矩形我们画一个圆代表V. 在这个圈子, 我们指示V点元素(见图1).
图1维恩图元音集合.
子集
定义3 一个集合A是另一个集合B的子集;当且仅当A的每个元素也是B的元素. 我们使用符号A?B表示B集合的子集A. 当A?B时,有对于?x(x?A→x?B)是正确的. 若A不是B的子集, 我们只需要找到一个元素x?A与x?B . 这样的一个x, 举出一个反例来.我们有这样一个有用的规则可以决定是否有一个集合是另一个集合的子集.
例8 集合的正整数奇数不到10是正整数小于10的集合的一个子集. 有理数集合是的实数集合的一个子集, 在你学校的所有的计算机科学专业学生集合是在你的学校所有的学生集合的一个子集.
图2 维恩图显示, 集合A是集合B的子集.
定理1证明每个非空集S能保证至少有两个子集, 空集和其本身, 即?和S. 定理1 对于任意一个非空集合S, (i)??S 和 (ii)S?S.
现在有A= {?,{a},{ b },{ a, b } }和b = { x | x是集合{ a, b } 的子集}. 请注意, 这两个集合相等, 即A= B. 还要注意, {a}?A但a?A. 幂集合
一些问题当考虑一些集合元素有一些特定的性质时候, 就可以知道得到一个含有
3
它的子集的集合.
定义6 给定一个集合S, S的幂集是S的子集的集合S所组成的集合. 用P(S).
例14 什么是集合{ 0, 1, 2 } 的幂集?
解 幂集P({ 0, 1, 2 })是集{ 0, 1, 2}的子集的元素集合组成的. 因此, P({ 0, 1, 2 })= {?,{ 0 },{ 1 },{ 2 },{ 0,1 },{ 0,2 }、{ 1,2 },{ 0、1、2 } }. 注意, 空集和集合本身是这个集合子集的成员.
例15 什么是空集的幂集吗?什么是集合{?}幂集 ?
解 空集是空集的子集,即空集的子集是其本身. 因此,P(?)= {?}. 集合{?}正好有两个子集, 即?和集合{?}, 也就是它本身. 因此, P({?})= {?, {?} }. 如果有n个元素组成的集合, 那么它的幂集有2n个元素. 在后续部分的文章当中,将从好几个方面展示这个事实.
10 图
10.1 图和图形
我们首先定义一个图.
定义1 设V和E是两个有限非空集合, V中的元素叫做节点（或顶点）, E中的元素叫做边, 且E中的每一条边恰好与V中的两个节点相对应, 就称G = (V, E)是一个图. 边是连接着它的顶点的.
注意: 顶点集合V在图G上可能是无限的. 一个图有无限的顶点的或无限数量的边, 这样的图被称为无限图. 相比之下, 一个图的顶点集与有限边的集合构成的图称为有限图. 在这本书中我们一般研究有限图.
定义2 有向图(V, E)由一个非空的顶点集合V和一组定向边(或弧)集合E, 每个有向边都关联一个有序对顶点. 有向边关联有序端点(u, v), 也就是说当描述一个有向图和无向图时, 一般使用一个箭头从u →v指示方向表示有向图, 从u开始到v的结束. 一个有向图可能包含多重边, 也它可能包含多个定向边. 也就是说, 当一个有向图包含一个边, 它还可能包含一个或多个边. 这里可以获得一个有向图.
一般只要给一个无向图指定一个方向就可以成为一个有向图.
如果一个图没有自环, 并且每两个顶点之间最多只有一条边, 这样的图称为简单图.,我们称(u, v)为边.
10.2 图的术语和特殊类型的图
介绍 基本术语
首先, 我们给一些术语, 描述顶点和边的无向图.
定义1 在无向图中, 若边e与节点(a, b)对应, 则称e与节点a关联, 同样, e与b关联.
4
若节点a和b之间有边连接, 则称节点a与b相邻, 否则不相邻. 若两条边关联一个共同的节点, 则称这两个边相邻, 否则, 若两条边不同时与任何一个节点关联, 则称这两个边不相邻.
定义3 一个无向图的一个顶点的度,一般一个重边在一个顶点的度的贡献两次, 这里v顶点的度用deg(v)表示.
例1 在G和H图中各个顶点的度是多少？
解 在G图中, deg(a)= 2, deg(b)=deg(c)=deg(f)= 4, deg(d)= 1, deg(e)= 3, deg(g)= 0. 在H图中, deg(a)= 4, deg(b)=deg(e)= 6, deg(c)= 1, deg(d)= 5.
图1
一个顶点的度为零称为孤立点. 由此可见, 一个孤立的顶点是不相邻于任何顶点. 图G中的顶点g在图1中就是孤立的. 若顶点是悬挂点, 当且仅当它有一个度. 因此,一个悬挂点只有一条边与它关联. 图H的顶点c在图1中就是悬挂点. 在检查顶点的度的时候, 一个模型图可以很直观地提供有用的信息.
定理1 现有G =(V,E)是一个无向图与m条边. 然后可以得到
2m??v?V?v?deg.
(注意,即使多个重边这里也存在这样的关系. )
例3 在一个有十个顶点, 每个顶点的度为6的图中有多少边呢?
解 因为6个顶点的度之和是6 * 10 = 60, 而2 m = 60, m是边数. 因此, m = 30.
有这个例题和定理1, 可以给出定理2。 定理2 一个无向图有偶数个奇节点.
定义4 在图G上的(u, v)是边连接的两个顶点, 就说u与v相邻, v和u是相邻的两个顶点. u被称为初始顶点, v称为终端或结束顶点.
定义5 在图G中, 定向边的一个v顶点的入度, 用deg-(v)表示, v作为他们的终端顶点. 这个顶点的出度, 用deg+(v)表示, v作为他们的初始顶点. (请注意, 一个重边在顶点处贡献1到2个入度或出度).
5
例4 在图G中找定向边到每个顶点的入度和出度. 如图2所示:
图2
解 在有向图G上, deg-(a)= 2, deg-(b)= 2, deg-(c)=3, deg-(d)= 2, deg-(e)= 3, deg-(f)= 0. deg+(a)= 4, deg+(b)= 1, deg+(c)= 2, deg+(d)= 2, deg+(e)= 3, deg+(f)= 0.因为在图上每个边有一个始点和一个终点. 度的总和所有顶点的出度与入度都是相同的.由此定理3得到.
定理3: 图G =(V,E)；然后
???deg(v)?deg(v)?E?v?Vv?V
现在, 即将介绍几类简单的图. 这些图用作例子通常出现在许多应用程序当中.
例5 一个完全图有n顶点, 用Kn表示, 是一个简单的完全图. 其中n = 1, 2, 3, 4, 5, 6. 如图3全都是完全图. 而一个简单的图, 有至少一条截然不同的顶点有未连接的边的图叫做非完全图.
图3
例6 循环一个周期cn, n≥3, 由n顶点v1, v2,……, 这个周期C3, C4, C5, C6显示在如图4:
6
