习题一
1. 一个工厂为一结点；若两个工厂之间有业务联系，则此两点之间用边相联；这样就得到一个无向图。若每点的度数为3，则总度数为27，与图的总度数总是偶数的性质矛盾。若仅有四个点的度数为偶数，则其余五个点度数均为奇数，从而总度数为奇数，仍与图的总度数总是偶数的性质矛盾。（或者利用度数为奇数的点的个数必须为偶数个）
2.
若存在孤立点，则m 不超过K n-1的边数, 故
m <= (n-1)(n-2)/2, 与题设矛盾。
3.
4. 用向量(a 1,a 2,a 3)表示三个量杯中水的量, 其中a i 为第i 杯中水的量, i = 1,2,3.
以满足a 1+a 2+a 3 = 8 (a 1,a 2,a 3为非负整数)的所有向量作为各结点, 如果(a 1,a 2,a 3)中某杯的水倒满另一杯得到 ( a ’1, a ’2, a ’3 ) , 则由结点到结点画一条有向边。这样可得一个有向图。
本题即为在此图中找一条由( 8, 0, 0 )到( 4, 4, 0 )的一条有向路，以下即是这样的一条：
5. 可以。
6 若9个人中没有4个人相互认识，构造图G ，每个点代表一个点，两个人相互认识则对应的两个点之间有边。
1） 若可以找到点v ，d(v)>5，则与v 相连的6个点中，要么有3个相互认识，要么有3个
相互不认识（作K 6并给边涂色:红=认识，蓝=不认识，只要证图中必有同色三角形。v 1有5条边，由抽屉原则必有三边同色(设为红)，这三边的另一顶点设为v 2, v 3, v 4。若 △v 2v 3v 4有一边为红，则与v 1构成红色△，若△v 2v 3v 4的三边无红色，则构成蓝色△）。若有3个人相互认识，则这3个人与v 相互认识，这与假设没有4个人相互认识矛盾，所以这6个人中一定有3个人相互不认识
2） 若可以找到点v ，d(v)<5，不与v 相连的点至少有4个，由于没有4个人相互认识，所
以这4个人中至少有2个人相互不认识，这两个人与v 共3个人相互不认识
∑
∑∑∑∑
∑∑==+====-=++=-==---=--=n
i i n i i n i n i n i n
i i i n i i n i i i i a a n n a a a n n n a n a v v 12 12 1211
2
212 12 i i 2/)1(C )1(2)1(])1[(a a 。
， 所以 因为 ，＋ 的负度数，则为结点的正度数，为结点记－－－－－
( 8, 0, 0 ) ( 5, 3, 0 ) ( 5, 0, 3 ) ( 2, 3, 3 ) ( 2, 5, 1 )
(7, 0, 1 ) ( 7, 1, 0 ) ( 4, 4, 0 )
( 4, 1, 3 )
3） 若每个点的度数都为5，则有奇数个度数为奇数的点，不可能。
7. 同构。同构的双射如下：
8. 记e 1= (v 1,v 2), e 2= ( v 1,v 4), e 3= (v 3,v 1), e 4= (v 2,v 5), e 5= (v 6,v 3), e 6= (v 6,v 4), e 7= (v 5,v 3), e 8= (v 3,v 4), e 9 = (v 6,v 1), 则
邻接矩阵为： 关联矩阵为：
边列表为：A= (1,1,3,2,6,6,5,3,6), B= (2,4,1,5,3,4,3,4,1). 正向表为：A= (1,3,4,6,6,7,10), B= (2,4,5,1,4,3,3,4,1).
?????????
??????
??
???---------100110000
00
1001000010100010011010100000001001100000111
, 001101000100000000001001010000001010????????????????????
习题二
1.用数学归纳法。k=1时，由定理知结论成立。设对于k命题成立。
对于k+1情形，设前k个连通支的结点总个数为n1, 则由归纳假设，前k个连通支的总边数m1<= ( n1－k+1)( n1－k)/2。最后一个连通支的结点个数为n－n1, 其边数
m2<= ( n－n1)( n－n1－1)/2，
所以，G的总边数
m= m1+ m2<= ( n1－k+1)( n1－k)/2 + ( n－n1)( n－n1－1)/2
n1=n－1时，m<= ( (n-1)－k+1)( (n-1)－k)/2 +0= ( (n－k)( (n－k－1)/2, 命题成立。
n1＜= n－2时，由于n1<=k, 故
m<= ( (n－2)－k+1)( n1－k)/2 + ( n－n1)( n－k－1)/2＝( n－k)( n－k－1)/2 , 命题成立。
2．若G连通，则命题已成立；否则，G至少有两个连通支。
任取结点v1, v2，若G的补图中边(v1, v2)不存在，则(v1, v2)是G中边，v1, v2在G的同一个连通支（假设为G1）中。设G2是G的另一连通支，取v3∈G2,则v1→ v3→v2是补图中v1到v2的一条道路，即结点v1, v2在补图中有路相通。
由v1, v2的任意性，知补图连通。
3．设L1,L2是连通图G的两条最长路，且L1,L2无公共结点。设L1,L2的长度(边数)为p.
由于G是连通的，故L1上必有一结点v1与L2上一结点v2有道路L’相通。
结点v1将L1分为两部分，其中一部分的长度≥ p/2 , 记此部分道路为L3。同样，结点v2将L2分为两部分，其中一部分L4的长度≥ p/2 。
这样，L3＋L’＋L4就是G的一条新的道路，且其长度大于p, 这与G的最长路(L1)的长度是p的假设矛盾。
4. 对结点数n作归纳法。
（1）n= 4时m≥5. 若有结点的度≤1, 则剩下的三结点的度数之和≥4，不可能。于是每个结点的度≥2，从而存在一个回路。
若此回路为一个三角形，则还有此回路外的一结点，它与此回路中的结点至少有二条边，从而构成一个新的含全部四个结点的回路，原来三角形中的一边（不在新回路中）即是新回路的一条弦。
若此回路为含全部四个结点的初等回路，则至少还有一边不在回路上，此边就是该回路的一条弦。
（2）设n-1情形命题已成立。对于n情形：
若有结点的度≤1, 则去掉此结点及关联边后，依归纳假设命题成立。
若有结点v的度=2, 设v关联的两结点为s,t，则去掉结点v及关联边、将s,t合并为一个结点后，依归纳假设命题成立。
若每个结点的度≥3，由书上例2.1.3的结果知命题成立。
5 a)对于任意边(u,v),由于不存在三角形，所以d(u)+d(v)<=n，对所有m条边求和，不等式左边每个d(v)被计算了d(v)次
b) 对n归纳，设小于n时不等式成立，当|V|=n时，删去边(u,v)及点u，v以及相关的边
得到G'，由归纳假设，G'最多(n-2)2/4条边，由于(u,v)与G'不构成三角形，因此由G'变回G时最多增加(n-2)+1条边，所以G的边最多(n-2)2/4+(n-2)+1=n2/4
注：此题与三角形的存在性无关
设最大度数为k，且d(v)=k，令E0={与v相连的边}，E1={不与v相连的边}，则|E0|=k，|E1|<=(n-k-1)*k，其中n-k-1表示去除了v及其邻点，这些点的度数都小于等于k
m=|E0|+|E1|<=nk-k2<= n2/4
6．问题可化为求下列红线表示的图是否存在一条欧拉道路的问题：存在欧拉道路！
7 设C是H道路，当S中顶点在C上不相邻时，C-S最多被分成|S|+1段，而当S中顶点有相邻时段数将更少，而C是G的生成子图，所以t<=|S|+1
8．由推论2.4.1, 只需验证G的任意一对结点的度数之和大于或等于n即可。
若存在结点v1, v2满足deg(v1)+deg(v2) G－{v1, v2} 的边数<= K n-2的边数= (n-2)(n-3)/2 . 另一方面，由题设知 G－{ v1, v2} 的边数＝m－（deg(v1)+deg(v2)）＞[(n-1)(n-2)/2+2]－n= (n-2)(n-3)/2 , 与上式矛盾。 9 对n进行数学归纳法，设n小于等于k时命题成立，则当n=k+1时 对任意顶点v，G-v得到的G'仍是有向完全图，由归纳假设存在H道路v1v2…v k 若G中存在边(v,v1)或(v k,v)则命题成立 否则G中存在边(v1,v)和(v,v k)，这也意味着可以找到i，1<=i 10 对于任意的点u,v，若u与v认识，则d(u)+d(v)=(n-2)+2=n 若u不认识v，则从V-{u,v}中让取一点w，w认识u和v 否则若w不认识u，则v和w都不认识u，v和w合起来只能最多认识n-3个人，矛盾。 由w的任意性，d(u)+d(v)>=2(n-2)，当n>=4时，2(n-2)>=n 所以对任意两个点度数和大于等于n 11 对于这q条边，每条边的两个端点压缩合并为一个点，并去掉重边得到G' G'各点度数均大于等于n/2，所以存在H回路，该回路中q个新点恢复成原2q个点，则所代表的q条边仍在此H回路中 注：q不能超过n/2 12 构造图G，每个小立方体对应一个点，两个立方体之间有公共面则对应顶点间有边 设最左上角点为黑色，依据相邻点不同色的原则给所有点着色，则黑色点有14个，白色点有13个，若所要求路径存在，则意味着从黑色点开始遍历这27个点到达白色点，这不可能 13．1）将边按权值由小到大排序： 边：a23a35a15a13a34a45a24a12a25a14 权：26 27 29 33 34 35 38 42 49 52 2)分支定界： S1: a23a35a15a13a34 , 非H回路,d (S1)=149; 将a34置换为其后的a45, a24，a12，a25，a14，也全都是非H回路； S2: a23a35a15a34a45, 非H回路,d(S2)=151; 将a45置换为其后的a24，a12，a25，a14，也全都是非H回路； S3: a23a35a15a45a24 , 非H回路,d (S8)=155; 将a24置换为其后的a12，a25，a14，也全都是非H回路； S4: a23a35a15a24a12 , 非H回路,d (S4)=162; S5: a23a35a15a24a25 , 非H回路,d (S5)=169; S6: a23a35a15a24a14 , H回路,d0:=172; S7: a23a35a15a12a25 , 非H回路,d (S7)=173; S8: a23a35a13a34a45 , 非H回路,d (S8)=155; 将a34 , a45置换为其后的数，也全都是非H回路； S9: a23a35a34a45a24 , 非H回路,d (S9)=160; 将a45 , a24置换为其后的数，也全都是非H回路； S10: a23a35a45a24a12 , 非H回路,d (S10)=168; 将a12置换为其后的a25 , a14，也全都是非H回路； S11: a23a35a45a12a25 , 非H回路,d (S11)=179; 将a12 ,a25置换为其后的数，其路长差于d0，故不必考虑； S12: a23a35a24a12a25, 非H回路,d (S12)=182; 将a24，a12，a25,置换为其后的数，其总长差于d0，故不必考虑； 继续下去所得组长度会比S6差，故可终止计算。 所以，H回路为S6, 路长为172。 14. 这是一个旅行商问题(具体计算略)： 15. 这是一个最短路问题(具体计算略)： 16. (0,0) (2,5) (6,6) 7 V 1 V 2 V 3 V 6 V 3 23. V3V2 习题三 1． 因为n 个结点的树的边有n-1条，故其总度数为 2 (n-1)，故度为1的结点个数为 2 (n-1)－2n 2－3n 3－……－kn k . 2. 设L 是树T 的一条最长路，L 中的结点依次为 v 1, v 2 , …, v k 。因为L 中各结点都有边相连，所以它们的度数均大于或等于1。 若deg (v 1)>1, 则除了边(v 1, v 2)外，还存在边(v 1, v’) 。因为树中不存在回路，故v’?{ v 1, v 2 , …, v k }，于是，(v’,v 1, v 2 , …, v k )是T 的一条新的路，其长度比L 更长。这与L 是T 的最长路矛盾。 所以deg (v 1)＝1，类似可证deg (v k )＝1。 4．(a) 直接根据图确定B 5B 5T 可得树的棵数： .1014 20124100 1411013)det(55=--------= T B B (b) 去掉边(v 1, v 5)，则直接根据图确定B 5B 5T 可得不含边(v 1, v 5)的树的棵数： ,754 20124100 1411012)det(55=--------= T B B 于是，含边(v 1, v 5)的树的棵数为：101－75＝26。 (c) 去掉边(v 4, v 5)，则直接根据图确定B 5B 5T 可得不含边(v 1, v 5)的树的棵数： . 60 32 1 241001411013 )det(55=--------= T B B 5. (a) 因为 , ?? ??? ???? ???----------=????????? ???----------=000 1 1 100100010001100010000000100001,11 00110010101100010001110010000000111001 * 11B B (b) 去掉边(v 1, v 5)后，有 , ????? ???? ???---------=? ???????? ???---------=00000100010010001001100010000001000 1,110011000 101100010011100100000011101*11B B (c) 去掉到v 3的其它全部边(v 4, v 3)、(v 5, v 3)后，有 ,0001001011000100000010000010000 1,1011001011000100010010000011100 1*11????? ???????--------=????? ???????--------=B B . . 242 1 1310113110021=-------= )B de t(B T 1*1为根的根树的个数为 因此以v . .810011 31011311002),(1=-------=)B de t(B T 1 *151的根树的个数为 为根且不含边因此以v v v . . 92 1 131000111002),(321=-----= )B de t(B T 1*1的根树的个数为 为根且含边因此以v v v 10. (1) 余树为｛e 1, e 2, e 5, e 8｝, 重排B 5的各列得 . 10 01000010 001 C I C e e e e e e e e , C 3.4.4,, 01-0 0 0001 1-010 11-00B , 1-000 1-010 01-01 0011-B , ) B B ( 01-0 0 0001 1-010 11-00 1- 000 1-010 01-01 0011- e e e e e e e e f12f 7 643851 f12121112117 643851????? ? ??? ?? ?------==????? ???????------=???? ????????---????????????-----=-=? ???? ???????=????????????=????? ???????=-10 1 001011001111 )(10 1 001011001111 10011000 10110100 1000 10100101 0011 21121152基本回路矩阵为由定理则 ＝T T B B B (2) 由定理3.4.8, 基本割集矩阵为 . 10 0100 00100 001 1 1 1 -0011-0101 1-001 I C - I S S e e e e e e e e T f12f11f 7643 851?? ??????????===)()(2 14．(a) 这是一个求最优二叉树的问题。 各字符出现次数为： s t a e c 空格 3 4 5 1 1 4 余树 树T 所以最优二进制编码为： e: 1100 c: 1101 s: 111 t: 00 空格：01 a: 10 此时字符串的二进制编码总长度为43 . (b) 去掉空格，类似(a)计算。 15. 将图中各边进行编号得右图。 取参考支撑树 t 0={ e 1, e 2, e 3, e 5} . (1) 因为S e1(t 0)={ e 1, e 4, e 6 }, S e2(t 0)={ e 2, e 4, e 6 }, S e3(t 0)={ e 3, e 6 }, S e5(t 0)={ e 5, e 6 }, 所以 T e1 ={{ e 4, e 2, e 3, e 5}, {e 6, e 2, e 3, e 5}}={ t 1, t 2}, T e2={{ e 1, e 4, e 3, e 5}, {e 1, e 6, e 3, e 5}}={ t 3, t 4}, T e3 ={{ e 1, e 2, e 6, e 5}}={ t 5}, T e5={{ e 1, e 2, e 3, e 6}}={ t 6}, 从而 T 1＝{ t 1, t 2, t 3, t 4, t 5, t 6} . (2) 因为S e2(t 1)={ e 2, e 1 }, S e3(t 1)={ e 3, e 6 }, S e5(t 1)={ e 5, e 6 }, S e2(t 2)={ e 2, e 1 }, S e3(t 2)={ e 3, e 1, e 4 }, S e5(t 2)={ e 1, e 4, e 5 }, S e3(t 3)={ e 3, e 6 }, S e5(t 3)={ e 6, e 5 }, S e3(t 4)={ e 3, e 2, e 4 }, S e5(t 4)={ e 2, e 4, e 5 }, S e5(t 5)={ e 5, e 3 }, 所以 S e2(t 0) ?S e2(t 1)＝{ e 2} , S e2(t 0) ?S e2(t 2)＝{ e 2} , 从而 T e1 e2＝?； S e3(t 0) ?S e3(t 1)＝{ e 3, e 6 } , S e3(t 0) ?S e3(t 2)＝{ e 3} , 从而 T e1 e3＝{{ e 4, e 2, e 6, e 5}}={ t 7}； S e5(t 0) ?S e5(t 1)＝{ e 5, e 6 } , S e5(t 0) ?S e5(t 2)＝{ e 5 } , 从而 T e1 e5＝{{ e 4, e 2, e 3, e 6}}={ t 8}； S e3(t 0) ?S e3(t 3)＝{ e 3, e 6 } , S e3(t 0) ?S e3(t 4)＝{ e 3 } , 从而 T e2 e3＝{{ e 1, e 4, e 6, e 5}}={ t 9}； S e5(t 0) ?S e5(t 3)＝{ e 5, e 6 } , S e5(t 0) ?S e5(t 4)＝{ e 5 } , 从而 T e2 e5＝{{ e 1, e 4, e 3, e 6}}={ t 10}； S e5(t 0) ?S e5(t 5)＝{ e 5} , 从而 T e3 e5＝?； 于是 T 2={ t 7 , t 8, t 9, t 10} . (3) 可以验证 T e1 e2 e3＝T e1 e3 e5＝T e2 e3 e5＝?, 所以T 3 = ?. 5 e 最后，由以上计算可知，全部生成树为{ t0 , t1, t2, t3, t4, t5, t6, t7 , t8, t9, t10 }. 16. 用Kruskal算法。先将权排序，而后按权由小到大选边8-1条(构成回路时所选边不放入)，可得一棵最小生成树（总权为22）： v6 v 7 3 8 https://www.doczj.com/doc/951239766.html,/blog/static/6742112520081231911205/ R^n至少有两种重要的结构：拓扑结构和代数结构（线性空间结构）。 函数连续性只涉及第一种，而可微性则涉及两种（？拓扑—>微分拓扑，拓扑群—>李群）因为微分Df(x)=A的定义牵涉到线性运算和极限概念：f(x+h)-f(x)-Ah=o(||h||) 可微性的概念可以推广到有拓扑结构和线性代数结构这两种结构的其他空间。 现代微分概念源于非线性问题的局部线性化。 半球面是可以摊成平面区域的 要把地球表面画成地图，就非得把球面“撕破”不可 https://www.doczj.com/doc/951239766.html,/lunwen/2008/200810/266972_5.shtml https://www.doczj.com/doc/951239766.html,/f?kz=113722720 同伦等价(homotopy equivalent)是拓扑学中所关心的另外一种等价关系，它的 要求比同胚更宽松。取一个拓扑空间，对它进行某些特定的连续形变，所得到的空 间与原来的空间是同伦等价的。举个例子：初始空间是一个实心球，我们可以把它 压缩成一张没有体积的圆盘，再搓成一条没有面积的线段，甚至挤成一个连长度都 没有的点，得到的这些空间都跟原来的同伦等价；我们也可以从原来的实心球里“长”出半个圆盘来作为“耳朵”(半圆盘的直径还贴在实心球表面上)，甚至再 “长”出几条线段来作为“触角”(线段的一端在实心球表面上)，所得到的空间还 是跟原来的同伦等价。“终结者2”里面那个给人深刻印象的液体机器人，它在身体 没有撕裂开的情况下的各种形态就是同伦等价的。 研究拓扑的一种方法是把拓扑问题转化为代数问题。最常见的例子是计算一个拓 扑空间各个维数的同调群(homology group)和同伦群(homotopy group)，然后根据这 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G 第四章代数结构（作业） 作业：P86：4、7、9 4、 （1）若a和b是整数，则a+b+ab也是整数，故a*b也是整数，所以运算*是封闭的。（2）任选整数集合中的三个元素x,y和z。则有： (x*y)*z = (x+y+xy)*z = (x+y+xy)+z+(x+y+xy)×z = x+y+z+xy+xz+yz+xyz x*(y*z) = x*(y+z+yz) = x+(y+z+yz)+x×(y+z+yz) = x+y+z+yz+xy+xz+xyz = (x*y)*z 因此，*运算满足结合律。 （3）假设e为（Z,*）的幺元，则有： 任选整数集中的一个元素x，都有 0*x = 0+x+0×x=x且 x*0 = x+0+x×0=x 故0是(Z,*)的幺元。 7、N+上的所有元素都是（N+ ,*）等幂元； （N+ ,*）无幺元； （N+ ,*）的零元为1。 9、（A,*）中的等幂元：a、b、c、d； （A,*）中的幺元：b； （A,*）中的零元：c； a-1 = d，b-1 = b，c-1 不存在，d-1 = a， 作业：P87：12、13、18 12、（A，*）到（N4,⊕4）的同构映射f为： f(a)=0, f(b)=1, f(c)=2, f(d)=3; 或者： f(a)=0, f(b)=3, f(c)=2, f(d)=1; 13、同构映射f为： f(0)=?, f(1)={a}, f(2)={b}, f(3)={a,b}; 或者： f(0)=?, f(1)={b}, f(2)={a}, f(3)={a,b}; 18、任选a ∈N +,b ∈N +, 只需证明f(a+b)=f(a)+f(b) 由f 的定义可知：f(a+b)=2a+2b=f(a)+f(b)，故f 是（N +,+）到(E +,+)的同态映射。 作业：P96：3，P97：7 3、(1)显然，*运算对Z 是封闭的。 (2) (a*b)*c = (3(a+b+2)+ab)*c = 3((3(a+b+2)+ab)+c+2)+(3(a+b+2)+ab)×c = 3(3a+3b+c+ab+8+ac+bc+2c)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc a*(b*c) = a*(3(b+c+2)+bc) = 3(a+(3(b+c+2)+bc)+2)+a(3(b+c+2)+bc) = 3(a+3b+3c+bc+8+ab+ac+2a)+abc = 3(3a+3b+3c+ab+ac+bc+8)+abc = (a*b)*c 故*运算满足结合律。 （3）任选a ∈Z ，(-2)*a=a 且a*(-2)=a ，所以-2是(Z,*)的幺元。 所以（Z,*）是独异点。 7、因为1为(A,*)运算的幺元，而且对任意A 的子集A ’,*在A ’上都是封闭和可结合的运算，因此，（A,*）的所有子独异点为(A ’,*)，其中A ’必须包含1。即：(A,*)的所有子独异点为： ({1},*),({1,2},*),({1,3},*),({1,4},*),({1,2,3},*),({1,2,4},*),({1,3,4},*),({1,2,3,4},*) P105：3、4、13 3、??????1100b a ×??????220 0b a ＝??? ?? ?212100b b a a ,a 1,a 2∈{1,-1}, 所以a 1×a 2∈{1,-1}，b 1×b 2∈{1,-1}。 故（G,×）是封闭的。 而 (??????1100b a ×??????2200b a )×??????3300b a =??????212 100b b a a ×????? ?3300b a =??????3213 2100b b b a a a ??????1100b a ×(????? ?22 00b a ×??????3300b a )=??????1100b a ×??????323 200b b a a =??????3213210 0b b b a a a 故（G,×）是可结合的。（也可以说因为矩阵乘法是可结合的。） 学号：0808 姓名：马涛 习题1 4．证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )u i (1 i 10) 容易证明，对v i v j E((a)),有f(v i v j )u i u j E((b)) (1 i 10, 1j 10 ) 由图的同构定义知，图1-27的两个图是同构的。 6．设G 是具有m 条边的n 阶简单图。证明：m =??? ? ??2n 当且仅当G 是完全图。 证明 必要性 若G 为非完全图，则 vV(G),有d(v) n-1 d(v) n(n-1) 2mn(n-1) m n(n-1)/2=??? ? ??2n , 与已知矛盾！ 充分性 若G 为完全图，则 2m= d(v) =n(n-1) m= ??? ? ??2n 。 9.证明：若k 正则偶图具有二分类V = V 1∪V 2，则 | V 1| = |V 2|。 (a) v 2 v 3 u 4 u (b) 证明 由于G 为k 正则偶图，所以，k V 1 =m = k V 2 V 1= V 2 。 12.证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于 2，因此，对v in ，存在点v ik 与之邻接，则v ik v in v ik 构成一个圈 。 17.证明：若G 不连通，则G 连通。 证明 对)(,_G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_G 中连通，因此，u 与v 在_G 中连通。 习题2 证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当)1(21-=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足E d n i i 21=∑=，E 为T 的边数，又有边数和顶点的关系1+=E n ，所以 )1(21-=?∑=n d n i i 证明：若e 是n K 的边，则3)2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生成树的总边数为：2)1(--n n n ，所以，每条边所对应的生成树的棵数为：32 2)1(2 1)1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 组合数学论文 现代数学可以分为两大类：一类是研究连续对象的，如分析、方程等，另一类就是研究离散对象的组合数学。组合数学不仅在基础数学研究中具有极其重要的地位，在其它的学科中也有重要的应用，如计算机科学、编码和密码学、物理、化学、生物等学科中均有重要应用。微积分和近代数学的发展为近代的工业革命奠定了基础。而组合数学的发展则是奠定了本世纪的计算机革命的基础。计算机之所以可以被称为电脑，就是因为计算机被人编写了程序，而程序就是算法，在绝大多数情况下，计算机的算法是针对离散的对象，而不是在作数值计算。正是因为有了组合算法才使人感到，计算机好像是有思维的。组合数学不仅在软件技术中有重要的应用价值，在企业管理，交通规划，战争指挥，金融分析等领域都有重要的应用。在美国有一家用组合数学命名的公司，他们用组合数学的方法来提高企业管理的效益，这家公司办得非常成功。此外，试验设计也是具有很大应用价值的学科，它的数学原理就是组合设计。用组合设计的方法解决工业界中的试验设计问题，在美国已有专门的公司开发这方面的软件。 广义的组合数学就是离散数学，离散数学是狭义的组合数学和图论、代数结构、数理逻辑等的总称。但这只是不同学者在叫法上的区别。总之，组合数学是一门研究离散对象的科学。随着计算机科学的日益发展，组合数学的重要性也日渐凸显，因为计算机科学的核心内容是使用算法处理离散数据。 狭义的组合数学主要研究满足一定条件的组态（也称组合模型）的存在、计数以及构造等方面的问题。组合数学的主要内容有组合计数、组合设计、组合矩阵、组合优化等。 组合数学中有几个著名的问题： 地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是否总共只需四种颜色？这是图论的问题。 船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、狼就会吃羊。船夫的船每次只能运送一种东西。怎样把所有东西都运过河？ 这是线性规划的问题。 中国邮差问题：由中国组合数学家管梅谷教授提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全问题，存在多项式复杂度算法：先求出度为奇数的点，用匹配算法算出这些点间的连接方式，然后再用欧拉路径算法求解。这也是图论的问题。 货郎问题：一个货郎要去若干城镇卖货，然后会到出发地，给定各个城镇之间的旅行时间，应怎么样计划他的路线，使他可以去每个城镇而且所用的时间最短。这个问题至今都没有有效的算法。 这几个问题将组合数学研究的问题具体表现出来，同时也可以看出他在我们生活中有着很重要的地位。 组合数学中主要可以分成以下几个部分：排列组合与容斥原理、二项式定理、递推关系与生成函数、polya定理。下面我将以这四个部分分别介绍组合数学的各方面问题。 1、排列组合与容斥原理： 排列组合里面的4个重要的基本原理：加法原理、乘法原理、减法原理、除法原理 前面两个最为基本，后面两个是根据前两个派生出来的。乘法原理有的时候的应用很巧妙，可以作为一种打开思路的办法。 组 组 组合数学与离散数学 习题三： ● 证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意及, G 中的路必含. 证明：充分性: 是的割边，故至少含有两个连通分支，设是其中一个连通分支的顶点集，是其余分支的顶点集，对12,u V v V ?∈?∈，因为中的不连通，而在中与连通，所以在每一条路上，中的必含。 必要性：取12,u V v V ∈∈，由假设中所有路均含有边，从而在中不存在从与到的路，这表明不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 ： 是块，任取的一点，一边，在边插入一点，使得成为两条边，由此得到新图，显然的是阶数大于3的块，由定理，中的u,v 位于同一个圈上，于是 中u 与边都位于同一个 圈上。 ： 无环，且任意一点和任意一条边都位于同一个圈上，任取的点u ，边e ，若在上，则三个不同点位于同一个闭路，即位于同一条路，如不在上，由定理，的两点在同一个闭路上，在边插入一个点v ，由此得到新图，显然的是阶数大于3的块，则两条边的三个不同点在同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,,无环，12,x v y v ∈∈，点在每一条的路上，则与已知矛盾，是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明：是单图的割点，则有两个连通分支。现任取, 如果不在的 同一分支中，令是与 处于不同分支的点，那么，与在的补图中连通。若在的同一分支中，则它们在的补图中邻接。所以，若是的割点，则不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给 出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ● 13.设H 是连通图G 的子图，举例说明：有可能k(H)> k(G). 解： 通常. 整个图为，割点左边的图为的的子图， ，则. e H 组合数学作业 第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？ 解：不能获得自由。 方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。 方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。 不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。 所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。 必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。 下面证明a既是m的因子又是n的因子。 方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。 方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。 信息科学技术学院2003-2004学年第二学期 本科生期末考试试卷 一、（每小题3分,共18分）判断以下命题的真假.如果为真在后面括弧内打 √，否则打?. 1．A ={x |x ∈N 且(x ,5)=1}，则构成代数系统，+为普通加法 （ ） 2．?x , y ∈R ，x o y =|x -y |，则0为 习题一 1. （题14）：证明图1-28中的两图是同构的 证明 将图1-28的两图顶点标号为如下的(a)与(b)图 作映射f : f(v i )u i (1 i 10) 容易证明，对v i v j E((a)),有f(v i v j )u i u j E((b)) (1 i 10, 1j 10 ) 由图的同构定义知，图1-27的两个图是同构的。 2. （题6）设G 是具有m 条边的n 阶简单图。证明：m =???? ??2n 当且仅当G 是 完全图。 证明 必要性 若G 为非完全图，则 v V(G),有d(v) n-1 d(v) n(n-1) 2m n(n-1) m n(n-1)/2=??? ? ??2n , 与已知矛盾！ 充分性 若G 为完全图，则 2m= d(v) =n(n-1) m= ??? ? ??2n 。 3. （题9）证明：若k 正则偶图具有二分类V = V 1∪V 2，则 | V 1| = |V 2|。 图1-28 (a) v 1 v 2 3v 4 v 5 v 6 v 7 v 8 v 9 v 10 u 1 u 2 u 3 u 4 u 5 u 6 u 7 u 8 u 9 u 10 (b) 证明 由于G 为k 正则偶图，所以，k V 1 =m = k V 2 V 1= V 2 。 4. （题12）证明：若δ≥2，则G 包含圈。 证明 只就连通图证明即可。设V(G)=｛v 1,v 2,…,v n ｝,对于G 中的路v 1v 2…v k ,若v k 与v 1邻接，则构成一个圈。若v i1v i2…v in 是一条路，由于 2，因此，对v in ，存在点v ik 与之邻接，则v ik v in v ik 构成一个圈 。 5. （题17）证明：若G 不连通，则G 连通。 证明 对)(,_ G V v u ∈?,若u 与v 属于G 的不同连通分支，显然u 与v 在_ G 中连通；若u 与v 属于g 的同一连通分支，设w 为G 的另一个连通分支中的一个顶点，则u 与w ，v 与w 分别在_ G 中连通，因此，u 与v 在_ G 中连通。 习题二 2、证明：每棵恰有两个1度顶点的树均是路。 证明：设树T 为任意一个恰有两个1度顶点的树，则T 是连通的，且无圈，令V 1 、V 2 为度为1的顶点，由于其他的顶点度数均为0或者2，且T 中无圈，则从V 1到V 2 有且只有一条连通路。所以，每棵恰有两个1度顶点的树均是路。得证。 5、证明：正整数序列),...,,(21n d d d 是一棵树的度序列当且仅当 )1(21 -=∑=n d n i i 。 证明：设正整数序列),...,,(21n d d d 是一棵树T 的度序列，则满足 E d n i i 21 =∑=，E 为T 的 边数，又有边数和顶点的关系1+=E n ，所以)1(21 -=? ∑=n d n i i 14、证明：若e 是n K 的边，则3 )2()(--=-n n n n e K τ。 若e 为Kn 的一条边，由Kn 中的边的对称性以及每棵生成树的边数为n-1，Kn 的所有生 成树的总边数为： 2 )1(--n n n ，所以，每条边所对应的生成树的棵数为： 32 2)1(2 1 )1(--=--n n n n n n n ，所以，K n - e 对应的生成树的棵数为： 332)2(2)(----=-=-n n n n n n n n e K τ 16、Kruskal 算法能否用来求： （1）赋权连通图中的最大权值的树 一、离散数学介绍 离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 离散数学常常被分成三门课程进行教学，即集合论与图论、代数结构与组合数学、数理逻辑。 其中各部分内容在本书中又有如下涉及： 1．集合论部分：集合及其运算(3.1)、二元关系(3.2)与函数(3.5)、自然数及自然数集、集合的基数注：集合这个概念比较了解，在数学上，基数(cardinal number)也叫势(cardinality)，指集合论中刻画任意集合所含元素数量多少的一个概念。这是康托尔在1874年～1884年引入最原始的集合论（现称朴素集合论）时, 给出的基数概念。他最先考虑的是集合{1,2,3} 和 {2,3,4}，它们并非相同，但有相同的基数。 那何谓两个集合有相同数目的元素？ 康托尔的答案，是所谓一一对应，即把两个集合的元素一对一的排起来，若能做到，两个集合的基数自然相同。 这个答案虽然简单，却起到了革命性的作用，因为用相同的方法即可比较任意集合，包括无穷集合的大小。 2．图论部分(第5章)：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配 集、覆盖集、独立集与匹配、带权图及其应用3．代数结构部分（第6、7章）：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数4．组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理 组合数学在本书中没有介绍，而关于组合数学的问题却是十分有趣的，可以供大家思考一下。 组合数学中的著名问题 ?计算一些物品在特定条件下分组的方法数目。这些是关于排列、组合和整数分拆的。 ?地图着色问题：对世界地图着色，每一个国家使用一种颜色。如果要求相邻国家的颜色相异，是 否总共只需四种颜色？这是图论的问题。 ?船夫过河问题：船夫要把一匹狼、一只羊和一棵白菜运过河。只要船夫不在场，羊就会吃白菜、 狼就会吃羊。船夫的船每次只能运送一种东西。 怎样把所有东西都运过河？这是线性规划的问 题。 ?中国邮差问题：由中国组合数学家 ?管梅谷教授① ?提出。邮递员要穿过城市的每一条路至少一次，怎样行走走过的路程最短？这不是一个NP完全 问题，存在多项式复杂度算法：先求出度为奇数 的点，用匹配算法算出这些点间的连接方式，然 后再用欧拉路径算法求解。这也是图论的问题。 ?任务分配问题（也称婚配问题）：有一些员工要完成一些任务。各个员工完成不同任务所花费的时 间都不同。每个员工只分配一项任务。每项任务 只被分配给一个员工。怎样分配员工与任务以使 所花费的时间最少？这是线性规划的问题。 ?如何构作幻方。 电子科技大学研究生试题图论及其应用参考答 案 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四． A C D 1 2 3 A B C D 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分) 求下图G 的色多项式P k (G). 解：用公式 )(e G P k -G 的色多项式： )3)(3)()(345-++=k k k G P k 。 六．(10分) 一棵树有n 2个顶点的度数为2，n 3个顶点的度数为3，…，n k 个顶点的度数 为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k 七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。 证明：(1) 若不然，设C=v 1v 2…v m v 1为G 的一个奇圈，不妨设v 1X, v 5 v v v 6 图G 习题三： ● 证明：e 是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u ，v ）必含e . 证明：充分性: e 是G 的割边，故G ?e 至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G 中的u,v 不连通，而在G 中u 与v 连通，所以e 在每一条(u,v)路上，G 中的(u,v)必含e 。 必要性：取12,u V v V ∈∈，由假设G 中所有(u,v)路均含有边e ，从而在G ?e 中不存在从u 与 到v 的路，这表明G 不连通，所以e 是割边。 ● 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G 是块，任取G 的一点u ，一边e ，在e 边插入一点v ，使得e 成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G 中的u,v 位于同一个圈上，于是G 1中u 与边e 都位于同一个圈上。 （2）→（3）： G 无环，且任意一点和任意一条边都位于同一个圈上，任取G 的点u ，边e ，若u 在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u 不在e 上，由定理，e 的两点在同一个闭路上，在e 边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G 连通，若G 不是块，则G 中存在着割点u ，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u 在每一条(x,y)的路上，则与已知矛盾，G 是块。 ● 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v 是单图G 的割点，则G ?v 有两个连通分支。现任取x,y ∈V(G ?v), 如果x,y 不在G ?v 的同一分支中，令u 是与x,y 处于不同分支的点，那么，x,与y 在G ?v 的补图中连通。若x,y 在G ?v 的同一分支中，则它们在G ?v 的补图中邻接。所以，若v 是G 的割点，则v 不是补图的割点。 ● 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} 精心整理 2019年－9月 习题三： ?证明：是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意 及, G 中的路 必含. 证明：充分性 : 是 的割边，故 至少含有两个连通分支，设 是其中一个连通分支的顶点 集，是其余分支的顶点集，对1,u V v ?∈?∈ 以在每一条 路上，中的 必含。 必要性：取12,u V v V ∈∈， 由假设中所有从而在中不存在从与到的路， 这表明不连通，所以e 是割边。 ?3.设G 是阶大于2（1） G 是块 （2） G （3） G 是块，任取的一点，一边，在 ，使得成为两条边，由此得到新图 ，显然 的块，由定理， 中u 与边都位于同一个 圈上。 ： 的点u ，边e ，若在上，则三个 不在 上，由定理，的两点在同一个闭路上， 在边插入一个点v ，由此得到新图，显然 的是阶数大于3的块，则两条边的三个不同点在 同一条路上。 ： 连通，若不是块，则中存在着割点，划分为不同的子集块,,, 无环，12,x v y v ∈∈， 点在每一条 的路上，则与已知矛盾，是块。 精心整理 2019年－9月 ?7.证明：若v 是简单图G 的一个割点，则v 不是补图的割点。 证明： 是单图 的割点，则 有两个连通分支。现任取 , 如果 不在的同一分支中，令是与处于不同分支的点，那么，与在 的补图中连通。若 在 的 同一分支中，则它们在 的补图中邻接。所以，若是的割点，则不是补图的割点。 ?12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）} ()25G κ= 最小点割{6,7,8,9,10} 2()5G λ= 最小边割{（2,7）…（1,6）} ?13.设H 是连通图G 解： 通常 . 整个图为，割点左边的图为的的子图， ，则 . 集合论与代数结构 课程名称：集合论与代数结构 课号：00830690 任课老师：于江生（副教授） 开课时间：每学年的下学期 学时：4学时/周 学分：4 授课对象：北大本科生（公共辅修课） 课程概要： 1.介绍Cantor的朴素集合论（包括基数理论和序数理论）和集合论ZF公理体系、GB公 理体系。回顾20世纪初数学基础之争和为解决Russell悖论所作的努力，科普G?del 不完全性定理、连续统假设及其意义。 2.介绍格论（Lattice Theory）及其应用，介绍抽象代数（Abstract Algebra）的基本概念（群、 环、域）。着重讲授群论及其应用（详细内容见《群论的应用_学生作业》）。课程的最后部分介绍域的扩张和Galois理论，并证明三等分角和倍立方体的尺规作图问题不可能。 课程目标：培养学生的数学美感，锻炼其逻辑思维能力和想象力，并使之了解近代集合论和代数学的发展。鼓励学生运用数学知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。 参考书及课外读物： [1]H. B. Enderton (1977), Elements of Set Theory, Academic Press, Inc. [2]L. C. Grove (1983), Algebra, Academic Press, Inc. [3]T. W. Hungerford (1980), Algebra, GTM series, Springer-Verlag [4]Jacobson, Lectures in Abstract Algebra (Vol 1, 2, 3), GTM series (No. 30, 31, 32), Springer-Verlag [5]Takeuti and Zaring, Introduction to Axiomatic Set Theory, GTM series (No. 1), Springer-Verlag [6]Takeuti and Zaring, Axiomatic Set Theory, GTM series (No. 8), Springer-Verlag [7] B. L. van der Waerden (1955), Algebra, Springer-Verlag [8]耿素云、屈婉玲、王捍贫（2002），《离散数学教程》，北京大学出版社 [9]耿素云（1998），《集合论与图论》，北京大学出版社 [10]屈婉玲（1998），《代数结构与组合数学》，北京大学出版社 离散数学教程 （集合论与图论） 离散数学：计算机科学与技术的数学基础课内容：集合论，图论，组合数学，代数结构，数 理逻辑 集合论:（第1-4章） 组合数学初步:（第5-7章） 图论:（第8-11章） 教师介绍 ?教师：吴永辉博士副教授 ?简历： ?1984-1988 上海科技大学计算机系本科?1988-1991 复旦大学计算机系硕士?1991-2003 华东师范大学计算机系工作?1998-2001 复旦大学计算机系博士?2003-复旦大学计算机系工作 ?答疑E-mail: yhwu@https://www.doczj.com/doc/951239766.html, 《集合论与图论》课件制作软件?Microsoft PowerPoint ?MathType Equation 《集合论与图论》课程大纲?课程性质与目的 ?教学内容与要求 ?使用教材、参考书籍 ?命题说明和题型 课程性质、目的与基本要求 ?课程性质 本课程讲授计算机科学与技术的数学基础 课《离散数学》的部分主要内容：集合论、图 论与组合数学初步，是计算机专业的主干课程 之一。 本课程前行课程为线性代数，数学分析(上)。 ?课程目的 使学生掌握集合论、图论与组合数学初步的基本内容，并对证明的思想和方法深入理 解和体会，初步培养学生的思维过程的数学化。 ?基本要求： ?掌握集合论、组合学和图论的基本概 念，清楚了解引入基本概念的实际背景、各概念间相互关系；掌握基本定理以及有关理论题的证明技巧；掌握解决计数问题的基本方法和技巧；掌握图论中各算法设计的思想、正确性证明以及算法的应用。为进一步学习计算机其他课程打下坚实的基础。 电子科技大学研究生试题 图论及其应用参考答案 Last revision date: 13 December 2020. 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于 3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图答__是___; 是否可1-因子分解答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k v v 1 3 图G代数结构与拓扑结构Cartan
电子科技大学研究生试题《图论及其应用》(参考答案)
离散数学代数结构作业部分答案
图论及其应用1-3章习题答案(电子科大)(1)
组合数学
组合数学前沿介绍
合
数
学
Combinatorics
马昱春 MA Yuchun myc@https://www.doczj.com/doc/951239766.html,
1
合
数
学
Combinatorics
组合数学:有人认为广义的组合数学就是离散数学，也有人认 为离散数学是狭义的组合数学和图论、代数结构、数理逻辑 等的总称。但这只是不同学者在叫法上的区别。总之，组合 数学是一门研究离散对象的科学。
https://www.doczj.com/doc/951239766.html,/zh-cn/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6
Combinatorics: Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics.
https://www.doczj.com/doc/951239766.html,/wiki/Combinatorics 2
? 狭义的组合数学主要研究满足一定条件的组态（ 也称组合模型）的存在、计数以及构造等方面的 问题。
– 组合数学的主要内容有组合计数、组合设计、组合矩 阵、组合优化等。
? 离散数学(Discrete mathematics)是数学的几个分 支的总称，以研究离散量的结构和相互间的关系 为主要目标，其研究对象一般地是有限个或可数 无穷个元素；因此它充分描述了计算机科学离散 性的特点。
– 离散数学通常研究的领域包括：数理逻辑、集合论、 关系论、函数论、组合学、代数系统与图论。 。
3图论及其应用 答案电子科大
组合数学作业答案1-2章2016
北大代数结构与组合数学期中试题_计算机基础数学
图论及其应用1-3章习题答案
离散数学(第一讲)
电子科技大学研究生试题图论及其应用参考答案完整版
图论及其应用第三章答案电子科大
图论及其应用总结归纳第三章答案(电子科大)
集合论与代数结构
离散数学教程(集合论与图论)-FudanUniversity
电子科技大学研究生试题图论及其应用参考答案
相关主题
文本预览