《图论(数学图解生活).doc》由会员分享，可在线阅读，更多相关《图论(数学图解生活).doc（36页珍藏版）》请在金锄头文库上搜索。
1、图论讲义第一课时第二课时集合的概念一定范围的，确定的，可以区别的事物，当作一个整体来看待，就叫做集合，简称集，其中各事物叫做集合的元素或简称元。元素与集合的关系：元素与集合的关系有“属于”与“不属于”两种。集合通常表示为大写字母 A， B， C。而元素通常表示为小写字母a,b,c。元素a属于集合A,记作aA。假如元素a不属于A，则记作aA。如果两个集合 A 和 B 它们各自所包含的元素完全一样，则二者相等，写作 A = B。集合的特点 无序性 在同一个集合里面的每一个元素的地位都是相同的，所以元素的排列是没有顺序的。 互异性 在同一个集合里面每一个元素只能出现一次，不能重复出现。 确定性 定制
2、集合的标准是确定的而不是含糊的，如全国全体较高的男生，这里的较高没有标准是含糊的。 集合的表示集合的表示方法：常用的有列举法和描述法。 1.列举法常用于表示有限集合，把集合中的所有元素一一列举出来写在大括号内这种表示集合的方法叫做列举法。1，2，3，2.描述法常用于表示无限集合，把集合中元素的公共属性用文字符号或式子等描述出来写在大括号内这种表示集合的方法叫做描述法。x|P（x为该集合的元素的一般形式，P为这个集合的元素的共同属性）如：小于的正实数组成的集合表示为：x|0x3.图式法（Venn图）为了形象表示集合，我们常常画一条封闭的曲线（或者说圆圈），用它的内部表示一个集合。尽管两个集合有不
3、同的表示，它们仍可能是相同的。比如：上述集合中，A = C 而 B = D，因为它们正好有相同的元素。元素列出的顺序不同，或者元素列表中有重复，都没有关系。比如：这三个集合 2, 4，4, 2 和 2, 2, 4, 2 是相同的，同样因为它们有相同的元素。集合的元素个数上述每一个集合都有确定的元素个数；比如：集合 A 有三个元素，而集合 B 有四个。一个集合中元素的数目称为该集合的基数。集合可以没有元素。这样的集合叫做空集，用符号 表示。比如：在2004年，集合 A 是所有住在月球上的人，它没有元素，则 A = 。就像数字零，看上去微不足道，而在数学上，空集非常重要。更多信息请看空集。如果集合
4、含有有限个元素，那么这个集合可以称为有限集。集合也可以有无穷多个元素。比如：自然数的集合是无穷大的。常用数集的符号：（1）全体非负整数的集合通常简称非负整数集（或自然数集），记作N（2）非负整数集内排除0的集，也称正整数集，记作N+（或N*）（3）全体整数的集合通常称作整数集，记作Z（4）全体有理数的集合通常简称有理数集，记作Q（5）全体实数的集合通常简称实数集，记作R子集如果集合 A 的所有元素同时都是集合 B 的元素，则 A 称作是 B 的子集，写作 A B。 若 A 是 B 的子集，且 A 不等于 B，则 A 称作是 B 的真子集，写作 AB。B 的子集 A举例： 所有男人的集合是所有人
5、的集合的真子集。 所有自然数的集合是所有整数的集合的真子集。 1, 31, 2, 3, 4 1, 2, 3, 41, 2, 3, 4 空集是所有集合的子集，而所有集合都是其本身的子集： A A A 并集有多种方法通过现有集合来构造新的集合。两个集合可以相加。A 和 B 的并集（联集），写作 AB，是或属于 A 的、或属于 B 的所有元素组成的集合。A 和 B 的并集举例： 1, 2红色, 白色 = 1, 2, 红色, 白色 1, 2, 绿色红色, 白色, 绿色 = 1, 2, 红色, 白色, 绿色 1, 21, 2 = 1, 2 并集的一些基本性质 AB=BA AAB AA=A A=A 交集一
6、个新的集合也可以通过两个集合共有的元素来构造。A 和 B 的交集，写作 AB，是既属于 A 的、又属于 B 的所有元素组成的集合。若 AB=，则 A 和 B 称作不相交。A 和 B 的交集举例： 1, 2红色, 白色 = 1, 2, 绿色红色, 白色, 绿色 = 绿色 1, 21, 2 = 1, 2 交集的一些基本性质 AB=BA ABA AA=A A= 补集两个集合也可以相减。A 在 B 中的相对补集，写作 BA，是属于 B 的、但不属于 A 的所有元素组成的集合。在特定情况下，所讨论的所有集合是一个给定的全集 U 的子集。这样， UA 称作 A 的绝对补集，或简称补集（余集），写作 A或C
7、UA。相对补集 A - B补集可以看作两个集合相减，有时也称作差集。举例： 1, 2红色, 白色 = 1, 2 1, 2, 绿色红色, 白色, 绿色 = 1, 2 1, 21, 2 = 若 U 是整数集，则奇数的补集是偶数 补集的基本性质： AA = U AA = (A) = A AB = AB 集合的运算：集合交换律AB=BAAB=BA集合结合律(AB)C=A(BC)(AB)C=A(BC)集合分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)集合德.摩根律Cu(AB)=CuACuBCu(AB)=CuACuB集合“容斥原理”在研究集合时，会遇到有关集合中的元素个数问题，我们把有限集
8、合A的元素个数记为card(A)。例如A=a,b,c，则card(A)=3card(AB)=card(A)+card(B)-card(AB)card(ABC)=card(A)+card(B)+card(C)-card(AB)-card(BC)-card(CA)+card(ABC)第三课时第九课时 图的基本概念定义 设V 是一个非空集合，E是V 上的(多重)二元关系，则称有序对(V, E)为有向图，记为G。 V 的元素称为G的顶点，V 称为G 的顶点集，V 的基数|V|称为G的顶点数，记为V(G )； E 的元素称为G的弧，E 称为G的弧集，E的基数|E|称为G的弧数，记为E(G)。 若弧 e
9、=(u, v)，则称 u为 e的起点，v为 e的终点， 若弧 e 的起点与终点相同，则称 e 为环。环 e =(u, u)弧 e =(u, v)ueuveueuve边 e =u, v环 e =u, u 若E是V 中元素 u, v 的无序对u, v的(多重)集合，则G 称为无向图，E的元素称为G的边，E称为G的边集。 在不会引起混淆的情形下, 无向图与有向图都可简称为图。无向图也可看成是由弧集 E是V 上对称的二元关系的有向图, 把二顶点u, v间的对称弧(u, v)与(v, u)变为一条边而形成的。4 .123有向图 1234.5多重有向图 .12345无向图.12345多重无向图.12345
10、对称有向图定义 设 e = (u, v) 是有向图G = (V, E) 的弧，则称顶点 u与 v 邻接，称顶点 u, v 与弧 e关联。 若G的顶点 v与任意弧都不关联，则称v为G的孤立点。 若G的两条弧 e1 和 e2都与顶点v关联，则称e1与e2邻接。顶点 u与 v 邻接即u和 v 由一条弧相连；两条弧 e1 和 e2邻接即e1与e2有公共的顶点。通常在讨论集合时，规定集合中的元素是各不相同的，否则该集合就称为多重集。同样，在讨论图时，把两对顶点相同的一对弧称为重弧。规定无环也无重弧的图为简单图，而有环或有重弧的图为多重图。今后，如果没有特别说明，讨论的都是简单图。定义 设G1=(V1,
11、E1)，G2=(V2, E2)为两个图，若顶点集V1=V2且弧集E1=E2，则称两个图G1与G2相等，记为G1=G2。定义 设G = (V, E)， G1=(V1, E1)为两个图，若V1V，E1 E，则称图G1为图G的子图，记为G1 G。 为了方便，以下概念都针对无向图给出，而有向图的概念可以类似地得到。 若G1是由图G的全部顶点及一部分边组成的图，即V1=V, E1 E，则称G1为G的生成子图。若G1是由图G的部分顶点(V1V )及二个端点都在V1中的边组成的图，则称G1为G的由顶点集V1导出的子图，简称为G的点导出子图，记为G(V1).若G1是由图G的部分边(E1 E)及所有与E1中的边
12、关联的顶点组成的图，则称G1为G的由边集E1导出的子图，简称为G的边导出子图，记为G(E1).例 如图所示，其中(d)是由顶点1, 3, 4, 5导出的子图，(e)是由弧(1,5), (2,5), (4,5) 导出的子图。21354(b) G的子图43512(c) G的生成子图345(a) 图G211354(d) G的点导出成子图4512(e) G的弧导出子图定义 设G = (V, E)为一个图，则 顶点v 关联的边数称为顶点v 的度数记为d(v)。 度数为零的点是孤立点。 度数是奇(偶)数的顶点称为奇(偶)度点。 G中顶点度数的最小(大)值称为G的最小(大)度，记为d(G ) (D(G )。
13、 对于有向图G，顶点v的度数d(v)分为两部分： 以v为起点(终点)的弧数称为顶点v的出度(入度) 记为d+(v) ( d-(v) )，并且d(v) = d+(v) + d-(v)。在多重图中讨论顶点v度数时，若与v关联的边中有环，则每个环按两条边计算。只有孤立顶点的图称为零图，也称为平凡图。一个零图的边集是空集。定理 设图G = (V, E)，则Sd(v) = 2E(G) 。 即图的各个顶点的度数之和为该图边数的两倍。注意到每条边都与两个顶点关联，而增加一条边就会使顶点度数的和也增加2。把度数是奇数的顶点称为奇度点，度数是偶数的顶点称为偶度点。 推论 任何图 G 中必有偶数个奇度点。 由图G中顶点的总度数是偶数，故奇度点的个数必为偶数。定理 设G=(V, E)为有向图, 则Sd+(v) =Sd-(v) 即有向图各个顶点的出度之和与入度之和
