篇一：e^(-jπn)
数论基础习题总结数论习题总结A、洛?P1072Hankson的趣味题题?描述Hanks博?是BT(Bio-Tech，?物技术)领域的知名专家，他的??名叫Hankson。现在，刚刚放学回家的Hankson正在思考?个有趣的问题。今天在课堂上，?师讲解了如何求两个正整数c1和c2的最?公约数和最?公倍数。现在Hankson认为??已经熟练地掌握了这些知识，他开始思考?个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满?：1．x和a0的最?公约数是a1；2．x和b0的最?公倍数是b1。Hankson的“逆问题”就是求出满?条件的正整数x。但稍加思索之后，他发现这样的x
并不唯?，甚?可能不存在。因此他转?开始考虑如何求解满?条件的x*的个数。请你帮助他编程求解这个问题。输?格式第??为?个正整数n，表?有n
组输?数据。接下来的n*?每??组输?数据，为四个正整数a0,a1,b0,b1，每两个整数之间??个空格隔开。输?数据保证a0能被a1整除，b1能被b0整除。输出格式共n?。每组输?数据的输出结果占??，为?个整数。对于每组数据：若不存在这样的x，请输出0；若存在这样的x，请输出满?条件的x的个数；输?输出样例输?#1241196288951371776输出#162说明/提?【说明】第?组输?数据，xx可以是9,18,36,72,144,288，共有6个。第?组输?数据，xx
可以是48,1776，共有2个。【数据范围】对于50%的数据，保证有1≤a0,a1,b0,b1≤10000且n≤100。对于100%的数据，保证有1≤a0,a1,b0,b1≤2,000,000,000且n≤2000。NOIP2009提?组
第?题分析题?的?意就是求同时满?\(gcd(x,a_0)=a_1\)\(lcm(x,b_0)=b_1\)的元素\(x\)的个数很显然，要想满?上?的条件，必须有\(gcd(a_0/a_1,x/a_1)=1\)并且\(gcd(b_1/b_0,b_1/x)=1\)同时我们还要顺便把\(b_1/i\)也判断?下，这样就可以降低时间复杂度，从1枚举到\(\sqrt{b_1}\)就可以了总的时间复杂度为\(2000\times\sqrt{2000000000}=1e8\)代码#include 样例输?3100样例输出3042分析题意?概是：给两个数，求这两个数之间的数的欧拉函数值。数据范围不?，直接线性筛求1~n的欧拉函数值，最后再枚举?遍相加就可以了代码#include constintmaxn=3e6+5;typedeflonglongll;llgetphi(llxx){llans=xx;llm=sqrt(xx+0.5);for(lli=2;i<=m;i++){if(xx%i==0){ans=ans/i*(i-1);}while(xx%i==0)xx/=i;}if(xx>1)ans=ans/xx*(xx-1);returnans;}intmain(){intt;scanf("%d",&t);while(t--){lln,m;scanf("%lld%lld",&n,&m);llans=0;for(lli=1;i*i<=n;i++){if(n%i)continue;if(i>=m)ans+=getphi(n/i);if(n/i>=m&&i*i!=n)ans+=getphi(i);}printf("%lld\n",ans);}return0;}D、洛?P2158[SCOI2008]仪仗队题?描述作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学?组成的N*N的?阵，为了保证队伍在?进中整齐划?，C君会跟在仪仗队的左后?，根据其视线所及的学??数来判断队伍是否整齐(如下图)。 输?格式共?个数N输出格式共?个数，即C君应看到的学??数。输?输出样例输?#14输出#19说明/提?【数据规模和约定】对于100%的数据，1≤N≤40000分析我们可以把矩阵看成?个平?直?坐标系以体育委员所在的点为原点，分别向其它的点作?条直线根据数学知识可得，如果点的坐标为\((x,y)\)则直线的斜率为\(y/x\)很显然，如果有多条直线的斜率相同，那么只能观察到?个点换句话说，只有当\(gcd(x,y)=1\)时，点\((x,y)\)才会被看到因为会有???列的点在坐标轴上，所以我们要把\(n--\)最后我们从2到n把欧拉函数值累加，最后再乘2因为我们相当于以\(y=x\)为界限把原图划分为两部分输出的结果的时候要把结果加3，因为\((0,1)(1,0)(1,1)\)三个点没有考虑当\(n=1\)的时候还要特判?下代码#include 现在，C君希望你告诉他队伍整齐时能看到的学??数。 }for(intj=1;j<=prime[0]&&i*prime[j]<=xx;j++){isnot_prime[i*prime[j]]=1;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*(prime[j]-1);}}}}intmain(){intn;scanf("%d",&n);if(n==1){printf("0\n");return0;}getphi(n);intans=3;for(inti=2;i<=n-1;i++){ans+=phi[i]*2;}printf("%d\n",ans);return0;}E.洛?P2303Longge的问题题?背景Longge的数学成绩?常好，并且他?常乐于挑战?难度的数学问题。题?描述现在问题来了：给定?个整数n，你需要求出$$\sum_{i=1}^ngcd(i,n)$$，其中\(\gcd(i,n)\)表? i 和n的最?公因数。输?格式输?只有???个整数，表?n。输出格式输出???个整数表?答案。输?输出样例输?#16输出#115说明/提?数据规模与约定对于60%的数据，保证n≤\(2^{16}\)。对于100%的数据，保证1≤n≤\(2^{32}\)。分析如果直接去暴?枚举的话，显然会T掉所以我们考虑?下\(\gcd\)的某些性质?先\(gcd(i,n)\)所得到的值必定是\(n\)的某?个因数拿我们就可以?\(\sqrt{n}\)的效率枚举n的每?个因?，也就是最终\(gcd\)的结果如果n%i=0的话，那么\(i\)对于答案的贡献就是$\varphi(n/i)\timesi$为什么呢，我们可以这么想如果要使\(gcd(n,a)=i\)，必定有\(a=k\timesi(1\lek\len/i)\)并且\(gcd(k,n/i)=1\)也就是求出区间\([1,n/i]\)中与\(n/i\)互质的数的个数，这正是欧拉函数的定义同时也要把另?个因数搞?下代码#include ans+=i*phi(n/i);if(i*i!=n)ans+=n/i*phi(i);}}printf("%lld\n",ans);return0;}F.沙拉公主的困惑题?描述?富翁国因为通货膨胀，以及假钞泛滥，政府决定推出?项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发?编号与M!互质的钞票。房地产第??户沙拉公主决定预测?下?富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数?常?，你只需计算出对R取模后的答案即可。R是?个质数。输?格式第??为两个整数T，R。\(R\leq10^{9}+10\)，\(T\leq10000\)，表?该组中测试数据数?，R为模后?T?，每??对整数N，M，见题?描述m<=n输出格式共T?，对于每?对N，M，输出1?N！中与M！素质的数的数量对R取模后的值样例样例输?11142样例输出1数据范围：对于100%的数据，1<=N,M<=10000000分析此题的?致题意为 求\(1.....n!\)中所有与\(m!\)互质的数的个数因为\(m\len\)，所以必定有\(m!\len!\)很显然\(n!\)?定是\(m!\)的倍数所以我们将\(n!\)拆成\(n!/m!\)块，那么每?块中与\(m!\)互质的数的数量相同那么最终的答案就是\(\frac{n!}{m!}\times\varphi(m!)\)已知\(φ(n)=n\times\frac{p1-1}{p1}\times\frac{p2-1}{p2}\times......\frac{pi-1}{pi}\)其中\(p_i\)为\(m!\)的质因数因为\(m!\)是从\(1\)连乘到\(m\)的根据欧拉函数的求法，我们从?到?枚举质因?很显然，质因?的???定不会超过\(m\)那么求\(p_i\)就变成了求\(1\)到\(m\)中质数的个数，可以?线性筛预处理\(\dfrac{n!}{m!}\times\varphi(m!)=\dfrac{n!}{m!}\timesm!\times\dfrac{p1-1}{p1}\times\dfrac{p2-1}{p2}\times......\dfrac{pi-1}{pi}=n!\times\dfrac{p1-1}{p1}\times\dfrac{p2-1}{p2}\times......\dfrac{pi-1}{pi}\)因为结果要取模，?除法运算不能像乘法运算那样直接取模所以我们还要处理出\(p_i\)在模\(R\)意义下的乘法逆元所以我们可以打出下?的代码#include intans=1LL*lc[n]*jc[m]%mod*jcc[m]%mod;printf("%d\n",ans);}return0;}但是这样做是不对的?如1354正解1错解017119正解5错解0我们仔细考虑?下，并?所有的情况下都存在乘法逆元，当且仅当\(gcd(a,b)=1\)即\(a\),\(b\)互质时，存在乘法逆元?我们在运算过程中?到了\(p_i\)在模\(R\)意义下的乘法逆元?先\(p_i\)必定为质数对于任何?个质数\(x\)，如果\(x\)不等于\(p_i\)，那么就会有\(\gcd(x,p_i)=1\)这时就可以求出逆元但是，当\(x=p_i\)的时候，\(gcd(x,p_i)\ne1\)，逆元就没有意义这?道题要求\(p_i\)在\(\%R\)意义下的逆元如果\(R\)不等于\(p_i\)，那么上?的做法就没有影响但是如果恰好存在\(R\)等于\(p_i\)，那么逆元就没有意义，做法错误所以我们分类讨论?下当\(n G.同余?程题?描述求关于x的同余?程\(ax\equiv1\pmod{b}\)的最?正整数解。输?格式??，包含两个正整数a,b，??个空格隔开。输出格式?个正整数$x_0$，即最?正整数解。输?数据保证?定有解。输?输出样例输?#1310输出#17说明/提?【数据范围】对于40%的数据，2≤b≤1,000；对于60%的数据，2≤b≤50,000,000；对于100%的数据，2≤a,b≤2,000,000,000。NOIP2012提?组 第?天 第?题分析就是?道很裸的扩展欧??得板?题我们把原式转换?下可以得到\(ax-by=1\)我们把负号和\(y\)绑在?起，就变成了\(ax+by=1\)那么怎么和扩展欧??得\(ax+by=gcd(a,b)\)联系在?起呢，我们引??下洛?学委的证明?程$ax+by=m$有解的必要条件是\(m\modgcd(a,b)=0\)。由最?公因数的定义，可知a是\(gcd(a,b)\)的倍数，且\(b\)是gcd(a,b)的倍数，若x,y都是整数，就确定了$ax+by$是gcd(a,b)的倍数，因为m=ax+by，所以m必须是gcd(a,b)的倍数，那么\(m\modgcd(a,b)=0\)所以这道题的\(gcd(a,b)=1\)，那问题就迎刃?解了代码#include intmain(){llx,y,m,n,l,xx,yy;scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);llaa=n-m;llcc=x-y;if(aa<0)aa=-aa,cc=-cc;llbb=l;llgcd=ex_gcd(aa,bb,xx,yy);if(cc%gcd){printf("Impossible\n");return0;}lladt=bb/gcd;xx=((xx*(cc/gcd)%adt)+adt)%adt;printf("%lld\n",xx);return0;}I.倒酒题?链接分析我们设最后剩余的酒量为\(ans\)那么必定有\(ans=-a*k_1+b*k_2\)很显然，?要利?扩展欧??得定理我们先求出\(a*k_1+b*k_2=gcd(a,b)\)的解由G题证明可得，若要有解，则$ans\mod\gcd(a,b)=0$要使得ans最?，那么ans只能等于\(\gcd(a,b)\)最后再把解转化为最??负的就可以了代码#include 题?链接分析通过观察可得，每进??次操作，牌的标号就会乘2我们假设这?张牌的标号为k那么就会有\(k\times2^{m}\mod(n+1)=l\)也就是\(k\times2^{m}-l=(n+1)*p\)等式两边同除以\(l\)，就会有\(k/l\times2^{m}-1=(n+1)*p/l\)很显然，这就是求\(2^{m}\)在模\(n+1\)意义下的逆元最后再把结果乘上\(l\)就可以代码#include 第7章 习题解答 7.1(1),(2),(3),(5)都能构成无向图的度数列,其中除⑸外又都能构成无 向简单图的度数列. n分析1°非负整数列d!,d2,…，dn能构成无向图的度数列当且仅当di为 i4偶数,即d!,d2,…，dn中的奇数为偶数个.(1),(2),(3),(5)中分别有4个,0个,4个,4个奇数，所以，它们都能构成无向图的度数列，当然，所对应的无向图很可能 是非简单图.而⑷中有3个奇数，因而它不能构成无向图度数列.否则就违背了 握手定理的推论. 2°(5)虽然能构成无向图的度数列,但不能构成无向简单度数列.否则,若 存在无向简单图 G,以1,3,3,3为度数列,不妨设G中顶点为v!,v,v,v ,且 234d(Vi)=1,于是 d(V2)=d(V3)=d(V4)=3.而 V!只能与 v?""之一相邻,设 w与v?相邻，这样一来，除V2能达到3度外，V3,V4都达不到3度,这是矛盾的. 在图7.5所示的4个图中,(1)以1为度数列,(2)以2为度数列,(3)以3为 度数列,(4)以4为度数列(非简单图). 7.2设有几简单图D以2,2,3,3为度数列，对应的顶点分别为V1,V2,V3,V4,由 于 d(v)二 d(v)d_(v),所示，d(vj-d-(y)=2-0=2,d(V2)=d(V2)-d“2) =2—0=2,d(vj=d(Vs)_d—(V3)=3_2=1,d(V4)=d(Vq)_d^v。)=3_3=1/11由此可知，D的出度列为2,2,1,0,且满足add-(Vi).请读者画出 一个有向图?以2,2,3,3为度数列,且以0,0,2,3为入度列,以2,2,1,0为出度列.7.3D的入度列不可能为 1,1,1,1.否则,必有出度列为 2,2,2,2(因为 d(v)=d(v)d~(v)),)此时,入度列元素之和为4,不等于出度列元素之和 8,这 违背握手定理.类似地讨论可知，1,1,1,1也不能为D的出席列. 7.4不能.N阶无向简单图的最大度 厶_n一1.而这里的n个正整数彼此不同 因而这n个数不能构成无向简单图的度数列，否则所得图的最大度大于n,这与最 大度应该小于等于n-1矛盾. 7.5(1)16个顶点.图中边数m=16,设图中的顶点数为n.根据握手定理可 n知 2m=32二"d(vj=2ni4所以，n=16.(2)13个顶点.图中边数m=21,设3度顶点个数为x,由握手定理有 2m=42=343x由此方程解出x=10.于是图中顶点数n=310=13.(3)由握手定理及各顶点度数均相同，寻找方程 224=nk的非负整数解，这里不会出现n,k均为奇数的情况.其中n为阶级，即顶点 数,k为度数共可得到下面10种情况. ①个顶点，度数为48.此图一定是由一个顶点的24个环构成，当然为非简单 ②2个顶点,每个顶点的度数均为 24.这样的图有多种非同构的情况，一定为 非简单图. ③3个顶点,每个顶点的度数均为 16.所地应的图也都是非简单图. ④4个顶点,每个顶点的度数均为 12.所对应的图也都是非简单图. ⑤6个顶点，每个顶点的度数均为 8,所对应的图也都是非简单图. ⑥ 个顶点，每个顶点的度数均为6.所对应的非同构的图中有简单图，也有非 简单图. 2/11⑦12个顶点，每个顶点的度数均为4.所对应的非同构的图中有简单图，也 有非简单图? ⑧ 16个顶点,每个顶点的度数均为3,所对应的非同构的图中有简单图，也有 非简单图? ⑨ 24个顶点,每个顶点的度数均为2.所对应的非同构的图中有简单图，也有 非简单图? ⑩ 48个顶点,每个顶点的度数均为1,所对应的图是唯一的,即由24个K2构 成的简单图? 分析 由于n阶无向简单图G中,：(G) 有简单图?⑥-⑨既有简单图，也有非简单图，读者可以画出若干个非同构的图，而 ⑩只能为简单图? 7.6设G为n阶图，由握手定理可知 n70=235八 d(vj_3n,i吕 所以，|7=23.这里，乂为不大于x的最大整数，例如.2」=2,25」=2,空=23. .3一 7.7由于：(G)=n-1,说明G中任何顶点v的度数d(v)八(G)=n-1,可是 由于G为简单图，因而列G)乞n-1,这又使得d(v)岂n-1,于是d(v)二n-1,也就 是说,G中每个顶点的度数都是n-1,因而应有"G)乞n-1.于是G为(n-1)阶正 则图，即G为n阶完全图Kn. 7.8由G的补图G的定义可知，GG为Kn,由于n为奇数，所以，Kn中各 项顶点的度数n-1为偶数.对于任意的V(G),应有vV(G),且 dG(v)_dG(v)二 dg(v)二 n-1其中dG(v)表示v在G中的度数，d(v)表示v在G中的度数.由于n_1为偶 数,所G3/11以,d(v)与d(v)同为奇数或同为偶数,因而若G有r个奇度顶点,则G也 有r个奇度顶GG点. 7.9由于D"D,所以，m"空m.而n阶有向简单图中，边数m乞n(n一 1),所以,应有 n(n_1)=m\m乞 n(n-d)这就导致m=n(n-1),这说明D为n阶完全图，且D"=D.7.10图7.6给出了 K4的18个非同构的子图,其中有11个生成子图(8-18),其中连通的有6个11,12,13,14,16,17).图7.6中,n,m分别为顶点数和边数.7.11K4有11个生成子图，在图7.6中，它们分别如图8-18所示.要判断它 们之中哪些是自补图，首先要知道同构图的性质，设G1与G2的顶点数和边数.若 G1三G?,贝U门丄=门2「且 m * ①Q J OD a -一 Q 0O ◎ Q 生 于 O A 1: ◎ □ n L &■——G 乙 国 7,6(8)的补图为(14)-K4,它们的边数不同,所以，不可能同构.因而(8)与(14)均不是自补图类似地，(9)的补图为(13),它们也非同构,因而它们也都不是自补 图.(10)与(12)互为补图,它们非同构,因而它们都不是自补图.(15)与(17)互为 补图,它们非同构，所以,它4/11们都不是自补图?类似地,(16)与(18)互为补图且非同 构，所以，它们也都不是自补图? 而(11)与自己的补图同构，所以,(11)是自补图? 7.123阶有向完全图共有20个非同构的子图，见图7.7所示，其中⑸-(20) 为生成子图，生成子图中(8),(13),(16),(19)均为自补图.分析 在图7.7所示的生成子图中，(5)与(11)互为补图,(6)与(10)互为补 图,(7)与(9)互为补图,(12)与(14)互为补图,(15)与(17)互为补图,(18)与(20)互为补图，以上互为补图的两个图边数均不相同 (8),(13),(16),(19)47.13不能.分析 在同构的意义下，G,G2,G3都中K4的子图，而且都是成子图.而K4的两条边的生成子图中，只有两个是非同构的，见图7.6中(10)与(15)所示.由鸽 巢原理可知，G,G2,G3中至少有两个是同构的，因而它们不可能彼此都非同构. 鸽巢原理m只鸽飞进n个鸽巢,其中m一 n,则至少存在一巢飞入至少［凹］只 n，所以，它们都不是自补图.而 个图都与自己的补图同构，所以，它们都是自补图.鸽子.这里x表示不小于x的最小整数.例如，|2=2,|2.5=3.7.14G是唯一的，即使G是简单图也不唯一. | Q 0■ O ?O o_ 生 子 田 匕 込 込 匕 込 陡 込 ?n 阻7.5/11分析 由握手定理可知2m=3n,又由给的条件得联立议程组 "2m=3n、2n—3=m.解出n=6,m二9.6个顶点,9条边，每个顶点的度数都是3的图有多种非同构 的情况,其中有多个非简单图(带平行边或环),有两个非同构的简单图，在图7.8中(1),(2)给出了这两个非同构的简单图. 满足条件的非同构的简单图只有图 7.中,(1),(2)所示的图,(1)与⑵所示的图,(1)与(2)是非同构的.注意在⑴中不存在3个彼此相邻的顶点 而在⑵中存在3个彼此相邻的顶点，因而⑴ 图与(2)图非同构.下面分析满足条件的简单 图只有两个是非同构的.首先注意到(1)中与 (2)中图都是K6的生成子图，并且还有这样 的事实，设G,G2都是n阶简单图，则G^G2当且仅当G^eG2,其中G,G2分别 为G与G2的补图.满足要求的简单图都是6阶9条边的3正则图，因而它们的补 图都为6阶6条边的2正则图(即每个顶点度数都是2).而K的所有生成子图 中,6条边2正6则的非同构的图只有两个，见图7.8中(3),(4)所示的图，其中(3)为(1)的补图,(4)为(2)的补图，满足要求的非同构的简单图只有两个. 但满足要求的非同简单图有多个非同构的，读者可自己画出多个来. 7.15将K6的顶点标定顺序，讨论X所关联的边.由鸽巢原理(见7.13题), 与V1关联的5条边中至少有3条边颜色相同，不妨设存在3条红色边,见图7.9中⑴所示(用实线表示红色的边)并设它们关联另外3个顶点分别为V2,v,V6.若 4V2,V4,V6构成的Kg中还有红色边，比如边(V2M)为红色，则Vj^M构成的Kg为 红色K3,见图7.9中⑵所示.若V2,V4,V6构成的K3各边都是蓝色(用虚线表示),则V2,V4,V6构成的Ka为蓝色的. 6/11珂 7.16在图7.10所示的3个图中，(1)为强连通图，(2)为单向连通图，但不是 强连通的,(3)是弱连通的，不是单向连通的，更不是强连通的. 图 7.1分析在⑴中任何两个顶点之间都有通路，即任何两个顶点都是相互可达 的,因而它是强连能的.(2)中c不可达任何顶点，因而它不是强连通的，但任两个 顶点存在一个顶点可达另外一个顶点，所以，它是单向可达的.(3)中a,c互相均 不可达，因而它不是单向连通的，更不是强连通的. 判断有向图的连通性有下面的两个判别法. 1°有向图D是强连通的当且仅当D中存在经过每个顶点至少一次的回路. 2°有向图D是单向连通的当且仅当D中存在经过每个顶点至少一次的通路. (1)中abcda为经过每个顶点一次的回路,所以，它是强连能的.(2)中abdc为经过每个顶点的通路，所以，它是单向连通的，但没有经过每个顶点的回路，所 以,它不是强连通的.(3)中无经过每个顶点的回路，也无经过每个顶点的通路，所 以,它只能是弱连通的. 7.17G-E"的连通分支一定为2,而G-V"的连通分支数是不确定的. 分析 设E"为连通图G的边割集,则G-E"的连通分支数p(G-E")二2,不可 能大于2.否则，比如p(G-E")=3,则G-E"由3个小图G「G2，G3组成，且E"中边 的两个端点分属于两个不同的小图.设E"中的边的两个端点一个在 G中,另一个7/11在G2中,则E" E",易知p(G一 E")=2,这与E"为边割集矛盾,所以,p(G一 E")=2. 但p(G-V")不是定数,当然它大于等于2,在图7.11中,V二｛u,v｝为⑴的点 割集,p(G-V)=2，其中 t G为(1)中图.V=｛v｝为⑵中图的点割集，且v为割 ini 点,p(G-V)=4,其中G为⑵中图. 屛 ;■ <]> (2) ￡ 7.117.18解此题，只要求出D的邻接矩阵的前4次幕即可. 01101000A=0101.0000一 ~1101A 211000100121A 3A 41D中长度为4的通路数为A4中元素之和，等于15,其中对角线上元素之和为 3,即D中长度为3的回路数为3.V3到V4的长度为4的通路数等于a34)=2. 分析 用邻接矩阵的幕求有向图D中的通路数和回路数应该注意以下几点： 1°这里所谈通路或回路是定义意义下的，不是同构意义下的.比如,不同始 点(终点)的回路 2°这里的通路或回路不但有初级的、简单的，还有复杂的.例 如，V1,V2,w,V2,V1是一条长为4的复杂回路. 3°回路仍然看成是通路的特殊情况. 读者可利用A2,A3,求D中长度为2和3的通路和回路数. 7.19答案A:④.分析G中有Nk个k度顶点，有(n—NQ个(k1)度顶点，由握手定理可知 8/11n、d(Vj)=kN (k1)(n-N)=2mkki4=N =n(k1)-2n.k7.20答案A:②；B:③.分析 在图7.12中，图(1)与它的补同构，再没有与图(1)非同构的自补图了 所以非同构的无向的4阶自补图只有1个.图⑵与它的补同构，图⑶与它的补也 同构，而图⑵与图⑶不同构，再没有与(2),(3)非同构的自补图了，所以，非同械 的5阶自补图有2个. <1) (Z)⑶ 圉 7.127.21答案 A:④;B:③;C:④;D:①.分析(1)中存在经过每个顶点的回路，如adcba..(2)中存在经过每个顶点 的通路，但无回路.(3)中无经过每个顶点至少一次的通路,其实,b,d两个顶点互 不可达.(4)中有经过每个顶点至少一次的通路,但无回路，aedcbd为经过每个顶 点的通路.(5)中存在经过每个顶点至少一次的回路,如aedbcdba.(6)中也存在经 过每个顶点的回路,如baebdcb.由7.16题可知，(1),(5),(6)是强连通 的,(1),(2),(4),(5),(6)是单向连能的,(2),(4)是非强连通的单向连通图.注意, 强连通图必为单向连通图.6个图中,只有(3)既不是强连通的，也不是连通的，它 只是弱连通图. 在⑶中，从a到b无通路，所以d,：：：a,b「：,而b到a有唯一的通路ba,所以 db,a=1.7.22答案 A:①;B:⑥㈩C:②;D:④. 9/11分析 用Dijkstra标号法，将计算机结果列在表7.1中.表中第x列最后标定 y/Z表示b到x的最短路径的权为y,且在b到x的最短路径上,Z邻接到x,即 x的前驱元为Z.由表7.1可知,a的前驱元为c（即a邻接到c）,c的前驱元为b,所以,b到a的最短路径为bca,其权为4.类似地计论可知,b到c的最短路径为 be,其权为1.b到d的最短路径为bcegd,其权为9.b到e的最短路径为bee,其 权为7.表7.1顶〔 点 a b c d e f g 肌 QO CO 1212QO QO 4/QO OO QO 114/c c 129/g 5/c 凶e 7.23答案 A:⑧；B:⑩C:③；D:③和④.分析 按求最早、最晚完成时间的公式，先求各顶点的最早完成时间，再求 最晚完成时间，最后求缓冲时间 （1）最早完成时间： TE（vJ=0-_(V2)二{vM, TE(v)=max{03}=32-_(V3)二{vz},厂(vj二{WM}, -(V5)二MM}, TE(v)=max{02,3C}-3TE(vJ=max{04,32}=53TE(V5)=max{34,34}-10/11-_(V6)二“他},-一山)={V4,V5}, (V8TE(v)=max{34,70}=76TE(v)=max{55,100}=17)={6,7, VV}TE(v8)=max{73,101}=11TE(v)=max{76,111}=139-讥)二{V5,V8}, (2)最晚完成时间: TL(V9)=13-(V8)二{V9}, -(V6)={V8}, -(V7)二 g}, -(V5)={V6,V9}, TL(v)=min{13_1}=12; 8TL(v)=min{12-3=9; 6TL(v)=min{12—1}=11; 7TL(v)=min{9-0,13-6}=7; 5：(V4)*7}, -(V3)二{V4,V5,V6}, (v2)={v3,V5}, TL(V4)=min{11-5=6; TL(v)=min{6-2.7-4.9-4二 5; 3TL(v)=min{3-0.7-4}=3; 2；(vj={V2,V3,V4}, (3)缓冲时间： TL(vJ=min{3—3.3—2,6—"4}=0; TS(Vi)二TS(V2)=TS(V3)=TS(V5)=TS(V9)=0TS(V4)=1,TS(V6)=2,TS(V7)=TS(V8)=1.(4)关键路径有两条： V1,V2,V5,V9和 V1,V2,V3,V5,V9. 11/11 推荐访问:e^(-jπn)
篇二：e^(-jπn)
