以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  离散数学两题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=53309)

--  作者：wenze
--  发布时间：9/30/2007 4:21:00 PM

--  离散数学两题
1.证明竞赛图一定有初级通路过每个顶点恰好一次.
2.设N是群G的一个正规子群，且[G:N]=m，证明对任意a属于G都有a^m属于N.

--  作者：albani
--  发布时间：9/30/2007 7:32:00 PM

--  
2：   证明 |G/N|=[G:N]=m=>(Na)^m=N=Na^m<=>a^m属于N
--  作者：applestar
--  发布时间：9/30/2007 11:10:00 PM

--  
(1)采用归纳法证明
  当n=2时显然成立
  假设当n=k时也成立，下面证明n=k+1时也成立。
  设G是k+1阶竞赛图，则G-{vk+1}是k阶竞赛图，存在经过每个顶点恰一次的初级通路  L=v1v2...vk.下面将vk+1加入其中。若L中含有v1v2...vi-1,i=1,2,...k满足<vi,vk+1>且<vk+1,vi>[vi=v0时说明<vk+1,v1>,显然vk+1v1v2...vk即是。因此只说明i>1情况]那么v1v2...vivk+1vi+1...vk即为经过每个顶点恰一次的初级通路否则<vi,vk+1>i=1,2,...,k则v1v2...vk+1即为经过每个顶点恰一次的初级通路。故当n=k+1时
也成立。综合知命题为真。

--  作者：datoubaicai
--  发布时间：10/1/2007 8:01:00 AM

--  
若L中含有v1v2...vi-1,i=1,2,...k满足<vi,vk+1>且<vk+1,vi>[vi=v0时说明<vk+1,v1>,显
                                         ~~~~~~~~~~~~~~~
然vk+1v1v2...vk即是。因此只说明i>1情况]那么v1v2...vivk+1vi+1...vk即为经过每个顶点恰一次的初级通路.

这一段下标i和i-1弄错了吧

你可能是这个意思：
由于G是竞赛图，因此vk+1，v1之间必存在一条有向边，<v1,vk+1>或<vk+1,v1>，下面分这两种情况讨论:
1)若<vk+1,v1>，vk+1v1v2...vk即是所求路径
2)否则若<v1,vk+1>，考虑v2与vk+1之间的边：
   若<vk+1,v2>,v1vk+1v2.....vk即是所求路径
   否则<v2,vk+1>,考虑v3与vk+1之间的边
   .....
   如此进行下去，最坏的情况是<v1,vk+1>，<v2,vk+1>,......<vk-1,vk+1>,考虑vk与vk+1之间的边：
  若<vk,vk+1>则v1v2.....vkvk+1即是所求路径
  否则若<vk+1,vk>,则v1v2.....vk-1vkvk+1即是所求路径
因此不论怎样 ，竞赛图中都存在经过每个顶点一次的路径。

W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 200.195ms