《离散
数学
数学高考答题卡模板高考数学答题卡模板三年级数学混合运算测试卷数学作业设计案例新人教版八年级上数学教学计划
》试题一 《离散数学》题库 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1) Q=>Q→P (2) Q=>P→Q (3)P=>P→Q (4) P (P Q)=> P 2、下列公式中哪些是永真式？( ) (1)(┐P Q)→(Q→ R) (2)P→(Q→Q) (3)(P Q)→P (4)P→(P Q) 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P Q (2) P Q=>P (3) P Q=>P Q (4)P (P→Q)=>Q (5) (P→Q)=>P (6) P (P Q)=> P 4、公式x((A(x)B(y，x)) z C(y，z))D(x)中，自由变元是( )，约束变元是( )。 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 8、设个体域为整数集，则下列公式的意义是( )。 (1) xy(x+y=0) (2) yx(x+y=0) 9、设全体域D是正整数集合，确定下列命题的真值： (1) xy (xy=y) ( ) (2) xy(x+y=y) ( ) (3) xy(x+y=x) ( ) (4) xy(y=2x) ( ) 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 11、命题“2是偶数或-3是负数”的否定是（ ）。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 13、公式( P Q) ( P Q)化简为（ ），公式 Q (P (P Q))可化简为（ ）。 14、谓词公式x(P(x) yR(y)) Q(x)中量词x的辖域是（ ）。 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（ ）。 （集合论部分） 16、设A={a,{a}}，下列命题错误的是（ ）。 (1) {a} P(A) (2) {a} P(A) (3) {{a}} P(A) (4) {{a}} P(A) 17、在0（ ） 之间写上正确的符号。 (1) = (2) (3) (4) 18、若集合S的基数|S|=5，则S的幂集的基数|P(S)|=（ ）。 19、设P={x|(x+1) 4且x R},Q={x|5 x +16且x R},则下列命题哪个正确（ ） (1) Q P (2) Q P (3) P Q (4) P=Q 20、下列各集合中，哪几个分别相等( )。 (1) A1={a,b} (2) A2={b,a} (3) A3={a,b,a} (4) A4={a,b,c} (5) A5={x|(x-a)(x-b)(x-c)=0} (6) A6={x|x2-(a+b)x+ab=0} 21、若A-B=Ф，则下列哪个结论不可能正确？( ) (1) A=Ф (2) B=Ф (3) A B (4) B A 22、判断下列命题哪个为真?( ) (1) A-B=B-A => A=B (2) 空集是任何集合的真子集 (3) 空集只是非空集合的子集 (4) 若A的一个元素属于B，则A=B 23、判断下列命题哪几个为正确？( ) (1) {Ф}∈{Ф,{{Ф}}} (2) {Ф} {Ф,{{Ф}}} (3) Ф∈{{Ф}} (4) Ф {Ф} (5) {a,b}∈{a,b,{a},{b}} 24、判断下列命题哪几个正确？( ) (1) 所有空集都不相等 (2) {Ф} Ф (4) 若A为非空集，则A A成立。 25、设 A∩B=A∩C， ∩B= ∩C，则B( )C。 26、判断下列命题哪几个正确？( ) (1) 若A∪B＝A∪C，则B＝C (2) {a,b}={b,a} (3) P(A∩B) P(A)∩P(B) （P(S)表示S的幂集） (4) 若A为非空集，则A A∪A成立。 27、Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确： (1) A B，B C=> A C (2) A B，B C=> A∈B (3) A∈B，B∈C=> A∈C （二元关系部分） 28、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求(1)R (2) R-1 。 29、举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 30、集合A上的等价关系的三个性质是什么？( ) 31、集合A上的偏序关系的三个性质是什么？( ) 32、设A={１,２,３,４}，Ａ上的关系Ｒ＝｛〈1,2〉，〈2,1〉，〈2,3〉，〈3,4〉｝ 求(1)R R (2) R-1 33、设Ａ＝｛1，2，3，4，5，6｝，Ｒ是A上的整除关系，求R= {( )}。 34、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=2y｝，求(1)R (2) R-1 。 35、设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，求R和R-1的关系矩阵。 36、集合A={1,2,…,10}上的关系R={
|x+y=10,x,y A}，则R 的性质为（ ）。 (1) 自反的 (2) 对称的 (3) 传递的，对称的 (4) 传递的 （代数结构部分） 37、设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点中，单位元是( )，零元是( )。 38、设A={3,6,9}，A上的二元运算*定义为：a*b=min{a,b}，则在独异点中，单位元是( )，零元是( )； （半群与群部分） 39、设〈G,*〉是一个群，则 (1) 若a,b,x∈G，a x=b，则x=( )； (2) 若a,b,x∈G，a x=a b，则x=( )。 40、设a是12阶群的生成元， 则a2是( )阶元素，a3是( )阶元素。 41、代数系统是一个群，则G的等幂元是( )。 42、设a是10阶群的生成元， 则a4是( )阶元素，a3是( )阶元素。 43、群的等幂元是( )，有( )个。 44、素数阶群一定是( )群, 它的生成元是( )。 45、设〈G,*〉是一个群，a,b,c∈G，则 (1) 若c a=b，则c=( )；(2) 若c a=b a，则c=( )。 46、是的子群的充分必要条件是( )。 47、群＜A,*＞的等幂元有( )个，是( )，零元有( )个。 48、在一个群〈G,*〉中，若G中的元素a的阶是k，则a-1的阶是( )。 49、在自然数集N上，下列哪种运算是可结合的？（ ） (1) a*b=a-b (2) a*b=max{a,b} (3) a*b=a+2b (4) a*b=|a-b| 50、任意一个具有2个或以上元的半群，它（ ）。 (1) 不可能是群 (2) 不一定是群 (3) 一定是群 (4) 是交换群 51、6阶有限群的任何子群一定不是（ ）。 (1) 2阶 (2) 3 阶 (3) 4 阶 (4) 6 阶 （格与布尔代数部分） 52、下列哪个偏序集构成有界格（ ） (1) （N, ） (2) （Z, ） (3) （{2,3,4,6,12},|（整除关系）） (4) (P(A), ) 53、有限布尔代数的元素的个数一定等于（ ）。 (1) 偶数 (2) 奇数 (3) 4的倍数 (4) 2的正整数次幂 （图论部分） 54、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图 (2) 树 (3) 平面图 (4) 连通图 55、下面给出的集合中，哪一个是前缀码？( ) (1) {0，10，110，101111} (2) {01，001，000，1} (3) {b，c，aa，ab，aba} (4) {1，11，101，001，0011} 56、一个图的哈密尔顿路是一条通过图中( )的路。 57、在有向图中，结点v的出度deg+(v)表示( )，入度deg-(v)表示( )。 58、设G是一棵树，则G 的生成树有( )棵。 (1) 0 (2) 1 (3) 2 (4) 不能确定 59、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 60、一棵无向树的顶点数n与边数m关系是( )。 61、一个图的欧拉回路是一条通过图中( )的回路。 62、有n个结点的树，其结点度数之和是( )。 63、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 64、n个结点的有向完全图边数是( )，每个结点的度数是( )。 65、一个无向图有生成树的充分必要条件是( )。 66、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 67、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 68、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 69、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 70、设T是一棵树，则T是一个连通且( )图。 71、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 72、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 73、设图G=，V={a，b，c，d，e}，E={,,,,},则G是有向图还是无向图？ 74、任一有向图中，度数为奇数的结点有( )个。 75、具有6 个顶点，12条边的连通简单平面图中，每个面都是由( )条边围成？ (1) 2 (2) 4 (3) 3 (4) 5 76、在有n个顶点的连通图中，其边数（ ）。 (1) 最多有n-1条 (2) 至少有n-1 条 (3) 最多有n条 (4) 至少有n 条 77、一棵树有2个2度顶点，1 个3度顶点，3个4度顶点，则其1度顶点为（ ）。 (1) 5 (2) 7 (3) 8 (4) 9 78、若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。 (1) n (2) 2n (3) n-1 (4) 2 79、下列哪一种图不一定是树（ ）。 (1) 无简单回路的连通图 (2) 有n个顶点n-1条边的连通图 (3) 每对顶点间都有通路的图 (4) 连通但删去一条边便不连通的图 80、连通图G是一棵树当且仅当G中（ ）。 (1) 有些边是割边 (2) 每条边都是割边 (3) 所有边都不是割边 (4) 图中存在一条欧拉路径 （数理逻辑部分） 二、求下列各公式的主析取范式和主合取范式： 1、(P→Q) R 2、(P R) (Q R) P 3、( P→Q) (R P) 4、Q→(P R) 5、P→(P (Q→P)) 6、 (P→Q) (R P) 7、P (P→Q) 8、(R→Q) P 9、P→Q 10、 P Q 11、P Q 12、（P R） Q 13、（P Q） R 14、(P (Q R)) ( P ( Q R)) 15、P ( P (Q ( Q R))) 16、(P Q) (P R) 三、
证明
住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问
： 1、P→Q， Q R， R， S P=> S 2、A→(B→C)，C→( D E)， F→(D E),A=>B→F 3、P Q， P→R, Q→S => R S 4、(P→Q) (R→S)，(Q→W) (S→X)， (W X)，P→R => P 5、(U V)→(M N), U P, P→(Q S)， Q S =>M 6、 B D，(E→ F)→ D， E=> B 7、P→(Q→R)，R→(Q→S) => P→(Q→S) 8、P→ Q， P→R，R→ S =>S→ Q 9、P→(Q→R) => (P→Q)→(P→R) 10、P→( Q→ R)，Q→ P,S→R,P => S 11、A，A→B， A→C， B→(D→ C) => D 12、A→(C B)，B→ A，D→ C => A→ D 13、(P Q) (R Q) （P R） Q 14、P (Q P) P (P Q) 15、（P Q） （P R）， (Q R)，S P S 16、P Q，Q R，R S P 17、用真值表法证明Ｐ Ｑ (Ｐ Ｑ) (Ｑ Ｐ) 18、P→Q P→(P Q) 19、用先求主范式的方法证明(P→Q) (P→R) (P→（Q R） 20、(P→Q) (Q R) P 21、为庆祝九七香港回归祖国，四支足球队进行比赛，已知情况如下，问结论是否有效? 前提: (1) 若A队得第一，则B队或C队获亚军; (2) 若C队获亚军，则A队不能获冠军; (3) 若D队获亚军，则B队不能获亚军; (4) A 队获第一; 结论: (5) D队不是亚军。 22、用推理规则证明P Q, (Q R),P R不能同时为真。 (集合论部分) 四、设Ａ，Ｂ，Ｃ是三个集合，证明： 1、A (B－C)＝(A B)－(A C) 2、(A－B) (A－C)=A－(B C) 3、A B=A C， B= C，则C=B 4、A B=A (B-A) 5、A=B A B= 6、A B = A C，A B=A C，则C=B 7、A B=A C， B= C，则C=B 8、A－(B C)＝(A－B)－C 9、(A－B) (A－C)=A－(B C) 10、A-B=B，则A=B= 11、A=(A-B) (A-C) A B C= 12、(A-B) (A-C)= A B C 13、(A-B) (B-A)=A B= 14、(A-B)-C A-(B-C) 15、P(A) P(B) P(A B) （P(S)表示S的幂集） 16、P(A) P(B)=P(A B) （P(S)表示S的幂集） 17、（A-B） B=（A B）-B当且仅当B= 。 n，则c的阶整除m与n的最大公因子(m,n)。 五、证明或解答： （数理逻辑、集合论与二元关系部分） 1、设个体域是自然数，将下列各式翻译成自然语言： (1) x y（xy=1）; (2) x y(xy=1); (3) x y (xy=0); (4) x y（xy=0）; (5) x y (xy=x); (6) x y（xy=x）; (7) x y z (x-y=z) 2、设A(x,y,z): x+y=z, M（x,y,z）: xy=z, L(x,y): xy， 个体域为自然数。将下列命题符号化： （1）没有小于0的自然数; （2）xyz; （4）存在x，对任意y 使得xy=y; （5）对任意x，存在y使x+y=x。 3、列出下列二元关系的所有元素： （1）A={0,1,2},B={0,2,4},R={|x,y }; （2）A={1,2,3,4,5},B={1,2},R={|2 x+y 4且x 且y B}; （3）A={1,2,3},B={-3,-2,-1,0,1},R={||x|=|y|且x 且y B}; 4、对任意集合A,B，证明：若A A=B B，则B=B。 5、对任意集合A,B，证明：若A ，A B=A C，则B=C。 故B=C。 6、设A={a,b}, B={c}。求下列集合： (1) A {0,1} B； (2) B2 A； (3) (A B)2; (4) P(A) A。 7、设全集U={a,b,c,d,e}, A={a,d}, B={a,b,c}, C={b,d}。求下列各集合： （1）A B ； （2） ；（3）(A ) C; （4）P(A)-P(B); （5）(A-B) (B-C); （6）(A B) C; 8、设A,B,C是任意集合，证明或否定下列断言： （1）若A B，且B C，则A C； （2）若A B，且B C，则A C; （3）若A B，且B C，则A C； （4）若A B，且B C，则A C； 9、A上的任一良序关系一定是A上的全序关系。 10、若R和S都是非空集A上的等价关系，则R S是A上的等价关系。 11、设R A×A，则R自反 IA R。 12、设A是集合，R A×A，则R是对称的 R＝R－1。 13、设A，B，C和D均是集合，R A×B，S B×C，T C×D，则 (1) R (S T)=(R S) (R T)； (2) R (S T) (R S) (R T)； 14、设〈A,≤〉为偏序集， B A，若B有最大(小)元、上(下)确界，则它们是惟一的。 15、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质： 1 1 1 2 3 2 3 2 3 16、设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？ （1）B={{1,3,6},{2,8,10},{4,5,7}}; （2）C={{1,5,7},{2,4,8,9},{3,5,6,10}}; （3）D={{1,2,7},{3,5,10},{4,6,8},{9}} 17、R是A={1,2,3,4,5,6}上的等价关系， R=I {<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>} 求R诱导的划分。 18、A上的偏序关系 的Hasse图如下。 （1） 下列哪些关系式成立：a b,b a,c e,e f,d f,c f； （2） 分别求出下列集合关于 的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）： (a) A; (b) {b,d}; (c) {b,e}; (d) {b,d,e} a e f b d c （半群与群部分） 19、求循环群C12={e,a,a2,…,a11}中H={e,a4,a8}的所有右陪集。 20、求下列置换的运算： 21、试求出8阶循环群的所有生成元和所有子群。 22、I上的二元运算*定义为： a,b I，a*b=a+b-2。试问是循环群吗？ 23、设是群，a G。令H={x G|a·x=x·a}。试证：H 是G 的子群。 24、证明：偶数阶群中阶为2 的元素的个数一定是奇数。 25、证明：有限群中阶大于2的元素的个数一定是偶数。 26、试求中每个元素的阶。 27、设是群，a,b G，a e，且a4·b=b·a5。试证a·b b·a。 28、I上的二元运算*定义为： a,b I，a*b=a+b-2。试证：为群。 29、设为半群，a S。令Sa={ai | i I+ }。试证是的子半群。 30、单位元有惟一逆元。 31、设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e 0。 32、证明在元素不少于两个的群中不存在零元。 33、证明在一个群中单位元是惟一的。 34、设a是一个群〈G,*〉的生成元，则a-1也是它的生成元。 35、在一个偶数阶群中一定存在一个2阶元素。 36、代数系统是一个群，则G除单位元以外无其它等幂元。 37、设是一个群，则对于a,b∈G，必有唯一的x∈G，使得a x=b。 38、设半群中消去律成立，则是可交换半群当且仅当 a,b S，（a·b）2=a2·b2。 39、设群除单位元外每个元素的阶均为2，则是交换群。 40、设*是集合A上可结合的二元运算，且 a,b A,若a*b=b*a，则a=b。试证明： （1） a A,a*a=a，即a是等幂元； （2） a,b A,a*b*a=a; （3） a,b,c A,a*b*c=a*c。 41、设是群，作f:G G,a a-1。证明：f是G的自同构 G是交换群。 42、若群的子群满足|G|＝2|H|，则一定是群的正规子群。 43、设H和K都 是G的不变子群。证明：H K也是G 的不变子群。 44、设群G的中心为C（G）={a G| x G,a·x=x·a}。证明C（G）是G的不变子群。 45、设是没有非平凡子群的有限群。试证：G是平凡群或质数阶的循环群。 46、设H和K都是G 的有限子群，且|H|与|K|互质。试证：H K={e}。 47、素数阶循环群的每个非单位元都是生成元。 48、若是可交换独异点，T为S中所有等幂元的集合，则是的子独异点。 49、设是群，且a∈G的阶为n，k∈I，则|ak|＝ ，其中(k,n)为k和n的最大公因子。 50、设是有限群，|G|＝n，则 a∈G，|a| n。 51、设G＝(a)，若G为无限群，则G只有两个生成元a和a-1； 52、设G＝(a)，{e} H G，am是H中a 的最小正幂，则 （1） H＝(am)； （2） 若G为无限群，则H也是无限群； 53、设G＝(a)，|G|＝n，则对于n 的每一正因子d，有且仅有一个d阶子群。因此n阶循环群的子群的个数恰为 n的正因子数。 54、设h是从群到的群同态，G 和G2的单位元分别为e1和e2，则 （1） h(e1)=e2； （2） a G1，h(a-1)=h(a)-1； （3） 若H G1，则h(H) G2； （4） 若h为单一同态，则 a G1，|h(a)|=|a|。 55、有限群G的每个元素的阶均能整除G的阶。 56、证明：在同构意义下，只有两个四阶群，且都是循环群。 57、在一个群〈G,*〉中，若G中的元素a的阶是k，即 |a|=k，则a-1的阶也是k。 58、在一个群中，若A和B 都是G的子群。若A B=G，则A=G或B=G。 59、设e是奇数阶交换群的单位元，则G的所有元素之积为e。 60、设S=Q Q，Q为有理数集合，*为S上的二元运算：对任意(a,b),(c,d) S,有 (a,b)*(c,d)=(ac,ad+b), 求出S关于二元运算*的单位元，以及当a 0时，(a,b)关于*的逆元。 61、设是一个群，H、K是其子群。定义G上的关系R：对任意a,b∈G，aRb 存在 h∈H,k∈K, 使得b=h*a*k，则R是G上的等价关系。 62、设H是G的子群，则下列条件等价： （1） H是G的不变子群； （2） a∈G，a H a-1 H； （3） a∈G，a-1 H a H； （4） a∈G， h∈G，a h a-1 H。 63、在半群中，若对 a,b G，方程a*x=b 和y*a=b都有惟一解，则是一个群。 64、设是群， H和K都是G的子群，令HK={h*s | s∈K，h∈H}, KH={s*h |s∈K,h∈H},，是G的子群的充分必要条件是HK=KH。 65、设H和K都 是G的不变子群。证明：HK也是G 的不变子群。 66、设为群，a,b,c G。若a*b=c*b*a,a*c=c*a,b*c=c*b，且a,b的阶分别为m, （格与布尔代数） 67、当n分别是24，36，110时，是布尔代数吗？若是，则求出其原子集。 68、设L是有界格，且|L|>1。证明：0 1。 证明： 69、设是格，若a,b,c L，a≤b≤c，则 a b=b⊙c , (a⊙b) (b⊙c)=(a b)⊙(a c) 70、在布尔代数中，证明恒等式a ( b)=a b 71、设是格，a1,a2,…,an L。试证：a1 a2 … an= a1 a2 … an当且仅当a1=a2=…=an。 72、在布尔代数中，证明恒等式(a c) ( b) (b c)=(a c) ( b) 73、在布尔代数中，证明恒等式(a b) ( c) ( c)=(a b) c 74、设是格，a,b,c,d L。试证：若a b且c d，则 a c b d 75、当n分别是10,45时，画出的哈斯图。 76、在布尔代数中，证明恒等式 (a ) (b ) (c )=( b) ( c) ( a) 77、设是格，a,b L，且a≤b，记 I[a,b]={x L|a≤x≤b} 则是的子格。 78、设A＝{a,b,c}，求的子格（P(A)表示A的幂集）。 79、证明：在同构意义下，4阶格只有2个。 80、设是有界格， 是A上的全序关系。若|A|＞2，则 a A-{0,1}，a无补元。 81、格是模格 a,b,c L，有 a (b (a c))=(a b) (a c) 82、设是分配格， a,b,c L。若(a b)＝(a c)且(a b)＝(a c)，则b＝c。 83、证明：在有补分配格中，每个元素的补元一定惟一。 84、设是格，则L是分配格当且仅当 a,b,c L，有 (a b) c a (b c) 85、设是一布尔代数，则 是一个交换群，其中＋定义为 a+b=(a⊙b′) (a′⊙b)。 86、设是一布尔代数，则 R={ | a b=b}是S上的偏序关系。 87、设是一布尔代数，则关系 ={ | a⊙b=a}是S上的偏序关系。 （图论部分） 88、证明在有n个结点的树中，其结点度数之和是2n-2。 88、任一图中度数为奇数的结点是偶数个。 89、连通无向图G的任何边一定是G的某棵生成树的弦。这个断言对吗？若是对的请证明之，否则请举例说明。 90、设T=是一棵树，若|V|>1，则T中至少存在两片树叶。 91、画一个使它分别满足： (1) 有欧拉回路和哈密尔顿回路； (2) 有欧拉回路，但无条哈密尔顿回路； (3) 无欧拉回路，但有哈密尔顿回路； (4) 既无欧拉回路，又无哈密尔顿回路。 92、设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？ 93、设图G=，|V|=n，|E|=m。k度顶点有nk个，且每个顶点或是k度顶点或是k+1度顶点。证明：nk=(k+1)-2m。 94、设G=是一个连通且|V|=|E|+1的图，则G中有一个度为1的结点。 95、若n阶连通图中恰有n-1 条边，则图中至少有一个结点度数为1。 96、若G有n个结点，m条边，f个面，且每个面至少由k(k 3)条边围成，则 m k(ｎ－2)／(ｋ－2)。 97、设G=是连通的简单平面图，|V|=n 3，面数为k,则k 2n-4。 98、证明对于连通无向简单平面图，当边数e＜30时，必存在度数≤4的顶点。 99、在一个连通简单无向平面图G=〈V，E，F〉中若|V| 3，则 |E| 3|V|－6。 100、给定连通简单平面图G=，且|V|=6, |E|=12, 则对于任意f F, d(f)=3。 101、设G=是n个顶点的无向图(n>2)，若对任意u,v V，有d(u)+d(v) n，则G是连通图。 102、一次会议有20人参加，其中每个人都在其中有不下10个朋友。这20人围成一圆桌入席，有没有可能使任意相邻而坐的两个人都是朋友？为什么？ 103、证明在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。 104、设有如下有向图G=， （1）求G的邻接矩阵；（2）G中v1到v4的长度为4 的通路有多少条？（3）G中经过v1的长度为3 的回路有多少条？（4）G中长度不超过4 的通路有多少条？其中有多少条通路？ v1 v4 v2 v3 题104图 105、求下列无向图中每个顶点的度数；求下列有向图中每个顶点的出度、入度和度。 a d e c b f c b a 106、求下列无向图的子图、生成子图、由边集诱导的子图和由顶点集诱导的子图。 a d e c b f 题106图 107、求下列赋权图顶点间的距离。 d a e 4 3 5 7 1 c b 14 f 108、求下列赋权图中v1到其他顶点的距离。 v2 10 v4 3 v1 2 2 6 4 3 4 v6 v3 2 v5 109、求下图的可达矩阵。 d a b e c 110、求下列图的生成树。 111、在一个有n个顶点的G=中，u,v V。若存在一条从u到v的一条通路，则必有一条从u到v的长度不超过n-1的通路。 112、设简单平面图G中顶点数n=7，边数m=15。证明：G是连通的。 113、已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？ 114、有向图G是强连通的 G中有一回路，它至少通过每个顶点一次。 115、一个有向图是单向连通图 它有一条经过所有结点的路。
浙公网安备 33021202002483