(完整版)離散數(shù)學(xué)試題及答案,推薦文檔

第第#頁共17頁若e為割邊，則G有兩個連通分支Gi和G2。Gi的結(jié)點(diǎn)數(shù)、邊數(shù)和面數(shù)分別為m、mi和門。顯然ni+n2=n=n,mi+m2=m=m—1,門+「2=r+1=r+1。由歸納假設(shè)有ni—mi+門=2,n2—m2+「2=2,從而(ni+n2)—(mi+m2)+(ri+「2)=4,n—(m—1)+(r+1)=4,即n—m+r=2。若e不為割邊，則n=n,m=m-1,r=r-1,由歸納假設(shè)有n—m+r=2,從而n-(m-1)+r—1=2,即n—m+r=2。由數(shù)學(xué)歸納法知，結(jié)論成立。七、(10分)設(shè)函數(shù)g：A-B,f:B-C,則：(1)fg是A至ijC的函數(shù)；(2)對任意的x€A,有fg(x)=f(g(x))。證明(1)對任意的x€A,因?yàn)間：A-B是函數(shù)，則存在丫€8使<*,y>Gg。對于yGB,因f:B—C是函數(shù)，則存在z€C使<y,z>Gf。根據(jù)復(fù)合關(guān)系的定義，由<x,丫>€§和<丫，z>Gf得<x,z>Gg*f,即<x,z>€fgo所以Dfg=A。對任意的xGA,若存在y1、y2€C,使得<x,y[>、<x,y2>Cfg=g*f,則存在t1使得<x,t1>€gJL<t1,y1>€f,存在t2使得<x,t2>Cg且<t2,y2>€fo因?yàn)間：A—B是函數(shù)，則t1=t2。又因f:B-C是函數(shù)，則y1=y2o所以A中的每個元素對應(yīng)C中惟一的元素。綜上可知，fg是A到C的函數(shù)。(2)對任意的xGA,由g：A-B是函數(shù)，有<x,g(x)>Gg且g(x)GB,又由f:B-C是函數(shù)，得vg(x),f(g(x))>Gf,于是<x,f(g(x))>€g*f=fg。又因fg是A到C的函數(shù)，則可寫為fg(x)=f(g(x))。八、(15分)設(shè)<H,*>是<6,*>的子群，定義R={<a,b>|a、bGG且a「1*bGH},則R是G中的一個等價關(guān)系，且[a]R=aHo證明對于任意aGG,必有a」1CG使得a1*a=e€H,所以<a,a>€Ro若<a,b>GR,則a1*b€Ho因?yàn)镠是G的子群，ft(a1*b)1=b1*a€H。所以<b,a>€Ro若<a,b>GR,<b,c>GR,則a1*b€H,b1*c€H。因?yàn)镠是G的子群，所以(a-1*b)*(b-1*c)=a1*c€H,故<a,c>€Ro綜上可得，R是G中的一個等價關(guān)系。對于任意的b€[a]R,有<a,b>€R,a1*b€H,則存在h€H使得a1*b=h,b=a*h,于是b€aH,[a]RaH。對任意的bGaH,存在